Teoria degli insiemi di Von Neumann-Bernays-Gödel

Nello studio dei fondamenti della matematica, la teoria degli insiemi di Von Neumann-Bernays-Gödel (NBG) è una teoria assiomatica degli insiemi che costituisce un'estensione conservativa della canonica teoria assiomatica degli insiemi di Zermelo-Fraenkel con l'assioma della scelta (ZFC). Una formula nel linguaggio di ZFC è dimostrabile in NBG se e solo se è dimostrabile in ZFC. L'ontologia di NBG include le classi proprie, oggetti che possono avere elementi ma che non possono essere elementi a loro volta. Il principio di comprensione di NBG è predicativo; le variabili quantificate nella formula possono spaziare solo all'interno di insiemi. Permettere la comprensione impredicativa trasforma NBG nella teoria degli insiemi di Morse-Kelley (MK). NBG, a differenza di ZFC e di MK, può essere finitamente assiomatizzata.

Ontologia

L'aspetto distintivo di NBG è la distinzione tra classe propria e insieme. Siano a e s due individui. Allora la formula atomica $a\in s$ è definita se a è un insieme ed s è una classe. In altre parole, $a\in s$ è definita a meno che a sia una classe propria. Una classe propria è molto grande; NBG ammette anche "la classe di tutti gli insiemi", la classe universale chiamata V. Tale precisione nello stabilire che a sinistra del simbolo $\in$ ci sia un insieme e a destra una classe fa sì che non sia ammesso definire, ad esempio, l'"insieme di tutti gli insiemi" o la "classe di tutte le classi".

Secondo lo schema di assiomi della Comprensione delle Classi di NBG, tutti gli oggetti che soddisfano una data formula nella teoria del primo ordine di NBG formano una classe; se la classe non fosse un insieme in ZFC, allora sarebbe una classe propria di NBG.

Lo sviluppo delle classi rispecchia lo sviluppo della teoria ingenua degli insiemi. Il principio di astrazione è dato, e quindi le classi possono essere formate da tutti gli individui che soddisfano una qualunque formula della teoria del primo ordine le cui formule atomiche coinvolgono tutte o la relazione di appartenenza o predicati definibili a partire dalla relazione di appartenenza. Uguaglianza, associazione, sottoclasse, e via dicendo, sono tutte definibili e quindi non hanno bisogno di essere assiomatizzate — la loro definizione denota una particolare astrazione di una formula.

Gli insiemi sono sviluppati in maniera molto simile a ZF. Si indichi con Rp(A,a) "l'insieme a rappresenta la classe A," allora Rp denota una relazione binaria definita come segue:

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

Che significa, a "rappresenta" A se ogni elemento di a è un elemento di A, e viceversa. Le classi che non hanno rappresentazione, come la classe di tutti gli insiemi che non contengono sé stessi (la classe invocata nel paradosso di Russell), sono le classi proprie.

Storia

La prima variante di NBG, ad opera di John von Neumann negli anni '20, prese funzioni, non insiemi, come primitive. In una serie di articoli pubblicati nel 1937-54, Paul Bernays modificò la teoria di Von Neumann in modo tale da rendere gli insiemi e l'appartenenza ad un insieme le primitive. Gödel (1940), mentre lavorava sull'indipendenza dell'ipotesi del continuo, semplificò ulteriormente la teoria e scoprì che poteva essere finitamente assiomatizzata. Montague (1961) mostrò che ZFC non può essere finitamente assiomatizzata.

Assiomatizzazione NBG

NBG è qui presentata come una teoria basata su due tipi di oggetti: con lettere minuscole si denotano le variabili che spaziano sugli insiemi, e con lettere maiuscole si denotano le variabili che spaziano sulle classi. Quindi $x\in y$ si deve leggere come "l'insieme $x$ appartiene all'insieme $y$," e $x\in Y$ come "l'insieme $x$ appartiene alla classe $Y$." Formule di uguaglianza possono avere la forma $x=y$ oppure $X=Y$. $a=A$ sta per $\forall x(x\in a\leftrightarrow x\in A)$ ed è un abuso di notazione. NBG può anche essere presentato come una teoria sulle classi basata su un solo tipo di oggetto, le classi, definendo gli insiemi come quelle classi che sono membri di almeno un'altra classe.

Per prima cosa assiomatizziamo NBG usando lo schema di assiomi della Comprensione delle Classi. Si può dimostrare che questo schema è equivalente a 9 delle sue istanze finite, definite nella sezione seguente. Quindi questi 9 assiomi finiti possono sostituire la Comprensione delle Classi. Questo è il senso preciso in cui NBG può essere assiomatizzata finitamente.

Con lo schema della Comprensione delle Classi

I 5 seguenti assiomi sono identici alle loro controparti ZFC:

• estensionalità: $\forall x(x\in a\leftrightarrow x\in b)\rightarrow a=b.$: Insiemi con gli stessi elementi sono lo stesso insieme.
• accoppiamento: $\forall x\forall y\exists z\forall w[w\in z\leftrightarrow (w=x\lor w=y)].$ Per tutti gli insiemi $x$ e $y$, esiste un insieme, $\{x,y\}$, i cui elementi sono esattamente $x$ e $y$.

accoppiamento implica che per ogni insieme $x$, l'insieme $\{x\}$(l'insieme singoletto) esiste. Inoltre, dati due insiemi qualunque $x$ e $y$ e l'usuale definizione delle coppie ordinate, la coppia ordinata $(x,y)$ esiste ed è un insieme. Nella Comprensione delle Classi, tutte le relazioni su insiemi sono classi. In più, certi tipi di relazioni tra classi sono uno o più tra funzioni, iniezioni, e biezioni da una classe all'altra. accoppiamento è un assioma nella teoria degli insiemi di Zermelo ed un teorema in ZFC.

• unione: Per ogni insieme $x$, esiste un insieme che contiene esattamente gli elementi degli elementi di $x$.
• insieme potenza: Per ogni insieme $x$, esiste un insieme che contiene esattamente i sottoinsiemi di $x$.
• infinito: Esiste un insieme induttivo, chiamato insieme $x$ i cui elementi sono (i) l'insieme vuoto; (ii) per ogni membro $y$ di $x$, $y\cup \{y\}$ è anche un elemento di $x$.

infinito può essere formulato in modo da implicare l'esistenza dell'insieme vuoto.

I rimanenti assiomi hanno iniziale maiuscola perché hanno principalmente a che fare con le classi piuttosto che con gli insiemi. I prossimi due assiomi differiscono dalle loro controparti ZFC solamente perché le variabili quantificate spaziano sulle classi, non sugli insiemi:

• Estensionalità: $\forall x(x\in A\Leftrightarrow x\in B)\Rightarrow A=B.$: Classi con gli stessi elementi sono la stessa classe.
• Fondazione (Regolarità): Ogni classe non vuota è disgiunta da uno dei suoi elementi.

Gli ultimi due assiomi sono peculiari di NBG:

• Limite della dimensione: Per ogni classe $C$, esiste un insieme $x$ tale che $x=C$ se e soltanto se non esiste una biezione tra $C$ e la classe $V$ di tutti gli insiemi.

Da questo assioma, dovuto a John von Neumann, Sottoinsiemi, Sostituzione, e Scelta Globale possono essere tutti derivati. Questo assioma implica l'assioma della scelta globale perché la classe degli ordinali non è un insieme; quindi esiste una biezione tra gli ordinali e l'universo. Se l'assioma del limite della dimensione fosse indebolito a "Se il dominio di una funzione tra classi è un insieme, allora il codominio di quella funzione è anch'esso un insieme", allora nessuna forma dell'assioma della scelta è un teorema NBG. In questo caso, ogni usuale forma locale dell'assioma della scelta può essere presa come un assioma in aggiunta, se lo si desidera.

Limite della scelta non può essere trovato in Mendelson (1997) NGB. Al suo posto troviamo l'usuale assioma della scelta per insiemi, e la seguente forma dello schema di assiomi della sostituzione: se la classe F è una funzione il cui dominio è un insieme, allora il codominio di $F$ è anch'esso un insieme.

• Schema della Comprensione delle Classi: per ogni formula $\phi$ non contenente quantificatori tra le classi (può contenere parametri di classi ed insiemi), esiste una classe $A$ tale che $\forall x(x\in A\Leftrightarrow \phi (x)).$

Questo assioma asserisce che l'invocazione del principio della comprensione non ristretta della teoria ingenua degli insiemi restituisce una classe piuttosto che un insieme, bandendo in tal modo i paradossi della teoria degli insiemi.

Comprensione delle Classi è l'unico schema di assiomi di NBG. Nella prossima sezione, mostriamo come questo schema può essere sostituito da un numero delle sue stesse istanze. Quindi NBG può essere finitamente assiomatizzata. Se le variabili quantificate in $\varphi (x)$ spaziano sulle classi invece che sugli insiemi, il risultato è la teoria degli insiemi di Morse-Kelley, un'estensione propria di ZFC che non può essere finitamente assiomatizzata.

Sostituzione della Comprensione delle Classi con finite istanze della stessa

Una caratteristica interessante ma un po' misteriosa della NBG è che il suo schema di assiomi della Comprensione delle Classi è equivalente alla congiunzione di un numero finito delle sue istanze. Gli assiomi in questa sezione possono sostituire gli assiomi della Comprensione delle Classi della precedente sezione. L'assiomatizzazione finita presentata di seguito non somiglia necessariamente ad ogni assiomatizzazione NBG in stampa.

Sviluppiamo la nostra assiomatizzazione considerando la struttura delle formule.

• Insiemi: Per ogni insieme $x$, esiste una classe $X$ tale che $x=X$.

Questo assioma, in combinazione con l'assioma dell'esistenza della sezione precedente, assicura l'esistenza di classi fin dall'inizio, e permette di avere formule con parametri di classe.

Siano $A=\{x\mid \phi \}$ e $B=\{x\mid \psi \}.$ Allora $\{x\mid \neg \phi \}=V-A$ e $\{x\mid \phi \wedge \psi \}=A\cap B$ sono sufficienti per generare tutti i connettivi logici, perché ∧ e ¬ sono un insieme di connettivi funzionalmente completo.

• Complemento: Per ogni classe $A$, il complemento $V-A=\{x\mid x\not \in A\}$ è una classe.
• Intersezione: Per ogni classe $A$ e $B$, l'intersezione $A\cap B=\{x\mid x\in A\wedge x\in B\}$ è una classe.

Ci rivolgiamo ora alla quantificazione. Per poter maneggiare variabili multiple, abbiamo bisogno di poter rappresentare relazioni. Definiamo la coppia ordinata $(a,b)$ come $\{\{a\},\{a,b\}\},$ come usualmente. Si noti che due applicazioni di accoppiamento a $a$ e $b$ assicurano che $(a,b)$ è senza dubbio un insieme.

• Prodotti: Per ogni classe $A$ e $B$, la classe $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$ è una classe. (In pratica, solo $V\times A$ serve.)
• Inversione: Per ogni classe $R$, le classi:

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

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

• Associazione: Per ogni classe $R$, le classi:

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

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

Questi assiomi permettono di aggiungere argomenti fittizi, e manipolando l'ordine degli argomenti, in relazioni di ogni arietà. La forma peculiare dell'Associazione è progettata per rendere possibile prendere qualunque termine in una lista di argomenti in prima posizione (con l'aiuto dell'Inversione). Rappresentiamo la lista di argomenti $(x_{1},x_{2},\ldots ,x_{n})$ come $(x_{1},(x_{2},\ldots ,x_{n}))$ (è una coppia con il primo argomento come prima proiezione e la "coda" come la seconda proiezione). L'idea è di applicare Assoc1 finché l'argomento da portare in prima posizione si trova in seconda, e poi applicare Inv1 o Inv2 in maniera appropriata per portare l'argomento in seconda posizione nella prima, applicare allora Assoc2 finché gli effetti dell'applicazione originale di Assoc1 (che ora si trovano dietro l'argomento spostato) non sono corretti.

Se $\{(x,y)\mid \phi (x,y)\}$ esiste, allora l'insieme $\{y\mid \exists x[\phi (x,y)]\}$ è semplicemente il codominio del primo insieme, considerato come relazione. Il quantificatore universale può essere definito in termini del quantificatore esistenziale e della negazione.

• Codominio: Per ogni classe $R$, la classe ${\mathit {Rng}}(R)=\{y\mid \exists x[(x,y)\in R]\}$ esiste.

L'assioma precedente può riordinare gli argomenti di ogni relazione in modo da portare l'argomento desiderato in cima alla lista degli argomenti, dove può essere quantificato.

Infine, ogni formula atomica implica l'esistenza di una corrispondente relazione tra classi:

• Adesione: La classe $[\in ]=\{(x,y)\mid x\in y\}$ esiste.
• Diagonale: La classe $[=]=\{(x,y)\mid \,x=y\}$ esiste.

Diagonale, insieme all'aggiunta di argomenti fittizi ed alla manipolazione degli stessi, può costruire una relazione affermando l'uguaglianza di due qualunque dei suoi argomenti; in tal modo le variabili ripetute possono essere gestite.

Varianti di Mendelson

Mendelson (1997: 230) si riferisce ai suoi assiomi B1-B7 della comprensione delle classi "assiomi dell'esistenza delle classi." Quattro di questi sono identici a quelli menzionati sopra: B1 è l'Adesione; B2, l'Intersezione; B3, il Complemento; B5, il Prodotto. B4 è il Codominio modificato per affermare l'esistenza del dominio di $R$ (essenzialmente tramite una quantificazione di $y$ invece di $x$). Gli ultimi due assiomi sono:

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

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

B6 e B7 permettono quello che l'Inversione e l'Associazione permettono: data una qualunque classe $X$ di triple ordinate, esiste un'altra classe $Y$ i cui membri sono i membri di $X$ ognuno ordinato nello stesso modo.

Discussione

Per una discussione di alcune implicazioni ontologiche ed altre filosofiche di NBG, specialmente confrontate con ZFC e MK, vedi Appendice C di Potter (2004).

Anche se NBG è un'estensione conservativa di ZFC, un teorema può avere una dimostrazione più corta ed elegante in NBG che in ZFC (o viceversa). Per una rassegna dei risultati noti di questo tipo, vedi Pudlak (1998).

Teoria dei modelli

ZFC, NBG, e MK hanno modelli descrivibili in termini di V, il modello interno di ZFC e l'universo di von Neumann. Ora includano gli elementi di V il cardinale inaccessibile κ. Inoltre denoti Def(X) i Δ₀ definibili sottoinsiemi di X (vedi universo costruibile). Allora:

• V_κ è un modello inteso di ZFC;
• Def(V_κ) è un modello inteso di NBG;
• V_κ+1 è un modello inteso di MK.

Teoria delle categorie

L'ontologia di NBG fornisce gli strumenti per parlare di "oggetti larghi" senza il rischio di paradossi. In alcuni sviluppi della teoria delle categorie, per esempio, una "categoria larga" è definita come una categoria i cui oggetti formino una classe propria, e la stessa cosa vale per i suoi morfismi. Una "categoria piccola", invece, è una categoria i cui oggetti e morfismi sono membri di qualche insieme. Possiamo così parlare facilmente della "categoria di tutti gli insiemi" o "categoria di tutte le categorie piccole" senza rischiare paradossi. Queste categoria sono ovviamente categorie larghe. Non esiste una "categoria di tutte le categorie" dal momento che dovrebbe contenere la categoria di tutte le categorie piccole, anche se un'altra estensione ontologica può permetterci di parlare formalmente di questa "categoria" (vedi per esempio la "quasicategoria di tutte le categorie" di Adámek et al. (1990), i cui oggetti e morfismi formano un "conglomerato proprio").

Per approfondire il problema se un'ontologia che includa classi e set sia adeguata per la teoria delle categorie, vedere Muller (2001).

Bibliografia

• Jiří Adámek, Herrlich, Horst, and Strecker, George E, Abstract and Concrete Categories (The Joy of Cats) (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. An Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall. ISBN 0-412-80830-7. Pp. 225–86 contain the classic textbook treatment of NBG, showing how it does what we expect of set theory, by grounding relations, order theory, ordinal numbers, transfinite numbers, ecc.
• Richard Montague, 1961, "Semantic Closure and Non-Finite Axiomatizability I," in Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, (Warsaw, 2-9 September 1959). Pergamon: 45-69.
• Muller, F. A., 2001, "Sets, classes, and categories," British Journal of the Philosophy of Science 52: 539-73.
• Potter, Michael, 2004. Set Theory and Its Philosophy. Oxford University Press.
• Pudlak, P., 1998, "The lengths of proofs" in Buss, S., ed., Handbook of Proof Theory. North-Holland: 547-637.
• John von Neumann, 1925, "An Axiomatization of Set Theory." English translation in Jean van Heijenoort, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard University Press.

Voci correlate

• Predicatività
• Teoria degli insiemi di Morse-Kelley
• Teoria degli insiemi di Zermelo-Fraenkel

Collegamenti esterni

• (EN) Neumann-Bernays-Gödel set theory, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Teoria degli insiemi di Von Neumann-Bernays-Gödel, su MathWorld, Wolfram Research.