Paradoksy teorii mnogości - Paradoxes of set theory

Ten artykuł zawiera omówienie paradoksów teorii mnogości . Podobnie jak w przypadku większości matematycznych paradoksów , ujawniają one raczej zaskakujące i sprzeczne z intuicją matematyczne wyniki, a nie rzeczywiste sprzeczności logiczne w ramach współczesnej aksjomatycznej teorii mnogości .

Podstawy

Liczby kardynalne

Teoria mnogości w ujęciu Georga Cantora zakłada istnienie nieskończonych zbiorów. Ponieważ założenie to nie może być udowodnione na podstawie pierwszych zasad, zostało ono wprowadzone do aksjomatycznej teorii mnogości przez aksjomat nieskończoności , który potwierdza istnienie zbioru N liczb naturalnych. Każdy nieskończony zbiór, który można wyliczyć liczbami naturalnymi, ma taki sam rozmiar (liczność) jak N i mówi się, że jest policzalny. Przykładami policzalnie nieskończonych zbiorów są liczby naturalne, liczby parzyste, liczby pierwsze , a także wszystkie liczby wymierne , czyli ułamki. Te zbiory mają wspólną liczbę kardynalną | N | = (aleph-zero), liczba większa niż każda liczba naturalna. ${\ displaystyle \ aleph _ {0}}$

Liczby kardynalne można zdefiniować w następujący sposób. Zdefiniuj dwa zestawy tak, aby miały ten sam rozmiar przez: istnieje bijekcja między dwoma zestawami (zgodność jeden do jednego między elementami). Zatem liczba kardynalna jest z definicji klasą składającą się ze wszystkich zbiorów tej samej wielkości. Posiadanie tego samego rozmiaru jest relacją równoważności , a liczby kardynalne to klasy równoważności .

Liczby porządkowe

Oprócz liczności, która opisuje rozmiar zbioru, zbiory uporządkowane również stanowią przedmiot teorii mnogości. Aksjomatu wyboru gwarantuje, że każdy zbiór można dobrze uporządkowane , co oznacza, że całkowita zamówienie może zostać nałożone na jego elementy takie, że każdy niepusty podzbiór ma pierwszy element w stosunku do tego celu. Porządek uporządkowanego zbioru jest opisany liczbą porządkową . Na przykład 3 to liczba porządkowa zbioru {0, 1, 2} w zwykłej kolejności 0 <1 <2; a ω jest liczbą porządkową zbioru wszystkich liczb naturalnych uporządkowanych w zwykły sposób. Pomijając porządek, pozostaje nam numer kardynalny | N | = | ω | = . ${\ displaystyle \ aleph _ {0}}$

Liczby porządkowe można definiować tą samą metodą, co w przypadku liczebników głównych. Zdefiniuj dwa dobrze uporządkowane zestawy, aby miały ten sam typ kolejności, przez: istnieje bijekcja między dwoma zestawami uwzględniająca kolejność: mniejsze elementy są mapowane na mniejsze elementy. Zatem liczba porządkowa jest z definicji klasą składającą się ze wszystkich uporządkowanych zbiorów tego samego typu. Posiadanie tego samego typu porządku jest relacją równoważności w klasie dobrze uporządkowanych zbiorów, a liczby porządkowe są klasami równoważności.

Dwa zestawy tego samego typu zamówienia mają tę samą liczność. Odwrotność nie jest generalnie prawdziwa dla zbiorów nieskończonych: możliwe jest narzucenie różnych porządków na zbiorze liczb naturalnych, które dają początek różnym liczbom porządkowym.

Na liczbach porządkowych istnieje naturalny porządek, który sam w sobie jest dobrym uporządkowaniem. Biorąc pod uwagę dowolną liczbę porządkową α, można rozważyć zbiór wszystkich liczb porządkowych mniejszy niż α. Okazuje się, że ten zbiór ma liczbę porządkową α. Ta obserwacja służy do innego sposobu wprowadzenia liczby porządkowej, w której liczba porządkowa jest utożsamiana ze zbiorem wszystkich mniejszych liczb porządkowych. Ta forma liczby porządkowej jest zatem kanonicznym reprezentantem wcześniejszej formy klasy równoważności.

Zestawy zasilające

Tworząc wszystkie podzbiory zbioru S (wszystkie możliwe wybory jego elementów), otrzymujemy zbiór potęg P ( S ). Georg Cantor udowodnił, że zbiór mocy jest zawsze większy niż zbiór, czyli | P ( S ) | > | S |. Szczególny przypadek twierdzenia Cantora dowodzi, że zbioru wszystkich liczb rzeczywistych R nie można wyliczyć liczbami naturalnymi. R jest niepoliczalne: | R | > | N |.

Paradoksy nieskończonego zbioru

Zamiast polegać na niejednoznacznych opisach, takich jak „to, czego nie można powiększyć” lub „zwiększanie bez ograniczeń”, teoria mnogości podaje definicje terminu nieskończony zbiór, aby nadać jednoznaczne znaczenie wyrażeniom takim jak „zbiór wszystkich liczb naturalnych jest nieskończony” . Podobnie jak w przypadku zbiorów skończonych , teoria tworzy dalsze definicje, które pozwalają nam konsekwentnie porównywać dwa nieskończone zbiory pod względem tego, czy jeden zbiór jest „większy niż”, „mniejszy niż” czy „ma taki sam rozmiar jak” drugi. Ale nie każda intuicja dotycząca rozmiaru zbiorów skończonych odnosi się do rozmiaru zbiorów nieskończonych, co prowadzi do różnych pozornie paradoksalnych wyników dotyczących wyliczenia, rozmiaru, miary i porządku.

Paradoksy wyliczenia

Przed wprowadzeniem teorii mnogości pojęcie rozmiaru zbioru było problematyczne. Dyskutowali o tym między innymi Galileo Galilei i Bernard Bolzano . Czy jest tyle liczb naturalnych, ile kwadratów liczb naturalnych mierzonych metodą wyliczenia?

Odpowiedź brzmi: tak, ponieważ dla każdej liczby naturalnej n jest liczba kwadratowa n ² i tak samo jest na odwrót.
Odpowiedź brzmi: nie, ponieważ kwadraty są odpowiednim podzbiorem liczb naturalnych: każdy kwadrat jest liczbą naturalną, ale istnieją liczby naturalne, takie jak 2, które nie są kwadratami liczb naturalnych.

Definiując pojęcie wielkości zbioru pod kątem jego liczności można rozstrzygnąć kwestię. Ponieważ między dwoma zaangażowanymi zbiorami istnieje bijekcja , wynika to w rzeczywistości bezpośrednio z definicji liczności zbioru.

Zobacz paradoks Hilberta Grand Hotelu, aby dowiedzieć się więcej o paradoksach wyliczenia.

Je le vois, mais je ne crois pas

„Widzę to, ale nie wierzę” - napisał Cantor do Richarda Dedekinda po tym, jak udowodnił, że zbiór punktów w kwadracie ma taką samą liczność jak punkty na krawędzi kwadratu: liczność kontinuum .

To pokazuje, że „rozmiar” zbiorów określony przez samą liczność nie jest jedynym użytecznym sposobem porównywania zbiorów. Teoria miary dostarcza bardziej zniuansowanej teorii rozmiaru, która jest zgodna z naszą intuicją, że długość i powierzchnia są niekompatybilnymi miarami wielkości.

Dowody silnie sugerują, że Cantor był całkiem pewny samego wyniku i że jego komentarz do Dedekinda odnosi się zamiast tego do jego wciąż utrzymujących się obaw co do ważności jego dowodu na to. Niemniej jednak uwaga Cantora dobrze służyłaby również do wyrażenia zdziwienia, którego tak wielu matematyków po nim doświadczyło, gdy po raz pierwszy napotkało wynik tak sprzeczny z intuicją.

Paradoksy dobrego uporządkowania

W 1904 roku Ernst Zermelo udowodnił za pomocą aksjomatu wyboru (który został wprowadzony z tego powodu), że każdy zbiór można dobrze uporządkować. W 1963 roku Paul J. Cohen wykazał, że w teorii mnogości Zermelo – Fraenkla bez aksjomatu wyboru nie można udowodnić istnienia dobrego uporządkowania liczb rzeczywistych.

Jednak umiejętność uporządkowania dowolnego zestawu pozwala na wykonanie pewnych konstrukcji, które nazwano paradoksem. Jednym z przykładów jest paradoks Banacha – Tarskiego , twierdzenie powszechnie uważane za nieintuicyjne. Stwierdza, że możliwe jest rozłożenie kuli o ustalonym promieniu na skończoną liczbę części, a następnie przesunięcie i ponowne złożenie tych kawałków za pomocą zwykłych tłumaczeń i obrotów (bez skalowania), aby uzyskać dwie kopie z jednej oryginalnej kopii. Konstrukcja tych utworów wymaga aksjomatu wyboru; Bierki nie są prostymi obszarami piłki, ale skomplikowanymi podzbiorami .

Paradoksy Supertask

W teorii mnogości nieskończony zbiór nie jest uważany za stworzony przez jakiś proces matematyczny, taki jak „dodanie jednego elementu”, który jest następnie wykonywany „nieskończoną liczbę razy”. Zamiast tego mówi się , że określony nieskończony zbiór (taki jak zbiór wszystkich liczb naturalnych ) już istnieje, „przez fiat”, jako założenie lub aksjomat. Biorąc pod uwagę ten nieskończony zbiór, udowadnia się istnienie innych nieskończonych zbiorów, co jest logiczną konsekwencją. Jednak rozważanie jakiejś fizycznej czynności, która faktycznie kończy się po nieskończonej liczbie dyskretnych kroków, jest nadal naturalnym pytaniem filozoficznym; a interpretacja tego pytania za pomocą teorii mnogości prowadzi do paradoksów super zadania.

Pamiętnik Tristrama Shandy

Tristram Shandy , bohater powieści Laurence'a Sterne'a , pisze swoją autobiografię tak sumiennie, że opisanie wydarzeń jednego dnia zajmuje mu rok. Jeśli jest śmiertelny, nigdy nie wygaśnie; ale gdyby żył wiecznie, żadna część jego dziennika nie pozostałaby niepisana, gdyż każdemu dniu jego życia odpowiadałby rok poświęcony opisowi tego dnia.

Paradoks Rossa-Littlewooda

Zwiększona wersja tego typu paradoksu przenosi nieskończenie odległe zakończenie do skończonego czasu. Napełnij ogromny zbiornik kulkami wyliczonymi numerami od 1 do 10 i zdejmij kulkę numer 1. Następnie dodaj kule wyliczone numerami od 11 do 20 i zdejmij numer 2. Kontynuuj dodawanie piłek wyliczonych numerami 10 n - 9 do 10 n i usunąć liczbę kulkową n dla wszystkich liczb naturalnych n = 3, 4, 5, .... Niech pierwsza transakcja trwa pół godziny, druga niech trwa kwadrans i tak dalej, tak aby wszystkie transakcje zostały zakończone po jedna godzina. Oczywiście zestaw kulek w zbiorniku zwiększa się bez ograniczeń. Niemniej jednak po godzinie zbiornik jest pusty, ponieważ dla każdej kulki znany jest czas jej usunięcia.

Paradoks dodatkowo potęguje znaczenie sekwencji usuwania. Jeśli kulki nie zostaną wyjęte w kolejności 1, 2, 3, ... ale w sekwencji 1, 11, 21, ... po godzinie nieskończenie wiele kulek wypełnia zbiornik, chociaż ta sama ilość materiału co poprzednio został przeniesiony.

Paradoksy dowodu i definiowalności

Pomimo całej swojej użyteczności w rozwiązywaniu pytań dotyczących zbiorów nieskończonych, naiwna teoria zbiorów ma kilka fatalnych błędów. W szczególności jest ofiarą logicznych paradoksów, takich jak te ujawnione przez paradoks Russella . Odkrycie tych paradoksów ujawniło, że nie wszystkie zbiory, które można opisać językiem naiwnej teorii mnogości, faktycznie istnieją bez tworzenia sprzeczności. XX wiek przyniósł rozwiązanie tych paradoksów w rozwoju różnych aksjomatyzacji powszechnie używanych teorii mnogości, takich jak ZFC i NBG . Jednak przepaść między bardzo sformalizowanym i symbolicznym językiem tych teorii a naszym typowym nieformalnym użyciem języka matematycznego powoduje różne paradoksalne sytuacje, a także filozoficzne pytanie, o czym dokładnie te systemy formalne proponują mówić.

Wczesne paradoksy: zbiór wszystkich zbiorów

W 1897 roku włoski matematyk Cesare Burali-Forti odkrył, że nie ma zbioru zawierającego wszystkie liczby porządkowe. Ponieważ każda liczba porządkowa jest zdefiniowana przez zbiór mniejszych liczb porządkowych, dobrze uporządkowany zbiór Ω wszystkich liczb porządkowych (jeśli istnieje) pasuje do definicji i sam jest liczbą porządkową. Z drugiej strony żadna liczba porządkowa nie może zawierać siebie, więc Ω nie może być liczbą porządkową. Dlatego zbiór wszystkich liczb porządkowych nie może istnieć.

Pod koniec XIX wieku Cantor był świadomy nieistnienia zbioru wszystkich liczebników głównych i zbioru wszystkich liczebników porządkowych. W listach do Davida Hilberta i Richarda Dedekinda pisał o niespójnych zbiorach, o których elementach nie można myśleć jako o całości, i wykorzystał ten wynik, aby udowodnić, że każdy spójny zbiór ma liczbę kardynalną.

Po tym wszystkim, wersja paradoksu „zbioru wszystkich zbiorów” opracowana przez Bertranda Russella w 1903 roku doprowadziła do poważnego kryzysu teorii mnogości. Russell uznał, że stwierdzenie x = x jest prawdziwe dla każdego zbioru, a zatem zbiór wszystkich zbiorów jest zdefiniowany przez { x | x = x }. W 1906 roku skonstruował kilka zestawów paradoksów, z których najsłynniejszy to zbiór wszystkich zestawów, które same siebie nie zawierają. Sam Russell wyjaśnił tę abstrakcyjną ideę za pomocą bardzo konkretnych zdjęć. Jeden z przykładów, znany jako paradoks fryzjera , mówi: Mężczyzna fryzjer, który goli wszystkich i tylko mężczyzn, którzy się nie golą, musi się golić tylko wtedy, gdy się nie goli.

Istnieją bliskie podobieństwa między paradoksem Russella w teorii mnogości a paradoksem Grellinga-Nelsona , który demonstruje paradoks w języku naturalnym.

Paradoksy przez zmianę języka

Paradoks Königa

W 1905 roku węgierski matematyk Julius König opublikował paradoks oparty na fakcie, że istnieje tylko policzalnie wiele skończonych definicji. Jeśli wyobrazimy sobie liczby rzeczywiste jako dobrze uporządkowany zbiór, te liczby rzeczywiste, które można ostatecznie zdefiniować, tworzą podzbiór. Stąd w tym uporządkowanym porządku powinna istnieć pierwsza liczba rzeczywista, której nie można ostatecznie zdefiniować. Jest to paradoksalne, ponieważ ta liczba rzeczywista została właśnie ostatecznie zdefiniowana w ostatnim zdaniu. Prowadzi to do sprzeczności w naiwnej teorii mnogości .

Ten paradoks unika się w aksjomatycznej teorii mnogości. Chociaż możliwe jest przedstawienie zdania o zbiorze jako zbiorze, za pomocą systemu kodów znanego jako liczby Gödla , w języku teorii mnogości nie ma wzoru, który dokładnie określa, kiedy jest kod zdania skończonego o zbiorze, jest zbiorem i trzyma się . Wynik ten jest znany jako twierdzenie o nieokreśloności Tarskiego ; dotyczy to szerokiej klasy systemów formalnych, w tym wszystkich powszechnie badanych aksjomatyzacji teorii mnogości. ${\ Displaystyle \ varphi (a, x)}$ ${\ displaystyle a}$ ${\ displaystyle x}$ ${\ displaystyle a}$ ${\ displaystyle x}$

Paradoks Richarda

W tym samym roku francuski matematyk Jules Richard użył wariantu metody diagonalnej Cantora, aby uzyskać kolejną sprzeczność w naiwnej teorii mnogości. Rozważ zbiór A wszystkich skończonych skupisk słów. Zestaw E wszystkich skończonych definicji liczb rzeczywistych jest podzbiorem A . Jako jest policzalny, taka E . Niech p będzie n- tym miejscem dziesiętnym n- tej liczby rzeczywistej określonej przez zbiór E ; tworzymy liczbę N mającą zero dla części całkowitej i p + 1 dla n- tego miejsca po przecinku, jeśli p nie jest równe 8 lub 9, i jedność, jeśli p jest równe 8 lub 9. Ta liczba N nie jest zdefiniowana przez zestaw E, ponieważ różni się od dowolnej skończonej liczby rzeczywistej, a mianowicie od n- tej liczby przez n- tą cyfrę. Ale N zostało zdefiniowane przez skończoną liczbę słów w tym akapicie. Należy zatem w zbiorze E . To jest sprzeczność.

Podobnie jak w przypadku paradoksu Königa, paradoks ten nie może być sformalizowany w aksjomatycznej teorii mnogości, ponieważ wymaga umiejętności stwierdzenia, czy opis dotyczy określonego zbioru (lub, równoważnie, stwierdzenia, czy formuła jest w rzeczywistości definicją pojedynczego zbioru).

Paradoks Löwenheim i Skolem

Opierając się na pracy niemieckiego matematyka Leopolda Löwenheima (1915), norweski logik Thoralf Skolem wykazał w 1922 roku, że każda spójna teoria rachunku predykatów pierwszego rzędu , taka jak teoria mnogości, ma co najwyżej policzalny model . Jednak twierdzenie Cantora dowodzi, że zbiory są niepoliczalne. Źródłem tego pozornego paradoksu jest to, że policzalność lub niepoliczalność zbioru nie zawsze jest bezwzględna , ale może zależeć od modelu, w którym mierzona jest liczność. Zbiór może być niepoliczalny w jednym modelu teorii mnogości, ale policzalny w większym modelu (ponieważ bijekcje, które określają policzalność, są w większym modelu, ale nie w mniejszym).

Zobacz też

Uwagi

Bibliografia

G. Cantor: Gesammelte Abhandlungen mathematischen und filozofischen Inhalts , E. Zermelo (red.), Olms, Hildesheim 1966.
H. Meschkowski, W. Nilson: Georg Cantor - Briefe , Springer, Berlin 1991.
A. Fraenkel: Einleitung in die Mengenlehre , Springer, Berlin 1923.
AA Fraenkel, A. Levy: Abstract Set Theory , Holandia Północna, Amsterdam 1976.
F. Hausdorff: Grundzüge der Mengenlehre , Chelsea, Nowy Jork 1965.
B. Russell: Zasady matematyki I , Cambridge 1903.
B. Russell: O pewnych trudnościach w teorii liczb pozaskończonych i typów porządków , Proc. London Math. Soc. (2) 4 (1907) 29-53.
PJ Cohen: Teoria mnogości i hipoteza kontinuum , Benjamin, Nowy Jork 1966.
S. Wagon: The Banach – Tarski Paradox , Cambridge University Press, Cambridge 1985.
AN Whitehead , B. Russell: Principia Mathematica I , Cambridge Univ. Press, Cambridge 1910, s. 64.
E. Zermelo: Neuer Beweis für die Möglichkeit einer Wohlordnung , Math. Ann. 65 (1908) str. 107-128.

Languages

In other projects