Formella bevis som vägar
Ett formellt bevissystem definierar en uppsättning axiomer & inferensregler. Varje bevisprogra navigerar genom detta system som ett sökproblem: börja med givna premisser, tillämpa inferensregler för att generera nya påståenden, tills du når målet.
Representera detta som en riktad graf:
Noder: välformade påståenden i det formella systemet.
Kanter: enstaka tillämpningar av inferensregler (modus ponens, SAS-kongruens, osv).
Bevis: en riktad väg från givna premisser till önskad slutsats.
Bevisets längd: antalet inferenssteg i vägen.
Det kortaste beviset för en sats motsvarar den kortaste vägen mellan premisspunkten & slutsatspunkten i denna graf.
Bevisprogrammet för geometri utforskade denna graf genom: (1) direkt tillämpning av regler; (2) om det fastnade, introducera hjälpkonstruktioner (som adderar nya noder till sökningen). Programmet fann självkongruensbeviset genom att helt undvika hjälpkonstruktionen — en kortare väg fanns som den klassiska metoden missade.
Bevisets längd & bevissökning
Bevissökning står inför samma exponentiella tillväxt som gränsträdsökning. Förgreningsfaktorn vid varje nod motsvarar antalet tillämpliga inferensregler. Bevisdjupet växer med satsens komplexitet.
Bevisprogrammet för geometri använde heuristik för att trimma bevisrymden, analogt med alfa-beta-trimning i spel.
Punkter, linjer & dualitet
Bevisprogrammet för geometri använder ett perspektiv på den likbenta triangelsatsen som inte förekommer i klassiska euklidiska bevis. Insikten: istället för att jämföra triangel ABC med en andra konstruerad triangel, jämföra ABC med sig själv med basvertikorna utbytta — motsvarelsen A↔A, B↔C, C↔B.
Detta är ett geometriskt symmetriargument: den likbenta triangeln är symmetrisk under reflektion över höjden från spetsen. Programmet konstruerade inte reflektionen explicit; det använde motsvarelsen som en abstraktion.
Den allmänna principen bakom detta är projektiv dualitet: i det projektiva planet har varje sats om punkter & linjer en dual sats erhållen genom att byta orden 'punkt' & 'linje' genom hela satsen.
Dualitetslexikon:
- Punkt ↔ Linje
- Punkt ligger på linje ↔ Linje passar genom punkt
- Två punkter bestämmer en unik linje ↔ Två linjer bestämmer en unik punkt
- Kolinjära punkter ↔ Konkurrenta linjer
Ett enda bevis för en sats om punkter ger automatiskt ett bevis för den duala satsen om linjer — & vice versa. De två bevisen har samma struktur, samma längd, & samma inferenssteg. Att hitta det duala perspektivet avslöjar ofta ett enklare bevis för originalet.
Tillämpa dualitet
Desargues sats: Om två trianglar är i perspektiv från en punkt (de tre linjerna genom motsvarande vertikaler möts alla i en punkt), så är de i perspektiv från en linje (de tre skärningspunkterna för motsvarande sidor ligger alla på en linje).
Denna sats är självdubbel: bytet av punkter & linjer ger exakt samma satsformulering.
Samplingsfrekvens & frekvensrymd
Det digitala musiksystemet vid Bell Labs vilade på en matematisk sats: Nyquist-Shannon-samplingssatsen.
Formulering: en bandbegränsad signal med maximal frekvens f_max kan perfekt rekonstrueras från samplingar tagna med en frekvens av minst 2 × f_max samplingar per sekund.
Den geometriska tolkningen: en bandbegränsad signal lever i ett ändligtdimensionellt underrum av rummet för alla kontinuerliga funktioner. Sampling med frekvens 2f_max tillhandahåller tillräckligt många koordinater för att unikt identifiera en punkt i detta underrum.
Aliasing: Geometrin för samplingsfel
Under Nyquist-frekvensen, alias för frekvenser över f_max — de verkar som lägre frekvenser i den samplade signalen. Två distinkta signaler blir omöjliga att särskilja efter sampling. Geometriskt: samplingoperatorn projicerar signalrummet på ett lägre-dimensionellt rum, vilket orsakar att olika signaler kolliderar.
För digital ljud (CD-kvalitet): f_max = 22 050 Hz (något över 20 000 Hz för mänsklig hörgräns), samplingsfrekvens = 44 100 samplingar/sekund. För telefon: f_max = 4 000 Hz, samplingsfrekvens = 8 000 samplingar/sekund.
Nyquist-frekvensberäkningar
Nyquist-satsen bestämmer den minimala samplingsfrekvens som krävs för att undvika informationsförlust.
Bevisrymd & signalrymd: Delad geometri
Bevisen-som-vägar & Nyquist-samplingssatsen delar en gemensam geometrisk struktur: båda handlar om att hitta den minimala representationen av något komplext.
Bevissminimering: hitta den kortaste vägen (färre inferenssteg) genom bevisgrafen från premisser till slutsats. Självkongruensbeviset minimerade väglängden genom att utnyttja symmetri.
Signalsampling: hitta det minimala antalet samplingar (lägsta samplingsfrekvens) som bevarar all information i en bandbegränsad signal. Nyquist-satsen minimerar representationen genom att utnyttja bandbreddsgränser.
Båda problemen lever i rum med struktur som möjliggör minimala-representations-resultat. Båda misslyckas när denna struktur bryter samman: bevisen blir längre när axiomrummet är dåligt organiserat; aliasing uppstår när signalen inte är bandbegränsad.