Numeri naturali

Assiomi di Peano

1. 0 $\in \mathbb{N}$ detto zero.
2. $\exists succ:\mathbb{N}\to \mathbb{N}$ tale che sia iniettiva.
3. $succ(n)\subset \mathbb{N}\mathrm{\setminus }\{0\})$ ovvero $\mathrm{\forall }n\in \mathbb{N},succ(n)\ne 0$

Assioma di induzione

Sia $A$ un sottoinsieme di $\mathbb{N}$. Supponiamo che:

1. 0 $\in A$ (base dell'induzione)
2. $\mathrm{\forall }n\in \mathbb{N}:(n\in A⟹succ(n)\in A)$ ovvero se n $\in A$ allora anche $succ(n)\in A$ ($\underset{―}{passoinduttivo}$).
   Allora $A=\mathbb{N}$

Proposizione 2.9

$\mathrm{\forall }m\in \mathbb{N}\mathrm{\setminus }\{0\}$, esiste unico $n\in \mathbb{N}$ t.c. $succ(n)=m$.

Dimostrazione

Se n esiste allora è unico, infatti se $n^{\prime }\in \mathbb{N}$ avesse la stessa proprietà allora:
$succ(n)=m=succ(n^{\prime })$
Grazie all'iniettività assunta dall'assioma (2.), $n=n^{\prime }$
Supponiamo per assurdo che non sia vero, ossia che esista un $m\ne 0$ che non abbia predecessori, ovvero
$succ(n)\ne m,\mathrm{\forall }n\in \mathbb{N}$
Definiamo quindi $A:=\mathbb{N}\mathrm{\setminus }\{m\}$.
Poichè $m\ne 0$ e $A=\mathbb{N}\mathrm{\setminus }\{m\}$, $0\in A$.
Sia $n\in A$. Osserviamo che $succ(n)\ne m⟹succ(n)\in A$. Grazie quindi all'assioma di induzione applicato ad $A$, si ha che $A=\mathbb{N}$. Ma questo è assurdo perchè $A=\mathbb{N}\mathrm{\setminus }\{m\}$.

Corollario 2.9

$\mathbb{N}$ e $\mathbb{N}\mathrm{\setminus }\{0\}$ sono equipotenti, ovvero esiste una bigezione fa $\mathbb{N}$ in $\mathbb{N}\mathrm{\setminus }\{0\}$.

Dimostrazione

Definiamo

Osserviamo che

• $f(\mathbb{N})=succ(\mathbb{N})\subset \mathbb{N}\mathrm{\setminus }\{0\}$
• Prop. 2.9 $⟹f(\mathbb{N})=\mathbb{N}\setminus \{0\}$
  $f$ è surgettiva
• $f$ è iniettiva grazie all'assioma 2.6