Dimostrazioni Formali come Percorsi
Un sistema di dimostrazione formale definisce un insieme di assiomi & regole di inferenza. Ogni programma di dimostrazione di teoremi naviga questo sistema come un problema di ricerca: partendo dalle premesse date, applica le regole di inferenza per generare nuove affermazioni, finché non raggiungi l'obiettivo.
Rappresenta questo come un grafo orientato:
Nodi: affermazioni ben formate nel sistema formale.
Archi: applicazioni singole di regole di inferenza (modus ponens, congruenza SAS, ecc.).
Dimostrazione: un percorso orientato dalle premesse date alla conclusione desiderata.
Lunghezza della dimostrazione: numero di passi di inferenza nel percorso.
La dimostrazione più breve di un teorema corrisponde al percorso più breve tra il nodo delle premesse & il nodo della conclusione in questo grafo.
Il programma di dimostrazione di teoremi geometrici ha esplorato questo grafo per: (1) applicazione diretta delle regole; (2) se bloccato, introducendo costruzioni ausiliarie (che aggiungono nuovi nodi alla ricerca). Il programma ha trovato la dimostrazione dell'autocongruenza evitando completamente la costruzione ausiliaria — un percorso più breve esisteva che l'approccio classico aveva mancato.
Lunghezza della Dimostrazione & Ricerca della Dimostrazione
La ricerca della dimostrazione affronta la stessa crescita esponenziale della ricerca dell'albero di gioco. Il fattore di ramificazione ad ogni nodo è uguale al numero di regole di inferenza applicabili. La profondità della dimostrazione cresce con la complessità del teorema.
Il programma di dimostrazione di teoremi ha utilizzato euristiche per potare lo spazio della dimostrazione, analogo al potaggio alfa-beta nei giochi.
Punti, Linee & Dualità
La dimostrazione dell'autocongruenza del programma di geometria del teorema del triangolo isoscele utilizza una prospettiva che non appare nelle dimostrazioni euclidee classiche. L'intuizione: invece di confrontare il triangolo ABC con un secondo triangolo costruito, confronta ABC con se stesso con i vertici della base scambiati — la corrispondenza A↔A, B↔C, C↔B.
Questo è un argomento di simmetria geometrica: il triangolo isoscele è simmetrico rispetto alla riflessione attraverso l'altitudine dall'apice. Il programma non ha costruito la riflessione esplicitamente; ha usato la corrispondenza come astrazione.
Il principio generale alla base di questo è la dualità proiettiva: nel piano proiettivo, ogni teorema sui punti & linee ha un teorema duale ottenuto scambiando le parole 'punto' e 'linea' in tutto.
Dizionario della dualità:
- Punto ↔ Linea
- Punto giace sulla linea ↔ Linea passa per il punto
- Due punti determinano una linea unica ↔ Due linee determinano un punto unico
- Punti collineari ↔ Linee concorrenti
Una singola dimostrazione di un teorema sui punti produce automaticamente una dimostrazione del teorema duale sulle linee — e viceversa. Le due dimostrazioni hanno la stessa struttura, la stessa lunghezza, & gli stessi passi di inferenza. Trovare la prospettiva duale spesso rivela una dimostrazione più semplice dell'originale.
Applicazione della Dualità
Teorema di Desargues: se due triangoli sono in prospettiva da un punto (le tre linee attraverso i vertici corrispondenti si incontrano tutti in un punto), allora sono in prospettiva da una linea (le tre intersezioni dei lati corrispondenti si trovano tutte su una linea).
Questo teorema è autoduale: scambiare i punti e le linee dà esattamente la stessa affermazione del teorema.
Frequenza di Campionamento & Spazio delle Frequenze
Il sistema di musica computerizzata presso Bell Labs si basava su un teorema matematico: il teorema del campionamento di Nyquist-Shannon.
Affermazione: un segnale limitato in banda con frequenza massima f_max può essere perfettamente ricostruito da campioni prelevati a una velocità di almeno 2 × f_max campioni al secondo.
L'interpretazione geometrica: un segnale limitato in banda vive in un sottospazio a dimensione finita dello spazio di tutte le funzioni continue. Il campionamento a velocità 2f_max fornisce abbastanza coordinate per identificare in modo univoco un punto in quel sottospazio.
Aliasing: La Geometria del Fallimento del Campionamento
Al di sotto della frequenza di Nyquist, le frequenze superiori a f_max si allontanano — appaiono come frequenze più basse nel segnale campionato. Due segnali distinti diventano indistinguibili dopo il campionamento. Geometricamente: l'operatore di campionamento proietta lo spazio del segnale su uno spazio a dimensione inferiore, causando la collisione di segnali diversi.
Per l'audio digitale (qualità CD): f_max = 22.050 Hz (leggermente sopra il limite dell'udito umano di 20.000 Hz), frequenza di campionamento = 44.100 campioni/secondo. Per il telefono: f_max = 4.000 Hz, frequenza di campionamento = 8.000 campioni/secondo.
Calcoli della Frequenza di Nyquist
Il teorema di Nyquist determina la frequenza di campionamento minima necessaria per evitare la perdita di informazioni.
Spazio della Dimostrazione & Spazio del Segnale: Geometria Condivisa
La dimostrazione-come-percorso e il teorema del campionamento di Nyquist condividono una struttura geometrica comune: entrambi implicano trovare la rappresentazione minima di qualcosa di complesso.
Minimizzazione della dimostrazione: trova il percorso più breve (fewest inference steps) attraverso il grafo della dimostrazione dalle premesse alla conclusione. La dimostrazione dell'autocongruenza ha minimizzato la lunghezza del percorso sfruttando la simmetria.
Campionamento del segnale: trova il numero minimo di campioni (frequenza di campionamento più bassa) che preserva tutte le informazioni in un segnale limitato in banda. Il teorema di Nyquist minimizza la rappresentazione sfruttando i limiti della banda.
Entrambi i problemi vivono in spazi con una struttura che consente risultati di rappresentazione minima. Entrambi falliscono quando quella struttura si rompe: le dimostrazioni diventano più lunghe quando lo spazio degli assiomi è scarsamente organizzato; l'aliasing si verifica quando il segnale non è limitato in banda.