Assiomi di Peano

Presa una terna $(\mathbb N_0,f,0)$, $f: \mathbb N_0 \rightarrow \mathbb N_0$ tale che:

• $0 \notin f(\mathbb N_0)$

• $f$ è iniettiva

• se $X \subseteq \mathbb N_0$ è tale che

  • $0 \in \mathbb N_0$
  • da $s \in X \Rightarrow f(s) \in X$

  allora $X = \mathbb N_0$

Successore

$f$ è detta funzione successore: $1 = f(0), 2 = f(f(0)), .., n = f(f..(f(0))))$ n volte, $n+1 = f(n)$

Principio di induzione (seconda forma)

Dato $X \subseteq \mathbb N_0$ tale che:

• $\overline{n} \in X$
• dato $t > \overline{n}$ se $k \in X,\forall \overline{n} \le k < t$ implica $t \in X$

allora $n \in X ,\forall n \ge \overline{n}$

Applicazioni del principio di induzione

Algoritmo della divisione euclidea in $\mathbb N_0$

Sia $b \in \mathbb N$, allora $\forall n \in \mathbb N_0$ esistono unici $q,r \in \mathbb N$ tali che $n = qb + r$ con $r<b$

I numeri $q$ e $r$ sono detti rispettivamente il quoziente e il resto della divisione di $n$ per $b$

Teorema fondamentale dell’aritmetica

Per ogni $n \ge 2, n \in \mathbb N$ esistono $t \in \mathbb N$ e $p_1,..,p_t$ numeri primi tali che $n=p_1 \cdot .. \cdot p_t$

La decomposizione è unica a meno dell’ordine dei fattori

Teorema di Euclide