Paradoxy teorie množin - Paradoxes of set theory

Tento článek obsahuje diskusi o paradoxy teorie množin. Stejně jako u většiny matematických paradoxy, obecně odhalují překvapivé a protiintuitivní matematické výsledky, spíše než skutečné logické rozpory v moderní axiomatická teorie množin.

Základy

Kardinální čísla

Teorie množin jak je pojato Georg Cantor předpokládá existenci nekonečných množin. Protože tento předpoklad nelze dokázat z prvních principů, do kterých byl zaveden axiomatická teorie množin podle axiom nekonečna, který tvrdí existenci sady N přirozených čísel. Každá nekonečná množina, kterou lze vyjmenovat přirozenými čísly, má stejnou velikost (mohutnost) jako N, a říká se, že to lze spočítat. Příklady spočetně nekonečných množin jsou přirozená čísla, sudá čísla, prvočísla, a také všechny racionální čísla, tj. zlomky. Tyto sady mají společné základní číslovka |N| = ${displaystyle aleph _ {0}}$ (aleph-nic), číslo větší než každé přirozené číslo.

Kardinální čísla lze definovat následovně. Definujte dvě sady na mít stejnou velikost podle: existuje a bijekce mezi dvěma sadami (vzájemná korespondence mezi prvky). Kardinální číslo je podle definice třídou skládající se z Všechno sady stejné velikosti. Mít stejnou velikost je vztah ekvivalence a hlavní čísla jsou třídy ekvivalence.

Řadové číslovky

Kromě mohutnosti, která popisuje velikost množiny, jsou uspořádané množiny také předmětem teorie množin. The axiom volby zaručuje, že každá sada může být dobře objednané, což znamená, že na jeho prvky lze uložit celkovou objednávku, takže každá neprázdná podmnožina má první prvek s ohledem na tuto objednávku. Pořadí dobře uspořádané sady je popsáno pomocí pořadové číslo. Například 3 je pořadové číslo množiny {0, 1, 2} s obvyklým řádem 0 <1 <2; a ω je pořadové číslo množiny všech přirozených čísel seřazených obvyklým způsobem. Při zanedbání pořadí nám zbývá hlavní číslo |N| = | ω | =${displaystyle aleph _ {0}}$.

Pořadová čísla lze definovat stejnou metodou, která se používá pro základní čísla. Definujte dvě dobře uspořádané sady na mají stejný typ objednávky podle: existuje a bijekce mezi dvěma sadami respektujícími pořadí: menší prvky jsou mapovány na menší prvky. Pořadové číslo je podle definice třída skládající se z Všechno dobře uspořádané sady stejného typu objednávky. Mít stejný typ objednávky je vztah ekvivalence na třídě dobře uspořádaných množin a pořadová čísla jsou třídami ekvivalence.

Dvě sady stejného typu objednávky mají stejnou mohutnost. Konverzace obecně neplatí pro nekonečné množiny: na množinu přirozených čísel, která vedou k různým pořadovým číslům, je možné uložit různá uspořádání řádků.

Na ordinálech je přirozené uspořádání, které je samo o sobě řádným uspořádáním. Vzhledem k libovolnému pořadovému α lze považovat množinu všech řadových čísel za menší než α. Ukázalo se, že tato sada má pořadové číslo α. Toto pozorování se používá pro jiný způsob zavádění ordinálu, ve kterém je ordinál přirovnáván se sadou všech menších ordinálů. Tato forma pořadového čísla je tedy kanonickým představitelem dřívější formy třídy ekvivalence.

Napájecí sady

Vytvořením všech podmnožiny sady S (všechny možné volby jeho prvků), získáme napájecí sada P(S). Georg Cantor dokázal, že výkonová sada je vždy větší než sada, tj. |P(S)| > |S|. Zvláštní případ Cantorovy věty dokazuje, že množina všech reálných čísel R nelze vyčíslit přirozenými čísly. R je nepočítatelné: |R| > |N|.

Paradoxy nekonečné množiny

Místo spoléhání se na nejednoznačné popisy jako „to, které nelze zvětšit“ nebo „zvětšit bez vazby“, poskytuje teorie množin definice výrazu nekonečná sada dát jednoznačný význam frázím jako „množina všech přirozených čísel je nekonečná“. Stejně jako pro konečné množiny, teorie dělá další definice, které nám umožňují důsledně porovnávat dvě nekonečné množiny, pokud jde o to, zda je jedna množina „větší než“, „menší než“ nebo „má stejnou velikost jako“ druhá. Ale ne každá intuice týkající se velikosti konečných množin platí pro velikost nekonečných množin, což vede k různým zjevně paradoxním výsledkům týkajícím se výčtu, velikosti, míry a řádu.

Paradoxy výčtu

Před zavedením teorie množin byl pojem velikost sady bylo problematické. Diskutoval o tom Galileo Galilei a Bernard Bolzano, mezi ostatními. Existuje tolik přirozených čísel jako druhé mocniny přirozených čísel, měřeno metodou výčtu?

• Odpověď zní ano, protože pro každé přirozené číslo n existuje čtvercové číslo n², a také naopak.
• Odpověď je ne, protože čtverce jsou a správná podmnožina přirozených: každý čtverec je přirozené číslo, ale existují přirozená čísla, například 2, která nejsou čtverci přirozených čísel.

Definováním pojmu velikost množiny z hlediska její mohutnost, problém lze vyřešit. Protože existuje bijekce mezi dvěma zapojenými množinami to ve skutečnosti vyplývá přímo z definice mohutnosti množiny.

Vidět Hilbertův paradox Grand hotelu pro více informací o paradoxech výčtu.

Je le vois, mais je ne crois pas

„Vidím to, ale nevěřím,“ napsal Cantor Richard Dedekind po prokázání, že množina bodů čtverce má stejnou mohutnost jako body na pouhém okraji čtverce: mohutnost kontinua.

To ukazuje, že „velikost“ množin definovaných samotnou mohutností není jediným užitečným způsobem porovnání sad. Teorie měření poskytuje podrobnější teorii velikosti, která odpovídá naší intuici, že délka a plocha jsou nekompatibilní měřítka velikosti.

Důkazy silně naznačují, že Cantor si byl docela jistý samotným výsledkem a že jeho komentář k Dedekindovi namísto toho odkazuje na jeho tehdy ještě přetrvávající obavy ohledně platnosti jeho důkazu.^[1] Cantorova poznámka by však také pěkně posloužila k vyjádření překvapení, které tolik matematiků po něm zažilo při prvním setkání s výsledkem, který je tak protiintuitivní.

Paradoxy dobrého uspořádání

V roce 1904 Ernst Zermelo pomocí axiomu výběru (který byl zaveden z tohoto důvodu) bylo prokázáno, že každá sada může být dobře uspořádána. V roce 1963 Paul J. Cohen ukázal, že v teorii množin Zermelo – Fraenkel bez axiomu volby není možné prokázat existenci řádného uspořádání reálných čísel.

Schopnost dobře objednat libovolnou sadu však umožňuje provádět určité konstrukce, které se nazývají paradoxní. Jedním z příkladů je Banach – Tarski paradox, věta široce považovaná za neintuitivní. Uvádí, že je možné rozložit kouli o pevném poloměru na konečný počet kusů a poté tyto kousky přesunout a znovu sestavit obyčejnými překlady a rotace (bez změny měřítka) k získání dvou kopií z jedné původní kopie. Konstrukce těchto kusů vyžaduje axiom výběru; kousky nejsou jednoduché oblasti míče, ale komplikované podmnožiny.

Paradoxy Supertask

V teorii množin se nekonečná množina nepovažuje za vytvořenou nějakým matematickým procesem, jako je „přidání jednoho prvku“, který se poté provede „nekonečný počet opakování“. Místo toho určitá nekonečná množina (například množina všech přirozená čísla ) již údajně existuje „fiat“ jako předpoklad nebo axiom. Vzhledem k této nekonečné množině je potom prokázáno, že existují i ​​další nekonečné množiny, což je logický důsledek. Je však stále přirozenou filozofickou otázkou uvažovat o nějaké fyzické akci, která se skutečně dokončí po nekonečném počtu jednotlivých kroků; a interpretace této otázky pomocí teorie množin vede k paradoxům supertaskingu.

Deník Tristrama Shandyho

Tristram Shandy, hrdina románu od Laurence Sterne, píše svou autobiografii tak svědomitě, že mu trvá jeden rok, než stanoví události jednoho dne. Pokud je smrtelný, nikdy nemůže skončit; ale kdyby žil věčně, pak by žádná část jeho deníku nezůstala nepsaná, protože každému dni jeho života by odpovídal rok věnovaný popisu toho dne.

Paradox Ross-Littlewood

Zvýšená verze tohoto typu paradoxu posune nekonečně vzdálený cíl do konečného času. Naplňte obrovskou nádrž koulemi vyčíslenými čísly 1 až 10 a sundejte kouli číslo 1. Poté přidejte koule vyčíslené čísly 11 až 20 a vzlétněte číslo 2. Pokračujte v přidávání koulí s čísly 10n - 9 až 10n a odstranit číslo koule n pro všechna přirozená čísla n = 3, 4, 5, .... Nechte první transakci trvat půl hodiny, nechte druhou transakci trvat čtvrt hodinu atd., Aby byly všechny transakce dokončeny po jedné hodině. Je zřejmé, že množina koulí v nádrži se zvyšuje bez omezení. Nicméně po jedné hodině je nádrž prázdná, protože pro každý míč je znám čas odstranění.

Paradox se dále zvyšuje významem sekvence odstranění. Pokud kuličky nejsou odstraněny v pořadí 1, 2, 3, ... ale v pořadí 1, 11, 21, ... po jedné hodině se v nádrži naplní nekonečně mnoho kuliček, i když stejné množství materiálu jako dříve již byl přesunut.

Paradoxy důkazu a definovatelnosti

Navzdory své užitečnosti při řešení otázek týkajících se nekonečných množin má naivní teorie množin některé fatální nedostatky. Je to zejména kořist logické paradoxy jako jsou vystaveni Russellův paradox. Objev těchto paradoxů odhalil, že ne všechny množiny, které lze popsat v jazyce naivní teorie množin, lze ve skutečnosti říci, že existují bez vytváření rozporu. 20. století vidělo řešení těchto paradoxů ve vývoji různých axiomatizace teorií množin, jako je ZFC a NBG dnes běžně používané. Rozdíl mezi velmi formalizovaným a symbolický jazyk z těchto teorií a našeho typického neformálního používání matematického jazyka vyplývají různé paradoxní situace, stejně jako filozofická otázka, co přesně je to, že takové formální systémy ve skutečnosti navrhuji mluvit.

Rané paradoxy: množina všech množin

V roce 1897 italský matematik Cesare Burali-Forti zjistil, že neexistuje žádná sada obsahující všechna pořadová čísla. Protože každé pořadové číslo je definováno sadou menších pořadových čísel, dobře uspořádaná množina Ω všech pořadových čísel (pokud existuje) odpovídá definici a je sama o sobě pořadovým číslem. Na druhou stranu žádné pořadové číslo nemůže obsahovat samo sebe, takže Ω nemůže být pořadové číslo. Sada všech pořadových čísel proto nemůže existovat.

Na konci 19. století si Cantor uvědomoval neexistenci množiny všech světových čísel a množiny všech řadových čísel. V dopisech pro David Hilbert a Richard Dedekind psal o nekonzistentních sadách, jejichž prvky nelze považovat za všechny dohromady, a pomocí tohoto výsledku dokázal, že každá konzistentní sada má základní číslo.

Po tom všem byla verze paradoxu „sada všech sad“ koncipována Bertrand Russell v roce 1903 vedl k vážné krizi teorie množin. Russell toto prohlášení uznal X = X platí pro každou množinu, a tedy množinu všech množin definuje {X | X = X}. V roce 1906 zkonstruoval několik paradoxních sad, z nichž nejznámější je sada všech sad, které neobsahují samy sebe. Russell sám vysvětlil tuto abstraktní myšlenku pomocí několika velmi konkrétních obrázků. Jeden příklad, známý jako Kadeřnický paradox, uvádí: Mužský holič, který holí všechny a jen muže, kteří se neholí sami, se musí oholit, pouze pokud se neholí sám.

Existuje Russellův paradox v teorii množin a Grelling – Nelsonův paradox, což ukazuje paradox v přirozeném jazyce.

Paradoxy změnou jazyka

Königův paradox

V roce 1905 maďarský matematik Julius König zveřejnil paradox založený na skutečnosti, že konečných definic je jen počitatelně mnoho. Pokud si představíme reálná čísla jako dobře uspořádanou množinu, tvoří ta reálná čísla, která lze definitivně definovat, podmnožinu. Proto by v tomto pořadí mělo být první reálné číslo, které není definitivně definovatelné. To je paradoxní, protože toto skutečné číslo bylo právě definitivně definováno poslední větou. To vede k rozporu v naivní teorie množin.

Tomuto paradoxu se v axiomatické teorii množin vyhýbáme. Ačkoli je možné představit výrok o množině jako množině, systémem kódů známých jako Gödelova čísla, neexistuje žádný vzorec ${displaystyle phi (a, x)}$ v jazyce teorie množin, který platí přesně kdy A je kód pro konečný popis množiny a tento popis je skutečným popisem množiny X. Tento výsledek je znám jako Tarskiho věta o nedefinovatelnosti; vztahuje se na širokou třídu formálních systémů včetně všech běžně studovaných axiomatizací teorie množin.

Richardův paradox

Ve stejném roce francouzský matematik Jules Richard použil variantu Cantorova diagonální metoda získat další rozpor v naivní teorii množin. Zvažte sadu A všech konečných aglomerací slov. Sada E všech konečných definic reálných čísel je podmnožinou A. Tak jako A je spočítatelné, tak je E. Nechat p být ndesetinné místo nreálné číslo definované množinou E; vytvoříme číslo N s nulou pro integrální část a p + 1 pro ndesítkové číslo, pokud p není rovno 8 nebo 9 a jednota pokud p se rovná 8 nebo 9. Toto číslo N není definován množinou E protože se liší od konečně definovaného reálného čísla, konkrétně od nth číslo podle nth číslice. Ale N byl definován konečným počtem slov v tomto odstavci. Měl by tedy být v sadě E. To je rozpor.

Stejně jako u Königova paradoxu nelze tento paradox formovat v axiomatické teorii množin, protože vyžaduje schopnost říci, zda se popis vztahuje na konkrétní množinu (nebo ekvivalentně říci, zda je formule ve skutečnosti definicí jedné množiny).

Paradox Löwenheimu a Skolemu

Na základě práce německého matematika Leopold Löwenheim (1915) norský logik Thoralf Skolem v roce 1922 ukázal, že každý konzistentní teorie predikátový počet prvního řádu, jako je teorie množin, má nanejvýš spočítatelné Modelka. Nicméně, Cantorova věta dokazuje, že existuje nespočet souborů. Kořenem tohoto zdánlivého paradoxu je, že spočetnost nebo nepočítatelnost množiny není vždy absolutní, ale může záviset na modelu, ve kterém je měřena mohutnost. Je možné, aby množina byla nespočetná v jednom modelu teorie množin, ale spočetná ve větším modelu (protože bijekce, které stanoví počitatelnost, jsou ve větším modelu, ale ne v menším).

Viz také

• Důkaz nemožnosti
• Berry paradox

Poznámky

Reference

• G. Cantor: Gesammelte Abhandlungen mathematischen und philosophischen InhaltsE. Zermelo (ed.), Olms, Hildesheim 1966.
• H. Meschkowski, W. Nilson: Georg Cantor - BriefeSpringer, Berlín 1991.
• A. Fraenkel: Einleitung in die Mengenlehre, Springer, Berlín 1923.
• A. A. Fraenkel, A. Levy: Teorie abstraktních množin, Severní Holandsko, Amsterdam 1976.
• F. Hausdorff: Grundzüge der Mengenlehre, Chelsea, New York 1965.
• B. Russell: Principy matematiky I, Cambridge 1903.
• B. Russell: K některým obtížím v teorii transfinitních čísel a typů řádů, Proc. London Math. Soc. (2) 4 (1907) 29-53.
• P. J. Cohen: Teorie množin a hypotéza kontinua, Benjamin, New York 1966.
• S. Wagon: Banach – Tarski paradox, Cambridge University Press, Cambridge 1985.
• A. N. Whitehead, B. Russell: Principia Mathematica Já, Cambridge Univ. Press, Cambridge 1910, str. 64.
• E. Zermelo: Neuer Beweis für die Möglichkeit einer Wohlordnung, Math. Ann. 65 (1908) str. 107-128.

externí odkazy

• Principia Mathematica
• Paradoxy definovatelnosti podle Timothy Gowers
• „Russellův paradox“. Internetová encyklopedie filozofie.
• "Russell-Myhill Paradox". Internetová encyklopedie filozofie.