Matematika Logične Algebre

Kazalo:

Matematika Logične Algebre
Matematika Logične Algebre

Video: Matematika Logične Algebre

Video: Matematika Logične Algebre
Video: Алгебра и математика. Объясняется с простой для понимания 3D-анимацией. 2024, Marec
Anonim

To je datoteka v arhivu filozofske enciklopedije Stanford.

Matematika logične algebre

Prvič objavljeno 5. julija 2002; vsebinska revizija, 27. februarja 2009

Boolova algebra je algebra dvovrednotene logike, ki ima samo sentencialne vezi, ali enakovredno algebre množic v združevanju in dopolnjevanju. Strog koncept je določena algebra, analogna matematičnemu pojmu skupine. Ta koncept ima korenine in aplikacije v logiki (algebre Lindenbaum-Tarski in teorija modelov), teoriji množic (polja množic), topologiji (popolnoma ločeni kompaktni Hausdorffovi prostori), temeljih teorije množic (modeli z logičnimi vrednostmi Boolea), teoriji meritev (ukrep algebre), funkcionalna analiza (algebre projekcij) in teorija obročev (Booleovi obroči). Študij boole algebra ima več vidikov: teorijo struktur, teorijo modelov logične algebre, vprašanja glede odločnosti in neodločljivosti za razred boolovih algeb in navedene aplikacije. Poleg tega je dr.čeprav tukaj ni razloženo, obstajajo povezave z drugimi logikami, subumpsija kot del posebnih vrst algebarske logike, končne boolove algebre in teorija stikalnih vezij in boolove matrike.

  • 1. Opredelitev in preproste lastnosti
  • 2. Osnovna algebrska teorija
  • 3. Posebni razredi boole algebre
  • 4. Teorija strukture in kardinalne funkcije na boolovih algebrih
  • 5. Vprašanja glede odločnosti in neodločljivosti
  • 6. Lindenbaum-Tarski algebre
  • 7. Modeli logične vrednosti
  • Bibliografija
  • Drugi internetni viri
  • Povezani vnosi

1. Opredelitev in preproste lastnosti

Boolova algebra (BA) je množica A, skupaj z binarnimi operacijami + in · in enotno operacijo - ter elementi 0, 1 A, tako da veljajo naslednji zakoni: komutacijski in asociativni zakoni za seštevanje in množenje, distributivni zakoni tako za množenje nad seštevanjem in seštevanje preko množenja ter naslednji posebni zakoni:

x + (x · y) = x

x · (x + y) = x

x + (−x) = 1

x · (−x) = 0

Ti zakoni so bolje razumljeni v smislu osnovnega primera BA, ki ga sestavljajo zbirka A podmnožice množice X, zaprte v operacijah združevanja, presečišča, dopolnjevanja glede na X, s člani ∅ in X. Iz teh aksiomov zlahka izpeljemo marsikateri osnovni zakon, pri čemer imamo v mislih ta primer za motivacijo. Vsak BA ima naravni delni vrstni red ≤, ki ga definira tako, da reče x x y, če in samo, če je x + y = y. To v našem glavnem primeru ustreza ⊆. Posebnega pomena je dvoelementni BA, ki je nastal tako, da ima množica X samo en element. Dvoelektrski BA prikazuje neposredno povezavo z osnovno logiko. Dva člana, 0 in 1, ustrezata neresničnosti in resnici. Boolove operacije nato izrazijo navadne tabele resnice za ločitev (s +), veznico (z ·) in negacijo (z -). Pomemben osnovni rezultat je, da enačba velja v vseh BA-jih, če in samo, če ima v dvo-elementnem BA. Nato določimo x ⊕ y = (x · - y) + (y · - x). Potem A skupaj z ⊕ in · skupaj z 0 in 1 tvori obroč z identiteto, v katerem je vsak element idempotenten. Nasprotno pa glede na tak obroč z seštevanjem ⊕ in množenjem določimo x + y = x ⊕ y ⊕ (x · y) in - x = 1 ⊕ x. Zaradi tega prstan postane BA. Ta dva procesa sta medsebojno obratna in kažeta, da sta teorija boole algebre in obročev z identiteto, v katerih je vsak element idempotenten, definitivno enakovredna. To postavlja teorijo BA v standardni predmet raziskovanja v algebri. Atom v BA je element, ki ni nič, tako da ni elementa b z 0 <b <a. BA je atomski, če je vsak ne-nič element BA nad atomom. Končni BA so atomski, vendar je toliko neskončnih BA. V delnem zaporedju ≤ zgoraj je x + y najmanjša zgornja meja x in y, x · y pa je največja spodnja meja x in y. To lahko posplošimo: Σ X je najmanjša zgornja meja množice X elementov in Π X je največja spodnja meja množice X elementov. Te ne obstajajo za vse množice v vseh logičnih algebrih; če vedno obstajajo, naj bi bila Boolova algebra popolna.boolova algebra naj bi bila končana.boolova algebra naj bi bila končana.

2. Osnovna algebrska teorija

Več algebrskih konstrukcij ima očitne definicije in preproste lastnosti za BA: subalgebre, homomorphizmi, izomorfizmi in neposredni produkti (tudi neskončno veliko algebre). Nekatere druge standardne algebarske konstrukcije so bolj značilne za BA. Ideal v BA je podvrsta, ki sem jo zaprl pod +, z 0 kot član, in tako, da če je a ≤ b ∈ I, potem tudi a ∈ I. Čeprav ni takoj očitno, je to enako kot teoretični koncept. Obstaja dvojni pojem filtra (na splošno ni obroba v obročih). Filter je podmnožica F, zaprta pod ·, ki ima 1 član, in če je a ≥ b ∈ F, potem tudi a ∈ F. Ultrafilter na A je filter F z naslednjimi lastnostmi: 0 ∉ F in za katerikoli a ∈ A bodisi a ∈ F ali - a ∈ F. Za katerikoli a ∈ A naj bo S (a) = {F: F ultrafilter na A in a ∈ F}. Potem je S izomorfizem na BA podskupine množice X vseh ultrafilterjev na A. S tem se vzpostavi osnovni izrek o Stone predstavitvi in pojasni izvor BA kot konkretnih algeb množic. Poleg tega je množice S (a) mogoče razglasiti za bazo za topologijo na X, kar X pretvori v popolnoma odklopljen kompaktni Hausdorffov prostor. S tem se vzpostavi medsebojna korespondenca med razredom BA in razredom takšnih prostorov. Posledično zelo pogosto uporabljeni v teoriji BA, veliko topoloških izrek in konceptov ima posledice za BA. Če je x element BA, pustimo 0 x = - x in 1 x = x. Če je (x (0),… x (m - 1)) končno zaporedje elementov BA A, potem vsak element podalgebre A ustvari z {x (0),…,x (m - 1)} lahko zapišemo kot vsoto monomerov e (0) x (0) ·… · e (m - 1) x (m - 1) za e v nekaterih skupinah funkcij, ki preslikajo m = {0,…, M - 1} v 2 = {0, 1}. To je algebrski izraz disjunktivnega teorema normalne oblike sentencialne logike. Funkcijo f iz množice X generatorjev BA A v BA B lahko razširimo na homomorfizem, če in samo, če je e (0) x (0) ·… · e (m - 1) x (m - 1) = 0 vedno pomeni, da je e (0) f (x (0)) ·… · e (m - 1) f (x (m - 1)) = 0. To je Sikorski razširitveno merilo. Vsak BA A je lahko vgrajen v celoten BA B tako, da je vsak element B najmanj zgornja meja niza elementov A. B je edinstven do A -izomorfizma in se imenuje dokončanje A. Če je f homomorfizem iz BA A v popolno BA B in če je A subalgebra C,potem se lahko f razširi na homomorfizem C v B. To je Sikorski podaljšek izrek. Drug splošni algebrski pojem, ki velja za boolove algebre, je pojem proste algebre. To je mogoče konkretno sestaviti za BA. Namreč, prosti BA na κ je BA zaprtih odprtih podmnožic dvo elementnega diskretnega prostora, dvignjenega na κ moč.

3. Posebni razredi boole algebre

Obstaja veliko posebnih razredov boolove algebre, ki so pomembni tako za notranjo teorijo BA kot tudi za uporabo:

  • Atomski BA, že omenjeni.
  • Atomi brez BA, ki so opredeljeni kot BA brez atomov. Na primer, vsak neskončno prosti BA je brez atoma.
  • Popolni BA, opredeljeni zgoraj. Te so še posebej pomembne v temeljih teorije množic.
  • Intervalne algebre. Izhajajo iz linearno urejenih nizov (L, <) s prvim elementom, kot sledi. Eden odvzame najmanjšo algebro podskupine L, ki vsebuje vse na pol odprte intervale [a, b) z a v L in b v L ali enak ∞. Te BA so uporabne pri študiji algeb Lindenbaum-Tarski. Vsak števni BA je izomorfen glede na intervalno algebro, zato lahko štetje BA opišemo tako, da označimo urejen niz, ki je izomorfen glede na ustrezno interalno algebro.
  • Drevesne algebre. Drevo je delno urejen niz (T, <), v katerem je niz predhodnikov katerega koli elementa dobro urejen. Glede na takšno drevo je treba upoštevati algebro podskupin T, ki jih pri nekaterih a v T ustvarijo vsi nizi oblike {b: a ≤ b}.
  • Superatomske BA. To so BA, ki niso samo atomske, ampak so takšne, da je vsaka podalgebra in homomorfna slika atomska.

4. Teorija strukture in kardinalne funkcije na boolovih algebrih

Večino globlje teorije boolovih algeb, ki pripoveduje o njihovi strukturi in klasifikaciji, je mogoče oblikovati v smislu določenih funkcij, opredeljenih za vse boolove algebre, z neskončnimi kardinali kot vrednostmi. Opredelimo nekatere pomembnejše od teh kardinalnih funkcij in navedemo nekaj znanih strukturnih dejstev, ki so večinoma oblikovana v smislu njih

  1. Celičnost c (A) BA je vrhunec kardinalnosti sklopov dvojno ločenih elementov A.
  2. Podmnožica X BA A je neodvisna, če je X skupek prostih generatorjev subalgebre, ki jih ustvarja. Neodvisnost A je vrhunec kardinalnosti neodvisnih podskupin A.
  3. Podvrsta X BA A je gosta v A, če je vsak necero element A A ≥ ne-nič element X. Π teža A je najmanjša kardinalnost gosto podskupino A.
  4. Dva elementa x, y A sta neprimerljiva, če niti eden ni ≤ drugi. Vrhunec kardinalnosti podskupine X v A, ki je sestavljen iz dvojno neprimerljivih elementov, je neprimerljiv z A.
  5. Podmnožica X A je nepomembna, če v subalgebri, ki jo ustvarijo drugi, ni nobenega elementa X.

Pomembno dejstvo v zvezi s celičnostjo je izrek Erdos-Tarski: če je celičnost BA edini kardinal, potem dejansko obstaja niz ločenih elementov te velikosti; za celično mobilnost redna meja (nedostopna) obstajajo kontraje primeri. Vsak neskončni popolni BA ima neodvisno podskupino iste velikosti kot algebra. Vsak neskončni BA A ima neprimerljivo neprimerljivo podskupino, katere velikost je π-teža A. Vsaka intervalna algebra ima številčno neodvisnost. Superatomska algebra niti nima neskončno neodvisne podskupine. Vsako drevesno algebro je mogoče vgraditi v intervalno algebro. BA s samo avtomatizmom identitete se imenuje tog. Obstajajo togi celotni BA, tudi toge intervalne algebre in toge drevesne algebre.

5. Vprašanja glede odločnosti in neodločljivosti

Osnovni rezultat Tarškega je, da je osnovna teorija logične algebre odločljiva. Celo teorija boolovih algeb z izrazitim idealom je odločljiva. Po drugi strani pa teorija boolove algebre z izrazito subalgebro ni mogoče določiti. Tako rezultati razgradljivosti kot tudi rezultati neodločljivosti se na različne načine razširijo na logične algebre v razširitvah logike prvega reda.

6. Lindenbaum-Tarski algebre

Zelo pomembna konstrukcija, ki prenaša številne logike in številne druge algebre razen Boolejevih algeb, je konstrukcija boolove algebre, povezane s stavki po neki logiki. Najenostavnejši primer je sentencialna logika. Tu so stavčni simboli in običajne vezi, ki iz njih sestavljajo daljše stavke: ločitev, zveza in negacija. Glede na nabor A stavkov v tem jeziku sta dva stavka s in t enakovredna modula A, če in samo, če je dvokondiciona med njima logična posledica A. Ekvivalentni razredi se lahko pretvorijo v BA tako, da + ustreza disjunkciji, · konjunkciji in - negaciji. Vsaka BA je izomorfna za eno od te oblike. Za teorijo prvega reda lahko naredimo nekaj podobnega. Naj bo T teorija prvega reda v jeziku prvega reda L. Formuli rečemo φ in ψ ekvivalent pod pogojem, da je T ⊢ φ ↔ ψ. Ekvivalenčni stavek stavka φ je označen s [φ]. Naj bo A zbirka vseh razredov enakovrednosti v tem razmerju enakovrednosti. A lahko v BA naredimo z naslednjimi opredelitvami, ki so enostavno upravičene:

[φ] + [ψ] = [φ ∨ ψ]
[φ] · [ψ] = [φ ∧ ψ]
- [φ] = [¬φ]
0 = [F]
1 = [T]

Vsak BA je izomorfen algebri Lindenbaum-Tarski. Vendar pa je ena najpomembnejših uporab teh klasičnih Lindenbaum-Tarski algebre ta, da jih opiše za pomembne teorije (ponavadi odločljive teorije). Pri štetjih jezikov je to mogoče storiti z opisom njihovih izomorfnih intervalnih algeb. To na splošno daje temeljito znanje teorije. Nekaj primerov je:

Teorija Izomorfna intervalna algebra na
(1) v bistvu neodločljiva teorija V, razumniki
(2) BA
Naravni
Naravni

×

Naravni
Naravni

kvadrat pozitivnih celih števil, urejen leksikografsko

(3) linearna naročila

× Q odredil antilexicographically, kjer je na oblast v običajnem vrstnem redu

Naravni
Naravni
Naravni
Naravni
(4) abelovske skupine (Q + A) × Q

7. Modeli logične vrednosti

V teoriji modelov je mogoče vzeti vrednosti v katerem koli celotnem BA, ne pa v dvoelementnem BA. Ta teorija modelov Booleova modela je bila razvita okoli 1950–1970, vendar se odtlej ni veliko delalo. Toda poseben primer, logični modeli za teorijo množic, ki so vredni Boola, je zelo v ospredju trenutnih raziskav v teoriji množic. Pravzaprav je enakovreden pogled na silovito konstrukcijo Cohena in ima nekatere tehnične prednosti in slabosti. Filozofsko se zdi bolj zadovoljiv kot koncept prisile. Tu opisujemo ta primer teorije množic; Nato bo postalo razvidno, zakaj se štejejo samo konkurenčni BA. Naj bo B popoln BA. Najprej določimo boolovo cenjeno vesolje V (B). Navadni teoretično množico lahko identificiramo z V (2), kjer je 2 BA z 2 elementi. Opredelitev je po transfinitivni rekurziji, kjer je α,β so zaporedne vrstice in λ je mejna zaporedja:

V (B, 0) =
V (B, α + 1) = nabor vseh funkcij f, tako da je domena f podvrsta V (B, α) in območje f podvrsta B
V (B, λ) = zveza vseh V (B, β) za β <λ.

Vesolje z vrednostmi B je pravi razred V (B), ki je združitev vseh teh V. Nato definiramo s precej zapleteno transfinitivno rekurzijo nad dobro utemeljeno množico vrednosti teoretične formule z elementi boolovega vesolja, dodeljene njegovim prostim spremenljivkam

|| x ∈ y || = Σ {(|| x = t || · y (t)): t ∈ domena (y)}
|| x ⊆ y || = Π {- x (t) + || t ∈ y ||: t ∈ domena (x)}
|| x = y || = || x ⊆ y || · || y ⊆ x ||
|| ¬φ || = - || φ ||
|| φ ∨ ψ || = || φ || + || ψ ||
|| ∃ x φ (x) || = Σ {|| φ (a) ||: a ∈ V (B)}

Bibliografija

  • Halmos, P., 1963, Predavanja o logični algebri, Princeton: Van Nostrand
  • Heindorf, L. in Shapiro, L., 1994, Skoraj projektivne boolove algebre, Opombe predavanj iz matematike št. 1596, Berlin: Springer-Verlag
  • Jech, T., 1997, Set Theory, 2. popravljena izdaja, Berlin, New York: Springer-Verlag
  • Monk, JD, in Bonnet, R., (eds), 1989, Priročnik boole algebre, 3 zvezki, Amsterdam: Severna Holandija.

Drugi internetni viri

[S predlogi se obrnite na avtorja.]

Priporočena: