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.

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 è 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ù ${\displaystyle n}$ mosse, l'ipergioco termina in ${\displaystyle 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 ${\displaystyle S}$ di giochi ben definiti (finiti e non finiti), e si limita il secondo giocatore a scegliere all'interno dei giochi finiti dell'insieme ${\displaystyle S}$, si può applicare lo stesso ragionamento fatto, ma la conclusione in questo caso è semplicemente che l'ipergioco non fa parte dell'insieme ${\displaystyle 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.

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

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

definiamo sentiero una qualsiasi sequenza finita o infinita

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

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

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

Infatti, supponendo per assurdo che esista ${\displaystyle x\in S}$ per cui ${\displaystyle Z=S_{x}}$, costruiamo un sentiero che parte da ${\displaystyle x}$. Se ${\displaystyle S_{x}}$ è vuoto, il sentiero è formato dal solo elemento ${\displaystyle x}$ ed è finito; se ${\displaystyle S_{x}}$ contiene almeno un elemento ${\displaystyle y}$, questo è normale, e tutti i sentieri che iniziano con ${\displaystyle y}$ sono finiti; allora sono finiti anche tutti i sentieri che iniziano con ${\displaystyle x,y}$, quindi ${\displaystyle 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 ${\displaystyle x}$ è normale, allora deve appartenere a ${\displaystyle S_{x}}$, quindi è possibile costruire il sentiero infinito ${\displaystyle x,x,x,\ldots }$, il che renderebbe ${\displaystyle 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.

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

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

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica