MU pusleriet
MIU-systemets strenge og slutningsregler
Inden i systemet: Aksiomer, slutningsregler, teoremer, beviser og M-mode
Udenfor systemet: I-mode
Afgørlighed for teoremhed
Store "puslerier"
Frit efter (en del bl.a. frit oversat):
Douglas R. Hofstadter: "Gödel, Escher, Bach - an Eternal Golden Braid", Basic Books, Inc., Publishers, New York, 1979.
Herfra er også tegningen af MIU-træet hentet. |
|
|
|
|
|
MIU-systemets strenge og slutningsregler
Her introduceres et formelt system i form af et
lille "pusleri". Det formelle system kaldes MIU-systemet, og reglerne er som følger:
Strenge
Med en streng menes en række tegn. Strengene i MIU-systemet består af bogstaverne M, I and U i vilkårlig rækkefølge og antal. Nedenfor er vist nogle eksempler på strenge:
MU UIM
MIU MIIUIIU
MUUMUU IIIIIIIII
Første streng
Forestil dig at du har en pose som du skal samle strenge i. De netop nævnte eksempler på strenge er ikke i din pose. Den eneste streng som du fra starten får lov at have i din pose i MIU-systemet er MI. Den eneste måde at få flere strenge i posen på er at benytte de regler som følger her:
Spilleregler
Her følger reglerne for hvordan du kan lave nye strenge ud fra de strenge du allerede har i din pose.
Regel 1: Hvis du har en streng hvis sidste bogstav er I, så må du tilføje et U i enden af strengen.
Eksempler: MII MIIU
UI UIU
MUI MUIU
I IU
Regel 2: Hvis du har en streng Mx, hvor 'x' står for sekvensen af bogstaver efter M, så må du lave en ny streng Mxx, dvs. du må gentage sekvensen af bogstaver efter M. (Bemærk at bogstavet 'x' selv ikke hører med til MIU-system).
Eksempler: MIU MIUIU
MUM MUMUM
MU MUU
MII MIIII
Regel 3: Hvis du har sekvensen III i en af dine strenge, så kan du lave en ny streng ved at erstatte III med U.
Eksempler: UMIIIMU UMUMU
MIIII MIU
MIIII MUI
MIII MU
Regel 4: Hvis du har sekvensen UU i en af dine strenge, så må du slette UU.
Eksempler: UUU U
MUUI MI
MUUUIII MUIII
UU (tom string)
Brugen af spillereglerne
Pas på! spillereglerne må ikke bruges den modsatte vej!!
Eksempler: MIU MI ikke tilladt!
MUU MU ikke tilladt!
MU MIII ikke tilladt!
II IUUI ikke tilladt!
Fra starten har du kun i din posen strengen MI. Opgaven er nu at prøve at tilføje nye strenge til din samling alene ved hjælp af de fire spilleregler.
Eksempel: Her vises hvordan strengen MUIIU kan tilføjes til din samling (tallene refererer til nummeret på den regel som anvendes i hvert trin):
MI 2 MII 2 MIIII 1 MIIIIU
3 MUIU 2 MUIUUIU 4 MUIIU
Herefter kan vi tilføje strengen MUIIU til vores samling, - og også de mellemliggende trin MII, MIIII, MIIIIU, etc.
Øvelse: Prøv at tilføje nogle nye strenge med MI som start, kun ved at bruge de fire spilleregler. Kan du lave MU?
Inden i systemet: Aksiomer, slutningsregler, teoremer, beviser og M-mode
At bevise teoremer
Måske har du prøvet at få strengen MU med i din samling. Undervejs har du sikkert opbygget en større privat samling af strenge. Sådanne strenge, produceret ved hjælp af spillereglerne, kaldes det formelle systems teoremer. At finde frem til en ny streng kaldes at udlede strengen eller at bevise et teorem. Som udgangspunkt har du fået et teorem frit til rådighed, nemlig MI. Et sådant "frit" theorem kaldes et aksiom. Så i MIU-systemet har vi kun ét aksiom:
Aksiom: MI
Spillereglerne kaldes slutningsregler.
For at bevise et nyt teorem, må du bruge slutningsreglerne på dit aksiom MI eller på teoremer der allerede er bevist. Udledningen af MUIIU betyder at vi har bevist at MUIIU er et teorem i MIU-systemet.
Øvelse: Prøv at bevise følgende teoremer (lad udledningen starte med aksiomet MI):
MUI, MUII, MIII, MU, MIIIII.
M-mode
Efter at have udledt en masse teoremer får du måske den oplevelse at dit arbejde meget ligner noget en maskine, f.eks. en computer, kunne gøre. Og det er faktisk rimelig nemt at programmere en computer til at bevise det ene teorem efter det andet i MIU-systemet. Et computerprogram kunne gøre det på følgende systematiske måde, - et forslag til en algoritme til dannelse af teoremer i MIU-systemet:
Trin 1: Benyt enhver anvendbar regel på aksiomer MI. Dette giver to nye teoremer: MIU, MII.
Trin 2: Benyt enhver anvendbar regel på de teoremer som blev lavet i trin 1.
Trin 3: Benyt enhver anvendbar regel på de teoremer som blev lavet i trin 2.
.........................
Trin n: Benyt enhver anvendbar regel på de teoremer som blev lavet i trin n - 1.
.........................
På denne måde kan computeren skabe et "træ af teoremer" hvor hver gren svarer til at benytte en regel til at skabe et nyt teorem ud fra et gammelt.
Øvelse: Lav træet af teoremer for MIU-systemet så langt som din tid og energi tillader. Begyndelsen er vist nedenfor.
Kan du nå frem til en gren som ender i MU?
Uanset om det er computeren eller dig som udvikler dette MIU-træ foregår arbejdet i "M-mode", dvs. i "maskin-tilstand". Men vi mennesker kan jo også bruge vores hjerne på en anden måde ...
Udenfor systemet: I-mode
I-mode og afgørlighed
Efter at have arbejdet et stykke tid med MU pusleriet med at udlede teoremer som en maskine, begynder du nok at bemærke nogle bestemte karakteristiske egenskaber ved teoremerne. Det er her den menneskelige intelligens kommer ind i billedet. F.eks. bliver det ret hurtigt klart at alle teoremer begynder med et M. Dette er jo også rimelig nemt at forstå, idet skridtet fra et gammelt teorem til et nyt teorem ved hjælp af hver og en af de fire slutningsregler sikrer at det første bogstav "nedarves", og udgangspunktet er jo aksiomet MI som netop har M som første bogstav.
Her bruger vi vores intelligens til at hoppe udenfor det formelle system. Det er vigtigt når man arbejder med formelle systemer at skelne mellem at arbejde indenfor systemet som en maskine, M-mode, og at lave observationer og overveje egenskaber om systemet ved hjælp af intelligens, I-mode.
Et hovedformål med at hoppe udenfor det formelle system er at prøve at finde en "test for teoremhed", dvs. at kunne karakterisere systemets teoremer, således at man kan teste om en given streng er et teorem eller ikke. Jamen har vi ikke allerede opnået dette i form af vores "MIU-træ" som jo blev lavet i M-mode? Denne metode producerer jo hvert eneste teorem før eller senere, fordi vi anvender reglerne i alle de mulige rækkefølger. Kunne man så ikke som "test for teoremhed" foreslå følgende:
Skab "MIU-træet". Vent til den streng vi vil teste dukker op i træet. Når det sker, kan vi fastslå at denne streng er et teorem. Sker det aldrig, så er denne streng ikke et teorem.
Problemet med denne "test" er at vi ikke kan være sikre på at få svar på vores spørgsmål om en bestemt streng er et teorem eller ej i løbet af et endeligt tidsrum. Hvad f.eks. med strengen MU? Hvis du kommer frem til MU i MIU-træet, så er du færdig og ved at MU er et teorem. Men hvis du ikke når frem til MU i dag, så kan du intet vide om MU's "teoremhed", - det kunne jo være at du nåede frem til MU i morgen! Vi kan ikke i et endeligt tidsrum nå frem til at afgøre at en given streng ikke er et teorem. Så MIU-træet dur ikke som test. Vi må kræve at en brugbar test må kunne færdiggøres i et endeligt tidsrum uanset resultatet. En test som i et endeligt tidsrum kan afgøre om en given streng er et teorem eller ej kaldes en "afgørligheds-procedure" ("decision procedure") for et bestemt formelt system.
Den omstændighed at vi ikke i M-mode i et endeligt tidsrum kan bruge MIU-træet som afgørligheds-procedure for teoremhed i MIU-systemet hænger sammen med at MIU-systemet nok er et ret simpelt formelt system, men ikke så simpelt. Hvis vi f.eks. forestillede os et formelt system hvor slutningsreglerne altid fører til længere strenge, så ville et teorem-træ faktisk kunne bruges som afgørligheds-procedure. For så ville f.eks. en streng af længden 7 tegn kunne dømmes som ikke-teorem hvis den ikke er dukket op i træet før en streng af længde 8 tegn, og dette sker i en endelig tid - også selv om den streng vi undersøger har længden 1 million tegn! Men MIU-systemet er i forhold til dette mere komplekst, for anvendelsen af de fire regler kan føre til både kortere og længere strenge (hvilke regler gør hvad?).
For at finde en afgørligheds-procedure for MIU-systemet må vi gå en anden vej. I de følgende øvelser bliver du ledt frem til mod dette i I-mode.
Afgørlighed for teoremhed i MIU-systemet
Øvelse:
Prøv at finde en regel for antallet af M'er, antallet af I'er og/eller antallet af U'er i MIU-systemets teoremer.
Øvelse:
Fokuser på antallet af I'er i teoremerne. Prøv at formulere en regel på formen:
"Hvis en streng x er et teorem i MIU-systemet, så må antallet af I'er i x være et tal med egenskaben ..."
Egenskaben ... kaldes i så fald en nødvendig betingelse for at en streng er et teorem. Hvis du har en streng i hvilken antallet af I'er ikke opfylder egenskaben ... , så ved du at denne streng ikke kan være et teorem.
Øvelse:
Hvis dette lykkes, skulle det nu være muligt for dig at afgøre endeligt om MU er et teorem.
Øvelse:
Er det også muligt at gå den anden vej? Altså at finde en regel på formen:
"Hvis antallet af I'er i en streng x opfylder egenskaben ... , så er x et teorem i MIU-systemet"
Egenskaben ... kaldes i så fald en tilstrækkelig betingelse for at en stren er et teorem.
Dette er noget mere vanskeligt. Få evt. hjælp i de følgende øvelser.
Øvelse:
Prøv at finde en metode til at bevise teoremer af formen MII...I, hvor strengen ikke har nogen U'er og hvor antallet af I'er opfylder egenskaben ... .
Øvelse:
Prøv at finde en metode til at bevise teoremer af den generelle form M..., hvor strengens antal af I'er opfylder egenskaben ... . (Det kan her være nødvendigt at tænke lidt strategisk "baglæns", - hvordan skal en streng med lutter I'er se ud, og hvordan kan man så ved hjælp af slutningsreglerne få sat U'er ind på de ønskede steder).
Øvelse:
Måske er det nu lykkedes dig at lave en afgørligheds-procedure for MIU-systemet, således at du ikke bare kan afgøre om en given streng x er et teorem eller ej, men også - igen nærmest som en maskine! - hvordan teoremet i givet fald kan bevises.
Øvelse:
Vis at afgørligheds-proceduren har sammenhæng med følgende talteoretiske udsagn:
Ethvert helt positivt tal som ikke er deleligt med 3 kan skrives på formen:
2n - 3m
hvor n og m er passende hele positive tal eller 0.
Store puslerier
MIU-systemets styrke og begrænsning
MIU-systemet er et lille og afgrænset eksempel på en matematiks formalisme, som udmærket demonstrerer et ideal indenfor matematik: At opbygge en formalisme baseret på strenge med slutningsregler og aksiomer med det formål at kunne stole på at de teoremer vi udleder kun er et resultat af denne formalisme, ikke af vores eventuelle forestillinger om hvad der måtte gælde eller ikke gælde. MIU-systemet er specielt fordi der findes en afgørligheds-procedure for om systemets strenge er teoremer eller ej.
Men MIU-systemet er et meget afgrænset formelt system som næppe kan bruges til meget andet end "leg". Dette formelle system "indfanger" ikke et større område af vore forestillinger, - sådan som f.eks. de formelle systemer bag geometrien hvor vore forestillinger om plan og rum formaliseres.
TTT - Typografisk Teori for Tal
Et "stort pusleri" er f.eks. at formalisere vores forestillinger om logiske udsagn og tal. Også her kan man opbygge et formelt system af slutningsregler og aksiomer baseret på "velformede" strenge af tegn. I denne form kaldes systemet et en "Typografisk Teori for Tal, TTT" (Typographical Number Theory). Kravene til et formelt system som TTT er at det skal være stærkt nok til at kunne formalisere tal-teorien, sådan at TTT kan "indfange" alle vore forestillinger om hvad der skal gælde om tal. Det kan faktisk godt lade sig gøre, men det er naturligvis mange gange mere kompliceret end MIU-systemet.
Indtryk af dette fås ved blot at kigge på (men ikke forstå) nedenstående udsnit af en udledning af en streng som svarer til fortolkningen at "addendernes orden er ligegyldig", altså at a + b = b + a for alle tal, også kaldet "den kommutative lov for addition", hentet fra Hofstadter's "Gödel, Escher, Bach":
Vi havde engang nogle forventninger til et kraftfuldt formelt system som TTT (formuleret i slutningen af 1800-tallet og starten af 1900-tallet). TTT skulle gerne være ...:
- modsigelsesfrit, dvs vi må ikke både kunne udlede et teorem ("der gælder ... ") og det negerede teorem ("der gælder ikke ...")
- fuldstændigt, dvs. at vi indenfor TTT kan finde bevis for alle teoremer og mod-bevis for alle ikke-teoremer
- afgørligt, dvs. at vi kan finde en afgørligheds-procedure for TTT.
Desværre viste det sig i løbet af 1900-tallet m.h.t TTT's ....:
- modsigelsesfrihed, - at TNT kan bekræftes at være modsigelsesfrit ud fra at systemet som model har tallene og at det kan "indfange" vore forventninger om tallenes egenskaber, men at det ikke kan lade sig gøre at bevise at TNT er modsigelsesfrit indenfor systemet selv, kun i et mere kraftfuldt system - som så igen skal bevises at være modsigelsesfrit.
- fuldstændighed, - at TNT ikke er fuldstændigt, dvs. at der findes sandheder om tallene som kan formuleres som velformede strenge indenfor TNT, men som ikke er teoremer i TNT, altså som ikke kan bevises indenfor TNT.
- afgørlighed, - at der ikke for TNT kan laves en afgørligheds-procedure, dvs. at man ikke har garanti for at man i et endeligt tidsrum kan afgøre om en given vilkårlig (velformuleret) streng er et teorem eller ej.
Eksempler på egenskaber for hele tal
Her følger nogle få eksempler på egenskaber for hele tal som vi vil forvente at et formelt system som TNT skal kunne "håndtere":
- Ethvert helt positivt tal som ikke er dividerbart med 3, kan skrives på formen 2n - 3m hvor n og m er hele positive tal eller 0. (Relevant i forbindelse med afgørlighed af MIU-systemet).
- "Der findes uendelig mange primtal". Bevist af Euklid.
- Ethvert lige tal større end eller lig med 4 kan skrives som en sum af to primtal. Goldbach's conjecture, fremsat 1742, endnu hverken bevist eller modbevist.
- Alle tal på formen er primtal. Fremsat af Pierre Fermat 1640. Men kan modvises, idet det ganske vist gælder for n = 1, 2, 3 og 4, men ikke for n = 5.
- For ethvert helt tal n > 2 findes der ingen hele positive tal, a, b og c, således at xn + yn = zn . Fremsat af Pierre Fermat i 1637, bevist af Andrew Wiles i 1995.
Se videre: Paradokser |