Sistemi di Peano

[universo]

Un saluto e buone vacanze a tutti! Oggi vi chiedo una mano sui sistemi di Peano e sulla ricorsività.
L'insieme $\mathbb{N}$ soddisfa le seguenti proprietà:
(P1) $\emptyset \in \mathbb{N}$;
(P2) $ \forall n \in \mathbb{N}, n \in \mathbb{N} \implies \sigma(n) \in \mathbb{N}$;
(P3) $ \forall n \in \mathbb{N}, \sigma(n) \ne \emptyset$;
(P4) $ \forall n \in \mathbb{N}, \sigma(n) = \sigma(m) \implies n = m$;
(P5) $S \subseteq \mathbb{N}$ tale che $(\emptyset \in S \wedge \forall n \in S \implies \sigma(n) \in S) \implies S = \mathbb{N}$.

Queste sono le premesse, ora vengono le perplessità banali che mi sono annotato:

- una terna $(E, s, e)$, dove $E$ è un insieme con un elemento $e \in E$ ed una funzione successore $s: E \to E$ soddisfa gli assiomi P1 e P2. In che modo viene soddisfatto P1? In una terna siffatta non mi sembra che $\emptyset$ debba appartenere necessariamente ad $E$. Se $E$ non è apodittico allora può darsi il caso in cui P2 è verificato mentre P1 non lo è;

- una terna $(E, s, e)$ che soddisfa gli assiomi P3 e P4 è una terna costituita da un insieme $E$ con $e \in E$ e la funzione iniettiva $s: E \to E$ tale che $e \notin s(E)$, dunque $s$ non è suriettiva. Però se $e \notin s(E)$ allora $e$ non è il successore di nessun elemento di E e dunque $e = \emptyset$ oppure $e \in s(E)$.

- infine non mi è chiaro l'enunciato del Teorema di Ricorsività che nel testo di riferimento è dato così: Sia $(N, s, e)$ un sistema di Peano (ossia soddisfa gli assiomi P3, P4 e P5). Per ogni funzione $t: X \to X$ e $x \in X$ esiste un'unica funzione $f: N \to X$ tale che $f(e) = x$ e $f(s(n)) = t(f(n)) \forall n \in N$.

[gugo82]

Semplicemente, $e$ è lo “zero” di $E$, come $0$ è lo “zero” di $NN$.

Per quanto riguarda il teorema di ricorsività, cos’è $X$? Un insieme a capocchia?

[caulacau]

Per quanto riguarda il teorema di ricorsività, cos’è $X$? Un insieme a capocchia?

Sì, è un qualsiasi insieme; quella è la proprietà universale di \(\mathbb N\) come oggetto dei numeri naturali, essere l'algebra iniziale dell'endofuntore \(X\mapsto X \sqcup 1\).

[universo]

Grazie per il chiarimento. Per quanto riguarda $e$ allora avevo ragione nel pensare che è, perdonatemi l'espressione impropria, "il primo" elemento della successione in $E$; dovevo solo generalizzare la questione.
Riguardo al Teorema della Ricorsività direi di sì, X è un insieme qualunque visto che il libro non specifica nulla.

@caulacau: sono argomenti di cui mi dovrei occupare? non ci sono nel testo.

[caulacau]

Beh, no, ma se vuoi ti dico di più. Grosso modo l'idea è che i numeri naturali sono l'esempio universale di insieme con una funzione definita induttivamente.

[caulacau]

Sia $(N, s, e)$ un sistema di Peano (ossia soddisfa gli assiomi P3, P4 e P5). Per ogni funzione $t: X \to X$ e $x \in X$ esiste un'unica funzione $f: N \to X$ tale che $f(e) = x$ e $f(s(n)) = t(f(n)) \forall n \in N$.

Questo significa grosso modo quanto segue.

1. Esiste una categoria \(\sf Dyn\) i cui oggetti sono le terne \((X,t : X \to X, x\in X)\), ovvero i diagrammi della torma
\[
\begin{CD}
1 @>x>> X @>t>> X
\end{CD}
\] e i morfismi tra \((X,t,x)\) e \((Y,g,y)\) consistono delle funzioni $u : X \to Y$ tali che $u(x)=y$ e $u\circ t=g\circ u$.

2. \(\mathbf{N}=(\text{s} : \mathbb N \to \mathbb N, 0\in \mathbb N)\) è un oggetto di questa categoria.

3. Per ogni oggetto \(\mathbf{X} = (X,t,x)\) di \(\sf Dyn\) esiste un morfismo \(u : \mathbf N \to\mathbf X\) in \(\sf Dyn\) tale che[1]
\[
\begin{CD}
1 @>0>> \mathbb N @>\text{s}>> \mathbb N \\
@| @VuVV @VVuV\\
1 @>>x> X @>>t> X
\end{CD}
\] e tale $u$ è unico con questa proprietà[2]; ciò significa esattamente che \((\mathbb N, \text{s}, 0)\) è l'oggetto iniziale di \(\sf Dyn\).

[1] Questo significa che dato \(u_0=x\) e un endomorfismo di $X$, esiste un unico modo di definire per ricorsione una successione di \(u_n\) ponendo
\[
\begin{cases}
u_0 = x \\
u_{n+1} = t(u_n)
\end{cases}
\]
[2] Se esiste una $v : \mathbb N \to X$ con la stessa proprietà, deve essere definita dalla stessa ricorsione usando $t$, quindi $u=v$.

[universo]

Non mi è chiara la notazione dei diagrammi, sulle categorie e l'oggetto iniziale ci sono

[universo]

Non mi è chiara la notazione dei diagrammi, sulle categorie e l'oggetto iniziale ci sono Cioè, se $x$ non è una funzione che significato ha quando viene riportato sopra alla freccia come nei diagrammi di cui sopra? Si potrebbe avere un esempio?
Capisco che sia difficile darmi una mano

[caulacau]

Gli elementi di un insieme X sono in biiezione con le funzioni dal singleton a X.

[Indrjo Dedej]

Pensa a \(1\) come l'insieme che contine esattamente un elemento. Quale? Non importa (perché?). Quello che importa è vedere una qualisiasi funzione \[x \colon 1 \to A\] come l'appartenenza di \(x\) ad \(A\). Se ci pensi bene non è un cosa così assurda. click!