Teoria mulțimilor Von Neumann-Bernays-Gödel

În studiul bazelor matematicii , teoria mulțimilor Von Neumann-Bernays-Gödel ( NBG ) este o teorie axiomatică a mulțimilor care constituie o extensie conservatoare a teoriei axiomatice canonice Zermelo-Fraenkel axiomatică cu axioma alegerii (ZFC). O formulă în limba ZFC este demonstrabilă în NBG dacă și numai dacă este demonstrabilă în ZFC. Ontologia NBG include propriile clase , obiecte care pot avea elemente, dar care nu pot fi ele însele. Principiul de înțelegere al NBG este predicativ ; variabilele cuantificate în formulă pot varia numai în seturi. Permiterea înțelegerii impredative transformă NBG în teoria seturilor Morse-Kelley (MK). NBG, spre deosebire de ZFC și MK, poate fi finit axiomatizat.

Ontologie

Caracteristica distinctivă a NBG este distincția dintre clasă și întreg . Fie a și s fie doi indivizi. Apoi formula atomică $a\in s$ ${\ displaystyle a \ in s}$ $a \ in s$ este definit dacă a este un set și s este o clasă . Cu alte cuvinte, $a\in s$ ${\ displaystyle a \ in s}$ $a \ in s$ este definit cu excepția cazului în care a este o clasă proprie. O clasă proprie este foarte mare; NBG admite, de asemenea, „clasa tuturor seturilor”, clasa universală numită V. O astfel de precizie în stabilirea faptului că în stânga simbolului $\in$ ${\ displaystyle \ in}$ $\în$ există un set și o clasă la dreapta înseamnă că nu este permis să se definească, de exemplu, „setul tuturor seturilor” sau „clasa tuturor claselor”.

Conform schemei axiomice NBG de Înțelegere a claselor, toate obiectele care îndeplinesc o formulă dată în teoria primului ordin NBG formează o clasă; dacă clasa nu ar fi un set în ZFC , atunci ar fi o clasă adecvată NBG.

Dezvoltarea claselor reflectă dezvoltarea teoriei naive a mulțimilor . Se dă principiul abstractizării și, prin urmare, clasele pot fi formate din toți indivizii care satisfac orice formulă a teoriei de ordinul întâi ale cărei formule atomice implică fie relația de apartenență, fie predicatele care pot fi definite pornind de la relația de apartenență. Egalitatea, asocierea, subclasa și așa mai departe, sunt toate definibile și, prin urmare, nu trebuie să fie axiomatizate - definiția lor denotă o abstracție particulară a unei formule .

Seturile sunt dezvoltate într-un mod foarte similar cu ZF. Fie Rp ( A, a ) să denote „setul a reprezintă clasa A ”, atunci Rp denotă o relație binară definită după cum urmează:

\mathrm {Rp} (A,a):=\forall x(x\in A\leftrightarrow x\in a).

{\ displaystyle \ mathrm {Rp} (A, a): = \ forall x (x \ in A \ leftrightarrow x \ in a).}

{\ mathrm {Rp}} (A, a): = \ forall x (x \ in A \ leftrightarrow x \ in a).

Adică, un "reprezintă" A dacă fiecare element al unui este un element al A, și vice - versa. Clasele care nu au reprezentare, precum clasa tuturor seturilor care nu se conțin (clasa invocată în paradoxul lui Russell ), sunt clase proprii .

Istorie

Prima variantă a NBG, de John von Neumann în anii 1920, a luat funcții , nu seturi, ca primitive. Într-o serie de articole publicate în 1937-54, Paul Bernays a modificat teoria lui Von Neumann în așa fel încât să facă mulțimi și să aparțină unui set primitiv. Gödel (1940), în timp ce lucra la independența ipotezei continuumului , a simplificat teoria și a descoperit că ar putea fi finit axiomatizată. Montague (1961) a arătat că ZFC nu poate fi axiomatizat finit.

Axiomatizare NBG

NBG este prezentat aici ca o teorie bazată pe două tipuri de obiecte: litere mici indică variabilele care se întind pe seturi, iar majusculele indică variabile care se întind pe clase. Prin urmare $x\in y$ ${\ displaystyle x \ in y}$ $x \ in y$ citit ca „setul x aparține setului y ”, e $x\in Y$ ${\ displaystyle x \ în Y}$ $x \ în Y$ ca „setul x aparține clasei Y ”. Formulele de egalitate pot avea forma $x=y$ ${\ displaystyle x = y}$ $x = y$ sau $X=Y$ ${\ displaystyle X = Y}$ $X = Y$ . a = A înseamnă $\forall x(x\in a\leftrightarrow x\in A)$ ${\ displaystyle \ forall x (x \ într-o \ leftrightarrow x \ în A)}$ $\ forall x (x \ in a \ leftrightarrow x \ in A)$ și este un abuz de notație . NBG poate fi, de asemenea, prezentat ca o teorie a claselor bazate pe un singur tip de obiect, clase, prin definirea seturilor ca acele clase care sunt membre ale cel puțin unei alte clase.

Mai întâi axiomatizăm NBG folosind schema axiomelor de înțelegere a clasei. Se poate arăta că această schemă este echivalentă ^[1] cu 9 din instanțele sale finite, definite în secțiunea următoare. Deci, aceste 9 axiome finite pot înlocui Înțelegerea claselor. Acesta este sensul precis în care NBG poate fi axiomatizat finit.

Cu schema de Înțelegere a clasei

Următoarele 5 axiome sunt identice cu omologii lor ZFC :

extensionalitate : $\forall x(x\in a\leftrightarrow x\in b)\rightarrow a=b.$ ${\ displaystyle \ forall x (x \ in a \ leftrightarrow x \ in b) \ rightarrow a = b.}$ $\ forall x (x \ in a \ leftrightarrow x \ in b) \ rightarrow a = b.$ : Seturile cu aceleași elemente sunt același set.
cuplare : $\forall x\forall y\exists z\forall w[w\in z\leftrightarrow (w=x\lor w=y)].$ ${\ displaystyle \ forall x \ forall y \ există z \ forall w [w \ in z \ leftrightarrow (w = x \ lor w = y)].}$ ${\ displaystyle \ forall x \ forall y \ există z \ forall w [w \ in z \ leftrightarrow (w = x \ lor w = y)]}$ Pentru toate seturile x și y , există un set, $\{x,y\}$ ${\ displaystyle \ {x, y \}}$ $\ {X y \}$ , ale căror elemente sunt exact x și y .

cuplarea implică faptul că pentru orice set x , setul { x } ( setul singlet ) există. Mai mult, având în vedere orice două seturi x și y și definiția obișnuită a perechilor ordonate , perechea ordonată ( x, y ) există și este o mulțime. În Înțelegerea claselor, toate relațiile pe seturi sunt clase. În plus, anumite tipuri de relații între clase sunt una sau mai multe funcții, injecții și bijecții de la o clasă la alta. cuplarea este o axiomă în teoria mulțimilor lui Zermelo și o teoremă în ZFC.

uniune : pentru fiecare set x , există un set care conține exact elementele elementelor lui x .
set de putere : pentru orice set x , există un set care conține exact subseturile lui x .
infinit : Există o mulțime inductivă , numită mulțimea x ale cărei elemente sunt (i) mulțimea goală ; (ii) pentru fiecare membru y al lui x , $y\cup \{y\}$ ${\ displaystyle y \ cup \ {y \}}$ $y \ cup \ {y \}$ este, de asemenea, un element al lui x .

infinitul poate fi formulat pentru a implica existența setului gol. ^[2]

Axiomele rămase sunt valorificate cu majuscule pentru că se ocupă mai ales de clase decât de seturi. Următoarele două axiome diferă de omologii lor ZFC numai pentru că variabilele cuantificate se întind pe clase, nu pe seturi:

Extensionalitate: $\forall x(x\in A\Leftrightarrow x\in B)\Rightarrow A=B.$ ${\ displaystyle \ forall x (x \ in A \ Leftrightarrow x \ in B) \ Rightarrow A = B.}$ $\ forall x (x \ in A \ Leftrightarrow x \ in B) \ Rightarrow A = B.$ : Clasele cu aceleași elemente sunt aceeași clasă.
Fundație (Regularitate): Fiecare clasă non-goală este disjunctă de unul dintre elementele sale.

Ultimele două axiome sunt specifice NBG:

Limita mărimii : pentru fiecare clasă C , există un set x astfel încât x = C dacă și numai dacă nu există o bijecție între C și clasa V a tuturor seturilor.

Din această axiomă, datorită lui John von Neumann , pot fi derivate toate subseturile , substituția și alegerea globală . Această axiomă implică axioma alegerii globale, deoarece clasa ordinalelor nu este un set; de aceea există o bijecție între ordinali și univers . Dacă axioma limitei de mărime a fost slăbită la „Dacă domeniul unei funcții între clase este un set, atunci domeniul acelei funcții este, de asemenea, un set”, atunci nici o formă a axiomei de alegere nu este o teoremă NBG. În acest caz, orice formă locală obișnuită a axiomei alese poate fi luată ca o axiomă suplimentară, dacă se dorește.

Limita de alegere nu poate fi găsită în Mendelson (1997) NGB. În locul său găsim axioma obișnuită de alegere pentru mulțimi și următoarea formă a schemei axiomelor de substituție : dacă clasa F este o funcție al cărei domeniu este un set, atunci codomainul lui F este, de asemenea, un set. ^[3]

Schema de înțelegere a clasei: pentru fiecare formulă $\phi$ ${\ displaystyle \ phi}$ $\ phi$ neavând cuantificatori între clase (poate conține clase și parametri setați), există o clasă A astfel încât $\forall x(x\in A\Leftrightarrow \phi (x)).$ ${\ displaystyle \ forall x (x \ în A \ Leftrightarrow \ phi (x)).}$ $\ forall x (x \ in A \ Leftrightarrow \ phi (x)).$

Această axiomă afirmă că invocarea principiului înțelegerii nerestricționate a teoriei naive a mulțimilor returnează mai degrabă o clasă decât o mulțime, alungând astfel paradoxurile teoriei mulțimilor .

Înțelegerea claselor este singura schemă axiomatică a NBG. În secțiunea următoare, vom arăta cum acest tipar poate fi înlocuit cu o serie de instanțe proprii. Prin urmare, NBG poate fi axiomatizat finit. Dacă variabilele cuantificate în φ ( x ) variază pe clase în loc de mulțimi, rezultatul este teoria mulțimilor Morse-Kelley , o extensie adecvată a ZFC care nu poate fi axiomatizată finit.

Înlocuirea Înțelegerii claselor cu instanțe finite ale acestora

O caracteristică interesantă, dar oarecum misterioasă, a NBG este că schema sa axiomatică de Înțelegere a clasei este echivalentă cu conjuncția unui număr finit de instanțe. Axiomele din această secțiune pot înlocui axiomele Înțelegerii clasei din secțiunea anterioară. Axiomatizarea finită prezentată mai jos nu seamănă neapărat cu fiecare axiomatizare NBG tipărită.

Ne dezvoltăm axiomatizarea luând în considerare structura formulelor.

Seturi: Pentru orice set x , există o clasă X astfel încât x = X.

Această axiomă, combinată cu axioma de existență a secțiunii anterioare, asigură existența claselor încă de la început și permite formule cu parametri de clasă.

Lasa-i sa fie $A=\{x\mid \phi \}$ ${\ displaystyle A = \ {x \ mid \ phi \}}$ $A = \ {x \ mid \ phi \}$ Și $B=\{x\mid \psi \}.$ ${\ displaystyle B = \ {x \ mid \ psi \}.}$ $B = \ {x \ mid \ psi \}.$ Atunci $\{x\mid \neg \phi \}=V-A$ ${\ displaystyle \ {x \ mid \ neg \ phi \} = VA}$ $\ {x \ mid \ neg \ phi \} = V-A$ Și $\{x\mid \phi \wedge \psi \}=A\cap B$ ${\ displaystyle \ {x \ mid \ phi \ wedge \ psi \} = A \ cap B}$ $\ {x \ mid \ phi \ wedge \ psi \} = A \ cap B$ sunt suficiente pentru a genera toate conectivitățile logice , deoarece ∧ și ¬ sunt un set funcțional complet de conectivități.

Complement: Pentru fiecare clasă A , complementul $V-A=\{x\mid x\not \in A\}$ ${\ displaystyle VA = \ {x \ mid x \ not \ în A \}}$ $V-A = \ {x \ mid x \ not \ în A \}$ este o clasă.
Intersecție: pentru fiecare clasă A și B , intersecția $A\cap B=\{x\mid x\in A\wedge x\in B\}$ ${\ displaystyle A \ cap B = \ {x \ mid x \ in A \ wedge x \ in B \}}$ $A \ cap B = \ {x \ mid x \ in A \ wedge x \ in B \}$ este o clasă.

Trecem acum la cuantificare. Pentru a gestiona mai multe variabile, trebuie să putem reprezenta relațiile . Definim perechea ordonată $(a,b)$ ${\ displaystyle (a, b)}$ $(a, b)$ ca $\{\{a\},\{a,b\}\},$ ${\ displaystyle \ {\ {a \}, \ {a, b \} \},}$ $\ {\ {a \}, \ {a, b \} \},$ ca de obicei. Rețineți că două aplicații de împerechere a a și b asigură că ( a , b ) este, fără îndoială, un set.

Produse: Pentru fiecare clasă A și B , clasa $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$ ${\ displaystyle A \ times B = \ {(a, b) \ mid a \ in A \ wedge b \ in B \}}$ $A \ times B = \ {(a, b) \ mid a \ in A \ wedge b \ in B \}$ este o clasă. (Practic, numai $V\times A$ ${\ displaystyle V \ times A}$ $V \ ori A$ servește.)
Inversie: Pentru fiecare clasă R , clasele:

{\mathit {Conv}}1(R)=\{(b,a)\mid (a,b)\in R\}

{\ displaystyle {\ mathit {Conv}} 1 (R) = \ {(b, a) \ mid (a, b) \ în R \}}

{\ mathit {Conv}} 1 (R) = \ {(b, a) \ mid (a, b) \ în R \}

Și

{\mathit {Conv}}2(R)=\{(b,(a,c))\mid (a,(b,c))\in R\}

{\ displaystyle {\ mathit {Conv}} 2 (R) = \ {(b, (a, c)) \ mid (a, (b, c)) \ în R \}}

{\ mathit {Conv}} 2 (R) = \ {(b, (a, c)) \ mid (a, (b, c)) \ în R \}

exista.

Asociere: Pentru fiecare clasă R , clasele:

{\mathit {Assoc}}1(R)=\{((a,b),c)\mid (a,(b,c))\in R\}

{\ displaystyle {\ mathit {Assoc}} 1 (R) = \ {((a, b), c) \ mid (a, (b, c)) \ în R \}}

{\ mathit {Assoc}} 1 (R) = \ {(((a, b), c) \ mid (a, (b, c)) \ în R \}

Și

{\mathit {Assoc}}2(R)=\{(d,(a,(b,c)))\mid (d,((a,b),c))\in R\}

{\ displaystyle {\ mathit {Assoc}} 2 (R) = \ {(d, (a, (b, c))) \ mid (d, ((a, b), c)) \ în R \} }

{\ mathit {Assoc}} 2 (R) = \ {(d, (a, (b, c))) \ mid (d, ((a, b), c)) \ in R \}

exista.

Aceste axiome permit adăugarea de argumente fictive și manipularea ordinii argumentelor în relațiile fiecărei arități . Forma particulară a Asociației este concepută pentru a face posibilă preluarea oricărui termen dintr-o listă de subiecte din prima poziție (cu ajutorul Inversiunii). Reprezentăm lista argumentelor $(x_{1},x_{2},\ldots ,x_{n})$ ${\ displaystyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ $(x_ {1}, x_ {2}, \ ldots, x_ {n})$ ca $(x_{1},(x_{2},\ldots ,x_{n}))$ ${\ displaystyle (x_ {1}, (x_ {2}, \ ldots, x_ {n}))}$ $(x_ {1}, (x_ {2}, \ ldots, x_ {n}))$ (este o pereche cu primul argument ca prima proiecție și „coada” ca a doua proiecție). Ideea este de a aplica Assoc1 până când argumentul care urmează să fie adus în prima poziție este în a doua, și apoi aplicați Inv1 sau Inv2 în mod corespunzător pentru a aduce argumentul în a doua poziție în prima, apoi aplicați Assoc2 până la efectele cererii originale din Assoc1 (care sunt acum în spatele argumentului mutat) sunt incorecte.

De sine $\{(x,y)\mid \phi (x,y)\}$ ${\ displaystyle \ {(x, y) \ mid \ phi (x, y) \}}$ $\ {(x, y) \ mid \ phi (x, y) \}$ atunci întregul există $\{y\mid \exists x[\phi (x,y)]\}$ ${\ displaystyle \ {y \ mid \ există x [\ phi (x, y)] \}}$ $\ {y \ mid \ există x [\ phi (x, y)] \}$ Este pur și simplu codomainul primului set, considerat ca o relație. Cuantificatorul universal poate fi definit în termenii cuantificatorului existențial și al negației .

Codominio: Pentru fiecare clasă R , clasa ${\mathit {Rng}}(R)=\{y\mid \exists x[(x,y)\in R]\}$ ${\ displaystyle {\ mathit {Rng}} (R) = \ {y \ mid \ există x [(x, y) \ în R] \}}$ ${\ mathit {Rng}} (R) = \ {y \ mid \ există x [(x, y) \ în R] \}$ există.

Axioma de mai sus poate rearanja argumentele fiecărei relații pentru a aduce argumentul dorit în partea de sus a listei de argumente, unde poate fi cuantificat.

În cele din urmă, fiecare formulă atomică implică existența unei relații corespunzătoare între clase:

Calitate de membru: Clasa $[\in ]=\{(x,y)\mid x\in y\}$ ${\ displaystyle [\ in] = \ {(x, y) \ mid x \ in y \}}$ $[\ in] = \ {(x, y) \ mid x \ in y \}$ există.
Diagonală: Clasa $[=]=\{(x,y)\mid \,x=y\}$ ${\ displaystyle [=] = \ {(x, y) \ mid \, x = y \}}$ $[=] = \ {(x, y) \ mid \, x = y \}$ există.

Diagonalul , împreună cu adăugarea de argumente fictive și manipularea lor, pot construi o relație afirmând egalitatea oricăruia dintre cele două argumente; în acest fel variabilele repetate pot fi gestionate.

Variantele lui Mendelson

Mendelson (1997: 230) se referă la axiomele sale B1-B7 ale înțelegerii claselor „axiome ale existenței claselor”. Patru dintre acestea sunt identice cu cele menționate mai sus: B1 este Adeziunea; B2 , Intersecția; B3 , Complementul; B5 , Produsul. B4 este Modomain modificat pentru a afirma existența domeniului R (în esență prin cuantificarea y în loc de x ). Ultimele două axiome sunt:

B6:

\forall X\exists Y\forall uvw[(u,v,w)\in Y\Leftrightarrow (v,w,u)\in X].

{\ displaystyle \ forall X \ există Y \ forall uvw [(u, v, w) \ în Y \ Leftrightarrow (v, w, u) \ în X].}

\ forall X \ există Y \ forall uvw [(u, v, w) \ în Y \ Leftrightarrow (v, w, u) \ în X].

B7:

\forall X\exists Y\forall uvw[(u,v,w)\in Y\Leftrightarrow (u,w,v)\in X].

{\ displaystyle \ forall X \ există Y \ forall uvw [(u, v, w) \ în Y \ Leftrightarrow (u, w, v) \ în X].}

\ forall X \ există Y \ forall uvw [(u, v, w) \ în Y \ Leftrightarrow (u, w, v) \ în X].

B6 și B7 permit ceea ce permit Inversiunea și Asocierea: având în vedere orice clasă X de tripluri ordonate, există o altă clasă Y ai cărei membri sunt membri ai X ordonați în același mod.

Discuţie

Pentru o discuție a unora dintre implicațiile ontologice și alte implicații filozofice ale NBG, în special în comparație cu ZFC și MK , consultați Anexa C. a lui Potter (2004).

Deși NBG este o extensie conservatoare a ZFC, o teoremă poate avea o dovadă mai scurtă și mai elegantă în NBG decât în ZFC (sau invers). Pentru o revizuire a descoperirilor cunoscute de acest tip, a se vedea Pudlak (1998).

Teoria modelului

ZFC, NBG și MK au modele care pot fi descrise în termeni de V , modelul intern al ZFC și universul von Neumann . Acum includeți elementele lui V cardinalul inaccesibil κ. De asemenea, denotați Def ( X ) i Δ ₀ subseturi definibile ale lui X (a se vedea universul construibil ). Atunci:

V _κ este un model destinat ZFC;
Def ( V _κ ) este un model destinat NBG;
V _{κ + 1} este un model destinat MK .

Teoria categoriilor

Ontologia NBG oferă instrumentele pentru a vorbi despre „obiecte mari” fără riscul paradoxurilor. În unele evoluții ale teoriei categoriilor , de exemplu, o „categorie largă” este definită ca o categorie ale cărei obiecte formează o clasă proprie și același lucru este valabil și pentru morfismele sale. O „categorie mică”, pe de altă parte, este o categorie ale cărei obiecte și morfisme fac parte dintr-un anumit set. Astfel putem vorbi cu ușurință despre „ categoria tuturor seturilor ” sau „ categoria tuturor categoriilor mici ” fără a risca paradoxuri. Aceste categorii sunt categorii evidente. Nu există o „categorie a tuturor categoriilor”, deoarece ar trebui să conțină categoria tuturor categoriilor mici, deși o altă extensie ontologică ne poate permite să vorbim formal despre această „categorie” (vezi de exemplu „aproape categoria tuturor categoriilor” de Adámek et. al. (1990), ale cărui obiecte și morfisme formează un „conglomerat propriu”).

Pentru a explora dacă o ontologie care include clase și seturi este adecvată pentru teoria categoriilor , vezi Muller (2001).

Notă

^ Mendelson (1997), p. 232, Prop. 4.4, demonstrează echivalența dintre Înțelegerea claselor și axiomele B1-B7 prezentate la p. 230 și descris mai jos.
^ Mendelson (1997), p. 239, Ex. 4.22 (b).
^ Mendelson (1997), p. 239, axioma R.

Bibliografie

Jiří Adámek, Herrlich, Horst și Strecker, George E, Categorii abstracte și concrete (Bucuria pisicilor) ( PDF ), New York, Wiley & Sons, 2004 [1990] , ISBN 0-471-60922-6 .
Bernays, Paul, Axiomatic Set Theory , Dover Publications, 1991, ISBN 0-486-66637-9 .
Mendelson, Elliott, 1997. O introducere în logica matematică , ediția a IV-a. Londra: Chapman & Hall. ISBN 0-412-80830-7 . Pp. 225–86 conțin tratamentul clasic al manualului NBG, arătând cum face ceea ce așteptăm de la teoria mulțimilor, prin fundamentarea relațiilor , teoria ordinelor , numerele ordinale , numerele transfinite etc.
Richard Montague , 1961, „Închiderea semantică și axiomatizabilitatea nonfinită I”, în Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics , (Varșovia, 2-9 septembrie 1959). Pergamon: 45-69.
Muller, FA, 2001, „Seturi, clase și categorii”, British Journal of the Philosophy of Science 52: 539-73.
Potter, Michael, 2004. Teoria seturilor și filosofia ei . Presa Universitatii Oxford.
Pudlak, P., 1998, „Lungimile dovezilor” în Buss, S., ed., Handbook of Proof Theory . Olanda de Nord: 547-637.
John von Neumann , 1925, „O axiomatizare a teoriei mulțimilor”. Traducere în limba engleză în Jean van Heijenoort , ed., 1967. De la Frege la Gödel: O carte sursă în logică matematică, 1879-1931 . Harvard University Press.

Elemente conexe

[1] Mendelson (1997), p. 232, Prop. 4.4, demonstrează echivalența dintre Înțelegerea claselor și axiomele B1-B7 prezentate la p. 230 și descris mai jos.

[2] Mendelson (1997), p. 239, Ex. 4.22 (b).

[3] Mendelson (1997), p. 239, axioma R.

[1]

[2]

[3]