Cantors diagonalargument: Definition, bevis og betydning for uendelige mængder

Lær Cantors diagonalargument: definition, trin-for-trin-bevis og betydning for uendelige mængders kardinalitet — klart, præcist og lettilgængeligt.

Forfatter: Leandro Alegsa

Cantors diagonalargument er en matematisk metode til at bevise, at to uendelige mængder har den samme kardinalitet. Cantor offentliggjorde artikler om den i 1877, 1891 og 1899. Hans første bevis for det diagonale argument blev offentliggjort i 1890 i tidsskriftet for det tyske matematiske selskab (Deutsche Mathematiker-Vereinigung). Ifølge Cantor har to mængder den samme kardinalitet, hvis det er muligt at knytte et element fra den anden mængde til hvert element i den første mængde og at knytte et element fra den første mængde til hvert element i den anden mængde. Dette udsagn fungerer godt for mængder med et endeligt antal elementer. Den er mindre intuitiv for mængder med et uendeligt antal elementer.

Hvad betyder "samme kardinalitet" for uendelige mængder?

To mængder siges at have samme kardinalitet (størrelse), hvis der findes en bijektion mellem dem — altså en en-til-en og på-til-korrespondance. For endelige mængder svarer dette til, at de har ligeså mange elementer. For uendelige mængder giver begrebet mulighed for, at nogle uendelige mængder kan være "større" end andre på en præcis måde. Et vigtigt eksempel er, at mængden af naturlige tal N er tælleligt uendelig (eller har kardinalitet aleph-0), mens mængden af reelle tal R er utællelig og har en større kardinalitet, ofte kaldet kontinummet.

Cantors diagonale argument — bevis for, at (0,1) er utællelig

Den klassiske form af Cantors diagonale argument viser, at mængden af reelle tal i intervallet (0,1) ikke kan sættes i bijektion med de naturlige tal. Fremgangsmåden er et bevis ved modstrid (reduktion til umulighed):

  1. Antag, modstrid, at alle reelle tal i (0,1) kan listes som en række r1, r2, r3, ... og at hver række skrives i decimalform:
    r1 = 0.d11 d12 d13...
    r2 = 0.d21 d22 d23...
    r3 = 0.d31 d32 d33...
    osv.
  2. Byg et nyt tal s = 0.s1 s2 s3... ved at vælge hver cifers sj forskellig fra cifret djj på diagonalen. For eksempel kan man vælge sj = 1 hvis djj ≠ 1, og sj = 2 hvis djj = 1. På den måde sikrer man, at sj ≠ djj for alle j.
  3. Det konstruerede tal s adskiller sig fra hvert listet tal rj i mindst det j'te decimaltegn, så s ≠ rj for alle j. Derfor findes s ikke i den antagne liste, hvilket er en modstrid.
  4. Konklusion: Ingen sådan komplet liste (ingen bijektion mellem N og (0,1)) kan eksistere. Intervallet (0,1) er utælleligt.

Bemærk: Man skal passe på representationer med endelige decimaler (f.eks. 0.4999... = 0.5000...), men man kan håndtere det ved at undgå at vælge cifre 9 i konstruktionen eller ved at arbejde med anden repræsentation (binær, ternær osv.).

Cantors sætning om potensmængder

Cantor gav også et mere generelt argument, som viser, at for enhver mængde A er potensmængden P(A) (mængden af alle delmængder af A) altid "større end" A. Argumentet er enklere og endnu mere fundamentalt, fordi det ikke afhænger af decimalrepræsentationer:

  1. Antag, modstrid, at der findes en funktion f: A → P(A) som er surjektiv (altså rammer alle delmængder).
  2. Definér S = { x ∈ A | x ∉ f(x) } — mængden af alle elementer i A, som ikke ligger i deres eget billede under f.
  3. Da f er antaget surjektiv, findes der et a ∈ A med f(a) = S. Spørgsmålet er så: er a ∈ S?
    • Hvis a ∈ S, så følger definitionen af S, at a ∉ f(a) = S, modstrid.
    • Hvis a ∉ S, så følger definitionen, at a ∈ f(a) = S, modstrid.
  4. Begge muligheder giver modstrid, så f kan ikke være surjektiv. Derfor findes ingen bijektion mellem A og P(A), og P(A) har strikt større kardinalitet end A.

Denne idé kaldes ofte Cantors diagonalargument i abstrakt form og er grundlaget for Cantors sætning: |A| < |P(A)| for enhver mængde A.

Intuition og betydning

  • Forskellige størrelser af uendelighed: Cantors resultater viste, at uendelighed ikke er ét enkelt begreb — nogle uendelige mængder er "større" end andre. Naturlige tal er tællelige, men reelle tal og potensmængden af naturtal er utællelige og har større kardinalitet.
  • Kontinuum-hypotesen: Cantors arbejde førte til spørgsmålet om, hvorvidt der findes en mængde hvis kardinalitet ligger mellem aleph-0 (naturliges kardinalitet) og kontinummet (reelles kardinalitet). Dette er kendt som kontinuum-hypotesen, som senere viste sig at være uafgørlig i Zermelo–Fraenkel-mængdeteori med valg (ZFC).
  • Grundlaget for moderne matematik og logik: Diagonalargumentet inspirerede og blev anvendt af senere tænkere som Gödel og Turing. Gödel brugte diagonaliseringsidéer i sit bevis af ufuldstændighedssætningerne; Turing brugte lignende metoder i beviset for at der ikke findes en generel algoritme til at løse haltingproblemet.

Eksempler og ekstra bemærkninger

  • Rationelle tal er tællelige: Selvom der er uendeligt mange brøker, kan man lægge dem i en rækkefølge (f.eks. via en diagonalisering på to dimensioner) så alle rationelle tal kommer med — derfor har Q samme kardinalitet som N.
  • Reelle tal er utællelige: Diagonalargumentet viser, at ikke engang alle reelle i et lille interval (0,1) kan listes, så R har en større kardinalitet end N.
  • Den abstrakte diagonaliseringsmetode er stærkere end blot decimaleksemplet: den viser en generel måde at konstruere et element, der afviger fra enhver liste på mindst ét sted, og den anvendes i mange grene af matematik og teoretisk datalogi.

Samlet set gav Cantors diagonalargument et skarpt værktøj til at skelne mellem forskellige typer af uendeligheder og har haft dybtgående konsekvenser for matematikens fundament, logik og teori om beregnelighed.

Cantors første diagonalargument

I eksemplet nedenfor bruges to af de enkleste uendelige mængder, nemlig de naturlige tal og de positive brøker. Ideen er at vise, at begge disse mængder, N {\displaystyle \mathbb {N} }{\displaystyle \mathbb {N} } og Q + {\displaystyle \mathbb {Q^{+}} }{\displaystyle \mathbb {Q^{+}} } har den samme kardinalitet.

Først tilpasses brøkerne i et array på følgende måde:

1 1 1 1 1 2 1 2 1 3 1 1 4 1 5 ⋯ 2 1 2 2 2 2 2 2 3 2 2 2 2 4 2 5 ⋯ 3 1 1 3 2 2 3 3 3 3 3 3 3 4 3 3 3 4 3 5 ⋯ 4 1 4 1 4 2 4 3 4 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccc}{\tfrac {1}{1}{1}}}&&{\tfrac {1}{2}}}&&&{\tfrac {1}{3}}}&&&{\tfrac {1}{4}}}&&&{\tfrac {1}{4}}}&{\tfrac {1}{5}}}&\cdots \\&&&&&&&&&\\\\{\tfrac {2}{1}}}&&{\tfrac {2}{2}{2}}}&&&{\tfrac {2}{3}}}&&&{\tfrac {2}{4}}}&&&{\tfrac {2}{5}}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}}&&&{\tfrac {3}{2}}}&&{\tfrac {3}{3}{3}}}&&&{\tfrac {3}{4}}}&&&{\tfrac {3}{5}}}&\cdots \\&&&&&&&&&&&\\\{\tfrac {4}{1}}}&&{\tfrac {4}{2}}}&&{\tfrac {4}{3}}}&&{\tfrac {4}{4}{4}}}&&{\tfrac {4}{5}}}&&\cdots \\&&&&&&&&&\\\\{\tfrac {5}{1}}}&&{\tfrac {5}{2}}}&&{\tfrac {5}{3}}}&&&&{\tfrac {5}{4}}}&&{\tfrac {5}{5}{5}}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}} {\displaystyle {\begin{array}{cccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

Derefter tælles tallene som vist. Brøker, som kan forenkles, udelades:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}}\ _{\color {Blue}(2)}&&&{\tfrac {1}{3}}}\ _{\color {Blue}(5)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}}}\ _{\color {Blue}(6)}&&&{\tfrac {1}{5}}}\ _{\color {Blue}(11)}&&{\tfrac {1}{5}}}{\color {MidnightBlue}\rightarrow }\&&{{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&\\\\{\tfrac {2}{1}}}}\ _{\color {Blue}(3)}&&&{\tfrac {2}{2}}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{3}}}\ _{\color {Blue}(7)}&&&{\tfrac {2}{4}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{5}}}&\cdots \\{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\swarrow }&&&{{\color {MidnightBlue}\nearrow }&&&&\\\\{\tfrac {3}{1}}}}\ _{\color {Blue}(4)}&&&{\tfrac {3}{2}}}\ _{\color {Blue}(8)}&&&{\tfrac {3}{3}{3}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {3}{4}}}&&&&{\tfrac {3}{5}}}&\cdots \\&&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&&&&&\\{{\tfrac {4}{1}}}\ _{\color {Blue}(9)}&&&{\tfrac {4}{2}}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}}&&&{\tfrac {4}{4}{4}}}}&&&{\tfrac {4}{5}}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\\{\tfrac {5}{1}}}\ _{\color {Blue}(10)}&&&{\tfrac {5}{2}}}&&&{\tfrac {5}{3}}}&&{\tfrac {5}{4}}}&&{\tfrac {5}{4}}}&{\tfrac {5}{5}}}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\end{array}}}} {\displaystyle {\begin{array}{lclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

På den måde tælles brøkerne med:

1 2 3 3 4 5 5 6 7 8 8 9 9 10 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 4 2 3 3 3 2 4 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccc}{color {Blue}1}&{\color {Blue}2}&{{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}11}&{\color {Blue}11}{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]1&{\tfrac {1}{2}}}&2&3&&{\tfrac {1}{3}}}&{\tfrac {1}{4}}}&{\tfrac {2}{3}}}}&{\tfrac {3}{2}}}&4&5&{\tfrac {1}{5}}}&\cdots \\\end{array}}}} {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\end{array}}}

Ved at udelade brøker, som stadig kan forenkles, er der en bijektion, som forbinder hvert element i de naturlige tal med et element i brøkerne:

For at vise, at alle naturlige tal og brøker har samme kardinalitet, skal elementet 0 tilføjes; efter hver brøk tilføjes dens negativ;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccc}{\color {Blue}1}}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}15}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]0&1&-1&{\tfrac {1}{2}}}&-{\tfrac {1}{2}}}&&{\tfrac {1}{2}}}&2&-2&3&-3&{\tfrac {1}{3}}}&-{\tfrac {1}{3}}}&{\tfrac {1}{4}}}&-{\tfrac {1}{4}}}&{\tfrac {2}{3}}}&-{\tfrac {2}{3}}}&\cdots \\\\end{array}}}} {\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}&\cdots \\\end{array}}}

På den måde er der en komplet bijektion, som knytter en brøk til hvert naturligt tal. Med andre ord: begge mængder har den samme kardinalitet. I dag kaldes mængder, der har det samme antal elementer som mængden af naturlige tal, for tællelige. Mængder, der har færre elementer end de naturlige tal, kaldes højst tællelige. Med denne definition er mængden af rationale tal/brøker tællelig.

Uendelige mængder har ofte egenskaber, som strider mod intuitionen: David Hilbert viste dette i et eksperiment, som kaldes Hilberts paradoks på Grand Hotel.

Reelle tal

Mængden af reelle tal har ikke samme kardinalitet som mængden af naturlige tal; der er flere reelle tal end naturlige tal. Ovennævnte idé har påvirket hans bevis. I sin artikel fra 1891 betragtede Cantor mængden T af alle uendelige sekvenser af binære tal (dvs. at hvert tal er nul eller et).

Han begynder med et konstruktivt bevis for følgende sætning:

Hvis s1 , s2 , ... , sn , ... er en hvilken som helst opregning af elementer fra T, er der altid et element s i T, som ikke svarer til noget sn i opregningen.

For at bevise dette, skal man give en opregning af elementer fra T, som f.eks.

s1 =

(0,

0,

0,

0,

0,

0,

0,

...)

s2 =

(1,

1,

1,

1,

1,

1,

1,

...)

s3 =

(0,

1,

0,

1,

0,

1,

0,

...)

s4 =

(1,

0,

1,

0,

1,

0,

1,

...)

s5 =

(1,

1,

0,

1,

0,

1,

1,

...)

s6 =

(0,

0,

1,

1,

0,

1,

1,

...)

s7 =

(1,

0,

0,

0,

1,

0,

0,

...)

...

Sekvensen s konstrueres ved at vælge det første ciffer som komplement til det første ciffer i s1 (0'er byttes ud med 1'er og omvendt), det andet ciffer som komplement til det andet ciffer i s2 , det tredje ciffer som komplement til det tredje ciffer i s3 , og generelt for hvert n, det nth ciffer som komplement til det nth ciffer i sn . I eksemplet giver dette:

s1

=

(0,

0,

0,

0,

0,

0,

0,

...)

s2

=

(1,

1,

1,

1,

1,

1,

1,

...)

s3

=

(0,

1,

0,

1,

0,

1,

0,

...)

s4

=

(1,

0,

1,

0,

1,

0,

1,

...)

s5

=

(1,

1,

0,

1,

0,

1,

1,

...)

s6

=

(0,

0,

1,

1,

0,

1,

1,

...)

s7

=

(1,

0,

0,

0,

1,

0,

0,

...)

...

s

=

(1,

0,

1,

1,

1,

0,

1,

...)

Ved konstruktionen adskiller s sig fra hvert sn , da deres nth cifre er forskellige (fremhævet i eksemplet). Derfor kan s ikke optræde i opregningen.

Baseret på denne sætning bruger Cantor derefter et modbevis for at vise, at:

Mængden T er utællelig.

Han antager, at T var tællelig. I så fald kunne alle dens elementer skrives som en opregning s1 , s2 , ... , sn , ... ... . Hvis man anvender den foregående sætning på denne opregning, vil man få en sekvens s, der ikke tilhører opregningen. Men s var et element i T og burde derfor være med i opregningen. Dette er i modstrid med den oprindelige antagelse, så T må være utællelig.

Spørgsmål og svar

Q: Hvad er Cantors diagonale argument?


A: Cantors diagonalargument er en matematisk metode til at bevise, at to uendelige mængder har samme kardinalitet.

Q: Hvornår udgav Cantor artikler om sit diagonalargument?


A: Cantor udgav artikler om sit diagonalargument i 1877, 1891 og 1899.

Q: Hvor blev Cantors første bevis for diagonalargumentet udgivet?


A: Cantors første bevis for diagonalargumentet blev offentliggjort i 1890 i tidsskriftet for det tyske matematiske selskab (Deutsche Mathematiker-Vereinigung).

Q: Hvornår har to mængder ifølge Cantor samme kardinalitet?


A: Ifølge Cantor har to mængder samme kardinalitet, hvis det er muligt at knytte et element fra den anden mængde til hvert element i den første mængde, og at knytte et element fra den første mængde til hvert element i den anden mængde.

Q: Fungerer Cantors udsagn om kardinalitet også for mængder med et endeligt antal elementer?


A: Ja, Cantors udsagn fungerer godt for mængder med et endeligt antal elementer.

Q: Er Cantors udsagn om kardinalitet intuitivt for mængder med et uendeligt antal elementer?


A: Nej, Cantors udsagn om kardinalitet er mindre intuitivt for mængder med et uendeligt antal elementer.

Q: Hvor mange gange udgav Cantor artikler om sit diagonalargument?


A: Cantor udgav artikler om sit diagonalargument tre gange - i 1877, 1891 og 1899.


Søge
AlegsaOnline.com - 2020 / 2025 - License CC3