Euclids bevis for at der er uendelig mange primtal

Et primtal er et helt positivt tal som kun er delelig uden rest med 1 og tallet selv.
Normalt medregnes tallet 1 ikke til primtallene.

Sætning: Der findes ikke noget største primtal.

Beviset er et indirekte bevis, "reductio ad absurdum", hvor vi antager det modsatte af det vi vil bevise, hvorefter vi påviser at dette fører til en modstrid, således at antagelsen må forkastes.

1. Antag at der findes et største primtal, kald det N.
2. Dan tallet y som produktet af alle primtal mindre end eller lig med N og læg 1 til:
   y = 2 * 3 * 5 * 7 * ... * N   +   1
3. Der er nu kun to muligheder: y er et primtal eller y er ikke et primtal.
4. Hvis y er et primtal,
   1. så kan N ikke være det største primtal, for y er større end N.
   2. Vi er kommet til en modstrid, N kan ikke være det største primtal, antagelsen må være forkert.
5. Hvis y ikke er et primtal,
   1. så må y være et sammensat tal, dvs. y kan skrives som et produkt af (mindst to) primtal.
   2. Ingen af de primtal som y i så fald er et produkt af, kan være primtallene fra 2 til N, for ved division af y med et af disse tal får vi resten 1.
   3. Derfor må de primtal som y er et produkt af være større end N.
   4. Vi er kommet til en modstrid, N kan ikke være det største primtal, antagelsen må være forkert.
6. Der findes altså intet største primtal.

Hvor mange rum deles cirklen i?

Kan vi lave en matematisk sætning om, hvor mange rum en cirkel maksimalt kan deles i, når n punkter på cirkelperiferien alle forbindes med rette linjer?

Antal punkter		Antal rum
n = 1		1
n = 2		2
n = 3		4
n = 4		8
n = 5		?
n = 6		?

Fermats sidste teorem

Fremsat 1637 af Pierre de Fermat, bevist af Andrew Wiles 1995.

Der findes ingen hele positive tal, x, y og z, som for n større end 2 opfylder ligningen:

xⁿ + yⁿ = zⁿ

Fermat-tal

Et Fermat-tal er et helt positivt tal som kan skrives på formen:

F_n =

hvor n er et helt tal og 0 eller positiv.
For n = 0, 1, 2, 3 og 4 bliver Fermat-tallet et primtal. Fermat fremsatte den hypotese at Fermat-tallene er primtal for alle værdier af n. Men Euler viste i 1732 at det allerede går galt ved 5:

Kvadratrod 2 er et irrationelt tal

Teorem: kan ikke skrives som en brøk med hel positiv tæller og nævner.

Antag at er et rationelt tal, dvs. at kan skrives som en brøk med hel positiv tæller og nævner, eller at = p / q hvor p og q er hele positive tal. Vi kan også antage at p / q er en uforkortelig brøk (skulle den ikke være det kan vi blot forkorte indtil den bliver uforkortelig).

= p / q      2 = p² / q²      p² = 2 q²      p² er et lige tal      p er et lige tal

   der findes et helt positivt tal n, således at p = 2 n  

   p² = 4 n²      2 q² = 4 n²      q² = 2 n²      q² er et lige tal      q er et lige tal

Men hvis både p og q er lige, kan brøken p / q forkortes med 2, og dette er i strid med antagelsen, at p / q var en uforkortelig brøk.

Antagelsen, at er et rationelt tal, fører altså til en modstrid. Så må antagelsen være falsk. Altså er er ikke et rationelt tal, men et irrationelt tal.

Irrationelt tal opløftet til irrationelt tal kan give et rationelt tal

Teorem: Der findes irrationelle tal x og y, således at

Algoritmer, beregnelighed

"En algoritme er en utvetydig og abstrakt beskrivelse af, hvordan en specifik type problem løses terminerende.
En algoritme er en opskrift til at løse et problem af en bestemt type, som leverer en løsning uanset den konkrete problemsituations udseende. Et eksempel kunne være en præcis beskrivelse af, hvordan man sorterer et spil kort, uanset hvordan de enkelte kort ligger fra udgangspunktet."

da.wikipedia.org/wiki/Algoritme
en.wikipedia.org/wiki/Algorithm

Beregnelige eller afgørlige problemer er problemersom kan løses ved hjælp af en algoritme.
Beregnelige tal er tal som kan findes ved hjælp af en algoritme.

Beregnelige reelle tal er f.eks. π, , 93/74 = 1,256756756756756..... , 0,22000222200000222222000000022222222 .....

Roger Penrose: "The Emperor's New Mind - concerning computers, minds, and the laws of Physics", Penguin Books, 1989, chap. 3.

Der findes også ikke-beregnelige problemer og tal.
en.wikipedia.org/wiki/Undecidable_problem
en.wikipedia.org/wiki/Computable_number

Selv hvis man har to beregnelige reelle tal, er det ikke nødvendigvis et beregneligt problem at konstatere om de to tal er lige store. Sml. f.eks. de to reelle tal:

15,2830999999.....   og   15,2831000000.....

Hvis de to tal er defineret som decimaludviklingen af det rationale tal 152831/10000 udviklet ved hjælp af to forskellige teknikker, så er de lige store.
Men hvis de to tal er genereret decimal for decimal ved hjælp af to algoritmer, kan vi ikke ved hjælp af nogen algoritme konstatere at de er lige store. Vi kan undersøge de første 1 million decimaler og måske få bekræftet at det venstre tals decimaler fortsat er 9-taller mens det højre tals decimaler fortsat er 0'er. Men vi kan ikke vide om der senere dukker andre tal op som decimaler. Og hvis der dukker andre tal op som decimaler, er de to tal ikke lige store.

Wondrous numbers (Collatz conjecture)

Douglas R. Hofstadter: "Gödel, Escher, Bach - an Eternal Golden Braid", Basic Books, Inc., Publishers, New York, 1979, chap. 8 & intro "Aria with Diverse Variations".

en.wikipedia.org/wiki/Wondrous_numbers

Algoritme:

1. Start med et helt positivt tal n.
2. Dan et nyt tal således:
   1. n/2     hvis n er lige
   2. 3n + 1  hvis n er ulige
3. Gentag punkt 2 med det nye tal.
4. Stop første gang du når tallet 1.

Collatz conjecture siger:

Denne algoritme vil for vilkårligt valg af start-tal nå tallet 1 efter et vist antal skridt.

Opkaldt efter Lothar Collatz, som fremsatte påstanden i 1937. Collatz conjecture er stadig hverken bevist eller modbevist.

Eksperimentér med Excel-filen: Wondeous.xls

I "pseudokode" kan algoritmen til beregning af talrækken med start i et givet tal n se således ud:

procedure wondrous(n)
   while n > 1
      if n odd then
         set n to 3n + 1
      else
         set n to n/2
   endwhile
output: "ja"
end of procedure

Tal som via Collatz-algoritmen når tallet 1 kaldes af Hofstadter "wondrous". Er tal-egenskaben "wondrous" ("vidunderlig") beregnelig?
Hvis vi for et givet tal n tager et vist antal skridt og ender på 1, så har vi vist at n er "wondrous".
Algoritmen i pseudokode stopper med svaret "ja".
Hvis vi for et givet tal n tager et vist antal skridt og stadig ikke er nået til tallet 1, så ved vi ikke om n er "wondrous" eller "ikke-wondrous". Vi kan så vælge at tage flere skridt, men egenskaben "wondrous" forbliver uafgørlig sålænge vi ikke er nået til tallet 1.
For et "ikke-wondrous" tal vil algoritmen i pseudokode aldrig stoppe.

(Egenskaben "ikke-wondrous" kan dog bestemmes, hvis algoritmen går ind i en lukket cykle af tal som ikke er cyklen 1-4-2-1-4-2-1- ....)

Med en passende udvidelse af den foregående algoritme kan vi generere "wondrous" tal ét efter ét. F.eks. således:

Undersøge tal 1 - 1000 i skridt 1 - 1000.
Undersøge tal 1 - 1000 i skridt 1001 - 2000
Undersøge tal 1001 - 2000 i skridt 1 - 1000.
Undersøge tal 2001 - 3000 i skridt 1 - 1000.
Undersøge tal 1001 - 2000 i skridt 1001 - 2000.
Undersøge tal 1 - 1000 i skridt 2001 - 3000.
Undersøge tal 1 - 1000 i skridt 3001 - 4000.
Undersøge tal 1001 - 2000 i skridt 2001 - 3000.
Undersøge tal 2001 - 3000 i skridt 1001 - 2000.
Undersøge tal 3001 - 4000 i skridt 1 - 1000.
Undersøge tal 2001 - 5000 i skridt 1 - 1000.
.....

Når man algoritmisk kan generere tallene i en mængde ét efter ét kaldes mængden "recursively enumerable". Mængden af "wondrous" tal er altså recursively enumerable.

Er mængden af "ikke-wondrous" tal (komplementær-mængden til "wondrous" tal) også recursively enumerable? Collatz conjecture siger jo, at denne mængde er tom, men dette er ikke bevist eller modbevist endnu. Vi må nøjes med at undersøge "wondrousness" ved hjælp af metoder svarende til algoritmen omtalt i starten af dette afsnit. Og den kan netop ikke afgøre om et tal er "ikke-wondrous", for vi ved ikke hvornår den stopper og giver svaret "1". Så mængden af "ikke-wondrous" tal er ikke recursively enumerable.
Vi har altså en situation, hvor vi ét efter ét kan indføje en uendeligmængdes elementer på en liste, men hvor vi intet ved om komplementær-mængden. Vi kan ikke definere egenskaben "ikke-wondrous" direkte, kun som det modsatte af egenskaben "wondrous".

Hofstadter omtaler i chap. 3 i sin bog "Gödel, Escher, Bach" at dette svarer til problemet med figur-og-baggrund. I nogle tilfælde udgør baggrunden i sig selv en figur, i andre tilfælde ikke. Hvis "wondrousness" er figuren, så er "ikke-wondrousness" baggrunden, og denne baggrund udgør ikke i sig selv en figur.

Nogle talmængder har den egenskab, at både mængden selv og dens komplementær-mængde er recursively enumerable. Dette gælder f.eks. for mængden af primtal og mængden af sammensatte tal.

Hofstadter giver følgende lille opgave, som også har relation til figur-baggrund:

Find det næste tal i rækken: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, .....

Goldbach's conjecture

Douglas R. Hofstadter: "Gödel, Escher, Bach - an Eternal Golden Braid", Basic Books, Inc., Publishers, New York, 1979, chap. 8 & intro "Aria with Diverse Variations".

en.wikipedia.org/wiki/Goldbach_conjecture

Goldbach's conjecture siger:

Ethvert lige tal større end to kan skrives som sum af to primtal

Indtil dato hverken bevist eller modbevist.

For et givet lige tal n > 2 kan en algoritme som undersøger om n har Goldbach-egenskaben se således ud:

Algoritme:

1. Start med et lige tal n større end 2.
2. Sæt p = 2
3. Undersøg om p og n - p er primtal
   1. Hvis både p og n - p er primtal: stop og svar "ja"
   2. Ellers: gå videre
4. Sæt p til p + 1
5. Undersøg om det nye p er større end eller lig med n
   1. Hvis p er større end n: stop og svar "nej"
   2. Ellers: gå til punkt 3.

Denne algoritme stopper i alle tilfælde efter højst n - 1 omgange, og den giver enten svaret "ja" eller "nej". Vi kan for et givet lige tal større end 2 i et endeligt antal skridt afgøre, om tallet har Goldberg-egenskaben eller ej. En sådan egenskab kaldes "primitive recursive".

Dette betyder ikke, at Goldbach's conjecture, altså at alle lige tal større end 2 har Goldbach-egenskaben, kan afgøres med en algoritme i et endeligt antal skridt!

Se på egenskaben at et lige tal kan skrives som differencen mellem to primtal.
Er denne egenskab primitive recursive?

Flere referencer

en.wikipedia.org/wiki/Godel_incompleteness_theorem#Examples_of_undecidable_statements
en.wikipedia.org/wiki/Continuum_hypothesis
en.wikipedia.org/wiki/Goodstein_theorem
en.wikipedia.org/wiki/Cantor_diagonal_argument
en.wikipedia.org/wiki/Continuum_hypothesis
en.wikipedia.org/wiki/Halting_problem

Se også kilder: Gödels bevis (1)

Se videre: Tilbage til introduktion