Su un particolare insieme numerico - induzione

“Allora, hai visto come funzionano le dimostrazioni riguardanti l'ordinamento tra due numeri?”.

“Sì, ho visto: una cosa complicatissima, abbiamo impiegato un sacco di tempo solo per verificare che 1 è minore di 2”.

“Sì, è vero, ma ora vorrei farti notare questo: ti sei accorto che la definizione di ordinamento è ricorsiva?”.

“Cioè?”.

“Cioè richiama sé stessa: per dimostrare che x è minore di y devi dimostrare che x_L non è maggiore o uguale di y, e poi che y_R non è minore o uguale di x”.

“Ah, hai ragione. Ora che ci penso, è poi il metodo che abbiamo usato per dimostrare che 1 è minore di 2: abbiamo sospeso la dimostrazione per verificare altre disuguaglianze”.

“Infatti, è così. Ogni dimostrazione fa riferimento su una dimostrazione precedente, è su questo che si basa il principio di induzione”.

“Siamo sicuri che sia sempre precedente?”.

“In che senso?”.

“Voglio dire: per dimostrare che a è minore di b devo prima aver dimostrato altre due disuguaglianze. Siamo sicuri che queste facciano riferimento a disuguaglianze che ho già dimostrato prima? Non può succedere che, per dimostrare che a è minore di b, devo prima dimostrare che c è minore di d, e quando vado a dimostrare che c è minore di d devo dimostrare che a è minore di b? Non ci possono essere riferimenti circolari?”.

“Ah, bene, ottima domanda. No, non possono esserci riferimenti circolari, ed è facile vederlo se pensi alla genesi dei numeri”.

“Uhm, quella storia per cui ogni giorno vengono creati nuovi numeri?”.

“Esatto. Ogni numero ha il suo compleanno, anche se la parola inglese rende meglio”.

“Birthday?”.

“Sì: letteralmente significa giorno di nascita. Ad ogni numero possiamo associare il giorno in cui è stato creato”.

“Va bene, ma questo come ci aiuta?”.

“Immagina di dover dimostrare che x ≤ y. Sia x che y hanno i loro giorni di nascita”.

“Ok. Non è che potremmo continuare a chiamarli compleanni? Mi pare che suoni meglio”.

“Va bene. Allora, per dimostrare che x ≤ y devi dimostrare che x_L non è maggiore o uguale di y, e poi che y_R non è minore o uguale di x. Cosa puoi dire sul compleanno di x_L?”.

“Ah, non so”.

“Ricorda che x_L ti è servito per costruire il numero x”.

“Ah, vuoi dire che i numeri contenuti in x_L devono essere stati creati prima di x?”.

“Esatto”.

“Forse comincio a capire: le due disuguaglianze x_L ≥ y e y_R ≤ x prendono in considerazione numeri creati precedentemente”.

“È così: ogni disuguaglianza è più semplice della precedente, perché ogni volta consideri dei numeri creati precedentemente. Ora, questo procedimento di andare indietro a un certo punto termina”.

“Quando arrivo al primo giorno?”.

“Sì. Anzi, no, quando arrivi al zeresimo giorno. E qual è l'unico numero nato in quel giorno?”.

“Zero! Che è composto, nelle sue due parti, dall'insieme vuoto”.

“E quali sono le proprietà che non sono valide per l'insieme vuoto?”.

“Nessuna, mi hai detto che gli elementi dell'insieme vuoto godono di qualunque proprietà, dato che non esistono”.

“Infatti. Quindi questo procedimento di induzione non ha bisogno di un punto di partenza. O meglio, il punto di partenza è sottinteso, perché riguarda sempre l'insieme vuoto”.

“Bè, questo sì che è elegante”.

“E funziona anche se abbiamo a che fare con insiemi infiniti, modificandolo un po'”.

“Oh, è vero che ci saranno prima o poi anche gli insiemi infiniti...”.

“L'induzione funziona così: P(x) è vera se lo sono P(x_L) e P(x_R)”.

“Tutto qua?”.

“Tutto qua”.