# Logica matematica/Intermezzo paradossi

Logica matematica
Copertina Tutti i moduli · Sviluppo
* InsiemiLogica matematica/Insiemi
* Sistemi formaliLogica matematica/Sistemi formali
* Calcolo delle proposizioniLogica matematica/Calcolo delle proposizioni
** Il sistema di Frege-HilbertLogica matematica/Calcolo delle proposizioni/Sistema di Hilbert
** La deduzione naturaleLogica matematica/Calcolo delle proposizioni/La deduzione naturale
** Il calcolo dei sequenti
** I tableaux semanticiLogica matematica/Calcolo delle proposizioni/I tableaux semantici
** La risoluzioneLogica matematica/Calcolo delle proposizioni/La risoluzione
** Esercizi su tavole di veritàLogica matematica/Calcolo delle proposizioni/Esercizi su tavole di verità
* Calcolo dei predicatiLogica matematica/Calcolo dei predicati
* Teoria dei modelliLogica matematica/Teoria dei modelli
* Computabilità
* IncompletezzaLogica matematica/Incompletezza
** Teoremi di incompletezza di GödelLogica matematica/Incompletezza/Teoremi di incompletezza di Gödel
* Intermezzo: EuclideLogica matematica/Intermezzo Euclide
* Intermezzo: i paradossiLogica matematica/Intermezzo paradossi
* Risorse internetLogica matematica/Risorse internet
Modifica il sommario

## Paradosso del mentitore

Il paradosso del mentitore è l'essenza dei paradossi legati all'autoreferenza.
Questa frase è falsa.
Se la frase fosse vera, poiché dice di essere falsa dovrebbe essere falsa. Se fosse falsa, poiché dice di esserlo è vera. Per essere vera deve essere falsa, per essere falsa deve essere vera.
Questo paradosso è noto fin dall'antichità: il cretese Epimenide diceva "Tutti i cretesi mentono". Paradosso del mentitore
Con l'autoreferenza è facile costruire situazioni paradossali. Anche la negazione del paradosso del mentitore contiene una certa dose di paradosso:
Questa frase è vera.
Se fosse vera deve dire di esserlo. Se fosse falsa, per esserlo deve dire di essere vera. Quindi ci troviamo di fronte ad una frase vera che dice di esserlo o falsa che dice di essere vera per poter essere falsa? La frase che dice di essere vera non trasmette informazioni su se stessa, in fondo tutti i bugiardi spergiurano di dire la verità e noi non sappiamo quando crederli o meno.
Una forma particolarmente frequente è la "pagina intenzionalmente bianca" che si trova in parecchi testi. La pagina dice di essere intenzionalmente bianca, in realtà contiene la scritta dove dice di essere bianca, quindi è intenzionalmente non bianca! Eppure quasi nessuno si accorge che la frase è palesemente falsa, perché la pagina non contiene nessuna informazione relativa al discorso portato avanti dal resto del testo e quindi in questo senso è vera: trasmette informazioni sulla pagina, non sull'argomento del libro.

## Paradosso di Russell

Questo paradosso è stato scoperto da Russell nella teoria intuitiva degli insiemi, creata da Cantor ed utilizzata da Frege nel primo tentativo di assiomatizzazione della matematica.
Il paradosso nasce considerando gli insiemi che hanno se stessi come elementi. Posso dividere gli insiemi in due gruppi, quello degli insiemi che hanno se stessi come elementi e il quello degli insiemi non appartenenti a se stessi. Chiamiamo $X$ il secondo gruppo.
1. $X=\{x|x\notin x\}$
Analizziamo questo insieme: se appartiene a se stesso dovrebbe far parte del primo gruppo, ma se fa parte del primo allora non appartiene più a stesso e quindi dovrebbe appartenere a se stesso. Sostituendo $X$ a $x$, cioè cercando di piazzare l'insieme $X$ stesso otteniamo:
2.$X\in X\leftrightarrow X\in \{x|x\notin x\}\leftrightarrow X\notin X$
arrivando così alla situazione paradossale: $X$ appartiene a $X$ se e solo se $X$ non appartiene a $X$. La situazione è simile a quella del paradosso del mentitore. In questo caso l'autoreferenza non è diretta, ma nasce dal fatto che stiamo considerando tutti gli insiemi, nessuno escluso.
Ci sono esempi semplificati di questo paradosso, il più famoso è quello del barbiere: in un piccolo paese il barbiere è colui che rade quelli che non si radono da soli. Chi rade il barbiere?
La teoria degli insiemi ha risolto il paradosso vietando l'insieme universale. L'insieme di tutti gli insiemi è contradditorio, è una classe e non un insieme (almeno per ZFC, la teoria assiomatica di Zermelo e Fraenkel; ci sono altre teorie dove esiste l'insieme universale, ma allora vengono poste altre limitazioni per evitare questo tipo di paradossi).
Il barbiere invece ogni mattina si rade in barba alla definizione ed al paradosso.

## Paradosso di Quine

"è falsa quando viene preceduta dalla sua citazione" è falsa quando viene preceduta dalla sua citazione

## Paradosso di Curry

Consideriamo questa frase:
Se questa frase è vera, allora Babbo Natale esiste
Supponiamo che sia vera, allora poiché ci dice che se è vera Babbo Natale esiste, dobbiamo derivare che Babbo Natale esiste, se Babbo Natale non esistesse avremmo che il vero implica il falso quindi la frase sarebbe falsa. Quindi se la frase è vera, non ci sono problemi logici solo se Babbo Natale esiste.
Supponiamo che sia falsa, allora la prima parte dell'implicazione è falsa e quindi possiamo derivare quello che vogliamo, quindi l'intera implicazione (e tutta la frase) è vera indipendentemente dal fatto che Babbo Natale esista o meno. Abbiamo una contraddizione.
Così ci troviamo nella situazione che se fosse falsa troviamo una contraddizione, se invece è vera non c'e' nessun problema di logica (formale) ma che la logica ci fornisca la prova dell'esistenza di Babbo Natale non è il tipo di risultato che ci aspettiamo da un sistema coerente di ragionamento.
Il paradosso è evidente: cambiando la parte "allora" in questo modo possiamo dedurre qualunque cosa.
Per convincersi che il paradosso esiste, anche senza le ambiguità del linguaggio naturale, possiamo esporlo in modo formale. Scriviamo la frase in questo modo $X=(X\rightarrow Y)$.
La dimostrazione formale è:
* $X\rightarrow X$, identità
* $X\rightarrow (X\rightarrow Y)$, sostituzione del secondo X con (X → Y)
* $X\rightarrow Y$, eliminazione di una ipotesi ripetuta: |- X → (X → Y) <==> X |- X → Y <==> X,X |- Y <==> X |- Y <==> |- X → Y
* $X\,$, sostituzione nella 3 di X → Y con X
* $Y\,$, per modus ponens tra 3 e 4
Un caso particolare è se la sentenza Y è del tipo Z ∧ $\neg$Z, che diventa X = (X → (Z ∧ $\neg$Z)). In questo caso per la legge di non contraddizione, poiché Z ∧ $\neg$Z è sicuramente falso dalla verità di X possiamo dedurre $\neg$X. Ma allora da X, che è falso possiamo dedurre qualunque cosa, quindi l'intera frase X = (X → (Z ∧ $\neg$Z)) è vera. Siamo così arrivati al paradosso del mentitore: X ↔ $\neg$X
Rispetto al paradosso del mentitore o al paradosso di Russel questo è molto più difficile da eliminare poiché non utilizza l'operazione di negazione.

## Paradosso del mucchio

I mucchi di sabbia possono essere grandi o piccoli. Un mucchio piccolo con un solo granellino in più non diventa un mucchio grande. Quindi aggiungendo un granellino alla volta un mucchio piccolo non diventa mai grande, indipendentemente da quanti granellini di sabbia aggiungiamo.
Questo paradosso nasce dall'imprecisione del linguaggio non formalizzato, il concetto di mucchio grande o piccolo non è preciso. Cosa succede quando il linguaggio diventa sufficientemente preciso, come in matematica? La risposta è molto interessante.
In matematica il grande è l'infinito. Ecco che appare tutta la forza del paradosso: partendo da un numero finito, per esempio 0, ed aggiungendo 1, possiamo continuare quanto vogliamo ma non costruiremo mai un numero infinito. Per ottenere l'infinito attuale dobbiamo cambiare strategia, non dobbiamo più contare, ma creare l'insieme di tutti i numeri naturali. Solo così otteniamo qualcosa di grande, qualcosa di infinito.
Questo si rispecchia nella teoria degli insiemi ZFC con la necessità di introdurre un assioma apposito, l'esistenza dell'insieme infinito non è derivabile dagli altri assiomi.
Ma ancora più sorprendente è quello che succede dopo: ora che abbiamo l'infinito scopriamo che è solo un mucchio piccolo per un infinito più grande, che possiamo costruire nuovi cardinali sempre più grandi finendo in una specie di struttura che si ripete a scala diversa e che non si lascia catturare nella sua interezza, al punto che l'insieme di tutti gli insiemi, l'infinito assoluto, l'ipotetico punto di arrivo, è un concetto contraddittorio (vedi il paradosso di Russell).
Ci sono delle teorie degli insiemi alternative (come la NF di Quine), che riescono ad ammettere l'insieme di tutti gli insiemi. Ma allora perdono altre proprietà, per esempio non è sempre possibile costruire una biiezione tra un insieme e gli insiemi costituiti prendendo uno ad uno i vari elementi (i singoletti). In NF non è più possibile dimostrare il teorema di Cantor che l'insieme delle parti ha una cardinalità maggiore dell'insieme stesso.
C'è anche un'altra soluzione: ridurre il grado di precisione. La logica "fuzzy" percorre questa strada. I concetti non sono più netti, ma sfumati; l'essere mucchio grande o piccolo non è più una proprietà netta ma una possibilità e non si cade più in questo tipo di paradossi.