Formele Bewijzen als Pad
Een formele bewijsstelsel definieert een set van axiomen & inferentierules. Elk theorem-verwijzingsprogramma navigeert dit stelsel als een zoekprobleem: beginnend bij de gegeven aannames, toepassen van inferentierules om nieuwe statements te genereren, tot je het doel bereikt.
Weergeef dit als een gecoordinate grafiek:
Knopen: welgevormde statements in het formele stelsel.
Kanten: enkelvoudige toepassingen van inferentierules (modus ponens, SAS congruentie, etc.).
Bewijs: een gecoordinate pad van de gegeven aannames naar het gewenste slot.
Bewijslengte: het aantal inferentiestappen in het pad.
Het kortste bewijs van een theorema correspondeert met het kortste pad tussen de aannamenknop en de slotsknop in deze grafiek.
Het geometrie-theoremaprogramma onderzocht deze grafiek door: (1) directe toepassing van regels; (2) als je vastloopt, introduceren van aanvullende constructies (wat nieuwe knopen toevoegt aan de zoektocht). Het programma vond het zelfcongruentiebewijs door de aanvullende constructie geheel te vermijden - een korter pad bestond dat de klassieke aanpak miste.
Bewijslengte & Bewijszoektocht
Bewijszoektochten staan voor hetzelfde exponentiële groeiprobleem als schaakboomstraten. Het splitsingsniveau op elke knop gelijk aan het aantal toepasselijke inferentierules. Bewijsdiepte groeit met de complexiteit van het theorema.
Het theorem-verwijzingsprogramma gebruikte heuristieken om de bewijsruimte te snoeien, analoog aan alpha-beta snoeien in spellen.
Punten, Lijnen & Dualiteit
De zelfcongruente bewijs van de drihakkenheid van de meetkundeprogramma gebruikt een perspectief dat niet voorkomt in klassieke Euclidische bewijzen. Het inzicht: in plaats van de drihokken ABC te vergelijken met een tweede opgebouwde driehoek, vergelijk ABC met zichzelf met de basispunten omgewisseld - de overeenkomst A↔A, B↔C, C↔B.
Dit is een geometrisch symmetrieargument: de driehoek met gelijke kanten is symmetrisch onder reflectie over de hoogte van de top. Het programma bouwde de reflectie niet expliciet; het gebruikte de overeenkomst als een abstractie.
De algemene principes achter deze zijn projectieve dualiteit: in de projectieve ruimte heeft elk theorema over punten & lijnen een dual theorema dat wordt verkregen door de woorden 'punt' en 'lijn' door het hele stuk uit te wisselen.
Dualiteitswoordenboek:
- Punt ↔ Lijn
- Punt ligt op lijn ↔ Lijn gaat door punt
- Twee punten bepalen een unieke lijn ↔ Twee lijnen bepalen een uniek punt
- Gelijnd punten ↔ Samenlopende lijnen
Een enkel bewijs van een theorema over punten levert automatisch een bewijs van het dual theorema over lijnen - en vice versa. De twee bewijzen hebben dezelfde structuur, dezelfde lengte & dezelfde inferentiestappen. Het vinden van de dualistische perspectief onthult vaak een eenvoudiger bewijs van het oorspronkelijke.
Toepassen van Dualiteit
Desargues' Theorem: Als twee driehoeken in perspectief zijn vanuit een punt (de drie lijnen door corresponderende hoekpunten komen allemaal samen in één punt), zijn ze dan ook in perspectief vanuit een lijn (de drie snijpunten van corresponderende zijden liggen allemaal op één lijn).
Dit theorema is zelf-dual: wisselen van punten en lijnen geeft precies hetzelfde stellingstatement.
Samplingsfrequentie & Frequentieruimte
Het computer muzieksysteem op Bell Labs was gebaseerd op een wiskundig theorema: het Nyquist-Shannon monstersamen theorem.
Statement: een bandbeperkt signaal met een maximumfrequentie f_max kan perfect worden hersteld van monsters genomen met een frequentie van minstens 2 × f_max monsters per seconde.
De geometrische interpretatie: een bandbeperkt signaal bestaat uit een eindig-dimensionale onderruimte van de ruimte van alle continue functies. Samplen met een frequentie van 2f_max biedt genoeg coördinaten om een uniek punt in die onderruimte te identificeren.
Aliasen: De Geometrie van Monstersamen Fout
Onder de Nyquist-frequentie aliasen frequenties boven f_max - ze verschijnen als lagere frequenties in het geprolileerde signaal. Twee verschillende signalen worden onderscheidbaar na het monsteren. Wiskundig: de monsteringsoperator projecteert het signaalruimte op een lager-dimensionaal ruimte, waardoor verschillende signalen botsen.
Voor digitale audio (CD-kwaliteit): f_max = 22.050 Hz (slechts boven de 20.000 Hz menselijke hoorlimiet), monsteringsfrequentie = 44.100 monsters per seconde. Voor de telefoon: f_max = 4.000 Hz, monsteringsfrequentie = 8.000 monsters per seconde.
Nyquist-frequentieberekeningen
Het Nyquist-theorema bepaalt de minimale monsteringsfrequentie nodig om informatieverlies te voorkomen.
Bewijsruimte & Signaalruimte: Gedeelde Wiskunde
Het bewijs als pad en de Nyquist-sampling stelling delen een gemeenschappelijke wiskundige structuur: zowel betreft het het vinden van de minimumvoorstelling van iets complex.
Bewijsvermindering: vind de kortste pad (weinigste inferentiestappen) door het bewijsgraf van aannames naar conclusie. Het zelfcongruentiebewijs vermindert de padlengte door symmetrie te exploiteren.
Signaalmonsterning: vind het minimumaantal monsters (laagste monstersnelheid) dat alle informatie in een bandbeperkt signaal behoudt. Het Nyquist-theorema vermindt de representatie door bandbreedtelimieten te exploiteren.
Beide problemen bevinden zich in ruimten met structuur die minimum-representatie-resultaten mogelijk maakt. Beide falen wanneer die structuur breekt: bewijzen worden langer als de axiomeruimte slecht georganiseerd is; aliasing treedt op als het signaal niet bandbeperkt is.