Su un particolare insieme numerico - semplifichiamo

“Grazie all'induzione, di cui abbiamo parlato la volta scorsa, possiamo dimostrare qualche semplice proprietà:”.

Per ogni gioco, si ha che:

• x non è maggiore o uguale di x_R
• x non è minore o uguale di x_L
• x ≤ x
• x = x
• se x ≥ y e y ≥ z, allora x ≥ z (proprietà transitiva)

Per ogni numero, si ha che:

• x_L < x < x_R
• x ≤ y oppure y ≤ x (l'ordinamento è totale)

“Perché dici gioco?”.

“Perché sono proprietà che valgono in generale per tutti i giochi, cioè non fanno uso del fatto che x_L non è maggiore o uguale di x_R”.

“Ah. E le dimostriamo?”.

“Pensavo di lasciarle come esercizio al lettore volonteroso: si basano sul concetto di induzione”.

“Ok”.

“Ora invece vediamo di rispondere a un'altra domanda: quand'è che un numero x = {x_L|x_R} è uguale a un numero X = {y, x_L|x_R}?”.

“Eh?”.

“Traducendo: quand'è che possiamo aggiungere un numero a sinistra senza cambiare il valore di x?”.

“Ah, ora ho capito. Avevamo dimostrato che {0,1|} e {1|} sono uguali, per esempio. Quindi quello 0 a sinistra era inutile”.

“Esatto: ora troviamo una regola generale. Consideriamo i due numeri x e X che abbiamo appena definito e chiediamoci quando x ≤ X”.

“Uhm, dovrei saperlo dire, ormai. Vediamo: x è minore o uguale di X a meno che qualche elemento dell'insieme di sinistra di x, cioè x_L, non sia maggiore o uguale di X (no, è impossibile, perché ogni x_L è anche un X_L, che non può essere maggiore o uguale di X), oppure a meno che qualche elemento dell'insieme di destra del secondo numero, cioè X_R, non sia minore o uguale di x (no, impossibile, perché ogni X_R è anche un x_R)”.

“Perfetto, ottima analisi. Dunque x ≤ X. Puoi fare la stessa analisi anche per X ≤ x?”.

“Ormai non mi ferma più nessuno. Allora, X è minore o uguale di x, a meno che qualche elemento dell'insieme di sinistra del primo numero, cioè {y, x_L}, sia maggiore o uguale di x — uhm, tutti gli x_L non sono maggiori o uguali di x, ma di y non so niente. Quindi devo imporre che anche y non sia maggiore o uguale di x”.

“Perfetto, vai avanti, manca la seconda condizione”.

“Ah, già. La seconda condizione dice che X è minore o uguale di x, a meno che qualche elemento dell'insieme di destra del secondo numero non sia minore o uguale di X — questo non può succedere perché ogni x_R è anche un X_R. Quindi siamo a posto, l'unica condizione che devo imporre è quella su y”.

“Ottimo. Riassumendo, {y, x_L|x_R} = {x_L|x_R} purché y non sia maggiore o uguale di x”.

“Ah, finalmente un bel risultato. A questo punto possiamo accorciare quella lista di venti numeri che avevamo fatto tempo fa?”.

“Sì, prova a semplificarla, ricordandoti che puoi eliminare un numero dalla parte sinistra dell'insieme se, sempre nella parte sinistra, ne esiste un altro maggiore di quello”.

“Eh, però mi piacerebbe sapere come fare a semplificare quei numeri che hanno più elementi nella parte destra”.

“Hai ragione: puoi usare evidenti ragioni di simmetria per dedurre che, nella parte destra, puoi eliminare un numero se ne esiste un altro minore di quello”.

“Uhm, non faccio commenti sulle ragioni di simmetria... Quindi posso dire che ogni numero x è uguale a quel numero che si ottiene prendendo il più grande elemento di x_L e il più piccolo elemento di x_R?”.

“Esatto, ammesso che, naturalmente, esista il più grande elemento dell'insieme di sinistra o il più piccolo di quello di destra”.

“Naturalmente”.

“Questa proprietà è valida per i nostri venti numeri, quindi possiamo andare avanti tranquilli”.

“Ok, allora, vediamo. L'elenco dei nuovi numeri dovrebbe ridursi così:”.

{|} = 0
{-1|}
{-1,0|} = {0|} = 1
{-1,1|} = {0,1|}= {-1,0,1|} = {1|}
{|-1,1} = {|-1,0} = {|-1,0,1}= {|-1}
{|0,1} = {|0} = -1
{|1}
{-1|0,1} = {-1|0}
{-1|1}
{-1,0|1} = {0|1}

“Giusto. Per ora ci fermiamo qua, poi vedremo come ridurlo ancora”.