Ricorsione, sost.: vedi Ricorsione.

Questo blog è già fin troppo geek-oriented, ma questo articolo (hat tip: Marco d’Itri) è troppo interessante per non scriverci su qualcosa, se non altro perché fornisce un esempio concreto (ammesso che un file possa definirsi concreto…) di quello che Yiannis Moschovakis chiama “the universally frustrating gift”. Ma andiamo a spiegarci.

Nell’articolo sopra linkato è descritto un metodo per costruire un file zip la cui decompressione coincide con il file di partenza (da cui la citazione della cosmologia delle tartarughe resa popolare da Hawking). Chiunque abbia una certa familiarità con le opere di Douglas Hofstadter non può fare a meno di riconoscere in ciò un esempio di strano anello (e in effetti i programmi autoreplicanti sono esplicitamente trattati in “Godel, Escher, Bach”), tant’è vero che all’inizio dell’articolo l’autore fa esplicito riferimento ad altri strani anelli tra cui il superclassico feedback video e la copertina di un celebre libro di teoria degli insiemi (anche se quest’ultima è solo un abbozzo dell’effetto Droste vero e proprio… ma non sottilizziamo). Proprio la teoria degli insiemi, però, fornisce esempi ben più calzanti di strano anello.

In qualunque teoria degli insiemi una domanda molto interessante da porsi è: esistono insiemi che sono membri di sé stessi? A prima vista una eventuale risposta affermativa non sembra nulla di catastrofico, e invece ha conseguenze abbastanza spiacevoli. Per vederlo cominciamo col ricordare un principio cardine di ogni teoria degli insiemi, l’assioma di estensionalità: ogni insieme è completamente determinato dalla conoscenza dei suoi elementi. Supponiamo ora che qualcuno ci dia un insieme \(X\) e, alla richiesta di specificarne gli elementi, risponda che

\(X = \{X\}\)

ovvero che \(X\) ha un unico membro e quell’unico membro è proprio sé stesso! Sembra difficile sostenere che questa affermazione aumenti le nostre conoscenze riguardo agli elementi di \(X\), e anche continuando a sostituire all’interno delle parentesi graffe la situazione non migliora:

\(X = \{X\} = \{ \{X\} \} = \{ \{ \{X\} \} \} = \ldots\)

È come se avessimo un pacco regalo che, una volta scartato, rivela al suo interno lo stesso identico pacco, e così di seguito ad infinitum; da cui la definizione di Moschovakis ricordata all’inizio del post. Il problema con l’estensionalità è evidente: se ora prendiamo un altro insieme \(Y\) tale che \(Y = \{Y\}\) come facciamo a decidere se \(X=Y\), visto che in nessuno dei due casi abbiamo idea di quali siano i loro elementi?

Ci sono due modi per uscire da questa impasse. Il primo è quello di vietare esplicitamente la possibilità che un insieme possa essere elemento di sé stesso, tipicamente adottando l’assioma di regolarità (il che ha anche altri vantaggi, soprattutto da un punto di vista meta-matematico); il secondo è quello di ammettere insiemi del genere ma modificare l’assioma di estensionalità in maniera tale da poter distinguere tra loro gli insiemi non ben fondati (vedi ad esempio questo libro di Peter Aczel per un’idea di come sia possibile procedere).