Giocando con le parole:
auto-referenza e logica matematica
Claudio Bernardi (Sapienza, Università di Roma)
autoreferente
qualcosa che parla di se stesso o che si riferisce a se stesso
un'autoreferenza si presenta per esempio quando in un
romanzo si racconta della scrittura di un romanzo
Otto e mezzo di Fellini
Effetto notte è un film sulla realizzazione di un film e dove il
regista François Truffaut è anche attore e interpreta il regista
nella commedia Sei personaggi in cerca d'autore di Pirandello
si costruisce una commedia all'interno di una commedia
Spesso, la presenza di aspetti autoreferenti in un'opera
conferisce un fascino e una suggestione particolare.
Maurits Cornelis Escher, Mani che disegnano (1948)
Jan Vermeer, L'arte della pittura, o L'atelier, 1672
Iniziamo con un rompicapo di Raphael Robinson (un logico).
La frase che segue è corretta.
«In questa frase la cifra 0 compare 1 volte,
la cifra 1 compare 11 volte,
la cifra 2 compare 2 volte,
la cifra 3 compare 1 volte,
la cifra 4 compare 1 volte,
la cifra 5 compare 1 volte,
la cifra 6 compare 1 volte,
la cifra 7 compare 1 volte,
la cifra 8 compare 1 volte,
la cifra 9 compare 1 volte»
Modificare i numeri scritti in rosso in modo che la frase risulti
ancora corretta (c'è un solo modo).
In numerazione binaria, abbiamo:
«In questa frase la cifra 0 compare 11 volte,
la cifra 1 compare 100 volte ».
(11)2 = 21 + 1 = 3, mentre (100)2 = 1⋅22 = 4
Poniamoci ora il problema della verità o falsità delle frasi.
Ogni enunciato o frase di senso compiuto è o vero o falso
(anche se noi non siamo sempre in grado di stabilirlo).
Il paradosso del mentitore, noto fin dall'antichità
Il poeta cretese Epimenide disse:
«tutti i cretesi sono bugiardi».
Se Epimenide dice la verità allora Epimenide, essendo cretese,
è un bugiardo e quindi dice il falso. Ma se mente, ...
A rigore, se Epimenide mente, se ne deduce solo che non tutti
i cretesi mentono: questo non significa che tutti i cretesi
dicono la verità, ma che almeno un cretese dice la verità.
Quindi, non c'è una contraddizione logica.
La conclusione è anzi ragionevole: almeno un cretese dice la
verità e il giudizio sommario di Epimenide è errato.
Tuttavia, è sconcertante che dall'affermazione di Epimenide
segua (logicamente!) che almeno un cretese diceva la verità.
Comunque, per ottenere una contraddizione basta considerare
la frase
«io sto mentendo»
Se dico la verità, allora mento; se mento, allora dico la verità!
Variante più semplice: «questa frase è falsa».
Il paradosso del mentitore è attribuito a Eubulide di Mileto,
(IV secolo a.C.)
Una variante spiritosa
Quanti errori contiene la frase seguente?
«cuesta fraze contiene tre errori».
Ci sono due errori ortografici, quindi è sbagliato anche il
numero degli errori. In conclusione la frase contiene ... errori.
Ne siamo sicuri?
È impossibile dare una risposta coerente alla domanda: la
risposta due va corretta in tre, ma la risposta tre va corretta in
due.
Paradosso di Jourdain
«la frase scritta in basso è vera»
«la frase scritta in alto è falsa»
Se la frase in alto è vera, anche la frase in basso è vera. Ma
allora ... Se la frase in alto è falsa, ...
Esiste una frase vera, tale che anche la sua negazione sia vera?
«Questa frase contiene cinque parole»
«Questa frase non contiene cinque parole»
(paradosso non troppo diverso dal paradosso di Russell)
uno scrittore vuole scrivere la biografia di tutti gli scrittori che
non hanno scritto (né stanno scrivendo) la loro autobiografia
Si potrebbe pensare che, escludendo frasi e situazioni
autoreferenti, superiamo tutti i paradossi.
Tuttavia l'autoreferenza viene correntemente accettata.
Io parlo un italiano perfetto. Questa è una lettera di protesta
Come si modifica la Costituzione Italiana?
E' stato inserito nella Costituzione un articolo specifico (il n.
138) che precisa come procedere.
Si sarebbe potuta fare una legge costituzionale a parte? Forse
sì, ma per spiegare la procedura per modificare questa legge ...
era necessaria un'altra legge. E per modificare quest'ultima ...
Esempi in cui una frase descrive la frase stessa
(le frasi che vedremo sono vere e dunque sensate)
«Questa frase contiene trentasette lettere»
«Questa frase comprende trentasei lettere»
«Questa frase contiene esattamente quarantotto lettere»
«Questa frase contiene esattamente quarantanove lettere»
«This sentence has thirtythree letters»
«Questa frase contiene ventiquattro vocali e trenta consonanti»
«Questa frase contiene dieci parole, ventisette sillabe e
sessantasei lettere»
Più difficile è costruire una coppia di frasi, ciascuna delle
quali parla dell'altra. Un esempio (Roberta Bindi):
«La frase seguente contiene
novanta consonanti e novanta vocali.»
«La frase precedente contiene
una parola di una lettera,
una parola di due lettere,
una parola di cinque lettere,
una parola di sei lettere,
due parole di sette lettere,
due parole di otto lettere,
una parola di dieci lettere.»
Un esempio divertente di Scott Kim e Douglas Hofstadter
«La frase seguente è sostanzialmente diversa da questa, dato
che sono state scambiate le parole "seguente" e "precedente",
così come le parole "tranne" e "dato" e le espressioni "identica
a" e "diversa da".»
«La frase precedente è sostanzialmente identica a questa,
tranne che sono state scambiate le parole "precedente" e
"seguente", così come le parole "dato" e "tranne" e le
espressioni "diversa da" e "identica a".»
frasi che si autoriproducono
Il risultato di sostituire «3» in «x è pari» è: 3 è pari.
Che cosa si trova partendo dalla frase che segue?
Il risultato di sostituire «Il risultato di sostituire «x» in «x»» in
«Il risultato di sostituire «x» in «x»».
Problema non banale in ambito informatico:
scrivere un programma che stampa se stesso
Ma l'autoreferenza non è solo un gioco!
autoreferenza e logica matematica
In una teoria matematica (assiomatica) per i numeri naturali
(cioè 0, 1, 2, 3, ...) si dimostrano teoremi; per esempio:
- la somma di un numero con il suo quadrato è sempre pari
- esistono infiniti numeri primi
- ogni numero è la somma di quattro quadrati
L'ultimo enunciato non è affatto banale; non è vero che ogni
numero si può esprimere come somma di tre quadrati
(per es. 6 = 22 + 12 + 02 , ma 15 = ?)
Ci sono anche enunciati dei quali non si sa se sono corretti o
sbagliati, come:
- ogni numero pari maggiore di 2 si può esprimere come
somma di due primi
Come ci convinciamo che «la somma di un numero con il suo
quadrato è pari» ?
controllo diretto: è il metodo più spontaneo, ma sarebbero
necessarie infinite verifiche; un procedimento concettualmente
diverso consiste nel dimostrare quell'enunciato
n + n2 = n(n + 1) fra i due numeri n e n + 1 uno è pari, e
quindi anche il prodotto è pari
Una differenza fondamentale:
- enunciato vero
esprime una proprietà di cui godono i numeri naturali (ma, in
genere, non siamo in grado di eseguire un controllo)
- teorema è un enunciato che si dimostra nella teoria (e ogni
dimostrazione ha lunghezza finita)
Se dimostriamo un enunciato, allora sappiamo che è vero, cioè
che vale per tutti i numeri naturali.
I teorema di Gödel. In una teoria non contraddittoria per i
numeri naturali, esiste un enunciato G che è vero per i numeri
naturali, ma che non si riesce a dimostrare.
Cenno della dimostrazione. Si codificano gli enunciati con i
numeri, cioè si associa un numero a ogni enunciato.
La cosa più interessante è che proprietà di un enunciato (per
esempio, il fatto che sia un teorema) si traducono in proprietà
del numero associato a quell'enunciato.
In particolare, esiste una formula della teoria
Theor (x)
x è il numero associato a un teorema
In questo modo, la teoria permette costruzioni autoreferenti.
Per la dimostrazione del I teorema di Gödel si riprende l'idea
del paradosso del mentitore nella forma «io sto mentendo».
Si riesce a costruire una formula G tale che è un teorema
G ←→ ¬ Theor (G)
Se G fosse un teorema, allora sarebbero teoremi
¬ Theor (G) perché equivale a G),
Theor (G)
perché Theor (G) esprime che G è un teorema
Se ¬ G fosse un teorema, allora sarebbe un teorema anche
Theor (G) e quindi sarebbe un teorema anche G.
In entrambi i casi, fra i teoremi troveremmo un enunciato e la
sua negazione (ma allora la teoria sarebbe contraddittoria).
In conclusione: G non è un teorema e ¬ G non è un teorema.
I giochi logici sono cose serie?
I paradossi sono cose serie?
Di fronte a un paradosso, la reazione di un matematico è il
tentativo di "far tornare le cose", per chiarire se c'è un errore.
Ma capire un paradosso non significa solo superarlo: la cosa
più importante è approfondire quel ragionamento, senza
paura.
È molto probabile che si possa riprodurre quel ragionamento
in altri contesti, con risultati interessanti.
Il paradosso di Yablo. Nell'isola dei furfanti e cavalieri
incontriamo infinite persone: a0, a1, a2, .... Ciascuno di loro
afferma che «tutti quelli che hanno un indice maggiore del
mio sono furfanti». Quali sono cavalieri?
La situazione porta ad una contraddizione, nel senso che non
riusciamo a trovare una soluzione del problema.
Infatti, se a0 è un cavaliere, tutti gli altri sono furfanti; ma, in
tal caso, l’affermazione di a1 risulterebbe vera.
Se a0 è un furfante, uno degli altri dovrebbe essere un
cavaliere, e la situazione si ripropone come prima.
C'è un'analogia con il paradosso del mentitore, ma in questo
caso nessuna affermazione si riferisce a sé stessa.