Les preuves formelles comme chemins
Un système de preuve formelle définit un ensemble d'axiomes & de règles d'inférence. Chaque programme de preuve de théorèmes explore ce système comme un problème de recherche : en partant des prémisses données, appliquer les règles d'inférence pour générer de nouvelles affirmations, jusqu'à ce que vous atteigniez l'objectif.
Représenter ceci comme un graphe dirigé :
Nœuds : énoncés bien formés dans le système formel.
Arêtes : applications uniques des règles d'inférence (modus ponens, congruence SAS, etc.).
Preuve : un chemin dirigé de prémisses données à la conclusion souhaitée.
Longueur de la preuve : nombre d'étapes d'inférence dans le chemin.
La preuve la plus courte d'un théorème correspond au chemin le plus court entre le nœud de prémisse & le nœud de conclusion dans ce graphe.
Le programme de preuve de théorèmes géométriques explore ce graphe par : (1) application directe des règles ; (2) si bloqué, introduire des constructions auxiliaires (qui ajoutent de nouveaux nœuds à la recherche). Le programme a trouvé la preuve d'auto-congruence en évitant entièrement la construction auxiliaire — un chemin plus court existait que l'approche classique n'a pas détecté.
Longueur de la preuve & recherche de preuve
La recherche de preuve fait face à la même croissance exponentielle que la recherche d'arbre de jeu. Le facteur de branchement à chaque nœud égale le nombre de règles d'inférence applicables. La profondeur de la preuve croît avec la complexité du théorème.
Le programme de preuve de théorèmes a utilisé des heuristiques pour élaguer l'espace de preuve, analogue à l'élagage alpha-bêta dans les jeux.
Points, lignes & dualité
La preuve d'auto-congruence du théorème du triangle isocèle du programme de géométrie utilise une perspective qui n'apparaît pas dans les preuves euclidiennes classiques. L'intuition : au lieu de comparer le triangle ABC à un deuxième triangle construit, comparer 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 réflexion sur l'altitude depuis l'apex. Le programme n'a pas construit la réflexion explicitement ; il a utilisé la correspondance comme une abstraction.
Le principe général derrière ceci est la dualité projective : dans le plan projectif, chaque théorème sur les points & les lignes a un théorème duel obtenu en échangeant les mots « point » & « ligne » partout.
Dictionnaire de dualité :
- Point ↔ Ligne
- Le point se trouve sur la ligne ↔ La ligne passe par le point
- Deux points déterminent une ligne unique ↔ Deux lignes déterminent un point unique
- Points colinéaires ↔ Lignes concurrentes
Une seule preuve d'un théorème sur les points donne automatiquement une preuve du théorème duel sur les lignes — & vice versa. Les deux preuves ont la même structure, la même longueur & les mêmes étapes d'inférence. Trouver la perspective duelle révèle souvent une preuve plus simple de l'original.
Appliquer la dualité
Théorème de Desargues : Si deux triangles sont en perspective à partir d'un point (les trois lignes passant par les sommets correspondants se rencontrent en un point), alors ils sont en perspective à partir d'une ligne (les trois intersections des côtés correspondants se trouvent tous sur une ligne).
Ce théorème est auto-duel : échanger les points & les lignes donne exactement le même énoncé du théorème.
Taux d'échantillonnage & espace de fréquence
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.
Énoncé : un signal limité en bande avec fréquence maximale f_max peut être parfaitement reconstruit à partir d'échantillons prélevés à un taux d'au moins 2 × f_max échantillons par seconde.
L'interprétation géométrique : un signal limité en bande vit dans un sous-espace de dimension finie de l'espace de toutes les fonctions continues. L'échantillonnage au taux 2f_max fournit suffisamment de coordonnées pour identifier de manière unique un point dans ce sous-espace.
Repliement : la géométrie de l'échec d'échantillonnage
En dessous du taux de Nyquist, les fréquences au-dessus de f_max se replient — elles apparaissent comme des fréquences plus basses dans le signal échantillonné. Deux signaux distincts deviennent indiscernables après l'échantillonnage. Géométriquement : l'opérateur d'échantillonnage projette l'espace du signal sur un espace de dimension inférieure, causant la collision de différents signaux.
Pour l'audio numérique (qualité CD) : f_max = 22 050 Hz (légèrement au-dessus de la limite d'audition humaine de 20 000 Hz), taux d'échantillonnage = 44 100 échantillons/seconde. Pour le téléphone : f_max = 4 000 Hz, taux d'échantillonnage = 8 000 échantillons/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'information.
Espace de preuve & espace de signal : géométrie partagée
La preuve-comme-chemin & le théorème d'échantillonnage de Nyquist partagent une structure géométrique commune : tous deux impliquent de trouver la représentation minimale de quelque chose de complexe.
Minimisation de la preuve : trouver le chemin le plus court (fewest inference steps) à travers le graphe de preuve de prémisses à conclusion. La preuve d'auto-congruence a minimisé la longueur du chemin en exploitant la symétrie.
Échantillonnage du signal : trouver le nombre minimum d'échantillons (taux d'échantillonnage le plus bas) qui préserve toutes les informations dans un signal limité en bande. Le théorème de Nyquist minimise la représentation en exploitant les limites de bande passante.
Les deux problèmes résident dans des espaces avec une structure qui permet des résultats de représentation minimale. Les deux échouent quand cette structure s'effondre : les preuves deviennent plus longues quand l'espace des axiomes est mal organisé ; le repliement se produit quand le signal n'est pas limité en bande.