Cantor-féle diagonális érv — a végtelen halmazok kardinálitásának bizonyítása

Ismerd meg Cantor diagonális érvet: lépésről lépésre magyarázat a végtelen halmazok kardinálitásának bizonyítására és következményeire.

Szerző: Leandro Alegsa

A Cantor-féle átlós érv egy matematikai módszer annak megállapítására, hogy két végtelen halmaz kardinálisa egyenlő-e, illetve — gyakrabban alkalmazva — arra, hogy bizonyos végtelen halmazok nem rendelkeznek ugyanazzal a kardinálissal. Cantor több ízben foglalkozott a témával (1877, 1891, 1899), és eredményeit cikkeiben közölte; az átlós érv első változata 1890-ben jelent meg a Német Matematikai Társaság (Deutsche Mathematiker-Vereinigung) folyóiratában. Cantor szerint két halmaznak akkor azonos a kardinalitása, ha az első halmaz minden eleméhez a második halmazból egy elemet, a második halmaz minden eleméhez pedig az első halmazból egy elemet lehet társítani — azaz ha létezik köztük kölcsönösen egyértelmű megfeleltetés (bijekció). Ez a megfogalmazás jól működik véges halmazoknál, de végtelen halmazoknál több, gyakran meglepő következménye van.

Az érv lényege (intuíció)

Az átlós módszer lényegében úgy működik, hogy feltételezünk egy listát (felsorolást) a vizsgált halmaz elemeiből, majd ezen felsorolás "átlóját" felhasználva konstruálunk egy olyan elemet, amely biztosan nincs a listában. Ha sikerül ilyen elemet előállítani, akkor a feltételezés — miszerint a lista tartalmaz minden elemet — ellentmondáshoz vezet, tehát nincs olyan felsorolás, ami az összes elemet tartalmazná.

Példa: a valós számok megszámlálhatatlansága

A legismertebb alkalmazás: a valós számok (például az (0,1) intervallum) nem megszámlálhatók, vagyis nincs bijekció a természetes számok és a valós számok között. A bizonyítás röviden:

  • Feltesszük, hogy létezik egy felsorolás minden (0,1)-beli valós számról: x1, x2, x3, ... és minden szám végtelen tizedes tört alakban felírható.
  • Kiírjuk ezeket egy táblázatba, ahol az i-edik sor az xi tizedesjegyeit tartalmazza: az i-edik sor j-edik oszlopában az xi j-edik tizedesjegye áll.
  • Most új számot készítünk úgy, hogy az n-edik tizedesjegye különbözzön az n-edik sor n-edik tizedesjegyétől (például ha az a(n) = 5, akkor válasszunk 6-ot; ha nem 5, válasszunk 5-öt). Ez a konstruktív szabály biztosítja, hogy az új szám eltér minden xi-től legalább egy tizedesjegyben — pontosan az i-edik szám i-edik helyén.
  • Tehát az új szám nincs a felsorolásban, tehát az eredeti feltételezés — miszerint létezik ilyen felsorolás — hamis. Következésképpen (0,1) megszámlálhatatlan.

Megjegyzés: a tizedesbeli felírások egyes esetekben nem egyértelműek (például 0,4999... = 0,5000...), ezt el lehet kerülni úgy, hogy bináris bővítést alkalmazunk, vagy egyszerű szabályt adunk a választáshoz (például soha ne használjunk végtelen 9-es sorozatot). A lényeg, hogy az átlós konstrukció minden lehetséges felsorolást megbuktat.

Cantor-tétel (a hatványhalmaz nagyobb kardinális)

A diagonális ötlet általánosítható: Cantor bizonyította, hogy bármely halmaz A hatványhalmaza P(A) (az A-nek minden részhalmazát tartalmazó halmaz) nagyobb kardinálissal rendelkezik, mint A maga. Formálisan: nincs olyan leképezés f: A → P(A), ami surjektív lenne. Az egyszerű bizonyítás a következő paradoxonszerű konstrukción alapul:

  • Tegyük fel, létezik surjektív f. Definiáljuk S = { x ∈ A | x ∉ f(x) } (azok az elemek, amelyek nincsenek benne a róluk képzett részhalmazban).
  • Mivel f surjektív, van y ∈ A, hogy f(y) = S. Most vizsgáljuk, benne van-e y S-ben. Ha y ∈ S, akkor definíció szerint y ∉ f(y) = S — ellentmondás. Ha y ∉ S, akkor definíció szerint y ∈ f(y) = S — szintén ellentmondás.
  • Tehát f nem lehet surjektív, és következik, hogy |P(A)| > |A|.

Következmények és alkalmazások

  • Cantor munkája megmutatta, hogy "végtelen" nem egységes fogalom: vannak kisebb és nagyobb végtelenek (pl. a természetes számok halmaza megszámlálható, a valós számok nem).
  • A diagonális érvet és annak változatait széleskörűen használják más területeken: a számítástudományban (Gödel-incompleteness és a Turing-féle megállási probléma bizonyításai), a logikában és halmazelméletben.
  • A Cantor-tétel az alapja a folytatásos hipotézis (continuum hypothesis) kérdésének, amely azt vizsgálja, hogy van-e halmaz a természetes számok és a valós számok közötti kardinális nagysággal.

Történeti megjegyzés

Cantor publikációi (említve korábban) révén váltak ismertté ezek az eredmények; az átlós érv és a hatványhalmazra vonatkozó tétel alapvető fogalommá vált a modern halmazelméletben és a matematika filozófiájában.

Összefoglalva: a Cantor-féle diagonális érv egyszerű, de rendkívül hatékony eszköz a végtelen halmazok kardinális viszonyainak feltárására — megmutatja, hogy bizonyos végtelen halmazok (például a valós számok vagy a hatványhalmazok) nagyobb "méretűek", mint más végtelen halmazok (például a természetes számok).

Cantor első diagonális érve

Az alábbi példa a legegyszerűbb végtelen halmazok közül kettőt használ, a természetes számok és a pozitív törtek halmazát. Az ötlet az, hogy megmutassuk, hogy mindkét halmaz, N {\displaystyle \mathbb {N} }{\displaystyle \mathbb {N} } és Q + {\displaystyle \mathbb {Q^{+}} }{\displaystyle \mathbb {Q^{+}} } ugyanolyan kardinalitásúak.

Először is a törteket egy tömbbe rendezzük a következőképpen:

1 1 1 1 2 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 2 2 3 2 4 2 2 5 ⋯ 3 1 3 2 2 3 3 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccccccc}{\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}}&&&{\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}{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 &&\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}}}

Ezután a számokat megszámoljuk, ahogyan az látható. Az egyszerűsíthető törteket kihagyjuk:

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 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 3 5 4 5 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\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}{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 &&\\\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}}}

Így a törteket is megszámoljuk:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 2 3 1 3 1 3 1 4 2 3 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccccccccccccccc}{\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}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 }\\\\[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}}}

A még egyszerűsíthető törtek elhagyásával egy olyan bijekciót kapunk, amely a természetes számok minden egyes elemét a törtek egy-egy eleméhez társítja:

Ahhoz, hogy megmutassuk, hogy az összes természetes szám és a törtek kardinalitása megegyezik, a 0 elemet kell hozzáadni; minden tört után a negatívját is hozzáadjuk;

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}{cccccccccccccccccccccccccc}{\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}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}}&&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}}}

Így létezik egy teljes bijekció, amely minden természetes számhoz egy törtet társít. Más szóval: mindkét halmaznak ugyanaz a kardinalitása. Ma azokat a halmazokat, amelyeknek ugyanannyi elemük van, mint a természetes számok halmazának, megszámlálhatónak nevezzük. Azokat a halmazokat, amelyeknek kevesebb elemük van, mint a természetes számok halmazának, legfeljebb megszámlálhatónak nevezzük. Ezzel a definícióval a racionális számok/törtek halmaza megszámlálható.

A végtelen halmazok gyakran rendelkeznek olyan tulajdonságokkal, amelyek ellentmondanak az intuíciónak: David Hilbert ezt egy kísérletben mutatta ki, amelyet Hilbert Grand Hotel-paradoxonjának nevezünk.

Valós számok

A valós számok halmaza nem azonos kardinalitású a természetes számok halmazával; több valós szám van, mint természetes szám. A fent vázolt gondolat befolyásolta a bizonyítását. Cantor 1891-es cikkében a bináris számjegyek (azaz minden számjegy nulla vagy egy) végtelen sorozatainak T halmazát vizsgálta.

A következő tétel konstruktív bizonyításával kezdi:

Ha s1 , s2 , ... , sn , ... a T elemek bármelyik felsorolása, akkor mindig van a T-nek egy olyan s eleme, amely nem felel meg a felsorolásban szereplő s elemnek.n

Ennek bizonyítására, adott a T elemeinek felsorolása, mint pl.

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,

...)

...

Az s sorozatot úgy állítjuk össze, hogy az 1. számjegyet az s1 1. számjegyének komplementerének választjuk (a 0-kat felcseréljük az 1-ekkel és fordítva), a 2. számjegyet az s2 2. számjegyének komplementerének, a 3. számjegyet az s3 3. számjegyének, és általában minden n esetében az nth számjegyet az sn nth számjegyének komplementerének:

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,

...)

A konstrukció szerint s különbözik minden sn -től, mivel nth számjegyük különbözik (a példában kiemelve). Ezért s nem fordulhat elő a felsorolásban.

E tétel alapján Cantor ezután egy ellentmondásos bizonyítással kimutatja, hogy:

A T halmaz megszámlálhatatlan.

Ellentmondás esetén feltételezi, hogy T megszámlálható volt. Ebben az esetben minden elemét fel lehetne írni egy felsorolásként s1 , s2 , ... , sn , ... ... . Az előző tételt erre a felsorolásra alkalmazva egy olyan s sorozatot kapnánk, amely nem tartozik a felsoroláshoz. Azonban s a T eleme volt, és ezért a felsorolásban kell lennie. Ez ellentmond az eredeti feltételezésnek, tehát T-nek megszámlálhatatlan kell lennie.

Kérdések és válaszok

K: Mi a Cantor-féle átlós érv?


V: Cantor diagonális érve egy matematikai módszer annak bizonyítására, hogy két végtelen halmaznak ugyanaz a kardinalitása.

K: Mikor publikált Cantor cikkeket az átlós érvéről?


V: Cantor 1877-ben, 1891-ben és 1899-ben publikált cikkeket a diagonális érvéről.

K: Hol jelent meg Cantor első bizonyítása a diagonális érvről?


V: Cantor első bizonyítása a diagonális érvről 1890-ben jelent meg a Német Matematikai Társaság (Deutsche Mathematiker-Vereinigung) folyóiratában.

K: Cantor szerint mikor van két halmaznak azonos kardinalitása?


V: Cantor szerint két halmaznak akkor van azonos kardinalitása, ha az első halmaz minden egyes eleméhez a második halmaz egy-egy elemét, a második halmaz minden egyes eleméhez pedig az első halmaz egy-egy elemét lehet hozzárendelni.

Kérdés: Cantor kardinálisra vonatkozó kijelentése véges elemszámú halmazok esetén is működik?


V: Igen, Cantor állítása jól működik véges elemszámú halmazok esetén.

K: A végtelen számú elemmel rendelkező halmazok esetében intuitív Cantor kijelentése a kardinalitásról?


V: Nem, Cantor kijelentése a kardinalitásról kevésbé intuitív a végtelen elemszámú halmazok esetében.

K: Hányszor publikált Cantor cikkeket az átlós érvéről?


V: Cantor háromszor - 1877-ben, 1891-ben és 1899-ben - publikált cikkeket a diagonális érvéről.


Keres
AlegsaOnline.com - 2020 / 2025 - License CC3