Domanda di Logica

[prime_number]

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

[fields]

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.

[TomSawyer]

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?

[fields]

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..

[fields]

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.

[TomSawyer]

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?

[fields]

Edit: post duplicato

[fields]

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.

[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$?

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 .

[TomSawyer]

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 .