Il Dilemma del Barbiere.


Ieri abbiamo aggiunto nuovi, preziosissimi strumenti alla nostra borsa del matematico. Ora siamo pronti ad affrontare il Paradosso di Russell:

In un villaggio c’è un unico barbiere. Il barbiere rade tutti (e solo) gli uomini che non si radono da sé. Il barbiere si rade da solo ?

Dicevamo di voler costruire la rappresentazione formale del nostro problema. Per prima cosa abbiamo bisogno di modellare l’insieme degli abitanti del paese P. Tra questi, abbiamo detto che esiste un elemento speciale b, il barbiere.

Inoltre, abbiamo bisogno di una relazione, rade, che va dall’insieme degli abitanti del paese a sé stesso:

rade P x P

Adesso, definiamo il sottoinsieme R, contenuto  in P, delle persone che si radono  e che non sono rase dal barbiere, in questo modo:

R = {x | (x,x)rade}

che si legge così: R è l’insieme delle persone x tali che la coppia (x,x) appartiene alla relazione rade (ovvero che si radono da sole). Sappiamo per ipotesi se un elemento x appartiene all’insieme R allora non viene raso dal barbiere, ovvero che (b,x) non appartiene alla relazione rade. Scriviamolo in modo formale

(x,x)rade <=> (b,x) rade, per ogni x

aggiungendo un altra piccola notazione formale, il concetto di implicazione, rappresentato dal simbolo =>. Questo è un caso ancor più forte perché l’implicazione vale nei due sensi: tutti gli elementi non rasi dal barbiere appartengono ad R e viceversa.

Mentre, specularmente, l’insieme NR le persone che non si radono e sono rase dal barbiere è espresso in questo modo:

NR = {x | (x,x) rade}

e, quindi, vale l’implicazione corrispondente

(x,x) rade <=> (b,x) rade

cioè tutti gli elementi appartenenti ad NR, che non si radono da soli, vengono rasi dal barbiere.

Ecco, la domanda che si pone Russell è: il barbiere si rade ? Ha due possibili risposte:

1. Prima ipotesi: il barbiere non si rade

b NR

ma allora se l’elemento b è contenuto in NR, si ottiene che – per definizione di NR – deve essere contemporanamente vera l’implicazione che abbiamo visto prima (basta sostituire b ad x nella definizione):

(b,b) rade <=> (b,b) rade

è una evidente contraddizione dire che una coppia di elementi appartenga e non appartenga contemporaneamente ad una relazione.

2. Seconda ipotesi: il barbiere  si rade

b R

di nuovo, basta sostituire b ad x nella definizione di R e si ottiene la stessa contraddizione:

(b,b) rade <=> (b,b) rade

Vedete qual’è la potenza dell’impostazione formale della logica matematica, attraverso la teoria degli insiemi ? E’ possibile scrivere relazioni logiche in modo compatto e possono operare trasformazioni e sulla base delle quali trarre deduzioni logiche vere e proprie. La potenza di questo strumento è notevole: oggi siamo in grado di far ragionare le macchine calcolatrici, usandolo in modo accorto e formalmente corretto.

Tornando al nostro paradosso, abbiamo dimostrato che la domanda (o proposizione) se b si rade o no non ammette soluzione, perché si ottiene una contraddizione in ogni caso. Proposizioni di questo tipo sono dette indecidibili, ci torneremo più in là parlando di un’altra brillante mente del XX secolo: Kurt Godel.

Annunci
Questa voce è stata pubblicata in Teoria e Pratica e contrassegnata con , , , , , , . Contrassegna il permalink.

3 risposte a Il Dilemma del Barbiere.

  1. Pingback: Lo zero è un numero naturale ? (parte 1) | LidiMatematici

  2. Pingback: Lo zero è un numero naturale ? (parte 2) | LidiMatematici

  3. Pingback: Kurt Godel e il Teorema di Incompletezza | LidiMatematici

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...