moderatore: A me questa sembra matematica universitaria, quindi sposto in MNE. --federico
Dimostrare che TR, l'insieme delle sentenze vere dell'Aritmetica, non è nemmeno semidecidibile.
Nota: dal teorema di Godel segue che l'insieme dei teoremi dell'Aritmetica non è decidibile, però esso è almeno semidecidibile. Invece l'esercizio chiede di dimostrare che TR non lo è.
Logica: l'Aritmetica non è nemmeno semidecidibile
Non so se nessuno abbia mai dato risposta a questo topic perchè la domanda era troppo semplice o cosa... fattostà che posto una soluzione, correggetemi dove sbaglio. Non è il massimo del rigore 
.
Dunque, prima di tutto, dimostrare che $ Tr $ non è decidibile, ovvero non è ricorsivo. Per chi non lo sapesse, un insieme S si dice ricorsivo se esiste un algoritmo, un automa, un programma, una macchina di turing - che dir si voglia- che applicato a un dato oggetto (un elemento dell'insieme universo considerato) dia come risultato, in un numero finito di passaggi, 1 se l'elemento appartiene a S, e 0 se non vi appartiene. Parimenti, un insieme S si dice ricorsivamente enumerabile (o semidecidibile) se esiste un algoritmo che applicato a un dato oggetto dia come risultato 1 se l'elemento appartiene a S, e giri indefinitamente altrimenti.
Th. 1: $ Tr $ non è ricorsivo.
Dim: Per il teorema di Godel, un sistema F corretto in grado di rappresentare al suo interno l'aritmetica, è incompleto. Ovvero, esiste una formula vera $ \varphi $ tale che nè $ \varphi $ nè $ \neg \varphi $ siano dimostrabili in F. (seguendo l'interpretazione della logica modale, il fatto che $ \alpha $ sia dimostrabile si indica con $ \Box \alpha $).
Fissiamo un ordinamento qualsiasi delle formule aritmetiche. Supponiamo esista un algoritmo, un programma $ p $ che, avente come dati di input l'indice $ \overline {\alpha} $ della formula $ \alpha $, dia come risultato 1 se $ \Box \alpha $ e quindi, per la correttezza, se è vera, e come risultato 0 se $ \Box \neg \alpha $, ovvero se la formula è falsa (sempre per la correttezza semantica).
Ma allora $ p(\overline{\varphi}) $ non può avere risultato 1 perchè $ \varphi $ non è dimostrabile; non può avere risultato 0 perchè neppure $ \neg \varphi $ lo è. Pertanto $ p $ non è in grado di decidere la verità o falsità di tutte le proposizioni aritmetiche (più brevemente, segue dall'incompletezza). Allora $ Tr $ non può essere ricorsivo.
Detto ciò
Th. 2: $ Tr $ non è nemmeno ricorsivamente enumerabile.
Dim: Supponiamo per assurdo che esista un automa $ p' $ tale che, senza perdita di generalità, $ p'(\overline \alpha) $ dia come risultato 1 se $ \Box \alpha $, e giri indefinitamente in caso contrario; supponiamo cioè che $ Tr $ sia ricorsivamente enumerabile. Costruiamo allora un automa $ q $, così formato: $ q(\overline \alpha) $ esegue contemporaneamente (in parallelo) due programmi/automi, ossia esegue in parallelo $ p'(\overline \alpha) $ e $ p'(\overline {\neg \alpha}) $, e riguardo a quest'ultimo, cambia un eventuale risultato 1 in uno 0. Vediamo allora che $ q(\overline \alpha) $ dà 1 se $ \Box \alpha $ (e l'altro programma gira indefinitamente, così viene fermato), mentre dà 0 se $ \Box \neg \alpha $. Ma allora sarebbe $ q(\overline \alpha) \equiv p(\overline \alpha) $, ovvero $ Tr $ sarebbe ricorsivo, il che abbiamo già dimostrato essere impossibile. QED.
Penso di non avere alcuna esperienza in questo, quindi la mancanza di rigore deve essere spaventosa per chi ne sa qualcosa. scusate.
.Dunque, prima di tutto, dimostrare che $ Tr $ non è decidibile, ovvero non è ricorsivo. Per chi non lo sapesse, un insieme S si dice ricorsivo se esiste un algoritmo, un automa, un programma, una macchina di turing - che dir si voglia- che applicato a un dato oggetto (un elemento dell'insieme universo considerato) dia come risultato, in un numero finito di passaggi, 1 se l'elemento appartiene a S, e 0 se non vi appartiene. Parimenti, un insieme S si dice ricorsivamente enumerabile (o semidecidibile) se esiste un algoritmo che applicato a un dato oggetto dia come risultato 1 se l'elemento appartiene a S, e giri indefinitamente altrimenti.
Th. 1: $ Tr $ non è ricorsivo.
Dim: Per il teorema di Godel, un sistema F corretto in grado di rappresentare al suo interno l'aritmetica, è incompleto. Ovvero, esiste una formula vera $ \varphi $ tale che nè $ \varphi $ nè $ \neg \varphi $ siano dimostrabili in F. (seguendo l'interpretazione della logica modale, il fatto che $ \alpha $ sia dimostrabile si indica con $ \Box \alpha $).
Fissiamo un ordinamento qualsiasi delle formule aritmetiche. Supponiamo esista un algoritmo, un programma $ p $ che, avente come dati di input l'indice $ \overline {\alpha} $ della formula $ \alpha $, dia come risultato 1 se $ \Box \alpha $ e quindi, per la correttezza, se è vera, e come risultato 0 se $ \Box \neg \alpha $, ovvero se la formula è falsa (sempre per la correttezza semantica).
Ma allora $ p(\overline{\varphi}) $ non può avere risultato 1 perchè $ \varphi $ non è dimostrabile; non può avere risultato 0 perchè neppure $ \neg \varphi $ lo è. Pertanto $ p $ non è in grado di decidere la verità o falsità di tutte le proposizioni aritmetiche (più brevemente, segue dall'incompletezza). Allora $ Tr $ non può essere ricorsivo.
Detto ciò
Th. 2: $ Tr $ non è nemmeno ricorsivamente enumerabile.
Dim: Supponiamo per assurdo che esista un automa $ p' $ tale che, senza perdita di generalità, $ p'(\overline \alpha) $ dia come risultato 1 se $ \Box \alpha $, e giri indefinitamente in caso contrario; supponiamo cioè che $ Tr $ sia ricorsivamente enumerabile. Costruiamo allora un automa $ q $, così formato: $ q(\overline \alpha) $ esegue contemporaneamente (in parallelo) due programmi/automi, ossia esegue in parallelo $ p'(\overline \alpha) $ e $ p'(\overline {\neg \alpha}) $, e riguardo a quest'ultimo, cambia un eventuale risultato 1 in uno 0. Vediamo allora che $ q(\overline \alpha) $ dà 1 se $ \Box \alpha $ (e l'altro programma gira indefinitamente, così viene fermato), mentre dà 0 se $ \Box \neg \alpha $. Ma allora sarebbe $ q(\overline \alpha) \equiv p(\overline \alpha) $, ovvero $ Tr $ sarebbe ricorsivo, il che abbiamo già dimostrato essere impossibile. QED.
Penso di non avere alcuna esperienza in questo, quindi la mancanza di rigore deve essere spaventosa per chi ne sa qualcosa. scusate.
FONDATORE DELLA LEGA ANTI MICKEY-MOUSE
(\_/)
(°_°)
(> <) il coniglietto non perdona
(\_/)
(°_°)
(> <) il coniglietto non perdona