Ragionare per vie diagonali
Uno degli strumenti più utilizzati dai matematici:
il metodo della diagonale di Cantor.
Un pizzico di insiemistica
X = {a, b, c} un insieme con 3 elementi a, b, c.
P(X) = insieme delle parti (sottoinsiemi) di X:
{ {a}, {b}, {a, c}, ... }
f : X -> P(X)
Teorema:
f non può essere suriettiva (non raggiunge tutto P(X))
Il ragionamento diagonale:
|
a |
b |
c |
| f(a)={b} |
0 |
1 |
0 |
| f(b)={a,b} |
1 |
1 |
0 |
| f(c)={c} |
0 |
0 |
1 |
[1,0,0] -> {a}
non è raggiunto da f
|
|
a |
b |
c |
| f(a)={} |
0 |
0 |
0 |
| f(b)={a,c} |
1 |
0 |
1 |
| f(c)={a,b} |
1 |
1 |
0 |
[1,1,1] -> {a,b,c}
non è raggiunto da f
|
Dimostrazione formale:
Y = { x in X tali che x non appartiene a f(x) }.
Allora non ci può essere nessun y in X tale che
f(y) = Y;
se ci fosse allora
- o y appartiene a Y, ma allora
y non appartiene a f(y),
- oppure y non appartiene a Y, ma allora
y appartiene a f(y)!
Qui si sente chiaramente odore di autoreferenza; viene
in mente il paradosso del mentitore, storielle Zen e altre amenità
simili.
Anche se qui X ha solo 3 elementi, questa dimostrazione funziona
altrettanto bene con insiemi di 50, 100 o anche infiniti elementi.
Il paradosso di Russell
Pensare che esista un insieme di tutti gli insiemi conduce
al paradosso dovuto a Bertrand Russell (1872-1970):
Se X è l'insieme degli insiemi che non contengono
sé stessi come elementi, allora si dimostra che
X non può né appartenere né non
appartenere a sé stesso!
Il paradosso viene risolto negli anni successivi fondando la teoria
degli insiemi in modo meno ingenuo (Zermelo - Fraenkel).