Sistemi di Peano
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$.
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$.
Risposte
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?
Per quanto riguarda il teorema di ricorsività, cos’è $X$? Un insieme a capocchia?
"gugo82":
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\).
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.
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.
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.
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$.
Non mi è chiara la notazione dei diagrammi, sulle categorie e l'oggetto iniziale ci sono 
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
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
Gli elementi di un insieme X sono in biiezione con le funzioni dal singleton a X.
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!
Non conoscevo quella notazione per indicare una funzione da un singoletto ad un insieme. Il testo usa semplicemente $1\toX$ senza scrivere l'elemento sopra alla freccia. Sul fatto che $X^1$ è un singoletto ci arrivo. Mi leggo il pdf allegato intanto.
Casomai \(1^X\).
Già. Per quello che ho scritto io ci sono $|X|$ funzioni.
Se possiamo chiamare successioni le composte $t \circ u$ e $u \ circ s$ allora quel che si vuole dire è che le due successioni sono identiche se e solo se la funzione $u$ è unica, dico male? Gli insiemi sono sempre sottoinsiemi di $\mathbb{N}$?
Rileggi la mia risposta: la richiesta che esista un morfismo in \(\sf Dyn\) da \(\bf N\) a \(\bf X\) equivale alla richiesta che esista una funzione \(u\ : \mathbb N \to X\) tale che
\[
\begin{CD}
1 @>0>> \mathbb N @>\text{s}>> \mathbb N \\
@| @VuVV @VVuV\\
1 @>>x> X @>>t> X
\end{CD}
\] questa condizione dice che, se \(u\) esiste, è unica, perché è definita ricorsivamente mediante $t$: se deve succedere che \(u(\text{s}(n)=t(u(n))\), allora \(u_{n+1} = t(u_n)\), considerando \(u\) come una successione \(\{u_n\}_{n\in\mathbb N}\) di elementi di \(X\). E' allora sufficiente specificare il valore \(u_0\) per avere che
\[
\begin{cases}
u_1 = t(u_0) \\
u_2 = t(u_1) = t(t(u_0))\\
u_3 = t(t(t(u_0)))\\
\vdots
\end{cases}
\]
\[
\begin{CD}
1 @>0>> \mathbb N @>\text{s}>> \mathbb N \\
@| @VuVV @VVuV\\
1 @>>x> X @>>t> X
\end{CD}
\] questa condizione dice che, se \(u\) esiste, è unica, perché è definita ricorsivamente mediante $t$: se deve succedere che \(u(\text{s}(n)=t(u(n))\), allora \(u_{n+1} = t(u_n)\), considerando \(u\) come una successione \(\{u_n\}_{n\in\mathbb N}\) di elementi di \(X\). E' allora sufficiente specificare il valore \(u_0\) per avere che
\[
\begin{cases}
u_1 = t(u_0) \\
u_2 = t(u_1) = t(t(u_0))\\
u_3 = t(t(t(u_0)))\\
\vdots
\end{cases}
\]
Ho trovato questa riformulazione meno rigorosa http://science.unitn.it/~luminat/didatt ... one/html/e dovrebbe essere più chiara
Non ho capito cosa non ti è chiaro.
È chiaro l'enunciato ma non cosa significa e quali conseguenze porta. Per esempio, il Teorema di Densità dice che scelti due elementi r,s di R esiste sempre un elemento q di R tale che r < q < s (chiaramente con r < s). Grazie a questo teorema posso dire che fissato a in R esiste sempre b > a appartenente ad R. Per il teorema di Ricorsione? Sarà che, nonostante me la cavi in informatica, la ricorsione non mi è mai entrata in testa.
Significa proprio quel che intendi dimostrare: ogni funzione \(f : X\to X\), quando sia dato un elemento \(x\in X\) determina univocamente un "sistema dinamico"
\[
\{ f^n(x) \mid n \in \mathbb N\}
\] dato dalle iterate di \(f\) su $x$.
Che cosa c'entri questo col fatto che \(\mathbb R\) è un ordine denso, poi, lo sai solo tu.
\[
\{ f^n(x) \mid n \in \mathbb N\}
\] dato dalle iterate di \(f\) su $x$.
Che cosa c'entri questo col fatto che \(\mathbb R\) è un ordine denso, poi, lo sai solo tu.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo