In tutti i testi di matematica sia universitari che non, quando si stabilisce una corrispondenza biunivoca tra due insiemi infiniti non si fa nulla, si mostrano semplicemente alcuni termini dei due insiemi, magari su due righe sovrapposte, ed è finita lì, come per esempio tra tutti i naturali e i naturali pari. Ora io dico: e se volessimo meccanizzare un algoritmo (magari con una macchina di Turing) per costruire effettivamente la corrispondenza come potremmo fare? Cioè se io desidero che sia una macchina a stabilire l’esistenza o meno della corrispondenza ciò non implica un tempo? Mi spiego: supponiamo di avere due macchine ( ideali per esempio) una che conta i termini di un insieme e l’altra conta i termini dell’altro insieme. Una delle due macchine non resterà sistematicamente indietro rispetto all’altra? E allora in che senso sono riuscito a stabilire la corrispondenza? Esistono ricerche in questa direzione? o non mi rendo conto di pensare in modo scorretto? Grazie per la vostra cortesia.

Si supponga di avere due insiemi A, B, supposti infiniti enumerabili,
ovvero che si ipotizzino aventi la stessa cardinalità dei
numeri naturali, e sia f(n) una corrispondenza biunivoca tale che
B=f(A).

Si disponga, inoltre, delle proprietà PA(n) e PB(n)
occorrenti alla definizione degli elementi in A e B.

Ad esempio:

A = l’insieme dei numeri naturali dispari
B = l’insieme dei numeri naturali pari
PA(n) = n è dispari se n/2 ha resto 1
PB(n) = n è pari se n/2 ha resto 0

e si supponga di voler testare se la mappa

f(n)=n+1

tra i numeri naturali pari e quelli dispari sia biunivoca.

La dimostrazione “computazionale” di una corrispondenza biunivoca
è, in linea teorica applicabile, ovvero esiste un’algoritmo che
dimostra la corrispondenza biunivoca tra A e B.

Per l’esecuzione dell’algoritmo non sono necessarie due macchine di Turing;
posto un’ordinamento completo di A e B, una sola Macchina
di Turing può testare, ad ogni passo, se per ogni n dispari,
i.e. per cui PA(n) è vera, allora PB(f(n)) è
vera.

Una funzione è detta computabile se esiste un algoritmo
che la calcola; f è computabile e l’algoritmo che la calcola
è il seguente:

sia n=0;

ripeti

aumenta n di 1;

finchè PB(f(n)) è FALSA;

l’algoritmo termina quando la mappa f , supposta corrispondenza
biunivoca fallisce di verificare la proprietà PB(n).

Viceversa, l’algoritmo non termina se la proprietà è verificata.
Possiamo quindi affermare che la mappa f(n) è una corrispondenza
biunivoca se l’algoritmo non termina.

In linea teorica avremmo a disposizione un algoritmo che computi la enumerabilità
degli insiemi infiniti. Peccato che, per i limiti intrinseci di noi umani,
non potremmo sopravvivere per vederne il risultato.

Uno strumento più maneggevole, per noi umani, per la dimostrazione
di proprietà su insiemi infiniti enumerabili è il principio
di induzione.

Sia P(n) una proprietà ed A un insieme infinito
enumerabile:

P(n) è VERA per il primo elemento di A (passo
base dell’induzione)

supposto che P(n) è VERA implichi che P(SUCC(n))
sia vera (ipotesi induttiva)

allora

P(n) è VERA per tutti gli elementi di A

ove SUCC(n) sia una qualsiasi funzione primitiva che determini
il successore dell’n-mo elemento di A.

Una branca interessantissima della Scienza dei Calcolatori, la Dimostrazione
Automatica dei Teoremi, consente, con i suoi risultati, di ideare
algoritmi che siano in grado di dimostrare teoremi in generale, purchè
posti in una forma data. Fortunatamente, il principio di induzione per
una proprietà P(n) ed un insieme infinito enumerabile A
rientra tra i teoremi dimostrabili e, quindi, una dimostrazione di biunivocità
può essere determinata proprio applicando questi risultati ad una
Macchina di Turing, piuttosto che “per forza bruta”.