Il Paradosso di Russell (formulato da Bertrand Russell nel 1901) è una delle scoperte più sconvolgenti della storia della logica e della matematica. Esso dimostra che la teoria degli insiemi di fine Ottocento (la cosiddetta “teoria ingenua” di Georg Cantor) conteneva una contraddizione logica insanabile. Per comprendere il paradosso, dobbiamo muoverci su tre livelli: la definizione logica, l’esempio pratico e le conseguenze storiche.

Cominciamo con la definizione logica. Secondo la logica dell’epoca, era possibile definire un insieme semplicemente indicando una proprietà dei suoi membri. Russell immaginò un insieme molto particolare: l’insieme di tutti gli insiemi che non appartengono a se stessi. Chiamiamo questo insieme R. La domanda paradossale è: R appartiene a se stesso? Se R appartiene a R allora, per definizione, R deve essere uno di quegli insiemi che non appartengono a se stessi. Quindi R non può appartenere a R (contraddizione). Se R non appartiene a R allora R soddisfa la condizione per entrare in R. Quindi R deve appartenere a R (contraddizione). Formalmente si scrive:

Passiamo all’esempio pratico, il Paradosso del barbiere. Per spiegare il concetto a un pubblico non esperto, lo stesso Russell inventò la celebre metafora del barbiere: in un villaggio c’è un unico barbiere che rade tutti e solo gli uomini del villaggio che non si radono da soli. Il barbiere si rade da solo? Se il barbiere si rade da solo, allora fa parte di chi si rade da sé, quindi il barbiere non deve raderlo. Ma lui è il barbiere! Se il barbiere non si rade da solo, allora rientra nella categoria di chi deve essere rasato dal barbiere. Ma il barbiere è lui stesso!

Prima di Russell, matematici come Gottlob Frege stavano cercando di fondare l’intera matematica sulla logica (il progetto del Logicismo). Il paradosso di Russell arrivò come una “doccia fredda”: dimostrò che non si può creare un insieme da “qualsiasi” proprietà, perché alcune proprietà portano al non-senso. Russell stesso cercò di risolvere il problema creando una gerarchia (i “tipi”): un insieme di livello 1 può contenere solo elementi di livello 0, non se stesso. Il paradosso portò alla nascita della teoria degli insiemi moderna, dove l’esistenza di un insieme deve essere giustificata da regole rigide (assiomi) per evitare l’auto-inclusione infinita.

Questo paradosso non è solo una curiosità filosofica. È il “nonno” di concetti informatici fondamentali. È alla base del Problema della Fermata di Alan Turing (un computer non può decidere se un programma si fermerà o meno in modo universale). È collegato ai Teoremi di Incompletezza di Gödel, che dimostrano che in ogni sistema logico complesso esistono verità che non possono essere dimostrate.