Prendo in prestito il titolo di un agilissimo libretto divulgativo che però, nei contenuti, non rispecchia esattamente ciò che il sottoscritto pensa quando sente parlare di matematica senza numeri.
Quando si dice “matematica”, il pubblico colto pensa quasi sempre ai numeri, all’analisi, all’algebra lineare e matriciale, alla probabilità, alla statistica. Numeri reali, funzioni, derivate, integrali, matrici, distribuzioni, grafici, regressioni, reti neurali, modelli predittivi. In soldoni: “quella roba che si studia a scuola e all’Università”.
È comprensibile. Per secoli, nella formazione tecnica, la matematica è stata presentata soprattutto come arte del calcolo; a fortiori nel mondo anglosassone, dove l’analisi stessa diventa calculus, nel bene e nel male — per quest’ultimo si può sempre andare a rileggere il magnifico How to Write Mathematics di Paul Halmos.
Calcolare bene. Stimare bene. Approssimare bene. Interpolare bene. Ottimizzare bene.
Tutto vero.
Ma non è tutto.
Esiste una vastissima regione della matematica nella quale i numeri non sono i protagonisti principali. È fatta di insiemi, relazioni, ordini, reticoli, grafi, alberi, parole, formule, termini, chiusure, implicazioni, algebre, morfismi, strutture finite, matrici booleane, funzioni logiche, concetti formali.
È una matematica apparentemente meno “numerica”, ma essenziale per comprendere la computazione, la logica, l’organizzazione dell’informazione, la verifica dei sistemi, la rappresentazione della conoscenza, la progettazione degli algoritmi, le basi di dati, la classificazione, l’analisi dei requisiti, il ragionamento automatico e molta parte dell’odierna intelligenza artificiale, ovvero la reginetta del ballo, la queenie delle cheerleader - almeno fino al prossimo cambio di moda, beninteso.
Prima di cominciare il nostro veloce giro turistico, dunque, conviene aprire la carta geografica.
La mappa del viaggio
Attraverseremo diversi continenti matematici che nei corsi universitari più gettonati vengono normalmente presentati come territori separati (o, peggio, del tutto ignorati):
- insiemi, relazioni, grafi e matrici booleane;
- ordini parziali, chiusure, reticoli e formal concept analysis;
- logica, algebra universale e logica algebrica;
- teoria della dimostrazione, Curry–Howard e Herbrand;
- reverse mathematics e forza assiomatica dei teoremi;
- teoria dei modelli e teoria dei modelli finiti;
- combinatoria, strutture finite e complessità computazionale.
La tesi sarà che non stiamo realmente visitando sette continenti indipendenti. Stiamo invece osservando la stessa geografia strutturale da sette punti di vista diversi.
Il problema dei compartimenti stagni
Queste discipline vengono infatti quasi sempre insegnate per silos.
La teoria elementare degli insiemi? Nel primo capitolo, spesso attraversato in fretta. La logica proposizionale e predicativa? In un corso di logica matematica, oppure come propedeutica all’informatica teorica. I grafi? Algoritmica e matematica discreta. I reticoli? Qui le cose vanno anche peggio: compaiono organicamente, se va bene, in qualche esame avanzato di algebra o in un raro corso di teoria dell’ordine.
L’algebra universale rimane generalmente confinata al settore specialistico. La formal concept analysis è una “modernità” ignota alla maggior parte dei laureati STEM. Le matrici booleane vengono spesso trattate come una variante povera delle “vere” matrici numeriche.
E poi ci sono le relazioni binarie, l’ectoplasma ubiquitario della matematica discreta: compaiono prima nei corsi elementari, poi nei database, poi nei grafi, poi nei preorder, poi nelle congruenze, quasi sempre come se ogni apparizione appartenesse a una specie differente.
Le funzioni booleane subiscono un destino analogo. Elettronica digitale, logica, complessità computazionale, teoria dei circuiti, BDD, algoritmi SAT: una ridda di formalismi, notazioni e linguaggi che raramente vengono ricondotti a un ecosistema unitario.
Questa frammentazione può essere didatticamente comoda.
Concettualmente, però, è disastrosa.
E non serve andare a cercare l’eccezione del docente illuminato che introduce trenta pagine di teoria dell’ordine nelle dispense della magistrale e magari fa studiare anche qualche capitolo del Davey-Priestley, o dello studente particolarmente brillante che intercetta queste connessioni nella propria tesi. Il problema è la norma, non l’eccezione o il singolo controesempio. Ed è una norma che attraversa ormai parecchie generazioni di professionisti STEM.
0. Il vero protagonista: il criptomorfismo
Il nucleo della matematica discreta moderna non è un elenco di argomenti. È una rete di criptomorfismi.
Un criptomorfismo, nel senso più fecondo del termine associato alla tradizione di Garrett Birkhoff e Gian-Carlo Rota, non consiste semplicemente nello scrivere un isomorfismo particolarmente elegante. Consiste nel riconoscere che uno stesso oggetto matematico può presentarsi sotto forme differenti, ciascuna delle quali rende visibili proprietà che nelle altre rappresentazioni rimangono nascoste.
Una famiglia di sottoinsiemi può diventare una matrice booleana.
Una relazione binaria può diventare un grafo diretto.
Un grafo può diventare una matrice di adiacenza.
Una chiusura può diventare una famiglia di insiemi chiusi.
Una famiglia di insiemi chiusi può diventare un reticolo.
Un reticolo può essere studiato attraverso il proprio ordine, attraverso ideali e filtri, elementi irriducibili, congruenze, operatori di chiusura.
Una teoria implicazionale può generare una chiusura.
Una chiusura può descrivere dipendenze funzionali, conseguenze logiche, vincoli, concetti, attributi, proprietà invarianti.
Cambia il linguaggio. Cambia la notazione. Cambia il manuale.
La struttura profonda rimane.
Questo è uno dei punti che più spesso manca nella formazione STEM contemporanea. Abbiamo prodotto generazioni di tecnici perfettamente capaci di manipolare matrici reali, distribuzioni di probabilità, regressioni, big data e reti neurali, ma molto meno allenati a riconoscere la medesima struttura quando passa da una tabella a una relazione, da una relazione a un grafo, da un grafo a un ordine, da un ordine a un reticolo, da un reticolo a una logica, da una logica a un sistema di implicazioni, da un sistema di implicazioni a un algoritmo di chiusura.
Eppure la computazione reale vive precisamente lì.
Un database relazionale non è anzitutto una collezione di numeri: è una struttura di relazioni.
Un sistema di tipi è una disciplina formale di classificazione, inferenza e compatibilità.
Un compilatore manipola alberi sintattici, grammatiche, termini, regole di riscrittura, grafi di controllo, reticoli di analisi statica.
Un sistema di verifica esplora stati, transizioni, invarianti, formule e modelli.
Un algoritmo SAT manipola strutture combinatorie di formule booleane.
Un BDD è una rappresentazione canonica compressa di una funzione logica.
Un sistema di classificazione non è soltanto statistica: è anche ordine, inclusione, dipendenza, gerarchia.
La matematica senza numeri non sostituisce la matematica con i numeri.
La affianca e ne completa la grammatica.
1. Primo continente: ordine, chiusura, reticoli
Il caso della formal concept analysis, FCA, è quasi paradigmatico.
Si parte da un’idea elementare: abbiamo oggetti, attributi e una relazione che specifica quali oggetti possiedano quali attributi.
Da questa struttura apparentemente modesta nasce un intero universo matematico.
Un concetto formale è una coppia costituita, da un lato, dall’insieme degli oggetti che condividono certi attributi e, dall’altro, dall’insieme degli attributi comuni a quegli oggetti.
No, non è psicologia dozzinale da rotocalco. Non è vaghezza semantica. È una definizione matematica rigorosa, computabile e replicabile.
Da questa definizione emerge un reticolo dei concetti.
Ed è qui che avviene il salto concettuale.
Una tabella oggetti-attributi diventa una struttura d’ordine. La classificazione non è più un elenco arbitrario di categorie, ma una struttura nella quale concetti più generali e più specifici sono collegati rigorosamente.
L’analisi dei dati diventa analisi delle implicazioni.
Se tutti gli oggetti che possiedono gli attributi A e B possiedono anche C, otteniamo una regola implicazionale. Le implicazioni generano chiusure. Le chiusure determinano insiemi chiusi. Gli insiemi chiusi ordinati per inclusione formano reticoli.
E improvvisamente siamo dentro una delle strutture portanti dell’algebra, della logica e dell’informatica teorica.
Non è un dettaglio specialistico. È un nodo centrale.
La FCA mostra con una chiarezza quasi brutale che classificare non significa semplicemente apporre etichette. Significa costruire una struttura di dipendenze. Capire quali proprietà ne implicano altre. Individuare gerarchie non arbitrarie. Trasformare dati grezzi in una mappa concettuale formalmente controllabile.
In altre parole: passare dalla tabella alla teoria.
Ecco perché questo mondo dialoga così naturalmente con knowledge representation, ontologie, knowledge graph, basi di conoscenza e sistemi ibridi che gravitano oggi attorno all’intelligenza artificiale.
È precisamente il tipo di passaggio che uno STEM del terzo millennio dovrebbe essere allenato a riconoscere.
2. Secondo continente: quando la logica diventa geometria dell’inferenza
La teoria dei reticoli, in questa prospettiva, smette di essere una curiosità algebrica e diventa una grammatica generale dell’organizzazione.
L’insieme delle parti di un insieme, ordinato per inclusione, è un reticolo booleano completo; più in generale, opportune famiglie di insiemi, ordinate per inclusione e dotate dei necessari infimi e supremi, formano reticoli. Le proposizioni ordinate attraverso l’implicazione generano reticoli. Le partizioni possono essere ordinate per raffinamento. Famiglie chiuse, ideali, filtri, congruenze e molte altre costruzioni parlano il linguaggio dell’ordine.
Uno dei luoghi in cui questa costellazione diventa particolarmente impressionante è il rapporto tra logica e teoria dei reticoli.
A prima vista sembrano discipline lontane. La logica parla di proposizioni, dimostrazioni, conseguenze, modelli, verità, inferenza. La teoria dei reticoli parla di ordini parziali, estremi superiori e inferiori, chiusure, ideali, filtri e congruenze.
Ma gran parte di questa distanza è un effetto della didattica. In profondità, moltissima logica è teoria dell’ordine e moltissima teoria dei reticoli è logica cristallizzata in forma algebrica. La logica è (anche) una teoria dei reticoli.
Prendiamo un sistema logico. Le formule possono essere ordinate mediante l’implicazione, scegliendo opportunamente la convenzione. La congiunzione e la disgiunzione assumono allora il ruolo di operazioni reticolari. Il falso e il vero diventano estremi della struttura.
Se identifichiamo le formule logicamente equivalenti otteniamo un oggetto algebrico: l’algebra di Lindenbaum–Tarski. Nella logica proposizionale classica incontriamo algebre booleane. Nella logica intuizionista incontriamo algebre di Heyting. Nelle logiche modali, temporali, descrittive e dinamiche compaiono operatori addizionali, strutture relazionali, algebre booleane con operatori e costruzioni affini.
La deduzione può essere letta come ordinamento. La conseguenza come chiusura. La teoria come insieme chiuso — e, nelle opportune presentazioni algebriche, come filtro. L’equivalenza logica come congruenza. Non è una metafora suggestiva da usare alla lavagna. È struttura.
Ogni volta che diciamo “da queste premesse segue questa conclusione” stiamo implicitamente parlando di un operatore di conseguenza. Dal punto di vista strutturale, un tale operatore si comporta come un operatore di chiusura: prende un insieme di formule e restituisce tutto ciò che ne segue.
Le teorie sono precisamente gli insiemi chiusi rispetto a questa operazione. E gli insiemi chiusi, ordinati per inclusione, formano naturalmente strutture reticolari. Conseguenza, chiusura, ordine, reticolo.
Ancora la stessa figura.
A questo punto la logica smette di apparire come una raccolta di regolette sintattiche vecchie quanto Aristotele e diventa qualcosa di molto più interessante:
una geometria dell’inferenza.
3. Terzo continente: algebra universale e logica algebrica
Il passo successivo conduce direttamente all’algebra universale.
L’algebra universale non studia questo o quel particolare gruppo, anello, reticolo, monoide o semigruppo. Cerca la forma comune dietro queste costruzioni.
Che cosa significa avere un insieme dotato di operazioni? Che cosa significa che certe identità valgono? Che cosa sono termini, equazioni, sottostrutture, prodotti, omomorfismi, quozienti, congruenze? Quali proprietà dipendono dalla firma? Quali dalle identità? Quali sono preservate da prodotti, sottostrutture e immagini omomorfe?
La logica algebrica porta queste domande dentro i sistemi deduttivi.
La logica classica può essere rappresentata attraverso algebre booleane. Quella intuizionista attraverso algebre di Heyting. Varie logiche modali attraverso opportune espansioni algebriche.
La logica algebrica universale compie poi un passo ulteriore: studia sistematicamente quando e in quale senso un sistema deduttivo possa essere algebrizzato, quali informazioni deduttive corrispondano a informazioni equazionali, quali filtri logici corrispondano a congruenze e quali classi algebriche rappresentino determinate forme di ragionamento.
Qui i due linguaggi — logico e algebrico — non sono semplicemente accostati.
Spesso si traducono l’uno nell’altro.
Le formule diventano termini. Le equivalenze deduttive diventano congruenze. Le regole logiche diventano proprietà algebriche. Le teorie assumono comportamento filtrale. Le classi di modelli algebrici si organizzano in varietà o quasivarietà.
Naturalmente non tutte le logiche sono algebrizzabili allo stesso modo. Ed è proprio qui che la teoria si fa interessante: esistono gradi, condizioni, casi forti e casi deboli. Alcune logiche possiedono una controparte algebrica quasi perfetta; altre richiedono strumenti più fini; altre mostrano precisamente il punto nel quale la corrispondenza si incrina.
La lezione generale, però, rimane. La logica non vive isolata. Ha una struttura algebrica, ordinata, reticolare e modellistica.
4. Quarto continente: le dimostrazioni sono oggetti
Esiste poi un territorio che rimane quasi completamente invisibile alla maggior parte dei professionisti STEM: la teoria della dimostrazione.
Di solito si pensa alla dimostrazione come a un prodotto finito: un testo, una successione di passaggi, una giustificazione scritta di un teorema.
La logica moderna ha insegnato invece a guardare le dimostrazioni come oggetti matematici.
Non soltanto strumenti per raggiungere una verità, ma strutture formali che possono essere trasformate, normalizzate, confrontate e studiate.
Una dimostrazione possiede una forma. Una complessità. Regole di costruzione. Riduzioni. Possibili eliminazioni di passaggi intermedi. Contenuto computazionale.
Qui entrano Hilbert, Gentzen, Gödel, Herbrand, Kleene, Prawitz, Girard, Troelstra, Schwichtenberg, Wainer e molti altri. Non come medagliere storico da blog “scientifico”, non come namedropping per una sfilza di teoremi più o meno famosi da sciorinare in sede di esame, ma come coordinate di una geografia storica e concettuale.
Gentzen, attraverso il calcolo dei sequenti e l’eliminazione del taglio, mostra che le dimostrazioni hanno una dinamica interna.
Prawitz e la deduzione naturale mettono al centro la forma dell’inferenza e la normalizzazione.
Girard, attraverso la logica lineare, mostra che persino le risorse logiche possono essere trattate strutturalmente.
Per uno STEM abituato a pensare agli algoritmi come oggetti analizzabili, tutto questo dovrebbe essere quasi naturale.
Se un algoritmo può essere studiato in termini di struttura, costo, normalizzazione, trasformazione e correttezza, perché una dimostrazione dovrebbe essere soltanto il certificato finale destinato a convincere un lettore?
Anche la prova possiede un’architettura.
Proposizioni come tipi, dimostrazioni come programmi
Qui incontriamo una delle idee più profonde della logica del Novecento: la corrispondenza di Curry–Howard.
Le proposizioni possono essere viste come tipi e le dimostrazioni come programmi. Dimostrare una proposizione significa costruire un termine del tipo corrispondente. La normalizzazione della prova corrisponde all’esecuzione o alla semplificazione del programma.
L’implicazione corrisponde al tipo funzione. La congiunzione al prodotto. La disgiunzione alla somma. L’assurdo al tipo vuoto.
Non è la solita vaga analogia pedagogica da manuale undergrad americano. È una corrispondenza tecnica, rigorosa e straordinariamente fertile, che attraversa logica intuizionista, lambda-calcolo, teoria dei tipi, linguaggi funzionali e proof assistant quali Coq, Agda, Lean e Isabelle.
A questo punto la formula proofs as programs smette di essere uno slogan.
La dimostrazione è computazione. Il programma è dimostrazione. Il tipo è specifica.
La correttezza non deve necessariamente essere appiccicata al programma dopo la sua costruzione come certificazione esterna: può essere incorporata nella costruzione stessa dell’oggetto.
Per chi lavora con software, sistemi critici, linguaggi, compilatori e specifiche formali, questa è una conferma operativa — senza alcuna necessità di trasformare ogni ingegnere in uno specialista di teoria dei tipi.
Herbrand: dai quantificatori alla combinatoria
Accanto a Curry–Howard va ricordato il teorema di Herbrand, uno dei più grandi ponti tra logica del primo ordine, combinatoria e computazione.
In termini estremamente generali, il teorema mostra come, in opportune condizioni e forme, il problema logico del primo ordine possa essere riportato a famiglie di istanze proposizionali costruite dai termini del linguaggio.
Una parte del ragionamento quantificato viene così ricondotta a un problema combinatorio di istanziazione.
Questo non rende magicamente "facile" la logica del primo ordine FOL. Spiega però perché il legame tra quantificatori, termini, sostituzioni, alberi di ricerca, dimostrazione automatica e calcolo simbolico sia tanto profondo.
Herbrand è uno dei punti nei quali diventa evidente che la logica non è un ornamento filosofico.
È una tecnologia concettuale che trasforma problemi di conseguenza in problemi di costruzione, enumerazione, istanziazione e ricerca.
Dalla risoluzione ai tableaux, dai prover automatici ai sistemi di riscrittura, quel nucleo continua a riapparire.
5. Quinto continente: quanto “costa” un teorema?
Esiste poi una disciplina dal nome quasi paradossale: la reverse mathematics.
La matematica ordinaria procede, almeno idealmente, in avanti: scegliamo assiomi e regole e da questi dimostriamo teoremi.
La reverse mathematics rovescia la domanda.
Dato un teorema della matematica ordinaria, quali assiomi sono realmente necessari per dimostrarlo?
Non "quali assiomi usiamo tradizionalmente", magari in modo enormemente sovrabbondante, come sembrano suggerire certe monografie: genuflessione all'altarino dei Padri Fondatori, manciata di assiomi storici buttati lì senza la minima giustificazione logica come un reliquiario medievale, e poi via a testa bassa con definizione-teorema-dimostrazione-corollari-GOTO10, per 480 pagine.
Parliamo di quali assiomi servono davvero. Qual è la forza logica esatta del risultato?
È una domanda straordinaria perché costringe a guardare un teorema non soltanto come una proposizione vera, ma come un oggetto dotato di un peso fondazionale, dimostrativo e computazionale.
Un teorema di analisi, combinatoria, algebra, teoria degli ordini, teoria dei grafi o topologia può rivelarsi equivalente — sopra un opportuno sistema base — a un principio di comprensione, compattezza, ricorsione o scelta.
A quel punto il teorema smette di essere un risultato isolato. Diventa una misura tecnica della struttura logica necessaria per ottenerlo.
Il programma inaugurato da Harvey Friedman e sistematizzato in maniera canonica da Stephen Simpson ha mostrato quanto questa prospettiva sia fertile. Attorno a esso si intrecciano computabilità, proof theory, combinatoria, teoria dei modelli computabile, analisi costruttiva e il lavoro di numerosi logici contemporanei.
Il quadro classico opera spesso entro sottosistemi dell’aritmetica del secondo ordine, usata come laboratorio sufficientemente espressivo per codificare una quantità sorprendente di matematica ordinaria: insiemi di naturali, successioni, alberi, grafi numerabili, funzioni, relazioni e molte strutture discrete.
Dentro questo laboratorio emergono i celebri Big Five, cinque grandi sistemi assiomatici nei quali ricadono, per rigorose equivalenze sopra un sistema base, moltissimi teoremi della matematica corrente.
La reverse mathematics insegna così che i teoremi hanno una specie di fisiologia logica.
Alcuni sono assiomaticamente deboli ed effettivi. Altri richiedono principi non costruttivi, forme di compattezza, di comprensione o di ricorsione più potenti.
Non basta domandare se un teorema sia vero. Possiamo domandare quanto costa ottenerlo.
Per uno STEM il parallelismo dovrebbe essere immediato. In ingegneria chiediamo quanto costa un algoritmo: tempo, memoria, scalabilità, precisione, stabilità, robustezza.
La reverse mathematics pone la stessa domanda, su un altro livello:
- Quali risorse logiche sto consumando?
- Posso ottenere il risultato in un sistema assiomaticamente più debole?
- La dimostrazione contiene informazione computazionale estraibile?
- Utilizza principi non costruttivi eliminabili, oppure quei principi sono davvero indispensabili?
Qui il dialogo con il proof mining, associato in particolare al lavoro di Ulrich Kohlenbach, diventa naturale: da dimostrazioni apparentemente non costruttive, puramente esistenziali, si possono talvolta estrarre ugualmente limiti quantitativi, algoritmi, tassi di convergenza e altra informazione computazionale.
Ancora una volta la prova, la dimostrazione formale, non è soltanto garanzia di verità. È un oggetto da analizzare.
6. Sesto continente: dai linguaggi ai modelli
La logica, naturalmente, non è soltanto teoria delle dimostrazioni. È anche teoria dei modelli.
Se la proof theory guarda alle prove, la model theory guarda alle strutture nelle quali le formule vengono interpretate. Una formula non vive nel vuoto. Viene interpretata sopra un dominio, con relazioni, funzioni, costanti e operazioni.
La teoria dei modelli studia precisamente il rapporto tra linguaggi formali e strutture matematiche.
- Che cosa può esprimere un linguaggio?
- Quali strutture soddisfano una teoria?
- Quando due strutture sono indistinguibili dal punto di vista del linguaggio considerato?
- Che cosa significa definire una proprietà?
- Quali proprietà sono preservate da determinate costruzioni?
- Che cosa può essere detto all’interno di un formalismo e che cosa ne rimane necessariamente fuori?
Da Tarski a Robinson, da Łoś a Chang e Keisler, da Hodges a molte delle sistemazioni moderne, la teoria dei modelli ha trasformato queste domande in un enorme programma matematico.
Per uno STEM possiede inoltre un valore metodologico fondamentale: insegna a non confondere il linguaggio con la struttura.
- Una cosa è la sintassi con cui descriviamo un sistema. Un’altra è il sistema interpretato.
- Una cosa è una specifica. Un’altra è la classe dei modelli che la soddisfano.
- Una cosa è scrivere vincoli. Un’altra è capire quali strutture li realizzano.
- Una cosa è la deduzione sintattica. Un’altra è la soddisfacibilità semantica.
Questa distinzione è centrale per database, ontologie, formal methods, semantica dei linguaggi, knowledge representation, verifica e sistemi di regole.
Il caso decisivo delle strutture finite
E poi arriva la teoria dei modelli finiti. La teoria dei modelli classica ha lavorato con straordinaria potenza su strutture infinite. L’informatica, però, lavora continuamente con oggetti finiti: database, grafi, automi, macchine a stati, istanze combinatorie, strutture di memoria, modelli finiti di sistemi.
La finite model theory nasce precisamente dall’esigenza di studiare la logica sopra strutture finite, dove molte proprietà della teoria classica cambiano radicalmente. Qui incontriamo Fagin, Immerman, Vardi, Libkin, Grädel, Ebbinghaus, Otto, Dawar e molti altri.
Ed emerge una delle connessioni più eleganti dell’informatica teorica moderna: quella tra espressività logica e complessità computazionale.
Il teorema di Fagin, per esempio, lega NP alla logica esistenziale del secondo ordine sulle strutture finite. Il filone Immerman–Vardi mette in relazione logiche a punto fisso e calcolo in tempo polinomiale sopra strutture finite opportunamente ordinate.
A questo punto la domanda non è più soltanto:
“Quanto tempo serve per calcolare questa proprietà?”
Diventa anche:
“Quale linguaggio logico è abbastanza potente per descriverla?”
Non soltanto algoritmi e macchine, dunque.
Formule e strutture.
Non soltanto esecuzione.
Definibilità.
Una struttura finita può essere un grafo. Il grafo può essere una relazione binaria. La relazione può essere rappresentata da una matrice booleana. La matrice descrive una struttura interrogabile mediante formule. Le formule appartengono a un linguaggio. Il linguaggio possiede una certa potenza espressiva. Quella potenza può essere collegata a una classe di complessità.
In pochi passaggi abbiamo attraversato grafi, relazioni, matrici booleane, logica, model theory e computational complexity.
Questo è il tipo di connessione che una formazione per compartimenti stagni tende a rendere invisibile.
7. Settimo continente: grafi, matrici e combinatoria
Lo stesso chiarimento va fatto per la teoria dei grafi.
Nei corsi ordinari, soprattutto in quelli destinati all’informatica applicata, essa viene spesso ridotta a un repertorio di algoritmi: BFS, DFS, cammini minimi, spanning tree, ordinamento topologico, componenti connesse, flussi.
Tutto indispensabile.
Ma identificare la teoria dei grafi con questo prontuario sarebbe come identificare l’analisi matematica con una tabella di primitive.
Un grafo è anzitutto una struttura relazionale.
Può rappresentare adiacenza, dipendenza, compatibilità, raggiungibilità, causalità, precedenza, conflitto, comunicazione, trasformazione, inclusione, copertura.
Può diventare automa, sistema di transizione, modello di Kripke, diagramma di dipendenza, rete di implicazioni, struttura di incidenza, oggetto combinatorio estremale.
E il legame con ordine e reticoli è immediato.
Un ordine parziale può essere rappresentato mediante il suo diagramma di Hasse. La raggiungibilità in un DAG può generare un ordine. Dipendenze tra moduli, grafi di precedenza, sistemi di build e gerarchie di tipi possiedono naturalmente una struttura ordinata.
La chiusura transitiva trasforma informazione relazionale locale in informazione globale.
La teoria dei matroidi porta ancora oltre questa unificazione, astraendo simultaneamente fenomeni di indipendenza che appaiono nell’algebra lineare e nella teoria dei grafi.
Non bisogna fermarsi ai pallini e alle linee.
Un grafo può essere una relazione.
Una relazione può essere una matrice booleana.
La composizione di relazioni può diventare un prodotto matriciale sopra il semianello opportuno.
Una relazione di raggiungibilità può generare un ordine.
Un ordine può generare un reticolo di ideali.
Un reticolo può rappresentare concetti, teorie e chiusure.
Ancora una volta, non abbiamo cambiato necessariamente oggetto.
Abbiamo cambiato rappresentazione.
Non tutte le matrici abitano in R
Anche le matrici, entrando in questo mondo, cambiano natura.
Non sono necessariamente matrici reali piene di coefficienti da sommare e moltiplicare.
Possono essere matrici booleane, matrici di incidenza, matrici di adiacenza, matrici su semianelli, matrici tropicali, matrici che rappresentano relazioni, vincoli, coperture, dipendenze e compatibilità.
La potenza di una matrice booleana può descrivere cammini. La moltiplicazione matriciale può diventare composizione di relazioni. La chiusura transitiva può essere vista come saturazione.
La distinzione scolastica tra “algebra lineare” e “matematica discreta” comincia così ad assottigliarsi.
Ciò che conta non è la forma tipografica rettangolare della matrice.
Conta la struttura algebrica nella quale quella matrice vive.
Una matrice reale, una matrice booleana, una matrice di incidenza di un ipergrafo e una matrice oggetti-attributi della FCA possono sembrare graficamente identiche.
Sono tutte tabelle rettangolari.
Ma il loro significato dipende dalle operazioni ammesse, dalle equivalenze considerate, dalle chiusure generate, dai morfismi che intendiamo preservare.
Lo STEM maturo non domanda soltanto:
“Quali sono gli elementi della matrice?”
Domanda:
“Quale struttura sta rappresentando?”
Questa è alfabetizzazione strutturale.
8. La combinatoria come laboratorio delle rappresentazioni
Lo stesso vale per la combinatoria delle famiglie finite.
A prima vista può sembrare un settore composto da problemi quasi ricreativi: quanti sottoinsiemi, quante configurazioni, quali intersezioni, quali estremi, quali coperture.
Sotto la superficie troviamo però vettori booleani, strati del cubo discreto, ordini per inclusione, anticatene, famiglie intersecanti, ipergrafi, matrici di incidenza, vincoli di margine, problemi estremali.
La medesima entità cambia continuamente pelle:
- insieme;
- vettore 0/1;
- riga di una matrice;
- punto del cubo booleano;
- elemento di un poset;
- iperarco;
- assegnamento logico;
- caratteristica di una proprietà.
Vedere questi passaggi non è estetica matematica.
È capacità progettuale.
Quando una famiglia di insiemi diventa una matrice booleana, possiamo applicare strumenti matriciali.
Quando diventa un ipergrafo, possiamo usare la teoria degli ipergrafi.
Quando diventa un sistema di vincoli, possiamo ricorrere a SAT, CSP e tecniche combinatorie.
Quando diventa un reticolo, possiamo studiare chiusure e implicazioni.
Quando diventa una struttura logica, possiamo chiederne modelli e definibilità.
Quando diventa un oggetto computazionale, possiamo rappresentarlo, comprimerlo, enumerarlo e manipolarlo.
La forza non consiste nel cambiare nome alle cose.
Consiste nel cambiare punto di vista scegliendo quello più adatto, più efficiente e più potente, senza perdere l’oggetto.
9. Dal manuale al mondo reale
È precisamente questo ciò che manca quando la formazione procede per silos.
Lo studente vede “grafi” in un corso, “logica” in un altro, “algebra” in un altro, “database” in un altro, “machine learning” in un altro.
Poi entra nel mondo reale e trova sistemi ibridi nei quali tutto è intrecciato: dati relazionali, vincoli logici, grafi di dipendenza, tassonomie, gerarchie, modelli probabilistici, regole, ontologie, modelli predittivi, pipeline software, controlli di coerenza, sicurezza, verifica e tracciabilità.
A quel punto la domanda non è più:
“So calcolare?”
La domanda decisiva diventa:
“So riconoscere la struttura?”
Viviamo in un’epoca nella quale la matematica numerica ha ottenuto un’enorme visibilità attraverso machine learning, ottimizzazione, deep learning, transformer e modelli generativi.
Ed è perfettamente giusto che sia così.
Algebra lineare, calcolo numerico, probabilità, statistica, teoria dell’informazione e ottimizzazione sono indispensabili.
Ma l’esplosione dell’intelligenza artificiale non rende meno importante la matematica discreta e logica.
La rende più necessaria.
Ogni sistema sufficientemente potente deve infatti essere rappresentato, controllato, verificato, interrogato, limitato, spiegato e integrato.
Un modello statistico può produrre output probabilisticamente plausibili.
Un sistema industriale, giuridico, medico, finanziario, aerospaziale o safety-critical richiede però anche vincoli, logiche, tracciabilità, coerenza, auditabilità, gerarchie di autorizzazione, ontologie, classificazioni e invarianti.
Richiede di sapere che cosa può accadere.
Che cosa non deve accadere.
Quali stati siano raggiungibili.
Quali transizioni siano lecite.
Quali proprietà vengano preservate.
Quali dipendenze siano ammesse.
Quali astrazioni siano corrette.
Queste non sono domande puramente statistiche.
Sono domande strutturali.
10. Due grammatiche, non due matematiche
Il futuro non appartiene a chi contrappone simbolico e subsimbolico, numerico e discreto, statistico e logico. Non appartiene a chi ancora si ostina a citare frasi come "La combinatoria? Bassifondi della topologia" in tutte le sue spocchiose varianti.
Appartiene a chi sa far dialogare rappresentazioni diverse e diversi punti di vista.
Ma per farli dialogare bisogna possedere entrambe le grammatiche.
Una è ubiqua nella formazione contemporanea: analisi, numeri, matrici reali, probabilità, statistica, ottimizzazione.
L’altra, per decenni trattata quasi da Cenerentola nonostante tradizioni scientifiche gigantesche — dalla scuola magiara a Gian-Carlo Rota, da Wilf a Zeilberger e moltissimi altri — è diventata con la computazione una delle protagoniste indiscutibili del nostro tempo.
Non basta conoscere le reti neurali se non si comprendono grafi, logiche, relazioni, ordini, tipi e vincoli.
Non basta conoscere la statistica se non si capisce che molte forme di informazione non nascono come variabili numeriche, ma come dipendenze, categorie, attributi, inclusioni e regole.
Non basta conoscere l’algebra lineare se non si comprende che una matrice può rappresentare qualcosa di radicalmente diverso da una trasformazione lineare sopra uno spazio vettoriale reale.
11. La matematica delle forme
La matematica senza numeri è, in questo senso, la matematica delle forme.
Forme esatte. Rigorose. Trasformabili.
È la matematica che ci dice quando due descrizioni rappresentano la stessa struttura.
Quando una classificazione è una chiusura.
Quando una gerarchia è un ordine.
Quando una tabella è una relazione.
Quando una relazione è un grafo.
Quando un grafo è una matrice.
Quando una matrice è definita su un semianello, e il significato di somma, prodotto e composizione dipende dalla struttura algebrica scelta.
Quando una famiglia di insiemi è un reticolo.
Quando un reticolo diventa algebra della logica.
Quando una logica possiede una semantica algebrica.
Quando una teoria è un insieme chiuso di conseguenze.
Quando una prova contiene un programma.
Quando un teorema possiede una precisa forza assiomatica.
Quando una classe di complessità può essere vista come potenza espressiva.
In questa prospettiva le discipline non si giustappongono.
Si illuminano reciprocamente.
La teoria degli insiemi fornisce un linguaggio di base.
Le relazioni descrivono connessioni, equivalenze, ordini e composizioni.
I grafi rendono visibili e computabili molte strutture relazionali.
Le matrici booleane rendono operative relazioni finite.
La combinatoria studia configurazioni, famiglie, estremi e vincoli.
La teoria dell’ordine organizza gerarchie e dipendenze.
La teoria dei reticoli studia combinazioni, chiusure, ideali, filtri e congruenze.
La formal concept analysis trasforma contesti oggetti-attributi in reticoli di concetti.
L’algebra universale generalizza operazioni, identità, omomorfismi e quozienti.
La logica studia conseguenze, modelli, dimostrazioni e definibilità.
La teoria della dimostrazione studia le prove come strutture.
La reverse mathematics misura la forza assiomatica dei teoremi.
La teoria dei modelli studia il rapporto tra linguaggi e interpretazioni.
La teoria dei modelli finiti porta tutto questo nel mondo delle strutture discrete effettivamente manipolate dalla computazione.
L’informatica teorica traduce questa architettura in automi, linguaggi, algoritmi, complessità, verifica e rappresentazioni canoniche.
Non sono province isolate.
Sono una costellazione.
12. Vedere la costellazione
Il termine “costellazione” è appropriato.
Le stelle sono distinte. Il disegno appare soltanto quando si vedono le connessioni.
Chi osserva un singolo punto luminoso vede un corso universitario.
Chi vede le connessioni vede una mappa.
Ed è questa mappa che serve oggi.
Serve perché i sistemi moderni sono complessi, ibridi e stratificati.
Serve perché la computazione non è soltanto calcolo numerico, ma manipolazione di strutture simboliche e discrete.
Serve perché l’informazione non è soltanto dato, ma relazione tra dati.
Serve perché la conoscenza non è soltanto predizione, ma organizzazione di concetti e implicazioni.
Serve perché la correttezza non è soltanto performance, ma rispetto di proprietà formali.
Serve perché l’astrazione non è un ornamento filosofico: è lo strumento con il quale controlliamo la complessità.
Uno STEM realmente formato non dovrebbe uscire dal proprio percorso sapendo soltanto diagonalizzare matrici, stimare parametri, addestrare modelli, calcolare probabilità o manipolare tensori.
Dovrebbe sapere anche che un ordine parziale non è un dettaglio; che un reticolo non è una stranezza; che una relazione di equivalenza è una macchina concettuale potentissima; che una chiusura è una forma generale di conseguenza; che una matrice booleana può rivelare aspetti che una matrice reale semplicemente non rappresenta.
Dovrebbe sapere che una famiglia di insiemi può nascondere un intero universo combinatorio.
Che una gerarchia ben costruita è matematica.
Che una classificazione rigorosa è già teoria.
Che un’implicazione tra attributi può essere importante quanto una regressione.
Dovrebbe sapere che un teorema non possiede soltanto una dimostrazione, ma anche una forza logica; che risultati apparentemente lontani possono richiedere le stesse risorse assiomatiche; che una dimostrazione può contenere informazione computazionale.
Dovrebbe sapere che la logica non è un rito scolastico di tavole di verità, ma una scienza delle conseguenze, dei modelli, delle prove, delle strutture e della computazione.
Dovrebbe sapere che una specifica può diventare un tipo, un programma un termine, la correttezza una costruzione.
Che un database finito è una struttura logica.
Che una query può essere una formula.
Che un linguaggio ha una potenza espressiva.
Che una proprietà può essere computabile ma non esprimibile nel formalismo che abbiamo scelto.
In definitiva, dovrebbe sapere che la matematica non è soltanto calcolo di quantità.
È scienza delle strutture possibili.
La quantità misura.
La struttura organizza.
La quantità risponde a:
“Quanto?”
La struttura risponde a domande differenti:
“Com’è fatto?”
“Da che cosa dipende?”
“Che cosa implica?”
“Che cosa conserva?”
“Che cosa cambia se identifico questi elementi?”
“Quali trasformazioni rispettano l’oggetto?”
“Quale rappresentazione rende il problema trattabile?”
“Quale linguaggio è abbastanza potente per descriverlo?”
“Quale prova certifica ciò che affermo?”
“Quali modelli soddisfano questa specifica?”
Sono domande diverse.
Entrambe necessarie.
La grande povertà di molta formazione tecnica contemporanea consiste nell’avere assolutizzato la prima famiglia di domande e relegato la seconda agli specialisti.
Ma nel mondo reale, e soprattutto nel mondo computazionale, la seconda famiglia è ovunque.
Ogni architettura software, sistema di dati, linguaggio, protocollo, modello di autorizzazione, ontologia, knowledge graph, sistema di verifica, compilatore, motore inferenziale, algoritmo combinatorio e pipeline di controllo della qualità è una risposta strutturale prima ancora che numerica.
Per questo la matematica senza numeri non è una matematica minore.
È la parte della matematica che insegna a vedere l’ossatura.
E chi vede l’ossatura vede molto più lontano.
Per chi volesse approfondire, propongo un minimo di bibliografia essenziale.
