2 86 386 577 668 298 411 128 469 151 667 598 498 812 366. Ecco il più grande numero di Dedekind noto a oggi! Ed è soltanto il nono (o il decimo, se si conta anche quello di indice 0). Questa incredibile successione, catalogata con la sigla A000372 nell’OEIS, l’Enciclopedia online delle successioni di interi di Neil Sloane, mette in difficoltà tutti i calcolatori da oltre un secolo. Eppure, vari punti di vista permettono di definire questa successione numerica, che compare in ambiti apparentemente molto diversi.
Il punto di vista originario consiste nello studiare le funzioni logiche crescenti. Una funzione logica riceve in ingresso dei booleani, cioè variabili che assumono il valore «Vero» o «Falso», e restituisce un booleano.
Come si può definire qui un senso di variazione? Ebbene, la soluzione più semplice consiste nell’attribuire il valore 0 a «Falso» e il valore 1 a «Vero». Le nostre funzioni sono dunque definite su n-uple di 0 e 1, e i loro valori sono 0 oppure 1. Prendiamo due n-uple, x = (x1, x2… *xn ) e y = (y*1, y2… *yn ) tali che x*1 ≤ y1, x2 ≤ y2… *xn ≤ yn. Diremo che la funzione logica f è crescente se, in tal caso, f (x) ≤ f ( y), il che richiama evidentemente l’idea di funzione crescente propria dell’analisi. Con un po’ di attenzione, ci si accorge che ciò equivale a considerare una funzione definita su {0, 1} n *tale che, se uno dei booleani in ingresso passa da «Falso» a «Vero», il valore della funzione non può passare da «Vero» a «Falso».
Nel 1897, il matematico tedesco Richard Dedekind si chiese quante funzioni di questo tipo esistessero per un dato intero n. E si rese subito conto che rischiavano di essere molte! Infatti, vi sono 2*nn-uple da considerare. Definire una funzione logica su questo insieme significa attribuire il valore 0 oppure 1 a ciascuna di queste n-uple. Ci ritroviamo dunque con un totale di funzioni, tra le quali cerchiamo quelle crescenti. Per n* = 5, si tratta già di oltre quattro miliardi di casi da studiare!
