Teoria degli insiemi ed aritmetica

Teoria degli insiemi ed aritmetica

NBG

Antonio Maida

Alfabeto ed assioma di estensionabilità ∈

NBG, teoria degli insiemi.

Il sistema formale della NBG ha una sola costante primitiva denotante l’appartenenza. Le variabili di NBG si indicheranno con lettere maiuscole. Le formule del tipo X∈Y sono le uniche formule atomiche di NBG. Gli individui in un qualunque modello di NBG 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.

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

Proprietà logiche

(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

L’AxE è il primo assioma proprio di NBG 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).

Variabili ristrette ad insiemi

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.

Assioma di comprensione e conseguenze

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

(AxC): NBG.

È il secondo proprio di NBG. 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 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 NBG, la classe degli insiemi x per i quali Ax è vera.

Definizione di costanti non predicative

.