Diagonální argument Cantors - Cantors diagonal argument - Wikipedia
v teorie množin, Cantorův diagonální argument, také nazývaný argument diagonalisation, argument diagonální lomítko, anti-diagonální argument, nebo diagonální metoda, byla vydána v roce 1891 autorem Georg Cantor jako matematický důkaz že existují nekonečné množiny do kterého nelze vložit osobní korespondence s nekonečnou sadou přirozená čísla.[1][2]:20–[3] Takové sady jsou nyní známé jako nespočetné sady, a velikost nekonečných množin je nyní zpracována teorií základní čísla kterou začal Cantor.
Diagonální argument nebyl Cantorův první důkaz nepočítatelnosti reálná čísla, který se objevil v roce 1874.[4][5]Ukazuje však obecnou techniku, která se od té doby používá v široké škále důkazů,[6] včetně prvního z Gödelovy věty o neúplnosti[2] a Turingova odpověď na Entscheidungsproblem. Diagonalizační argumenty jsou často také zdrojem rozporů Russellův paradox[7][8] a Richardův paradox.[2]:27
Nespočetná sada
Ve svém článku z roku 1891 Cantor uvažoval o sadě T všeho nekonečného sekvence z binární číslice (tj. každá číslice je nula nebo jedna). Začíná na a konstruktivní důkaz následující věty:
- Li s1, s2, … , sn, ... je jakýkoli výčet prvků z T, pak vždy existuje prvek s z T což odpovídá č sn ve výčtu.
Důkaz začíná výčtem prvků z T, například:
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, ...) ...
Dále sekvence s je konstruováno výběrem první číslice jako komplementární na první číslici s1 (výměna 0s pro 1s a naopak), druhá číslice jako doplňková k druhé číslici s2, 3. číslice jako doplňková k 3. číslici s3a obecně pro každého n, nth číslice jako doplněk k nth číslice sn. U výše uvedeného příkladu to přináší:
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, ...)
Podle konstrukce s se od každého liší sn, protože jejich nth číslice se liší (zvýrazněno v příkladu). s nemůže dojít ve výčtu.
Na základě této věty pak Cantor použije a důkaz rozporem ukázat, že:
- Sada T je nepočítatelné.
Důkaz začíná tím, že se to předpokládá T je počitatelný Poté lze všechny jeho prvky zapsat jako výčet s1, s2, ... , sn, .... Použití předchozí věty na tento výčet vytvoří sekvenci s nepatřící do výčtu. To je však v rozporu s být prvkem T a proto patří do výčtu. Tento rozpor naznačuje, že původní předpoklad je nepravdivý. Proto, T je nepočítatelné.
Skutečná čísla
Nepočítatelnost reálná čísla již byla založena Cantorův první důkaz nespočetnosti, ale také to vyplývá z výše uvedeného výsledku. Dokázat to, an injekce bude sestaven ze sady T nekonečných binárních řetězců do sady R reálných čísel. Od té doby T je nepočítatelné, obraz této funkce, což je podmnožina R, je nespočet. Proto, R je nepočítatelné. Také použitím konstrukční metody navržené společností Cantor, a bijekce bude postavena mezi T a R. Proto, T a R mají stejnou mohutnost, která se nazývá „mohutnost kontinua "a je obvykle označen nebo .
Injekce od T na R je dán mapováním řetězců v T na desetinná místa, například na mapování t = 0111 ... na desetinné místo 0,0111 .... Tato funkce, definovaná F (t) = 0.t, je injekce, protože mapuje různé řetězce na různá čísla.
Vytvoření bijekce mezi T a R je o něco komplikovanější. Namísto mapování 0111 ... na desetinné místo 0,0111 ... jej lze namapovat na základna b číslo: 0,0111 ...b. To vede k rodině funkcí: Fb (t) = 0.tb. Funkce F b(t) jsou injekce, kromě F 2(t). Tato funkce bude upravena tak, aby vytvářela bijekci mezi T a R.
| Konstrukce bijekce mezi T a R |
|---|
Funkce h: (0,1) → (−π / 2, π / 2) Funkce tan: (−π / 2, π / 2) → R Tato konstrukce využívá metodu navrženou Cantorem, která byla publikována v roce 1878. Použil ji k vytvoření bijekce mezi uzavřený interval [0, 1] a iracionální v otevřený interval (0, 1). Nejprve odstranil a počítatelně nekonečný podmnožinu z každé z těchto sad, takže mezi zbývajícími nespočetnými sadami existuje bijekce. Vzhledem k tomu, že existuje bijekce mezi spočetně nekonečnými podmnožinami, které byly odstraněny, kombinace těchto dvou bijekcí vytvoří bijekci mezi původními sadami.[9] K úpravě funkce lze použít Cantorovu metodu F 2(t) = 0.t2 vyprodukovat bijekci z T až (0, 1). Protože některá čísla mají dvě binární rozšíření, F 2(t) není injekční. Například, F 2(1000…) = 0.1000...2 = 1/2 a F 2(0111…) = 0.0111...2 = 1/4 + 1/8 + 1/16 + … = 1/2, takže 1000 ... i 0111 ... mapují na stejné číslo, 1/2. Pozměnit F2 (t), všimněte si, že se jedná o bijekci s výjimkou spočetně nekonečné podmnožiny (0, 1) a spočetně nekonečné podmnožiny T. Není to bijekce pro čísla v (0, 1), která mají dvě binární expanze. Tito se nazývají dyadický čísla a mít formulář m / 2n kde m je liché celé číslo a n je přirozené číslo. Uveďte tato čísla v pořadí: r = (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...). Taky, F2 (t) není bijekce na (0, 1) pro řetězce v T se objeví po binární bod v binárních expanzích 0, 1 a čísla v pořadí r. Vložte tyto postupně konstantní řetězce v pořadí: s = (000..., 111..., 1000..., 0111..., 01000..., 00111..., 11000..., 10111..., ...). Definujte bijekci G(t) z T do (0, 1): Pokud t je nth řetězec v pořadí s, nechť G(t) být nth číslo v pořadí r ; v opačném případě, G(t) = 0.t2. Postavit bijekci z T na R, začněte s tangenciální funkce opálení(X), což je bijekce od (−π / 2, π / 2) do R (viz obrázek zobrazený vpravo). Dále pozorujte, že lineární funkce h(X) = πX - π / 2 je bijekce od (0, 1) do (−π / 2, π / 2) (viz obrázek zobrazený vlevo). The složená funkce opálení(h(X)) = opálení (πX - π / 2) je bijekce od (0, 1) do R. Skládání této funkce pomocí G(t) vytváří funkci tan (h(G(t))) = opálení (πG(t) - π / 2), což je výrok z T na R. |
Obecné sady
Zobecněnou formu diagonálního argumentu použil Cantor k prokázání Cantorova věta: pro každého soubor S, napájecí sada z S—To znamená množina všech podmnožiny z S (zde psáno jako P(S)) - nemůže být v bijection s S sám. Tento důkaz probíhá následovně:
Nechat F být kdokoli funkce z S na P(S). Stačí dokázat F nemůže být surjektivní. To znamená, že nějaký člen T z P(S), tj. nějaká podmnožina S, není v obraz z F. Jako kandidát zvažte sadu:
- T = { s ∈ S: s ∉ F(s) }.
Pro každého s v S, buď s je v T nebo ne. Li s je v T, pak podle definice T, s není v F(s), tak T se nerovná F(s). Na druhou stranu, pokud s není v T, pak podle definice T, s je v F(s), takže znovu T se nerovná F(s); srov. Podrobnější popis tohoto důkazu viz Cantorova věta.
Důsledky
Řazení kardinálů
Cantor definuje objednávkový vztah kardinálností, např. a , pokud jde o existenci injekcí mezi podkladovými sadami, a . Argument v předchozím odstavci pak dokázal, že množiny jako jsou nespočetné, to znamená a můžeme přirozené objekty vložit do funkčního prostoru, abychom to měli . V kontextu klasická matematika, tím se vyčerpají možnosti a diagonální argument lze tedy použít k prokázání, že například ačkoli jsou obě uvažované množiny nekonečné, ve skutečnosti existují více nekonečné posloupnosti jedniček a nul, než jsou přirozená čísla. Tento výsledek pak také naznačuje, že pojem sada všech sad je nekonzistentní: Pokud S byly tedy sadou všech sad P(S) bude zároveň větší než S a podmnožina SZa předpokladu zákon vyloučeného prostředku, každý započitatelný set (vlastnost z hlediska surjekcí) je také již započítatelný.
v Konstruktivní matematika, je obtížnější nebo nemožné objednat si ordinály a také kardinály. Například Schröder – Bernsteinova věta vyžaduje zákon vyloučeného prostředku. Pořadí na realitách (standardní pořadí rozšiřující racionální čísla) také nemusí být nutně rozhodovatelné. Ani většina vlastností zajímavých tříd funkcí není rozhodnutelná Riceova věta, tj. správná množina počitatelných čísel pro započítatelné množiny nemusí být rekurzivní. V teorii množin jsou teorie matematiky modelován. Například v teorii množin „množina“ reálných čísel je identifikován jako soubor, který některé splňuje axiomy reálných čísel. Byly studovány různé modely, například Dedekind reals nebo Cauchy reals. Slabší axiomy znamenají menší omezení a umožňují tak bohatší třídu modelů. V důsledku toho je v jinak konstruktivním kontextu (zákon vyloučeného prostředku nepovažovaný za axiom) důsledně přijímat neklasické axiomy, které jsou v rozporu s důsledky práva vyloučeného prostředku. Například nespočetný prostor funkcí lze tvrdit, že je započitatelný, pojem velikosti kolmý k výroku .[10] V takovém kontextu je možné spočítat reálná čísla, což intuitivně vytváří tenčí sadu čísel než v jiných modelech.
Otevřené otázky
Motivován poznatkem, že množina reálných čísel je „větší“ než množina přirozených čísel, je veden k otázce, zda existuje množina, jejíž mohutnost je „mezi“ celými čísly a reálnými čísly. Tato otázka vede ke slavnému hypotéza kontinua. Podobně otázka, zda existuje množina, jejíž mohutnost je mezi |S| a |P(S) | pro některé nekonečné S vede k zobecněná hypotéza kontinua.
Diagonalizace v širších souvislostech
Russellův paradox to ukázal naivní teorie množin, na základě neomezené porozumění je rozporuplný. Všimněte si, že existuje podobnost mezi konstrukcí T a děj v Russellově paradoxu. Proto v závislosti na tom, jak upravíme schéma axiomu porozumění, abychom se vyhnuli Russellovu paradoxu, mohou a nemusí zůstat platné argumenty, jako je neexistence množiny všech množin.
Analogy úhlopříčného argumentu jsou v matematice široce používány k prokázání existence nebo neexistence určitých objektů. Například konvenční důkaz o neřešitelnosti zastavení problému je v podstatě diagonální argument. Také diagonalizace byla původně použita k prokázání existence libovolně tvrdé třídy složitosti a hrál klíčovou roli v prvních pokusech dokázat P se nerovná NP.
Verze pro Quine's New Foundations
Výše uvedený důkaz selže W. V. Quine „“Nové základy "teorie množin (NF). V NF, naivní axiom schéma porozumění je upraven, aby se zabránilo paradoxům zavedením jakési „místní“ teorie typů. V tomto schématu axiomu
- { s ∈ S: s ∉ F(s) }
je ne množina - tj. nesplňuje schéma axiomu. Na druhou stranu bychom se mohli pokusit vytvořit upravený diagonální argument tím, že si toho všimneme
- { s ∈ S: s ∉ F({s}) }
je soubor v NF. V takovém případě, pokud P1(S) je sada jednoprvkových podmnožin S a F je navrhovaná bijekce z P1(S) až P(S), jeden je schopen použít důkaz rozporem dokázat, že |P1(S)| < |P(S)|.
Důkaz vyplývá ze skutečnosti, že pokud F byly skutečně mapou na P(S), pak jsme mohli najít r v S, takový, že F({r}) se shoduje s upravenou sadou úhlopříček výše. Dospěli bychom k závěru, že pokud r není v F({r}), pak r je v F({r}) a naopak.
to je ne možné dát P1(S) ve vztahu jedna ku jedné s S, protože oba mají různé typy, a tak by každá takto definovaná funkce porušila pravidla psaní pro schéma porozumění.
Viz také
Reference
- ^ Georg Cantor (1891). „Ueber eine elementare Frage der Mannigfaltigkeitslehre“. Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. Anglický překlad: Ewald, William B. (ed.) (1996). Od Immanuela Kanta po Davida Hilberta: Kniha pramenů v základech matematiky, svazek 2. Oxford University Press. str. 920–922. ISBN 0-19-850536-1.CS1 maint: další text: seznam autorů (odkaz)
- ^ A b C Keith Simmons (30. července 1993). Univerzalita a lhář: Esej o pravdě a diagonálním argumentu. Cambridge University Press. ISBN 978-0-521-43069-2.
- ^ Rudin, Walter (1976). Principy matematické analýzy (3. vyd.). New York: McGraw-Hill. str.30. ISBN 0070856133.
- ^ Gray, Robert (1994), „Georg Cantor a transcendentní čísla“ (PDF), Americký matematický měsíčník, 101 (9): 819–832, doi:10.2307/2975129, JSTOR 2975129
- ^ Bloch, Ethan D. (2011). Skutečná čísla a skutečná analýza. New York: Springer. str.429. ISBN 978-0-387-72176-7.
- ^ Sheppard, Barnaby (2014). Logika nekonečna (ilustrované vydání). Cambridge University Press. str. 73. ISBN 978-1-107-05831-6. Výňatek ze strany 73
- ^ „Russellův paradox“. Stanfordská encyklopedie filozofie.
- ^ Bertrand Russell (1931). Základy matematiky. Norton. str. 363–366.
- ^ Viz strana 254 z Georg Cantor (1878), „Ein Beitrag zur Mannigfaltigkeitslehre“, Journal für die Reine und Angewandte Mathematik, 84: 242–258. Tento důkaz je popsán v Joseph Dauben (1979), Georg Cantor: Jeho matematika a filozofie nekonečna, Harvard University Press, ISBN 0-674-34871-0, str. 61–62, 65. Na straně 65 dokazuje Dauben výsledek, který je silnější než Cantorův. Nechává "φν označte jakoukoli posloupnost racionálních znaků v [0, 1]. “Cantor umožňuje φν označují sekvenci výčet racionály v [0, 1], což je druh sekvence potřebné pro jeho konstrukci bijekce mezi [0, 1] a iracionály v (0, 1).
- ^ Rathjen, M. "Principy volby v konstruktivních a klasických teoriích množin ", Proceedings of the Logic Cololoquium, 2002
