Matematik
diagonaliseringsargumentet
okay, jeg har vist spurgt om det her før, men jeg forstår det altså stadig ikke helt. Man viser, at de rationale tal er tællelige ved at lave en slags skema, hvor man tæller langs den ene diagonal efter den anden. Det viser, at vi kan mappe hvert rationalt tal til et naturligt tal unikt.
Når Kantor så viste (på den måde jeg har set), at intervallet (0,1) er utælleligt, så sagde han: antag, at der fandtes en ordning som ved de rationale tal. Så kan vi skrive alle decimaltal op i et skema som før, hvor der er en 1-1 korrespondance mellem de naturlige tal og de reelle tal. Men dette kan ikke passe, fordi uanset hvad så springes det tal, som har forskellige decimaler langs diagonalen over. I kan selv lige google det, men det er sådan jeg forstår tankegangen,
I hvertfald at, der på en eller anden måde uundgåeligt springes et tal over i skemaet. Men kunne man ikke bare tage det tal med efter? Så kommer der ganske vist et nyt tal, der springes over, men man kunne vel bare successivt sætte dette nye tal foran. Hvem siger man så ikke kommer igennem alle de reelle tal? Okay det er nok lidt rodet skrevet det her, men helt fundamentalt forstår jeg ikke forskellen mellem argumentet for de reelle tal og de rationale: for de rationale mangler der jo op til et vist punkt i skemaet jo også hele tiden tal, der først kommer senere.
Håber I kan hjælpe min forståelse bare lidt..
Svar #1
31. august 2013 af SuneChr
Man antager, at have en uendelig følge { an , ... } af elementer tilhørende en mængde af uendelige decimalbrøker < 1 med lutter to forskellige cifre. Det skal bevises, at mængden af decimalbrøker ikke er numerabel, da det er ensbetydende med, at R ikke er numerabel.
Vi skal vise, at følgen ikke kan indeholde alle elementer i mængden af decimalbrøker.
Vi skal finde en decimalbrøk tilhørende mængden af decimalbrøker men ikke tilhøre følgen {an , ... } .
Svar #2
01. september 2013 af SuneChr
Lad nu M være mængden af uendelige decimalbrøker, der kan skrives på formen 0,d1d2d3..... , hvor
di enten er 5 eller 7 (to tilfældige cifre). Lad nu også de første elementer i følgen { an , ...} være
a1 = 0,77557575...
a2 = 0,75555757...
a3 = 0,57575757...
Vi bestemmer nu en decimalbrøk T ∈ M ved at fastsætte d1 = 5 (modsat af a1 s første ciffer). Heraf følger,
at T ≠ a1 uanset de efterfølgende cifre. Andet ciffer, 7, bestemmes igen som det modsatte af a2 s andet ciffer
og igen T ≠ a2 .
Når vi nu fortsætter sådan, får vi et T ∈ M . Men vi har undervejs sikret os, at T ≠ ai , så T kan ikke tilhøre
følgen.
Dermed viste Cantor, at M, og dermed R , ikke er numerabel.
Svar #3
01. september 2013 af Andersen11 (Slettet)
Jeg vil her skitsere et alternativt bevis for, at R ikke er numerabel, selv om der er en vis lighed med diagonaliseringsargumentet, der er gennemgået i #1 og #2. Man viser først denne
Sætning. Lad A være en numerabel delmængde af R. For ethvert åbent interval ]α,β[ ⊆ R gælder der, at
(R\A) ∩ ]α,β[ ≠ Ø .
Bevis. Lad A være en numerabel delmængde af R, og lad det åbne interval ]α,β[ være givet. At intervallet er åbent, betyder, at α < β . Da A er numerabel, kan vi skrive A = {x1, x2, ....}. Vi vælger nu et afsluttet interval [α1,β1] ⊂ ]α,β[ , så at x1 ∉ [α1,β1] . Dernæst vælges et afsluttet interval [α2,β2] ⊂ [α1,β1], så at x2 ∉ [α2,β2] , og således fortsættes. Herved bestemmes en dalende følge
[α1,β1] ⊃ [α2,β2] ⊃ [α3,β3] ⊃ ...
af afsluttede intervaller, hvis fællesmængde indeholder mindst ét punkt af intervallet ]α,β[ , og denne fællesmængde indeholder intet punkt fra A. Altså har vi, at (R\A) ∩ ]α,β[ ≠ Ø , hvormed sætningen er bevist.
Heraf følger det specielt, at det for enhver numerabel delmængde A af R gælder, at R\A ≠ Ø, hvilket viser, at R selv ikke kan være numerabel.
Skriv et svar til: diagonaliseringsargumentet
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.