Domanda di Logica
Ciao!
Sto studiando l'aritmetica di Peano sul Lolli. Prima di arrivarci ho fatto la definizione di funzione successore, la teoria del successore, dimostrando che è completa, definito la definibilità in essa...
C'è un Lemma che dice che gli unici sottoinsiemi di N definibili nella teoria del successore sono i finiti o i cofiniti (cioè quelli il cui complementare è un insieme finito). Grazie a questo lemma si vede che non è definibile l'addizione. Infatti se A[x,y,z] stesse per x+y=z si avrebbe che $\exists$x A[x,x,z] definirebbe l'insieme dei pari che è infinito e coinfinito.
Poi dice che allo stesso modo non è definibile una relazione d'ordine <.
Però non fa vedere perchè. Qualcuno mi dà una mano?
Grazie!!
Paola
Sto studiando l'aritmetica di Peano sul Lolli. Prima di arrivarci ho fatto la definizione di funzione successore, la teoria del successore, dimostrando che è completa, definito la definibilità in essa...
C'è un Lemma che dice che gli unici sottoinsiemi di N definibili nella teoria del successore sono i finiti o i cofiniti (cioè quelli il cui complementare è un insieme finito). Grazie a questo lemma si vede che non è definibile l'addizione. Infatti se A[x,y,z] stesse per x+y=z si avrebbe che $\exists$x A[x,x,z] definirebbe l'insieme dei pari che è infinito e coinfinito.
Poi dice che allo stesso modo non è definibile una relazione d'ordine <.
Però non fa vedere perchè. Qualcuno mi dà una mano?
Grazie!!
Paola
Risposte
Io farei così.
Probabilmente Lolli avrà dimostrato l'eliminazione dei quantificatori per la teoria del successore. Dunque ogni formula $F(x,y)$ si può scrivere nella forma $(A_1\wedge ...\wedge A_n)\vee...vee (B_1\wedge...\wedge B_m)$ dove le $A_i$ e $B_i$ sono atomiche o negazioni di atomiche e contengono solo come variabili libere $x$ e $y$.
Se supponessimo per assurdo che la relazione di minore su $NN$ fosse definibile da $F(x,y)$, vedremmo facilmente che, senza perdita di generalita', le $A_1,...,A_n$ dovrebbero, salvo previa eliminazione di formule banali tipo $S^n(0)=S^m(0)$ e di qualche equivalenza banale, essere tutte della forma $\not x=S^n(0)$ o della forma $\not y=S^n(0)$ o della forma $\not x=S^n(y)$ o della forma $\not y=S^n(x)$. Scegliendo numeri $k,j$ sufficientemente grandi e distanziati fra loro, avremmo allora che $F(k,j)$ sarebbe vera e anche $F(j,k)$ sarebbe vera: assurdo.
Probabilmente Lolli avrà dimostrato l'eliminazione dei quantificatori per la teoria del successore. Dunque ogni formula $F(x,y)$ si può scrivere nella forma $(A_1\wedge ...\wedge A_n)\vee...vee (B_1\wedge...\wedge B_m)$ dove le $A_i$ e $B_i$ sono atomiche o negazioni di atomiche e contengono solo come variabili libere $x$ e $y$.
Se supponessimo per assurdo che la relazione di minore su $NN$ fosse definibile da $F(x,y)$, vedremmo facilmente che, senza perdita di generalita', le $A_1,...,A_n$ dovrebbero, salvo previa eliminazione di formule banali tipo $S^n(0)=S^m(0)$ e di qualche equivalenza banale, essere tutte della forma $\not x=S^n(0)$ o della forma $\not y=S^n(0)$ o della forma $\not x=S^n(y)$ o della forma $\not y=S^n(x)$. Scegliendo numeri $k,j$ sufficientemente grandi e distanziati fra loro, avremmo allora che $F(k,j)$ sarebbe vera e anche $F(j,k)$ sarebbe vera: assurdo.
Ha un nome specifico quel lemma che dice gli unici sottoinsiemi definibili in PA sono solo quelli finiti o cofiniti?
PS: ma, fields, tu sfrutti questo lemma nella tua soluzione?
PS: ma, fields, tu sfrutti questo lemma nella tua soluzione?
Non ho usato il lemma (non credo abbia un nome) Però non vorrei avere inventato una teoria che non esiste...
Per teoria del successore, intendo la teoria con i tre assiomi:
$\forall x \not S(x)=0$
$\forall x \forall y S(x)=S(y)\to x=y$
$\forall x \not x=0 \to \exists y S(y)=x$
Io una volta avevo il Lolli, poi me l'hanno fregato, e non ero ancora arrivato al capitolo sulla teoria del successore. In ogni caso le cose che ho detto su questa teoria le ho dimostrate ieri sera, dunque sono giuste. Magari poi le trasformiamo in esercizio.
Per ora aspetto conferme o smentite sulla teoria del successore..
Per teoria del successore, intendo la teoria con i tre assiomi:
$\forall x \not S(x)=0$
$\forall x \forall y S(x)=S(y)\to x=y$
$\forall x \not x=0 \to \exists y S(y)=x$
Io una volta avevo il Lolli, poi me l'hanno fregato, e non ero ancora arrivato al capitolo sulla teoria del successore. In ogni caso le cose che ho detto su questa teoria le ho dimostrate ieri sera, dunque sono giuste. Magari poi le trasformiamo in esercizio.
Per ora aspetto conferme o smentite sulla teoria del successore..
Ok, ci possiamo anche arrivare da soli. La teoria che ho definito è per forza quella che c'è sul Lolli. Infatti la teoria data da i due assiomi:
$\forall x \not S(x)=0$
$\forall x \forall y S(x)=S(y)\to x=y$
non è completa. Dal momento che prime number dice che la teoria del successore è completa, allora quella che ho definito, che è completa, deve essere la stessa di Lolli.
$\forall x \not S(x)=0$
$\forall x \forall y S(x)=S(y)\to x=y$
non è completa. Dal momento che prime number dice che la teoria del successore è completa, allora quella che ho definito, che è completa, deve essere la stessa di Lolli.
Dato il punto in cui ha scritto quell'affermazione, forse c'è un metodo molto simile a quello con cui ha dimostrato che non è definibile l'addizione.
Comunque, come si può dimostrare che nella teoria senza l'ultimo assioma, non ogni formula equivale ad una senza quantificatori?
Comunque, come si può dimostrare che nella teoria senza l'ultimo assioma, non ogni formula equivale ad una senza quantificatori?
Edit: post duplicato
In poche parole suggerisci che, se < fosse definibile nella teoria del successore, allora si potrebbe definire un insieme infinito e coinfinito di numeri naturali? Io ho provato questa strada, ma non ne ho cavato niente. Ho trovato più comodo eliminare i quantificatori.. Di certo non è ovvissimo come definire un insieme infinito e coinfinito usando solo il < e la funzione successore. A questo punto è una questione stuzzicante... Puoi provare a pensarci anche tu, non serve nessuna conoscenza particolare di logica per affrontare questo problema...
Tuttavia eliminando i quantificatori, e con una argomentazione analoga a quella che ho scritto, si ha anche come corollario che i soli insiemi di naturali definibili sono quelli finiti e cofiniti. Per cui il metodo non è che differisca poi molto da quello "ipotetico" suggerito da Lolli (sempre che effettivamente intendesse dare il suggerimento come l'ha interpretato prime number)
Per la seconda domanda, i primi due assiomi non permettono l'eliminazione dei quantificatori, altrimenti la teoria sarebbe completa. Per vedere che essa non è completa basta trovare due suoi modelli che rendano rispettivamente vero e falso il terzo assioma.
Come primo modello prendiamo $NN$, e siamo a posto. Come secondo modello prendiamo $NN$ e in più ci mettiamo dentro una altra catena infinita di elementi del tipo $a_o,a_1,a_2,.....$ in cui ogni $a_i$ è il successore di $a_(i-1)$ e $a_0$ non è successore di nessuno.
Tuttavia eliminando i quantificatori, e con una argomentazione analoga a quella che ho scritto, si ha anche come corollario che i soli insiemi di naturali definibili sono quelli finiti e cofiniti. Per cui il metodo non è che differisca poi molto da quello "ipotetico" suggerito da Lolli (sempre che effettivamente intendesse dare il suggerimento come l'ha interpretato prime number)
Per la seconda domanda, i primi due assiomi non permettono l'eliminazione dei quantificatori, altrimenti la teoria sarebbe completa. Per vedere che essa non è completa basta trovare due suoi modelli che rendano rispettivamente vero e falso il terzo assioma.
Come primo modello prendiamo $NN$, e siamo a posto. Come secondo modello prendiamo $NN$ e in più ci mettiamo dentro una altra catena infinita di elementi del tipo $a_o,a_1,a_2,.....$ in cui ogni $a_i$ è il successore di $a_(i-1)$ e $a_0$ non è successore di nessuno.
Quindi il secondo modello rende falso il terzo assioma perché esiste un $x\ne0$ che non è successore di nessun elemento appartenente al modello, cioè $a_0$?
Io non vedo come si possa definire un sottoinsieme dei naturali infinito e coinfinito usando solo la relazione d'ordine. Si potrebbe tentare di definire ancora i numeri pari, ma come?? L'altro modo per risolvere il mistero è di contattare Lolli in persona
.
Io non vedo come si possa definire un sottoinsieme dei naturali infinito e coinfinito usando solo la relazione d'ordine. Si potrebbe tentare di definire ancora i numeri pari, ma come?? L'altro modo per risolvere il mistero è di contattare Lolli in persona
.
La risposta di Lolli alla mia e-mail: "Non ricordo dove ho scritto il risultato che cita, che tuttavia è
giusto, purché ci si intenda: il linguaggio deve contenere solo il
successore! Allora si ha un risultato di eliminazione dei quantificatori,
da cui ne discendono vari altri, tra i quali che gli unici insiemi
definibili sono solo i finiti e i cofiniti. Se c'è anche l'addizione i
definibili sono quelli eventualmente periodici.
Può vedere per i dettagli in Enderton, A mathematical introduction to
logic, cap. 3.
Cordiali saluti
Gabriele Lolli"
Dunque è proprio come hai detto tu, fields.
giusto, purché ci si intenda: il linguaggio deve contenere solo il
successore! Allora si ha un risultato di eliminazione dei quantificatori,
da cui ne discendono vari altri, tra i quali che gli unici insiemi
definibili sono solo i finiti e i cofiniti. Se c'è anche l'addizione i
definibili sono quelli eventualmente periodici.
Può vedere per i dettagli in Enderton, A mathematical introduction to
logic, cap. 3.
Cordiali saluti
Gabriele Lolli"
Dunque è proprio come hai detto tu, fields
.
"TomSawyer":
Quindi il secondo modello rende falso il terzo assioma perché esiste un $x\ne0$ che non è successore di nessun elemento appartenente al modello, cioè $a_0$?
Esatto.
"TomSawyer":
La risposta di Lolli alla mia e-mail...
Gentile, ha risposto subito e di domenica! Il "A mathematical introduction to logic" lo trovi sul mulo
Il problema è che ora, indicandomi la fonte, mi hai fatto finire il divertimento Forse è meglio, così mi metto a studiare Fisica...
"fields":
[quote="TomSawyer"]Quindi il secondo modello rende falso il terzo assioma perché esiste un $x\ne0$ che non è successore di nessun elemento appartenente al modello, cioè $a_0$?
Esatto.[/quote]
E servivano necessariamente anche i $a_1,a_2,a_3...$? Cioè si può solo duplicare il modello, in qualche modo?
"fields":
[quote="TomSawyer"]La risposta di Lolli alla mia e-mail...
Gentile, ha risposto subito e di domenica! Il "A mathematical introduction to logic" lo trovi sul mulo
Il problema è che ora, indicandomi la fonte, mi hai fatto finire il divertimento Forse è meglio, così mi metto a studiare Fisica...[/quote]Sì, era molto stuzzicante l'idea di fare una cosa simile anche per la relazione d'ordine. Comunque, $\exists x S^{(x)}=z$ definisce di nuovo i pari, vero?
"TomSawyer":
E servivano necessariamente anche i $a_1,a_2,a_3...$? Cioè si può solo duplicare il modello, in qualche modo?
Sì, perché è richiesto implicitamente che ogni elemento abbia un successore e inoltre il secondo assioma impone che la funzione successore sia iniettiva. Nel momento in cui esiste un elemento $a_0$ devono esistere $a_1,a_2,....$ e così via. Se si nega il terzo assioma di fatto il modello risultante sarà composto da un certo numero di "copie" di $NN$.
Se vuoi un altro problema elementare e stuzzicante, dimostra che l'addizione su $NN$ è definibile solo con la funzione successore e la moltiplicazione. In particolare, esiste un formula senza quantificatori $F(x,y,z)$, contenente i soli simboli $x,y,z,0,S,\cdot,=$ tale che
$x+y=z$ sse $F(x,y,z)$
Ad esempio, ovviamente $x+x=z$ sse $S(S(0))\cdot x=z$
"TomSawyer":
Comunque, $\exists x S^{(x)}=z$ definisce di nuovo i pari, vero?
A parte l'errore di battitura, non puoi definire insiemi infiniti e coinfiniti nella teoria del successore. Quindi non capisco che vuoi dire.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo