Preuves formelles comme des chemins
Un système de preuve formelle définit un ensemble d'axiomes & de règles d'inference. Chaque programme de démonstration théorique navigue dans ce système comme un problème de recherche : commençant par les prémisses données, appliquer les règles d'inference pour générer de nouvelles déclarations, jusqu'à atteindre le but.
Représentez cela sous forme de graphe directé :
Nœuds : déclarations bien formées dans le système formel.
Arêtes : applications simples de règles d'inference (modus ponens, congruence SAS, etc.).
Preuve : un chemin directé de la prémisses données à la conclusion souhaitée.
Longueur de preuve : nombre d'étapes d'inference dans le chemin.
La plus courte preuve d'un théorème correspond à la plus courte distance entre le nœud de la prémisses et le nœud de la conclusion dans ce graphe.
Le programme de preuve géométrique explorait ce graphe par : (1) application directe des règles ; (2) si bloqué, introduction de constructions accessoires (ce qui ajoute de nouveaux nœuds à la recherche). Le programme a trouvé la preuve de selfcongruence en évitant la construction accessoire entièrement - un chemin plus court existait que l'approche classique a manqué.
Longueur de preuve et recherche de preuve
La recherche de preuve rencontre la même croissance exponentielle que la recherche d'arbre de jeu. Le facteur de ramification à chaque nœud est égal au nombre de règles d'inference applicables. La profondeur de la preuve augmente avec la complexité du théorème.
Le programme de preuve utilisait des heuristiques pour élaguer l'espace de preuve, analogue à l'élagage alpha-beta dans les jeux.
Points, Lignes & Dualité
La preuve de selfcongruence du programme de géométrie de l'axiome du triangle isocèle utilise une perspective qui ne figure pas dans les preuves euclidiennes classiques. L'insight : au lieu de comparer le triangle ABC à un deuxième triangle construit, comparez ABC à lui-même avec les sommets de base échangés — la correspondance A↔A, B↔C, C↔B.
C'est un argument de symétrie géométrique : le triangle isocèle est symétrique par rapport à la réflexion à partir de l'apex. Le programme n'a pas construit la réflexion explicite ; il a utilisé la correspondance comme une abstraction.
La principale généralisation derrière cela est la dualité projective : dans le plan projectif, chaque théorème sur les points et les lignes a un théorème dual obtenu en remplaçant les mots 'point' et 'ligne' partout.
Dictionnaire de dualité:
- Point ↔ Ligne
- Point appartient à la ligne ↔ Ligne passe par le point
- Deux points déterminent une ligne unique ↔ Deux lignes déterminent un point unique
- Points collinéaires ↔ Lignes concourantes
Une seule preuve d'un théorème sur les points fournit automatiquement une preuve du théorème dual sur les lignes - et vice versa. Les deux preuves ont la même structure, la même longueur et les mêmes étapes d'inference. Trouver la perspective dual souvent révèle une preuve plus simple de l'original.
Application de la dualité
Théorème de Desargues : Si deux triangles sont en perspective d'un point (les trois lignes traversant les sommets correspondants se rencontrent toutes au même point), alors ils sont en perspective d'une ligne (les trois intersections des côtés correspondants se trouvent sur une même ligne).
Ce théorème est auto-duel : l'échange des points et des lignes donne exactement la même déclaration de théorème.
Taux d'échantillonnage & Espace des fréquences
Le système de musique informatique des Bell Labs reposait sur un théorème mathématique : le théorème d'échantillonnage de Nyquist-Shannon.
Enoncé : un signal à bande limitée avec une fréquence maximale f_max peut être reconstruit parfaitement à partir d'échantillons pris à un taux de au moins 2 × f_max échantillons par seconde.
L'interprétation géométrique : un signal à bande limitée vit dans un sous-espace à dimensions finies de l'espace de toutes les fonctions continues. L'échantillonnage à un taux de 2f_max fournit suffisamment de coordonnées pour identifier de manière unique un point dans ce sous-espace.
Échauffement : La Géométrie de l'échec de l'échantillonnage
En dessous du taux de Nyquist, les fréquences supérieures à f_max se superposent - elles apparaissent comme des fréquences plus basses dans le signal échantillonné. Deux signaux distincts deviennent indistingibles après échantillonnage. Géométriquement : l'opérateur d'échantillonnage projette l'espace signal sur un espace à dimension inférieure, provoquant la collision de signaux différents.
Pour l'audio numérique (qualité CD) : f_max = 22 050 Hz (legèrement au-dessus du plafond de l'audition humaine de 20 000 Hz), taux d'échantillonnage = 44 100 échantillons par seconde. Pour le téléphone : f_max = 4 000 Hz, taux d'échantillonnage = 8 000 échantillons par seconde.
Calculs du Taux de Nyquist
Le théorème de Nyquist détermine le taux d'échantillonnage minimum nécessaire pour éviter la perte d'informations.
Preuve et Espace Signal : Géométrie Partagée
La preuve-en-chemin et le théorème d'échantillonnage de Nyquist partagent une structure géométrique commune : les deux impliquent la recherche d'une représentation minimale de quelque chose de complexe.
Minimisation de la preuve : trouver le chemin le plus court (moins d'étapes d'inference) à travers le graphe de la preuve des prémisses à la conclusion. La preuve de selfcongruence minimise la longueur du chemin en exploitant la symétrie.
Échantillonnage du signal : trouver le nombre minimal d'échantillons (taux d'échantillonnage le plus bas) qui conserve toutes les informations dans un signal à largeur de bande limitée. Le théorème de Nyquist minimise la représentation en exploitant les limites de la bande passante.
Les deux problèmes se trouvent dans des espaces avec une structure qui permet des résultats de représentation minimale. Les deux échouent lorsque cette structure cède : les preuves deviennent plus longues lorsque l'espace des axiomes est mal organisé ; l'aliasing se produit lorsque le signal n'est pas à largeur de bande limitée.