Paradossi della teoria degli insiemi

La teoria ingenua degli insiemi contiene alcuni paradossi interessanti, che alla fine hanno portato a elaborare una teoria degli insiemi più rigorosa. Questi paradossi si basano spesso sul fatto che nella teoria classica, ingenua, è possibile che un insieme contenga se stesso come proprio elemento.

Il paradosso di Russell

Tra i paradossi più noti c’è il paradosso di Russell. Possiamo formularlo così: consideriamo l’insieme N che contiene esattamente quegli insiemi che non contengono se stessi come proprio elemento. Quindi, se un insieme contiene se stesso come proprio elemento, allora non appartiene all’insieme N. Se invece non contiene se stesso, allora appartiene all’insieme N.

La domanda è: l’insieme N contiene come proprio elemento l’insieme N, cioè se stesso?

Analizzando i casi scopriamo che: se l’insieme N non contiene N, allora si tratta di un insieme che non contiene se stesso e dovrebbe stare nell’insieme N, quindi dovrebbe valere N ∈ N.

Se però l’insieme N contiene l’elemento N, allora non dovrebbe valere N ∈ N, perché l’insieme N contiene solo gli insiemi che non contengono se stessi come proprio elemento.

Il paradosso sta dunque nel fatto che violiamo sempre una delle condizioni. Se N ∈ N, ciò contraddice la definizione dell’insieme N (contiene solo insiemi che non contengono se stessi, mentre qui N evidentemente contiene N come proprio elemento), e se non vale N ∈ N, violiamo di nuovo la definizione di N.

Un tale insieme quindi non possiamo costruirlo, cosa che in una teoria degli insiemi corretta non dovrebbe succedere.

Il paradosso di Russell ha anche diverse interpretazioni naturali. Ad esempio il paradosso del barbiere. In un paese c’è un barbiere che rade esattamente quelle persone che non si radono da sole. Viene spontanea la domanda: il barbiere rade se stesso?

Il paradosso di Cantor

Un altro paradosso è quello di Cantor. Si basa sul fatto che, se abbiamo un insieme M, il suo insieme delle parti P(M) (l’insieme di tutti i sottoinsiemi di M) ha sempre una cardinalità maggiore, è più grande. Per gli insiemi finiti lo si vede a colpo d’occhio, per gli insiemi infiniti si può dimostrare facilmente. Questa affermazione si chiama appunto teorema di Cantor, e il suo enunciato preciso e la dimostrazione si trovano su Wikipedia.

Il paradosso vero e proprio è più semplice del precedente. Immaginiamo l’insieme di tutti gli insiemi e chiamiamolo M. Quindi per qualsiasi insieme N vale N ∈ M. Ma per il teorema di Cantor la cardinalità dell’insieme delle parti P(M) è maggiore di quella di M. Questo però è in contraddizione con il fatto che M contiene tutti gli insiemi: se l’insieme P(M) è più grande di M, deve necessariamente contenere elementi che l’insieme M non contiene.