3.8 Numeri naturali in ZF[246]

In questa sezione costruiremo un modello dei numeri naturali all’interno della teoria ZF degli insiemi; questo modello soddisfa gli assiomi di Peano 132 e ha un ordinamento che soddisfa 143, dunque questo modello gode di tutte le proprietà elencate in Sez. 4; per questo motivo in questa sezione approfondiremo solo le proprietà specifiche di questo modello.

Successore

Definizione 83

[24X]Dato \(x\) si definisce il successore come

\begin{equation} S(x) {\stackrel{.}{=}}x ∪ \{ x\} \quad . \label{eq:successore} \end{equation}
84

Spesso scriveremo \(Sx\) invece di \(S(x)\) per semplicità.

Diciamo che un insieme \(A\) è S-saturo se \(∅∈ A\) e se per ogni \(x∈ A\) si ha \(S(x)∈ A\). 1

E84

[24V]Notate che \(z∈ S(x)\) se e solo se \(z∈ x∨ z=x\);

E84

[24M]Prerequisiti:13,1.Dimostrate che \(x∈ S(x)\) e \(x\varsubsetneq S(x)\). Soluzione nascosta: [UNACCESSIBLE UUID ’24N’]

E84

[239]Prerequisiti:13,84,1.Siano \(x,y\) elementi (qualunque, non necessariamente numeri naturali), tali che

\begin{equation} x⊆ y⊆ S(x) \label{eq:x_ y_ Sx} \end{equation}
85

si mostri che allora

\[ x=y∨ y = S(x)\quad ; \]

dove le due condizioni precedenti sono mutualmente esclusive, e (nell’ipotesi ?? precedente) la seconda vale se e solo se \(x\in y\); riassumendo

\[ \ref{eq:x_ y_ Sx} ⇒ (x=y\iff y ≠ S(x)\iff x∉ y )\quad . \]

Notate l’analogia con 2.

E84

[245]Si mostri che la intersezione di insiemi S-saturi è un insieme S-saturo.

E84

[1YM]Prerequisiti:13,84,1. 2 Mostrate che

\[ x=y \iff S(x) = S(y) \quad . \]

In particolare questo dimostra che, se \(A\) è un insieme S-saturo, allora è ben definita la funzione \(S:A→ A\), il cui grafico è la relazione

\[ \{ (x,y)∈ A^ 2 : y=S(x) \} \quad ; \]

inoltre \(S\) è iniettiva.

Soluzione nascosta: [UNACCESSIBLE UUID ’1YN’]

E84

[24Q]Trovate un esempio di \(x,y\) tali che \(x∈ y∧ x⊆ y\) ma \(S(x)∉ S(y)\)

Soluzione nascosta: [UNACCESSIBLE UUID ’24R’]

E84

[24S]Mostrate che se \(x∈ y∧ x⊆ y\) allora \(S(x)⊆ y\). Soluzione nascosta: [UNACCESSIBLE UUID ’24T’]

Numeri naturali in ZF

Definizione 86

[243] L’assioma dell’infinito garantisce che esiste un insieme \(A\) che è S-saturo.

Usando l’assioma dell’infinito 86 si può mostrare la esistenza dell’insieme dei numeri naturali.

Teorema 87

[244]\(ℕ\) è il più piccolo insieme S-saturo.

Prova ▼

Dato un insieme \(A\) che sia S-saturo, si definisce \(ℕ_ A\) come l’intersezioni di tutti i sottoinsiemi S-saturi di \(A\). Per 4, \(ℕ_ A\) è S-saturo. Dati due insieme \(A,B\) che siano S-saturi, si mostra che \(ℕ_ A=ℕ_ B\): si indica dunque con \(ℕ\) questo insieme. In particolare, dato un insieme \(A\) che sia S-saturo, si ha \(ℕ\subseteq A\).

Esempio 88

[291]In questo modello il primo numero naturale è \(0\) ed è identificato con \(∅\). Poi

\begin{align*} 1& = 0 ∪ \{ 0\} = \{ 0\} = \big\{ \{ \} \big\} ,\\ 2& = 1 ∪ \{ 1\} = \{ 0, 1\} = \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} ,\\ 3& = 2 ∪ \{ 2\} = \{ 0, 1, 2\} = \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} \bigg\} ,\\ .... \end{align*}

Nota 89

[25C]Vale questo risultato

\[ ∀ y∈ℕ, y≠ ∅⇒ ∃ x∈ℕ , S(x)=y \]

questo può essere dimostrato per induzione, come in 131, o mostrando che se

\[ ∃ y∈ℕ, y≠ ∅∧ ∀ x∈ℕ , S(x)≠ y \]

allora \(ℕ ⧵ \{ y\} \) sarebbe un insieme S-saturo più piccolo di \(ℕ\), una contraddizione. In particolare da 5 si ottiene che la funzione successore

\[ S:ℕ → ℕ⧵\{ 0\} \]

è bigettiva.

Se \(n\neq 0\) chiameremo \(S^{-1}(n)\) il predecessore di \(n\).

Possiamo anche dimostrare direttamente il principio di induzione.

Teorema 90 Principio di induzione

[23B] Sia \(A⊇ ℕ\) e \(P(n)\) una proposizione logica che possa essere valutata per \(n∈ A\). Supponiamo siano soddisfatte le due seguenti ipotesi:

  • \(P(n)\) è vera per \(n=0\) e

  • \(∀ n∈ ℕ, P(n)⇒ P(S(n))\) ;

allora \(P\) è vera per ogni \(n∈ ℕ\).
La prima ipotesi è nota come “base dell’induzione” e la seconda come “passo induttivo”

Prova ▼

Sia \(U=\{ n∈ ℕ:P(n)\} \) sappiamo che \(0∈ U\) e che \(∀ x, x ∈ U⇒ S(x)∈ U\), così \(U\) è S-saturo e \(U\subseteq N\) si conclude \(U=\mathbb {N}\).

Teorema 91

[24D] Consideriamo la relazione d’ordine \(⊆ \) su \(ℕ\); allora

\begin{equation} ∀ x,y ∈ ℕ , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y ) \quad . \label{eq:subseteq_ caratt_ le_ N} \end{equation}
92

Questo sarà dimostrato nell’Esercizio 4.

Per dimostrare il teorema precedente si possono usare gli esercizi nella prossima sezione.

Nota 93

[26K]Questo modello di \(ℕ\) soddisfa gli Assiomi di Peano; inoltre la relazione d’ordine soddisfa i principi richiesti in Ipotesi 143; dunque questo modello di \(ℕ\) gode di tutte le proprietà presentate in Sez. 4: le diverse versioni del principio di induzione; \((ℕ,⊆)\) è bene ordinato; le definizioni per ricorsione; l’aritmetica; ecc.

Quando vorremo confrontare questo modello con altri modelli, lo indicheremo con \(ℕ_\text {ZF}\).

Le proprietà dell’insieme ordinato \(ℕ,⊆\) sono dunque queste.

Proposizione 94

[26J]Questo modello di \(ℕ\) è un insieme bene ordinato dall’ordinamento

\[ n≤ m \iff n⊆ m\quad . \]

Inoltre in questo modello si ha

\begin{equation} ∀ n,m∈ ℕ, n ∈ m \iff (n ⊆ m ∧ n≠ m)\quad . \label{eq:n_ in_ m_ iff} \end{equation}
95

dunque, definendo (come usuale)

\[ n{\lt}m ≐ (n≤ m ∧ n≠ m) \]

possiamo scrivere

\[ n∈ m \iff n{\lt}m\quad . \]

Questo è dimostrato negli esercizi successivi, e in particolare in 1.

Per approfondimenti si veda negli appunti del corso (Cap. 1 Sez. 7 in [ 3 ] ); o anche in [ 14 ] , [ 13 ] .

Insiemi transitivi

Definizione 96

[24Z] Un insieme \(A\) si dice transitivo se valgono queste condizione equivalenti:

  • \[ ∀ x, x ∈ A ⇒ x⊆ A\quad , \]

    cioè ogni elemento di \(A\) è anche un sottoinsieme di \(A\);

  • \[ ∀ x,y, x ∈y ∧ y∈ A ⇒ x∈ A\quad . \]

Esempio 97

[290]Esempi di insiemi transitivi sono:

\begin{align*} \{ \} = 0 \\ \big\{ \{ \} \big\} = 1, \\ \Big\{ \{ \} ,\big\{ \{ \} \big\} \Big\} = 2,\\ \bigg\{ \{ \} ,\big\{ \{ \} \big\} ,\Big\{ \big\{ \{ \} \big\} \Big\} \bigg\} , \\ \Bigg\{ \{ \} ,\big\{ \{ \} \big\} ,\Big\{ \big\{ \{ \} \big\} \Big\} , \bigg\{ \Big\{ \big\{ \{ \} \big\} \Big\} \bigg\} \Bigg\} ,\\ ...\\ \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} \bigg\} =3\\ \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \big\{ \{ \} \big\} \Big\} ,\Big\{ \{ \} ,\big\{ \{ \} \big\} \Big\} \bigg\} ,\\ .... \end{align*}

Confrontando con 88 notate che vi sono insiemi transitivi che non sono numeri naturali.

E97

[25J]Se ogni elemento di \(A\) è un insieme transitivo, allora \(x ∈y\) è una relazione transitiva in \(A\) . (Notate che questo vale anche quando \(A\) non è un insieme transitivo). Soluzione nascosta: [UNACCESSIBLE UUID ’25K’]

E97

[257]Dimostrate che per ogni \(m ∈ ℕ\), \(m\) è un insieme transitivo.

Soluzione nascosta: [UNACCESSIBLE UUID ’258’]

E97

[26N]Prerequisiti:96,7,2.

\(∀ n,k∈ℕ\) se \(n∈ k\) allora \(Sn⊆ k\).

(Sugg: si può dimostrare senza induzione, usate il fatto che ciascun \(n∈ℕ\) è un insieme transitivo).

E97

[26P]Prerequisiti:3,13.Per concludere il Teorema 91 dobbiamo dimostrare

\begin{equation} ∀ x,y ∈ ℕ , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y )\quad . \tag {\ref{eq:subseteq_ caratt_ le_ N}}\end{equation}
98

Dimostrate che se \(X\) è un insieme in cui ogni elemento è transitivo allora

\begin{equation} ∀ x,y ∈ X , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y ) \quad . \label{eq:caratt_ le_ ordinale} \end{equation}
99

Soluzione nascosta: [UNACCESSIBLE UUID ’26Q’]

Gli esercizi precendenti dimostrano il Teorema 91, dopodiché dai risultati in Sez. 4 otteniamo che \((ℕ,≤)\) è bene ordinato.

A seguire altri interessanti esercizi.

E99

[269]Sappiamo da 93 che la relazione \(n ⊆ m\) è totale in \(ℕ\). Dimostrate che

\begin{equation} ∀ n,m∈ ℕ, n ∈ m \iff (n ⊆ m ∧ n≠ m)\quad . \tag {\ref{eq:n_ in_ m_ iff}}\label{eq:n_ in_ m_ iff_ 2} \end{equation}
100

Per 4 questo implica

\[ ∀ n,m∈ ℕ, n ⊆ m \iff (n ∈ m \lor n= m)\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’26B’]

E99

[265]Mostrate questa affermazione

\[ ∀ k∈ ℕ, k≠ ∅⇒ ∅∈ k\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’266’]

E99

[25D]Prerequisiti:91,94.Dimostrate che

\[ ∀ x,y∈ ℕ~ ,~ x⊆ y~ ∧ ~ x≠ y ⇒ Sx⊆ y\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’279’]

[UNACCESSIBLE UUID ’25F’]

[25W]Fissato \(N\in ℕ\), consideriamo la relazione d’ordine \(n⊆ m\) per \(n,m\in N\). Dato che \(N\subseteq ℕ\) è bene ordinato, allora la Proposizione 94 implica che \((N,\subseteq )\) è bene ordinato; cionondimeno provate a dimostrare direttamente per induzione che \(n⊆ m\) è un buon ordinamento in \(N\).

Soluzione nascosta: [UNACCESSIBLE UUID ’25X’] [25Z]Dimostrate che

\[ \underline⋃ ℕ = ℕ\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’260’]

Ordinali

Sfruttando i risultati precedenti, possiamo dare qualche cenno della teoria degli ordinali.

Definizione 101

Un ordinale (secondo Von Neumann) è un insieme transitivo \(A\) tale che ogni suo elemento è un insieme transitivo.

E101

[25Q]Prerequisiti:13,3.Se \(A\) è un insieme dove \(∈\) è transitiva, definiamo

\[ x≤ y ≐ x∈ y∨ x=y \]

si mostri che \(x≤ y\) è una relazione d’ordine in \(A\) (possibilmente parziale).

Soluzione nascosta: [UNACCESSIBLE UUID ’25S’]

E101

[25B]Dimostrate che l’intersezione di insiemi transitivi è un insieme transitivo.

E101

[25N]Dimostrate che l’intersezione di ordinali è un ordinale.

E101

[25M]Dimostrate che se \(X\) è un ordinale e \(A\in X\) allora \(A\) è un ordinale.

Soluzione nascosta: [UNACCESSIBLE UUID ’25P’]

E101

[25G] Usate l’assioma di buona fondazione 13 per mostrare che se \(A\) è transitivo e \(A≠ ∅\) allora \(∅∈ A\).

Soluzione nascosta: [UNACCESSIBLE UUID ’25H’]

E101

[255]Dimostrare che \(ℕ\) è un insieme transitivo. (Sugg.: usare l’induzione).

Soluzione nascosta: [UNACCESSIBLE UUID ’256’]

Questo e 2 ci dicono che \(ℕ\) è un ordinale.

E101

[26S]Sia \(X\) un ordinale e

\[ P_ x =\{ z\in X, z\in x\} \]

mostrate che

\[ ∀ x,y∈ X~ ,~ P_ x = P_ y ⇒ x=y\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’26T’]

(Notate la somiglianza con 2).

E101

[26V]Prerequisiti:1,13,11,4,7.

Sia \(X\) un ordinale, definiamo

\[ x≤ y ≐ x∈ y∨ x=y \]

sappiamo da 1 che \(x≤ y\) è una relazione d’ordine in \(X\) (possibilmente parziale). Si mostri che \(x≤ y\) è un buon ordinamento.

Soluzione nascosta: [UNACCESSIBLE UUID ’26W’]

Nota 102

[275]Consideriamo di nuovo la proposizione 94 che afferma che \(ℕ_\text {ZF}\) è ben ordinato dalla relazione \(⊆\).

Sappiamo da 6 e 2 che \(ℕ_\text {ZF}\) è un ordinale; potremmo essere tentati di vedere la proposizione 94 come corollario del risultato precedente 8.

Questo purtroppo non è un modo ben posto per dimostrare questo risultato, a causa di questa cascata di dipendenze:

  • la dimostrazione di 8 si basa sul risultato 11

  • il risultato 11 a sua volta necessita di una definizione per ricorrenza di una funzione: questo è il Teorema 134

  • la dimostrazione del Teorema 134 usa il fatto che il principio di induzione vale in \(ℕ\).

Quindi dobbiamo prima dimostrare le proprietà di \(ℕ_\text {ZF}\) in modo indipendente della teoria degli ordinali, e quindi dimostrare i risultati in Sec. 4, e quindi alla fine possiamo dimostrare il risultato 8, che afferma che ogni ordinale è ben ordinato dalla relazione \(⊆\).

(da sistemare)

  1. In [ 14 ] un tale insieme viene definito “inductive”.
  2. Proposizione 1.7.4 punto 5 in [ 3 ] .