Paradosso dell'ipergioco

Il paradosso dell'ipergioco è un paradosso dovuto al matematico William Zwicker; esso è strettamente legato con il teorema di Cantor, di cui in effetti costituisce una dimostrazione alternativa.

L'ipergioco viene definito come un particolare gioco in cui il primo giocatore sceglie il gioco a cui giocare, e il secondo inizia il gioco. Questa definizione, apparentemente semplice, nasconde tuttavia delle proprietà contraddittorie, che nascono dall'ambiguità della definizione di gioco.

Formulazione del paradosso

Definizioni preliminari

Considerando l'insieme dei giochi a due giocatori, un gioco viene definito finito se termina necessariamente in un numero finito di mosse, con la vittoria di uno dei due giocatori o con il pareggio; un esempio semplice è il gioco del tris, che può durare al massimo nove mosse.

Un gioco infinito è un gioco non finito, ovvero un gioco per il quale esiste almeno una strategia che porta a non concludere mai la partita, anche in presenza di un'altra strategia che la concluderebbe in un numero finito di mosse. Ad esempio è infinito il seguente gioco: il primo giocatore sceglie un numero naturale non primo, e i giocatori sommano alternativamente 1 o 2 al numero dell'avversario fino a quando non si ottiene un numero primo; se il primo giocatore sceglie un numero pari diverso da 2 ed entrambi continuano a sommare 2, il gioco non termina mai. È da notare che questa strategia non è ottimale, e qualunque giocatore potrebbe facilmente interromperla a suo vantaggio; la sua esistenza comporta comunque la non finitezza del gioco. Un altro esempio di gioco infinito è PONG dove, teoricamente, si potrebbe continuare a far rimbalzare la pallina all'infinito tra le due barrette.

L'ipergioco e il paradosso

L'ipergioco è definito come il gioco in cui alla prima mossa un giocatore sceglie un gioco finito e lo comunica all'altro giocatore; alla seconda mossa questi inizia il gioco scelto dal primo giocatore.

Il paradosso si genera nel momento in cui si cerca di determinare se l'ipergioco sia un gioco finito o meno. In prima analisi l'ipergioco sembrerebbe un gioco finito: se infatti il primo giocatore è obbligato a scegliere un gioco finito, e se supponiamo che il gioco scelto termini in al più $n$ mosse, l'ipergioco termina in $n+1$ mosse ed è in particolare finito. Segue però che, se l'ipergioco è finito, allora il primo giocatore può scegliere di giocare all'ipergioco, e così può fare a sua volta il secondo giocatore, e così via; se entrambi continuano a scegliere l'ipergioco, la partita non termina mai. Seguirebbe l'esistenza di una strategia che porta il gioco a non finire mai, e l'ipergioco si configurerebbe come gioco infinito.

Segue allora che, se l'ipergioco è un gioco, deve essere un gioco finito; ma non può essere un gioco finito, perché se lo fosse sarebbe un gioco infinito.

Il paradosso nasce dall'ambiguità insita nella definizione di gioco: se infatti si decide a priori un insieme $S$ di giochi ben definiti (finiti e non finiti), e si limita il secondo giocatore a scegliere all'interno dei giochi finiti dell'insieme $S$, si può applicare lo stesso ragionamento fatto, ma la conclusione in questo caso è semplicemente che l'ipergioco non fa parte dell'insieme $S$, perché non può essere né un suo elemento finito né un suo elemento infinito, in analogia col paradosso di Russell riguardo agli insiemi e alle classi.

Legame con il teorema di Cantor

Il teorema di Cantor afferma che non esiste una corrispondenza biunivoca tra gli elementi di un insieme $S$ e gli elementi del suo insieme delle parti ${\mathcal {P}}(S)$ (ovvero i suoi sottoinsiemi); la dimostrazione del teorema è basata sulla costruzione di un sottoinsieme di $S$ che non può essere messo in corrispondenza con alcun elemento di $S$.

Il ragionamento di Zwicker corrisponde in effetti alla costruzione di un tale sottoinsieme, diverso da quello originale utilizzato da Cantor. Data infatti una corrispondenza

${\begin{matrix}S&\rightarrow &{\mathcal {P}}(S)\\x&\mapsto &S_{x},\end{matrix}}$

definiamo sentiero una qualsiasi sequenza finita o infinita

$x_{1},x_{2},\ldots ,x_{n},\ldots$

tale che per ogni termine $x_{n}$, o $x_{n}$ è l'ultimo termine, o il termine successivo appartiene a $S_{x_{n}}$; in generale è sempre possibile prolungare una sequenza finita $x_{1},x_{2},\ldots ,x_{n}$ aggiungendo un elemento di $S_{x_{n}}$, a meno che questo non sia l'insieme vuoto.

Un elemento $x\in S$ è detto normale se ogni sequenza che inizia con $x$ è finita. Si dimostra allora che l'insieme $Z$ degli elementi normali non può essere messo in corrispondenza biuniovoca con nessun elemento di $S$, ovvero per ogni $x\in S$, $Z\neq S_{x}$.

Infatti, supponendo per assurdo che esista $x\in S$ per cui $Z=S_{x}$, costruiamo un sentiero che parte da $x$. Se $S_{x}$ è vuoto, il sentiero è formato dal solo elemento $x$ ed è finito; se $S_{x}$ contiene almeno un elemento $y$, questo è normale, e tutti i sentieri che iniziano con $y$ sono finiti; allora sono finiti anche tutti i sentieri che iniziano con $x,y$, quindi $x$ è normale anche in questo caso. Questa parte di dimostrazione corrisponde alla considerazione per cui l'ipergioco è un gioco finito, perché dopo la prima mossa viene scelto un gioco finito.

Tuttavia, se $x$ è normale, allora deve appartenere a $S_{x}$, quindi è possibile costruire il sentiero infinito $x,x,x,\ldots$, il che renderebbe $x$ non normale, generando una contraddizione. In maniera analoga, se l'ipergioco è finito, allora i due giocatori possono continuare all'infinito a scegliere di giocare all'ipergioco.

Bibliografia

• Raymond Smullyan, Satana, Cantor e l'infinito, Milano, Bompiani, 1994, ISBN 88-452-2262-4.

Voci correlate

• Autoreferenza
• Paradossi dell'infinito
• Teorema di Cantor
• Teoria degli insiemi