Teoria degli insiemi di Von Neumann-Bernays-Gödel (NBG)

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Teoria degli insiemi di Von Neumann-Bernays-Gödel (NBG)

Messaggioda Lord K il mer 17 mar 2010, 15:02

Storia: la formulazione originale è di John Von Neumann negli anni '20, successivamente riprese da Paul Bernays che la modificò per rendere più generale il risultato, in alcuni suoi articoli nel periodo 1937-1954. Gödel intervenne nella sua semplificazione negli anni '40 e determinò che poteva essere finitamente assiomatizzata, cosa non possibile per la ZFC.

La teoria assiomatica degli insiemi NBG è una estensione conservativa della canonica teoria assiomatica degli insimei ZFC (Zermelo-Fraenkel + assioma della scelta) e si fonda soprattutto nella distinzione tra clase propria e insieme. Dunque siano a insiemi (e d'ora in poi tutte le lettere minuscole si riferiranno a insiemi) e A classi (e d'ora in poi tutte le lettere maiuscole si riferiranno a classi).

Assiomi (identici a ZFC):

(1) estensionalità: \forall x(x \in a \leftrightarrow x \in b) \rightarrow a=b. Insiemi con gli stessi elementi sono lo stesso insieme.
Oss: da qui si evince subito che se un elemento sta in un insieme allora ci sta una volta sola senza molteplicità, quindi \{1,1\}=\{1\}, inoltre anche che gli elementi di un insieme non hanno ordine \{1,2\}=\{2,1\}

(2) accoppiamento: \forall x \forall y \exists z \forall w[w \in z \leftrightarrow (w=x \vee w=y)]. Per ogni insieme x e per ogni insieme y esiste un insieme \{x,y\}i cui elementi sono x e y.
Oss: qui la prima cosa che emerge è che se x è un insieme allora anche il singoletto \{x\} è un insieme.

(3) unione: \forall x \exists y \forall z: z \in y \leftrightarrow (\exists w: z \in w \wedge w \in x). Per ogni insieme x esiste un insieme che contiene esattamente gli elementi degli elementi di x. L'unione di un insime è un insieme.

(4) insieme potenza: \forall x \exists p \forall y : y \in p \leftrightarrow (\forall z: z \in y \rightarrow z \in x). Per ogni insieme x esiste un insieme, usualmente denominato \mathcal P(x) che contiene come elementi esattamente i sottoinsiemi di x.
Oss: da qui è possibile la costruzione naturale del prodotto cartesiano di insiemi come insieme, infatti x \times y = \{(a,b): a \in x \wedge b \in y\} \subseteq \mathcal P (\mathcal P (x \cup y)).

(5) infinito: \exists x : \emptyset \in x \wedge (\forall y: y \in a \leftrightarrow y \cup \{y\} \in x). Esiste un insieme induttivo di x.
Oss: questo assioma permette la costruzione dei numeri naturali mediante la funzione successore che assegna \sigma: x \mapsto x \cup \{x\} ove lo sero è l'insieme vuoto.

Assiomi propri di NBG:

(6) estensionalità di classi: \forall x(x \in A \leftrightarrow x \in B) \rightarrow A=B. Classi con gli stessi elementi sono la stessa classe.

(7) regolarità: \forall X[\exists A(A \in X) \rightarrow \exists Y(Y \in X \wedge \nexists Z(Z \in Y \wedge Z \in X))] Ogni classe non vuota è disgiunta da uno dei suoi elementi.
Oss: la formulazione sembra un poco più corretta ma non sono ancora troppo convinto...

(8) limite di dimensione: \forall C \exists x, x=C \leftrightarrow (\nexists \varphi: C \rightleftharpoons V). Per ogni classe C, un insieme x tale che x=C esiste se e soltanto se non esiste una biezione tra C e la classe V di tutti gli insiemi.
Oss: la classe degli ordinali non è un insieme e quindi esiste una biezione tra gli ordinali e l'universo. Inoltre

(9) schema della comprensione delle classi: Per ogni formula \psi non contenente quantificatori tra le classi, esiste una classe A tale che \forall x(x \in A \leftrightarrow \psi(x)).
Oss: questo assioma ci permette di sostituire l'insieme con la classe nel principio di comprensione della teoria ingenua degli insiemi, rendendo impossibili i paradossi propri di ZFC (paradosso di Russel).

Il Paradosso di Russel

Secondo quanto specificato sopra, la costruzione, dato x insieme:

M=\{x:x \notin x\}

non è un insieme, ma bensì una classe.

Teoria delle categorie:

Alcuni punti fondamentali derivanti da NBG:

-Una categoria \mathbf X viene detta piccola quando la classe \mathbf X di tutti i suoi oggetti (e morfismi) è un insieme secondo NBG.
-Le categorie "larghe" sono quelle ove sia i morfismi che gli oggetti sono facenti parte di classi proprie.
-Non esiste una categoria di tutte le categorie.

P.S. il trattare questo argomento mi pare molto interessante in termini di basi dell'algebra categoriale.

Edit: modifica sull'assioma della regolarità.
Ultima modifica di Lord K il gio 26 gen 2012, 11:30, modificato 2 volte in totale.
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Messaggioda killing_buddha il gio 18 mar 2010, 15:54

Lord K ha scritto:(7) regolarità: Ogni classe non vuota è disgiunta da uno dei suoi elementi.

Suggerisco
(A\neq\varnothing) \Rightarrow \exists B(B\in A\land \lnot(C(C\in A\land C\in B)))
- Se incontri il Buddha uccidilo. Devi vivere libero da ogni dogma: se non riesci a uccidere Buddha, come ucciderai il tuo pregiudizio?
- "Peu d'abstraction on éloigne de la géometrie; beaucoup on y ramène"
Avatar utente
killing_buddha
 
Messaggi: 2739
Iscritto il: gio 17 lug 2008, 19:51

Messaggioda killing_buddha il gio 18 mar 2010, 16:04

Non esiste una categoria di tutte le categorie.

E' un punto interessante per porsi questa domanda: vorremmo dare una base categorica alle costruzioni che si fanno con un tot di categorie date. Come scritto qui la categoria prodotto nasce come il prodotto (inteso in senso categoriale, come oggetto P universale, dotato di due proiezioni che fattorizzano ogni freccia X\to P) tra le due categorie date: finche' le categorie in gioco sono piccole, o si suppone di muoversi in un universo opportuno, la costruzione puo' avere senso. Ma... se ci si sposta oltre? Espresso in termini piu' precisi: esiste un modo di definire un prodotto tra categorie grandi, alla luce del fatto che non si puo' postulare l'esistenza di una classe che contenga tutte le categorie?
- Se incontri il Buddha uccidilo. Devi vivere libero da ogni dogma: se non riesci a uccidere Buddha, come ucciderai il tuo pregiudizio?
- "Peu d'abstraction on éloigne de la géometrie; beaucoup on y ramène"
Avatar utente
killing_buddha
 
Messaggi: 2739
Iscritto il: gio 17 lug 2008, 19:51

Messaggioda Lord K il gio 18 mar 2010, 17:02

Credo che in questo caso sia da chiarire come sono fatti i morfismi tra oggetti che sono classi proprie e non semplici insiemi. Per cominciare vediamo che il punto (8) ci porta a dire che ogni oggetto di una categoria "larga" è in corrispondenza con l'insieme di tutti gli insiemi... da qui però mi sa che dovremo affinare le nostre armi!
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Osservazioni sulla costruzione degli interi secondo NBG

Messaggioda Lord K il lun 22 mar 2010, 16:27

Usando in maniera intensa l'assioma (5) otteniamo facilmente la successione degli elementi che formano \mathbb{N} ed anche il loro ordine, infatti esiste una biezione canonica per la costruzione dei numeri. Necessitiamo ancora dell'assioma denominato principio di induzione?
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Von Neumann universe

Messaggioda Lord K il mar 23 mar 2010, 11:54

killing_buddha ha scritto:[...] Espresso in termini piu' precisi: esiste un modo di definire un prodotto tra categorie grandi, alla luce del fatto che non si puo' postulare l'esistenza di una classe che contenga tutte le categorie?


Ci ho pensato un poco e sono giunto a qualche interessante osservazione. Il punto (8) ci permette di dire che se C è una classe, allora esiste una biezione con la classe V di tutti gli insiemi, ma questa è ancora da definirsi decentemente, allora facciamolo partendo dalle definizioni base:

Definizione:
Il rango di un insieme X ben-costruito (qui) è definito induttivamente come il più piccolo ordinale più grande del rango di tutti gli elementi dell'insieme X. Coerentemente si forma una gerarchia di ranghi (denominata gerarchia cumulativa -cumulative hierarchy-)che servirà poi per la costruzione di V

Esempi:
-Insieme vuoto :arrow: rango zero
-Ordinale :arrow: rango con lo stesso ordinale

Definzione:
La gerarchia cumulativa è una collezione di insiemi V_\alpha indicizzati dalla classe degli ordinali. In particolare V_\alpha è l'insieme di tutti gli insiemi che hanno rango minore di \alpha. (per completezza V_0 è vuoto)

Osservazione: Per ogni ordinale \beta, V_{\beta+1} è l'insieme delle parti di V_\beta, nulla di nuovo visto che deriva dalla definizione degli ordinali (qui)

Nota: tralascio, ove non necessaria, la trattazione dei numeri ordinali limite (qui)

Finalmente:

Definzione:
La classe V (denominata Von Neumann Universe) è definita come:

\displaystyle V := \bigcup_\alpha V_\alpha

o equivalentemente come:

\displaystyle V := \bigcup_{\beta < \alpha} \mathcal P (V_\beta)

Prop. V non è un insieme in NBG
Proof: per costruzione e grazie all'assioma (8). \diamond

Prop. V non è un insieme in ZFC
Proof: provate un poco a pensare a questa... ed aiutatevi con questo.\diamond

Arrivati a questo punto abbiamo gli ingredienti per poter costruire degli oggetti che sono classi e non insiemi, la ricetta però pare abbastanza insidiosa e densa di molti dettagli da esplicare. Per ora mi fermo a questo punto e prima di aggiungere altro mi documenterò a dovere.
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Messaggioda Lord K il mar 23 mar 2010, 12:20

Lord K ha scritto:Usando in maniera intensa l'assioma (5) otteniamo facilmente la successione degli elementi che formano \mathbb{N} ed anche il loro ordine, infatti esiste una biezione canonica per la costruzione dei numeri. Necessitiamo ancora dell'assioma denominato principio di induzione?


Teorema
Sia P(n) una proprietà senza quantificatori sulle classi, se è vera per n=0 e inoltre P(n) \rightarrow P(n \cup \{n\}), allora P(n) è vera per ogni n \in \mathbb{N}, ove \mathbb{N} è l'insieme dei naturali costruito come supporto come sopra.

Proof:
Per l'assioma (9) di comprensione delle classi definiamo la classe:

A&#39;=\{n: n \in \mathbb{N}\} \cap \{n:P(n)\} = \mathbb{N} \cap N

infatti genericamente N:=\{n:P(n)\} è una classe. Se A&#39; fosse una classe propria, allora lo sarebbe anche \mathbb{N} che però è un insieme dall'assioma dell'infinito. Dunque A&#39; è un insieme!

Nella dimostrazione originale di ZFC qui si dice che A&#39; è un insieme e si fa vedere che valgono entrambe A&#39;\subseteq \mathbb{N} ed anche \mathbb{N} \subseteq A&#39;. Qui applicando la stessa idea si arriva alla tesi. \diamond

Non è necessario quindi aggiungere il principio di induzione!

P.S. Grazie a Feanor per l'illuminazione finale :winner_first:
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Assioma della Scelta Globale

Messaggioda Lord K il gio 6 mag 2010, 15:31

Come per gli insiemi, la generalizzazione dell'assioma della scelta deriva direttamente dall'assioma (8), tale assioma cita:

Forma debole: Ogni classe di insiemi non vuoti ha una funzione di scelta.
Forma forte: ogni collezione di classi non vuote ha una funzione di scelta.

Altre forme:
  • L'universo di Von Neumann meno l'insieme vuoto, ha una funzione di scelta
  • Esiste un buon ordinamento sull'universo di Von Neumann
  • Esiste una biezione tra l'universo di Von Neumann e la classe di tutti gli ordinali

Proof:
[Omissis per ora]

P.S. Da notarsi come la definizione del link riportato per la funzione di scelta usi ZFC e non NBG, cercherò di adattarla a breve al contesto.
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Teorema di Cantor-Bernstein-Shroeder su NBG

Messaggioda Lord K il ven 7 mag 2010, 10:24

La formulazione originale cita (do per scontato le definizioni formali di iniettività e suriettività, immagine e dominio)

Proposizione: Siano A,B due insiemi, se esistono f:A \to B e g:B \to A iniettive, allora esiste una funzione biettiva h:A \to B.

Proof: Consideriamo:

  • un punto x \in A ha un precedente y \in B se x=g(y)
  • un punto y \in B ha un precedente a \in A se y=f(x)
Per l'ipotesi iniziale di iniettività se esistono precedenti o successori, allora sono unici. Possiamo costruire una successione di elementi (x, x_1,x_2,\cdots) dove x_i è il precedente di x_{i+1}. Se la successione ha termine, l'ultimo elemento lo chiameremo "primo elemento". Ora si determina naturalmente una partizione di A nella seguente maniera:

  • A_A è l'insieme dei punti di A per i quali esiste il "primo elemento" \eta_0 \in A
  • A_B è l'insieme dei punti di A per i quali esiste il "primo elemento" \nu_0 \in B
  • A_T è l'insieme dei punti di A per i quali la successione non ha mai temine.
Definiamo la biezione h:A \to B sulle partizioni:

  • h(x)=f(x), x \in A_A
  • h(x)=g^{-1}(x), x \in A_B
  • h(x)=f(x), x \in A_T

la verifica della biettività è un (semplice) esercizio lasciato al lettore.

Osservazioni: Questo fondamentale teorema ci porta a comprendere come si possano costruire degli ordinamenti parziali tra insiemi. Per giungere agli ordinamenti totali è comunque necessario l'assioma della scelta. Per le classi credo che la situazione possa cambiare (in peggio) e mi riserbo l'aggiornamento a breve.
Ultima modifica di Lord K il lun 10 mag 2010, 11:06, modificato 1 volta in totale.
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara

Sottoinsiemi di insiemi

Messaggioda Feanor il lun 10 mag 2010, 9:46

Lord K ha scritto:(8) limite di dimensione: (\forall\: C)\,(\exists\: x)\ \bigl(x=C \leftrightarrow (\nexists \varphi: C \rightleftharpoons V)\bigr). Per ogni classe C, un insieme x tale che x=C esiste se e soltanto se non esiste una biezione tra C e la classe V di tutti gli insiemi.

Prop. Sia x un insieme e Y una sua sottoclasse, cioè esista una funzione iniettiva \pi_Y(\cdot): Y \to x. Allora Y è un insieme.

Dim. Supponiamo, per assurdo, che Y sia una classe propria, ossia esista una biezione \varphi(\cdot): Y \to V dove V è la classe di tutti gli insiemi (generata, e.g., dalla proprietà x \in V \Leftrightarrow x=x). Esiste senz'altro una iniezione \pi_x(\cdot): x \to V, quindi (\varphi^{-1} \circ \pi_x)(\cdot): x \to Y è una iniezione. Per il teorema di Cantor-Bernstein-Schroeder, esiste una biezione \sigma(\cdot): x \to Y. Ne consegue che (\varphi \circ \sigma)(\cdot): x \to V è una biezione, in contrasto con quanto assunto nelle ipotesi. Dunque, esiste y (insieme) tale che y=Y.
Ultima modifica di Feanor il gio 21 feb 2013, 15:22, modificato 1 volta in totale.
Feanor
 
Messaggi: 732
Iscritto il: lun 29 set 2008, 20:58

Prossimo

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite