Diagonaalbewijs van Cantor

De diagonaalredenering van Cantor is een wiskundige methode om te bewijzen dat twee oneindige verzamelingen dezelfde kardinaliteit hebben. Cantor publiceerde er artikelen over in 1877, 1891 en 1899. Zijn eerste bewijs van het diagonaalargument werd in 1890 gepubliceerd in het tijdschrift van het Duits Wiskundig Genootschap (Deutsche Mathematiker-Vereinigung). Volgens Cantor hebben twee verzamelingen dezelfde kardinaliteit, als het mogelijk is om een element van de tweede verzameling te associëren met elk element van de eerste verzameling, en om een element van de eerste verzameling te associëren met elk element van de tweede verzameling. Deze uitspraak werkt goed voor verzamelingen met een eindig aantal elementen. Ze is minder intuïtief voor verzamelingen met een oneindig aantal elementen.

Cantor's eerste diagonaal argument

In het onderstaande voorbeeld worden twee van de eenvoudigste oneindige verzamelingen gebruikt, die van de natuurlijke getallen en die van de positieve breuken. Het idee is om aan te tonen dat beide verzamelingen, N {\displaystyle \mathbb {N} {\displaystyle \mathbb {N} }en Q+ {Q^{+}} dezelfde kardinaliteit {\displaystyle \mathbb {Q^{+}} }hebben.

Eerst worden de fracties als volgt in een matrix geplaatst:

1 1 1 2 1 3 1 4 1 5 2 1 2 2 3 2 4 2 5 3 1 3 2 3 3 3 4 3 5 4 1 4 2 4 3 4 4 5 5 1 5 2 5 3 5 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccc}{{tfrac {1}{1}}&&&{tfrac {1}{2}&&{{tfrac {1}{3}}&&{tfrac {1}{4}}&&&{\displaystyle {{array}{cccccccc}&{{tfrac {1}{1}}&&&{&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&&{\&&&&&&&&}&{\tfrac {2}{1}&&{\tfrac {2}{2}&{\tfrac {2}{3}}&&{\tfrac {2}{4}&&{\tfrac {2}{5}}&\&&&&&&&&}&&{\tfrac {3}{1}}&&{\tfrac {3}{2}&&&{\tfrac {3}{3}}&&{\tfrac {3}{4}&&{\tfrac {3}{5}}&\\&&&&&&&&&&{\tfrac {4}{1}&&&{\tfrac {4}{2}&&{\tfrac {4}{3}&&{\tfrac {4}{4}&&{\tfrac {4}{5}}&\&&&&&&&& }{\tfrac {5}{1}}&&{\tfrac {5}{2}&&{\tfrac {5}{3}}&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&&\dots &&\dvdots &&\dvdots &&\dvdots &&\dvdots &&dvdots &&dvdvdots &&dvdvdots &dith{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}}}

Vervolgens worden de getallen geteld, zoals afgebeeld. Breuken die vereenvoudigd kunnen worden, worden weggelaten:

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 5 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 ⋯ ⋮ ⋮ {{{displaystyle}{lclclclc}{lclclclc}{{tfrac {1}{1}}}}{{{color {Blue}(1)}&{\color {MidnightBlue}}&{\tfrac {1}{2}} _{\color {Blue}(2)}&&{\tfrac {1}{3}} _{\color {Blue}(5)}&{\color {MidnightBlue}}&{\tfrac {1}{4}} _{\color {Blue}(6)}&&{\tfrac {1}{5}} _{\color {Blue}(11)}&Nachtblauw, nachtblauw, nachtzwaluw, nachtzwaluw, nachtzwaluw, nachtzwaluw{\color {MidnightBlue}}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&{\tfrac {2}{1}}{\tfrac {2}{2}}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {2}{3}} _{\tcolor {Blue}(7)}&&{\tfrac {2}{4}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {2}{5}}&&{\\\\\\\\\\\kleurenblauw}&{\\kleurenblauw}&&{\\\kleurenblauw}&&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&{\tfrac {3}{1}}&&{\tfrac {3}{2}}} _{\tcolor {Blue}(8)}&&{\tfrac {3}{3}} _{\tcolor {Blue}(\cdot )}&&{\tfrac {3}{4}}&@ @tfrac {4}{1}}&&& @tfrac {4}{2}}&&{\color {Blue}(\cdot )}&&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}&&{\tfrac {4}{5}}&&{\}}&{\color {MidnightBlue}}&{\color {MidnightBlue}}&{\nearrow }&&&&&&&& &{\tfrac {5}{1}}&&&{\tfrac {5}{2}&&&{\tfrac {5}{3}&&&{\tfrac {5}{4}}&

Op die manier worden de breuken geteld:

1 2 3 4 5 6 7 8 9 10 11 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 4 2 3 3 2 4 5 1 5 {\displaystyle {begin{array}{cccccccccccccccccccccccccccccccccccc}{{color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{Blue}6}& {Blue}7}& {Blue}8}& {Blue}9}& {Blue}10}& {Blue}11}&{\a6}&{\a6}&\a6}&{\a6}&\a6}&{\a6}&{\a6}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{\a7}&{\a9}&{\a9}&{a8}&{\a9}&{\a9}{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&...en...en...en...en...en...en...en...en...en...en...{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\olor {MidnightBlue}\downarrow }&{\olor {MidnightBlue}\l3pt]1&{\tfrac {1}{2}}&2&3&{{tfrac {1}{3}}&{{tfrac {1}{4}}&{{tfrac {2}{3}}&{{tfrac {3}{2}&4&5&{{tfrac {1}{5}}&{{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}}}

Door het weglaten van fracties die nog vereenvoudigd kunnen worden, is er een bijectie die elk element van de natuurlijke getallen associeert met een element van de fracties:

Om aan te tonen dat alle natuurlijke getallen en de breuken dezelfde kardinaliteit hebben, moet het element 0 worden toegevoegd; na elke breuk wordt het negatief toegevoegd;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 - 2 3 {\displaystyle {\begin{array}{cccccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{Blue}8}& {Blue}9}& {Blue}10}& {Blue}11}& {Blue}12}& {Blue}13}& {Blue}14}& {Blue}15}&{\color {Blue}{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a6}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{\a9}&{a9}{a9}}...en...en...en...en...en...en...en...en...en...en...{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an5}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}&{\an8}{\an8}}&{\an8}{\an8}}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}}}

Op die manier is er een volledige bijectie, die aan elk natuurlijk getal een breuk toekent. Met andere woorden: beide verzamelingen hebben dezelfde kardinaliteit. Tegenwoordig heten verzamelingen die evenveel elementen hebben als de verzameling van natuurlijke getallen telbaar. Stellen die minder elementen hebben dan de natuurlijke getallen noemen we hoogstens telbaar. Met die definitie is de verzameling van rationale getallen/fracties telbaar.

Oneindige verzamelingen hebben vaak eigenschappen die tegen de intuïtie ingaan: David Hilbert toonde dit aan in een experiment dat Hilbert's paradox van het Grand Hotel wordt genoemd.

Reële getallen

De verzameling van reële getallen heeft niet dezelfde kardinaliteit als die van de natuurlijke getallen; er zijn meer reële getallen dan natuurlijke getallen. Het hierboven geschetste idee beïnvloedde zijn bewijs. In zijn artikel uit 1891 beschouwde Cantor de verzameling T van alle oneindige reeksen van binaire cijfers (d.w.z. elk cijfer is nul of één).

Hij begint met een constructief bewijs van de volgende stelling:

Indien s1, s2, ... , sn, ... een willekeurige opsomming is van elementen uit T, dan is er altijd een element s van T dat met geen sn in de opsomming overeenkomt.

Om dit te bewijzen, gegeven een opsomming van elementen uit T, zoals b.v.

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,

...)

...

De rij s wordt geconstrueerd door het eerste cijfer te kiezen als complementair met het eerste cijfer van s1 (waarbij 0's worden verwisseld met 1's en vice versa), het tweede cijfer als complementair met het tweede cijfer van s2, het derde cijfer als complementair met het derde cijfer van s3, en in het algemeen voor elke n, het n-de cijfer als complementair met het n-de cijfer van sn. In het voorbeeld levert dit op:

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,

...)

Volgens de constructie verschilt s van elke sn, aangezien hun n-de cijfers verschillen (in het voorbeeld gemarkeerd). Daarom kan s niet in de opsomming voorkomen.

Gebaseerd op deze stelling, gebruikt Cantor een bewijs van tegenspraak om aan te tonen dat:

De verzameling T is niet telbaar.

Hij neemt voor tegenspraak aan dat T telbaar was. In dat geval zouden al zijn elementen geschreven kunnen worden als een opsomming s1, s2, ... , sn, ... . Toepassing van de vorige stelling op deze opsomming zou een reeks s opleveren die niet tot de opsomming behoort. Echter, s was een element van T en zou dus in de opsomming moeten staan. Dit is in tegenspraak met de oorspronkelijke aanname, dus moet T ontelbaar zijn.

Vragen en antwoorden

V: Wat is het diagonaalargument van Cantor?


A: Het diagonaalargument van Cantor is een wiskundige methode om te bewijzen dat twee oneindige verzamelingen dezelfde kardinaliteit hebben.

V: Wanneer publiceerde Cantor artikelen over zijn diagonaal-argument?


A: Cantor publiceerde artikelen over zijn diagonaal argument in 1877, 1891 en 1899.

V: Waar werd Cantors eerste bewijs van het diagonaalargument gepubliceerd?


A: Cantor's eerste bewijs van het diagonaal-argument werd in 1890 gepubliceerd in het tijdschrift van het Duitse Wiskundige Genootschap (Deutsche Mathematiker-Vereinigung).

V: Wanneer hebben volgens Cantor twee verzamelingen dezelfde kardinaliteit?


Antwoord: Volgens Cantor hebben twee verzamelingen dezelfde kardinaliteit als het mogelijk is om aan elk element van de eerste verzameling een element van de tweede verzameling te koppelen, en aan elk element van de tweede verzameling een element van de eerste verzameling.

Vraag: Werkt Cantors verklaring over kardinaliteit goed voor verzamelingen met een eindig aantal elementen?


Antwoord: Ja, Cantors verklaring werkt goed voor verzamelingen met een eindig aantal elementen.

V: Is Cantors verklaring over kardinaliteit intuïtief voor verzamelingen met een oneindig aantal elementen?


Antwoord: Nee, Cantors verklaring over kardinaliteit is minder intuïtief voor verzamelingen met een oneindig aantal elementen.

V: Hoe vaak publiceerde Cantor artikelen over zijn diagonaalargument?


A: Cantor heeft drie keer artikelen over zijn diagonaalargument gepubliceerd - in 1877, 1891 en 1899.

AlegsaOnline.com - 2020 / 2023 - License CC3