algebra induttiva

Un’algebra $(A,\gamma )$ si dice induttiva quando:

1. Tutte le $\gamma$ sono iniettive.
2. Tutte le $\gamma$ hanno immagini disgiunte.
3. $\forall S\subseteq AS\text{eˋ chiuso rispetto a tutte le}{\gamma }_i⟹S=A$.

Le operazioni $\gamma$ si chiamano costruttori dell’algebra induttiva.

• morfismi tra algebre
• algebra induttiva degli alberi binari (finiti)

Esempio dell’algebra induttiva dei numeri naturali

Rappresentazione (di Von Neumann) dei numeri naturali

$$\begin{array}{c}\varnothing =\{\}\\ 1=\{\varnothing \}=\{\{\}\}\\ 2=\{\varnothing ,1\}=\{\{\},\{\{\}\}\}\\ \dots \end{array}$$

La funzione per generare il successore di $n$ è $\text{succ}(n)=n\cup \{n\}$, perciò $n\in \text{succ}(n)$.

Struttura dei numeri naturali

È definita tramite i quattro assiomi di Peano del primo ordine:

1. $\varnothing \in \mathbb{N}$
2. $\forall nn\in \mathbb{N}⟹\text{succ}(n)\in \mathbb{N}$
3. $\nexists n\varnothing =\text{succ}(n)$
4. $\forall n,m\text{succ}(n)=\text{succ}(m)⟹n=m$

Ma non bastano, ad esempio, un insieme di “numeri naturali” tale che $a\to b\to c,d\to e,e\to d$ li rispetta, ma questi non sono i veri numeri naturali.

Serve un quinto assioma, del secondo ordine, che garantisce la chiusura di $\text{succ}$ su $\mathbb{N}$:

$$\forall S\subseteq \mathbb{N}(\varnothing \in S\wedge (n\in S⟹\text{succ}(n)\in S))⟹S=\mathbb{N}$$

Praticamente, nell’esempio $a\to b\to c,d\to e,e\to d$ c’era della “spazzatura”, cioè $d\to e,e\to d$. La particolarità di $e$ e $d$ è che non discendono da 0 (l’insieme vuoto). Il quinto assioma definisce i numeri naturali come una singola catena di elementi dall’elemento 0 in poi.

Abbiamo visto che la rappresentazione di un’algebra induttiva non è sufficiente a definirne la sua struttura.

Il quinto assioma di Peano è l’induzione

$$\forall S\subseteq \mathbb{N}(\varnothing \in S\wedge (n\in S⟹\text{succ}(n)\in S))⟹S=\mathbb{N}$$

Definiamo $n\in \mathbb{N}$ come $P(n)$, cioè $n$ rispetta la proprietà $P$ (essere un numero naturale).

• $(\varnothing \in S)=P(0)$
• $(n\in S)=P(n)$
• $(\text{succ}(n)\in S)=P(n+1)$
• $(S=\mathbb{N})=\forall nP(n)$

$$(P(0)\wedge (P(n)⟹P(n+1))⟹\forall nP(n)$$

Quindi l’assioma equivale alla regola di inferenza:

$$\frac{P(0)P(n)⟹P(n+1)}{\forall nP(n)}$$

Cioè l’induzione.

Perché gli assiomi di Peano sono necessari?

Cosa succede se si toglie il terzo assioma? (Elemento minimo)

Sarebbe impossibile dimostrare induttivamente una proprietà per tutti gli elementi dell’insieme.

Cosa succede se si toglie il quarto assioma? (Iniettività di $\text{succ}(n)$)

Consideriamo un’algebra su $\{0,1\}$ dove $\text{succ}(0)=1$, $\text{succ}(1)=1$, $\text{not}(\text{true})=\text{false}$, $\text{not}(\text{false})=\text{true}$.

Definiamo una funzione $\text{is-even}$ per casi:

$$\{\begin{array}{l}\text{is-even}(0)=\text{true}\\ \text{is-even}(\text{succ}(n))=\text{not}(\text{is-even}(n))\end{array}$$

Si può dimostrare che $\text{true}=\text{false}$, quindi questa matematica non è valida.

Cosa succede se si toglie il quinto assioma? (Induzione)

Non si riesce a fare definizioni induttive:

$$\{\begin{array}{l}\text{fact}(0)=1\\ \text{fact}(\text{succ}(n))=\text{fact}(n)\cdot \text{succ}(n)\end{array}$$

Inoltre ovviamente non si potrebbero fare definizioni per induzione.

Ad esempio in un insieme $\mathbb{N}$ fatto così

$$\mathbb{N}=\left\{\begin{array}{c}0\\ \text{succ}(0)\\ \text{succ}(\text{succ}(0))\\ \text{succ}(\text{succ}(\text{succ}(0)))\\ \dots \end{array}\right\}\cup \{♡,\text{con}\text{succ}(♡)=♡\}$$

Applicando l’induzione si potrebbe dimostrare che $♡\ne ♡$. Questo succede perché $♡$ non è “raggiungibile” da $0$ attraverso una catena di induzione, visto che è scollegato dagli altri elementi. Ciò significa che l’insieme $\mathbb{N}$ così definito contiene due sottoalgebre proprie, quella generata da $0$ e $\text{succ}$ e quella in $\{♡\}$.

Ciò non deve succedere nell’insieme $\mathbb{N}$ induttivo che conosciamo.

Come gli assiomi di Peano dei numeri naturali rispettano la definizione astratta di algebra

• $0$ può essere definita la funzione che va da qualsiasi insieme $1$ (insieme con un solo elemento) al numero natrurale minimo.
• $\text{succ}$ è l’altra funzione che “genera” gli altri numeri partendo dal numero naturale minimo.

$O(z)=\text{zero},z\in 1,\text{succ}(\text{zero})\in \mathbb{N}$ e $\text{succ}(n)=m,n,m\in \mathbb{N},n,m\ne \text{zero},\text{zero}\in \mathbb{N}$ hanno immagini disgiunte, sono iniettive, e $\mathbb{N}$ è chiuso rispetto a entrambe, quindi $(\mathbb{N},\{0,\text{succ}\})$ è un’algebra induttiva.