Teoria degli insiemi ed aritmetica

Teoria degli insiemi ed aritmetica

NBG

Antonio Maida

1 Alfabeto ed assioma di estensionabilità ∈

NBG teoria degli insiemi

Il sistema formale della ha una sola costante primitiva denotante

NBG

l’appartenenza. Le variabili di si indicheranno con lettere maiuscole. Le formule del tipo

NBG. NBG

X∈Y sono le uniche formule atomiche di Gli individui in un qualunque modello di si

diranno classi. Si definiscono le seguenti costanti non logiche:

≈ ∃Y(X∈Y)

MX ≈

PrX MX.

⎤

≈ ∀Z(MZ→Z∈X).

TotX ≈ ∀Z((MZ∧Z∉Z) ↔

RuX Z∈X).

≈ ∀Z(Z∉X).

VX

Le nuove formule MX PrX TotX RuX VX

si leggono rispettivamente “X è un insieme”, “X è una classe propria”, “X è una classe totale”, “X

è una classe di Russell” ed “X è una classe vuota”.

Si definisce ulteriormente:

≈ ∀Z(Z∈X→Z∈Y).

X⊂Y ≈ ∀Z(Z∈X

↔ Z∈Y).

X=Y ≈ ∀Z(X∈Z

↔

X≡Y Y∈Z). NBG,

I seguenti, che come si è visto sono proprietà vere in ogni possibile modello di sono teoremi

NBG:

logici di

(1) X=X. X≡X. X⊂X. (X≡Y∧MX)→MY.

(RuX∧RuY)→X=Y.

X=Y→Y=X. X≡Y→Y≡X. X⊂Y⊂Z→X⊂Z. (PrX∧PrY)→X≡Y.

(TotX∧TotY)→X=Y.

X=Y=Z→X=Z. X≡Y≡Z→X≡Z. X⊂Y⊂X↔X=Y. RuX→PrX.

(VX∧VY)→X=Y.

Assioma di estensionabilità

(AxE): X=Y→X≡Y.

Conseguenze dell’AxE NBG

L’AxE è il primo assioma proprio di e sulla sua utilità si è ampiamente discusso.Sue

conseguenze sono le due:

a) Classi uguali sono omonime. Infatti: (X=Y∧MX)⇒(X≡Y∧MX)⇒MY.

NBG

b) è una teoria con uguaglianza.

La riflessività deriva immediatamente dalla definizione. Per quanto concerne la sostitutività basta

provare le seguenti proprietà

immediate:

X=Y→(X∈Z→Y∈Z).

X=Y→(Z∈X→Z∈Y).

X=Y→(X∈X→Y∈X).

X=Y→(X∈X→X∈Y).

X=Y→(X∈X→Y∈Y).

Si utilizzano variabili minuscole come variabili ristrette ad insiemi. In sintesi,

Ax sta per MX→AX,

∀xAx ∀X(MX→AX)

sta per

∃xAx ∃X(MX∧AX).

sta per

In ogni caso, X è la prima variabile non occorrente in Ax ed AX è la formula ottenuta da Ax

rimpiazzandovi x con X. Una formula dicesi predicativa se vi sono quantificate solo variabili

minuscole.

Modelli (Indipendenza e compatibilità dell’AxE)

∈>

Si considerino i modelli M=<U, ed M’=<U’,∈’> dove

∈=⎨aa, ∈’=⎨ba,

U=⎨a,b,c,d,e,f⎬ ba, ca, cc, cd, be⎬ U’=⎨a,b,c,d,e⎬ ca, bb, cc, ad,

ae⎬.

Le loro tabelle sono: ≡ ⊂

M P Ru Vu Tot

H =

b

a b c de f e b f a x=x b=f c=d x≡x d≡e≡f f⊂x⊂x b⊂c⊂d⊂c⊂a e⊂a

≡ ⊂

M Pr Ru Vu Tot

H =

a

a b c d e de x=x d=e x≡x d≡e x⊂x b⊂a c⊂a d⊂e

e⊂d

In M b=f; v’è l’uguaglianza fra una classe propria ed un insieme, entrambe classi vuote. Ciò capita

solo perché nel modello non vale, come si verifica immediatamente, l’AxE. Si osserva ancora che,

poiché e⊂a, v’è una classe propria inclusa in un insieme. Ciò capita perché, evidentemente, non v’è

ancora un assioma che caratterizzi gli insiemi in base alla cardinalità. In M’ vale invece l’AxE.

2 Assioma di comprensione e conseguenze

Assioma di comprensione ∃Z∀x(x∈Z↔Ax).

(AxC): NBG.

È il secondo proprio di In esso Ax è una formula predicativa, la x è libera in Ax, e la Z non

occorre in Ax. Dalla

definizione di uguaglianza e dall’AxC deriva

╞ ⏐

(∃ Z∀x(x∈Z↔Ax).

NBG

Se le X sono le n≥0 variabili libere di Ax diverse da x, allora, in base al metateorema di

i

definizione, la formula ∃ ⏐ Z∀x(x∈Z↔Ax) n

f

puó interpretarsi come un teorema di esistenza ed unicità per una costante funzionale ad n

m

argomenti; si puó porre n

⎨x/Ax⎬=

f X …X =Z.

m 1 n

⎨x/Ax⎬

Si osservi che è dunque un termine nel quale occorrono le uniche variabili y .

i

In definitiva:

Per ogni formula predicativa Ax=A(x,X …,X ) avente la x e le X come uniche variabili libere,

1 n i

⎨x/Ax⎬

NBG,

esiste, in ogni modello di la classe degli insiemi x per i quali Ax è vera.

Definizione di costanti non predicative

.

L’assioma di comprensione permette di definire le costanti non predicative seguenti, per le quali

NBG

sono valide le usuali proprietà, e che individuano in un modello di le corr