Come si dimostrano proprietà combinatorie e strutture induttive in Lean?

Nel contesto della matematica discreta formale, Lean offre un ambiente rigoroso e potente per definire e dimostrare proprietà di insiemi, funzioni e strutture dati attraverso una combinazione di metodi classici e meccanismi automatizzati. Un esempio emblematico è la dimostrazione dell’esistenza di due elementi coprimi in un insieme con n+1 elementi contenuto nell’intervallo $[0, 2n)$. Questo fatto, apparentemente semplice, si formalizza in Lean utilizzando il principio del piccione (pigeonhole principle) e funzioni di conteggio delle fibre. Lean semplifica alcune parti di questa dimostrazione con strumenti come il tactic omega, che automatizza la verifica di disuguaglianze aritmetiche, riducendo notevolmente il carico formale per l’utente.

La seconda parte dell’estratto riguarda le definizioni induttive, fulcro della rappresentazione di dati e strutture ricorsive in Lean. Ad esempio, la definizione della lista (List α) illustra come Lean consenta di costruire insiemi di oggetti a partire da un caso base (lista vuota, nil) e da un costruttore ricorsivo (cons), che aggiunge un elemento all’inizio di una lista. Questo paradigma permette di definire funzioni ricorsive come append (concatenazione) e map (applicazione di una funzione ad ogni elemento della lista) in modo naturale e rigoroso, garantendo l’esistenza di base e la corretta costruzione delle definizioni.

Lean formalizza inoltre le proprietà fondamentali di queste operazioni, come le uguaglianze definitorie (rfl), e permette di dimostrare teoremi per induzione strutturale su queste definizioni. L’uso di namespace temporanei aiuta a isolare definizioni sperimentali evitando conflitti con la libreria standard, mantenendo il codice pulito e modulare.

L’estratto illustra anche la definizione di tipi induttivi più complessi, come gli alberi binari (BinTree), che si costruiscono a partire da un albero vuoto e nodi con due sottoalberi. Vengono definiti funzioni di misura come size (dimensione) e depth (profondità), con una disuguaglianza importante che lega la dimensione alla profondità attraverso potenze di due, sottolineando la relazione tra struttura e grandezza in questi tipi.

Nel complesso, Lean facilita la formalizzazione rigorosa della matematica discreta combinando definizioni induttive, funzioni ricorsive, strumenti di automatizzazione e tecniche di induzione strutturale. Questo approccio è fondamentale non solo per la verifica formale di teoremi ma anche per la progettazione e l’analisi di algoritmi e strutture dati nella scienza computazionale.

Infine, la formalizzazione in Lean richiede un’attenzione particolare alla gestione della complessità, mediante l’uso di strumenti come namespace, tactic automatizzati e tecniche di modularizzazione, che favoriscono la scalabilità dei progetti formali, rendendo sostenibile anche la formalizzazione di teorie molto articolate.

Come si dimostra la suriettività nel teorema cinese del resto e il ruolo delle algebre di polinomi

La dimostrazione della suriettività della mappa cinese, fondamentale nel teorema cinese del resto, si basa su una raffinata comprensione della coprimalità degli ideali e sull’uso sapiente di induzioni sulle insiemi finiti. La nozione di coprimalità, o più precisamente di co-massimalità, è espressa attraverso diversi equivalenti: dall’uguaglianza dell’addizione di ideali, all’esistenza di certi elementi che soddisfano condizioni di annullamento modulo ideali, fino a proprietà di disgiunzione codimensionale. Queste equivalenze sono essenziali per manovrare la dimostrazione in modo efficace.

L’uso dell’induzione su insiemi finiti (Finset) consente di estendere la proprietà di coprimalità da singole coppie di ideali a intersezioni finite di ideali, sfruttando la proprietà che l’intersezione di ideali coprimi con un altro ideale rimane coprima. Tale passo è cruciale, poiché consente di passare da una verifica locale (su coppie di ideali) a una proprietà globale (sull’intersezione di tutti gli ideali considerati). Questo risultato è formalizzato tramite la proprietà isCoprime_Inf, la quale si basa su una serie di passaggi che coinvolgono manipolazioni di somme e prodotti di ideali e la struttura dell’anello considerato.

La suriettività della chineseMap si ottiene poi combinando questi risultati con il fatto che ogni classe di resto modulo un ideale ha un rappresentante nell’anello originale, ossia si può scegliere un elemento che rappresenta ogni elemento del quoziente. L’esistenza di elementi idempotenti particolari (gli e_i nella dimostrazione) permette di costruire un elemento dell’anello la cui immagine tramite chineseMap coincide con qualsiasi elemento del prodotto diretto dei quozienti, garantendo così la suriettività.

Passando alle algebre, la nozione di algebra sopra un anello commutativo è incarnata da un semianello A dotato di un morfismo di anelli che rispetta la struttura di scala. Questo morfismo, detto struttura o algebraMap, definisce una moltiplicazione scalare che conferisce all’algebra proprietà simili a quelle di uno spazio vettoriale, ma in un contesto più generale e algebrico. Il fatto che l’algebraMap sia un morfismo di anelli garantisce la coerenza con le operazioni di somma e prodotto e permette di estendere risultati e tecniche note dai semianelli agli anelli e alle loro algebre.

Un esempio paradigmatico è l’algebra dei polinomi univariati R[X] con coefficienti in R. Qui l’algebraMap invia ogni elemento r di R nella costante corrispondente in R[X], denotata da C r. La variabile indeterminata X rappresenta la base del polinomio e permette di definire strutture complesse e funzioni polinomiali. Le proprietà degli operatori C e X, così come le regole di calcolo nei polinomi, sono fondamentali per le operazioni algebriche e per la formalizzazione di teoremi come la formula di fattorizzazione, la valutazione in un punto, e lo studio delle radici.

La definizione del grado di un polinomio si presenta come un problema sottile a causa della particolare natura del polinomio nullo. Si distinguono due definizioni: la versione con grado naturale (Polynomial.natDegree), che assegna grado zero al polinomio nullo, e la versione con grado in WithBot N, che estende i naturali con un elemento inferiore (⊥) per gestire il polinomio nullo in modo più coerente. La seconda definizione è più elegante nel formalismo algebrico e consente di stabilire formule per il grado di prodotti di polinomi, anche in presenza di zero divisori assenti.

Le operazioni di composizione polinomiale, la valutazione e la considerazione delle radici sono poi sviluppate rigorosamente, facendo uso di proprietà di morfismi e di strutture algebriche sottostanti. Il concetto di radice è definito tramite un predicato che identifica gli elementi annullanti un polinomio e, in domini privi di zero divisori, si formalizza la nozione di radici con molteplicità, realizzando una corrispondenza tra grado e numero massimo di radici.

È importante inoltre riconoscere che polinomi definiti su un anello di coefficienti R possono avere radici in estensioni algebriche di R, aspetto non coperto dalla sola definizione interna all’anello di coefficienti. Per trattare questi casi è necessario ampliare la struttura algebrica, introducendo polinomi su anelli estesi, come passare da Q[X] a R o da R[X] a C, e sviluppando la teoria delle estensioni di anelli e algebre.

La trattazione rigorosa di questi concetti è alla base di molte aree della matematica moderna, dalla teoria dei numeri alla geometria algebrica, passando per la teoria dei moduli e la teoria delle rappresentazioni. Comprendere la struttura degli ideali, delle loro intersezioni e delle algebre costruite sopra anelli commutativi è fondamentale per affrontare problemi complessi di algebra astratta e applicata.

Che cos'è uno spazio quoziente e come funziona attraverso gli endomorfismi e le matrici?

Il vero potere della costruzione dello spazio quoziente si manifesta attraverso la sua proprietà universale: ogni mappa lineare $\varphi : V \to W$ che si annulla su $E$, cioè tale che $E \subseteq \ker(\varphi)$, fattorizza univocamente attraverso lo spazio quoziente. In simboli, esiste una mappa $\tilde{\varphi} : V \⧸ E \to W$ tale che $\varphi = \tilde{\varphi} \circ \text{mkQ}$. Questa estensione è definita da $\text{liftQ}$.

Nel contesto degli endomorfismi $\phi : V \to V$, cioè le applicazioni lineari dallo spazio vettoriale a se stesso, emerge una struttura algebrica ancora più ricca. Gli endomorfismi formano un'algebra su $K$, e possiamo valutarvi polinomi: dato un polinomio $P \in K[X]$, l’applicazione $\text{aeval}(\phi, P)$ rappresenta il risultato della valutazione di $P$ in $\phi$. In particolare, $\text{aeval}(\phi, X) = \phi$, e se due polinomi $P, Q$ sono coprimi, allora i rispettivi nuclei delle valutazioni su $\phi$, $\ker(P(\phi))$ e $\ker(Q(\phi))$, sono in somma diretta e forniscono il nucleo di $(PQ)(\phi)$: $\ker(P(\phi)) \oplus \ker(Q(\phi)) = \ker((PQ)(\phi))$.

Il teorema di Cayley-Hamilton afferma che ogni endomorfismo $\phi$ annulla il proprio polinomio caratteristico: $\text{aeval}(\phi, \text{charpoly}(\phi)) = 0$. Questa identità è uno strumento essenziale per il calcolo simbolico e per la riduzione di espressioni contenenti potenze di endomorfismi.

È importante notare che questa notazione non è ottimizzata per il calcolo numerico ma per la dimostrazione formale: il linguaggio Lean utilizza funzioni piuttosto che array per rappresentare matrici e vettori. Inoltre, nella moltiplicazione, il significato di vettore riga o colonna è implicito nella posizione dell’operando: $M *ᵥ v$ rappresenta una matrice che agisce da sinistra su un vettore colonna, mentre $v ᵥ* M$ rappresenta