Paradoks Richarda - Richard's paradox

W logice , paradoks Richarda to semantyczne antynomia z teorii mnogości i języka naturalnego pierwszy opisany przez francuskiego matematyka Jules Richard w 1905 Paradoksem jest zwykle wykorzystywane do motywowania znaczenie rozróżnienia między starannie matematyki i metamatematyki .

Kurt Gödel przytacza antynomię Richarda jako semantyczny odpowiednik jego wyniku niezupełności składniowej we wstępnej części książki „ O formalnie nierozstrzygalnych twierdzeniach w Principia Mathematica i systemach pokrewnych I ”. Paradoks był także motywacją rozwoju matematyki predykatywnej .

Opis

Pierwotne stwierdzenie paradoksu, wygłoszone przez Richarda (1905), jest silnie powiązane z argumentem diagonalnym Cantora o nieprzeliczalności zbioru liczb rzeczywistych .

Paradoks zaczyna się od spostrzeżenia, że ​​niektóre wyrażenia języka naturalnego definiują liczby rzeczywiste w sposób jednoznaczny, podczas gdy inne wyrażenia języka naturalnego nie. Na przykład „Liczba rzeczywista, której część całkowita wynosi 17, a n- te miejsce dziesiętne wynosi 0, jeśli n jest parzyste, a 1, jeśli n jest nieparzyste” definiuje liczbę rzeczywistą 17.1010101... = 1693/99, podczas gdy Wyrażenie „stolica Anglii” nie definiuje liczby rzeczywistej, ani wyrażenie „najmniejsza dodatnia liczba całkowita, której nie można zdefiniować w sześćdziesięciu literach” (patrz paradoks Berry'ego ).

Tak więc istnieje nieskończona lista fraz angielskich (takich, że każda fraza ma skończoną długość, ale sama lista ma nieskończoną długość), które jednoznacznie definiują liczby rzeczywiste. Najpierw układamy tę listę fraz zwiększając długość, a następnie porządkujemy leksykograficznie wszystkie frazy o jednakowej długości (w porządku słownikowym, np. możemy użyć kodu ASCII , frazy mogą zawierać tylko kody od 32 do 126), tak aby kolejność była kanoniczna . Daje to nieskończoną listę odpowiednich liczb rzeczywistych: r 1 , r 2 , ... . Teraz zdefiniuj nową liczbę rzeczywistą r w następujący sposób. Część całkowitą r wynosi 0, n p miejsca po przecinku r oznacza 1 gdy n p miejsca po przecinku R n jest 1, a n p miejsca po przecinku R oznacza 2 gdy n p miejsca po przecinku R n jest 1.

Poprzedni akapit to wyrażenie w języku angielskim, które jednoznacznie definiuje liczbę rzeczywistą r . Zatem r musi być jedną z liczb r n . Jednak r zostało skonstruowane tak, że nie może równać się żadnemu z r n (zatem r jest niedefiniowalną liczbą ). To paradoksalna sprzeczność.

Analiza i związek z metamatematyką

Paradoks Richarda skutkuje sprzecznością nie do utrzymania, którą należy przeanalizować, aby znaleźć błąd.

Zaproponowana definicja nowej liczby rzeczywistej r wyraźnie zawiera skończony ciąg znaków, a więc na pierwszy rzut oka wydaje się być definicją liczby rzeczywistej. Jednak definicja odnosi się do samej definiowalności w języku angielskim. Gdyby to było możliwe, aby ustalić, które wyrażenia angielski faktycznie nie określają liczbę rzeczywistą, a które nie, to paradoksem byłoby przejść. Tak więc rozwiązanie paradoksu Richarda polega na tym, że nie ma sposobu na jednoznaczne określenie, które zdania angielskie są definicjami liczb rzeczywistych (zob. Good 1966). Oznacza to, że nie ma sposobu na opisanie skończoną liczbą słów, jak stwierdzić, czy dowolne wyrażenie angielskie jest definicją liczby rzeczywistej. Nie jest to zaskakujące, ponieważ umiejętność dokonania tego określenia oznaczałaby również możliwość rozwiązania problemu zatrzymania i wykonania wszelkich innych niealgorytmicznych obliczeń, które można opisać w języku angielskim.

Podobne zjawisko występuje w sformalizowanych teoriach, które są w stanie odwoływać się do własnej składni, takich jak teoria mnogości Zermelo-Fraenkla (ZFC). Powiedzmy, że formuła φ( x ) definiuje liczbę rzeczywistą, jeśli istnieje dokładnie jedna liczba rzeczywista r taka, że ​​( r ) zachodzi. Wtedy nie jest możliwe zdefiniowanie przez ZFC zbioru wszystkich ( liczb Gödla ) formuł definiujących liczby rzeczywiste. Gdyby bowiem można było zdefiniować ten zbiór, możliwe byłoby przekątne nad nim, aby otrzymać nową definicję liczby rzeczywistej, zgodnie z zarysem paradoksu Richarda powyżej. Zauważ, że zbiór formuł definiujących liczby rzeczywiste może istnieć jako zbiór F ; ograniczeniem ZFC jest to, że nie ma żadnej formuły, która definiuje F bez odniesienia do innych zbiorów. Wiąże się to z twierdzeniem Tarskiego o niedefiniowalności .

Przykład ZFC ilustruje znaczenie odróżnienia metamatematyki systemu formalnego od zdań samego systemu formalnego. Własność D(φ), że formuła φ ZFC definiuje unikalną liczbę rzeczywistą, nie jest sama w sobie wyrażalna przez ZFC, ale musi być uważana za część metateorii używanej do sformalizowania ZFC. Z tego punktu widzenia paradoks Richarda wynika z traktowania konstrukcji metateorii (wyliczenia w oryginalnym systemie wszystkich zdań definiujących liczby rzeczywiste) tak, jakby ta konstrukcja mogła być wykonana w oryginalnym systemie.

Odmiana: liczby Richardian

Odmiana paradoksu wykorzystuje liczby całkowite zamiast liczb rzeczywistych, zachowując jednocześnie autoreferencyjny charakter oryginału. Rozważmy język (np. angielski), w którym zdefiniowane są właściwości arytmetyczne liczb całkowitych. Na przykład „pierwsza liczba naturalna” określa własność bycia pierwszą liczbą naturalną, jeden; a „podzielna przez dokładnie dwie liczby naturalne” określa własność bycia liczbą pierwszą . (Oczywiste jest, że niektórych własności nie można jednoznacznie zdefiniować, ponieważ każdy system dedukcyjny musi zaczynać się od pewnych aksjomatów . Ale dla celów tego argumentu zakłada się, że wyrażenia takie jak „liczba całkowita jest sumą dwóch liczb całkowitych” są już rozumiane .) Chociaż lista wszystkich możliwych definicji jest sama w sobie nieskończona, łatwo zauważyć, że każda poszczególna definicja składa się ze skończonej liczby słów, a zatem również ze skończonej liczby znaków. Ponieważ to prawda, możemy uporządkować definicje, najpierw według długości, a następnie leksykograficznie .

Teraz możemy odwzorować każdą definicję na zbiór liczb naturalnych , tak aby definicja z najmniejszą liczbą znaków i kolejnością alfabetyczną odpowiadała liczbie 1, następna definicja w serii będzie odpowiadała 2 i tak dalej. Ponieważ każda definicja jest powiązana z unikalną liczbą całkowitą, możliwe jest, że czasami liczba całkowita przypisana do definicji pasuje do tej definicji. Jeśli na przykład definicja „niepodzielna przez żadną liczbę całkowitą inną niż 1 i sama” byłaby 43., to byłaby to prawda. Ponieważ 43 samo w sobie nie jest podzielne przez żadną liczbę całkowitą inną niż 1 i ono samo, to liczba tej definicji ma własność samej definicji. Jednak nie zawsze tak jest. Jeżeli do liczby 58 przypisano definicję: "podzielna przez 3", to numer definicji nie ma własności samej definicji. Ponieważ 58 samo w sobie nie jest podzielne przez 3. Ten ostatni przykład będzie określany jako posiadający właściwość bycia Richardem . Tak więc, jeśli liczba jest Richardem, to definicja odpowiadająca tej liczbie jest właściwością, której sama liczba nie ma. (Bardziej formalnie, „ x jest Richardian” jest równoznaczne z „ x jest nie mają własność określana wyrażeniem określającym z którym x jest skorelowane seryjnie uporządkowanego zbioru definicji”). Tak więc, w tym przykładzie, 58 jest Richardian, ale 43 nie jest.

Teraz, ponieważ własność bycia Richardem jest sama w sobie liczbową własnością liczb całkowitych, należy ona do listy wszystkich definicji własności. Dlatego własności bycia Richardem przypisuje się pewną liczbę całkowitą, n . Na przykład, do liczby 92 można przypisać definicję „bycie Richardem”. W końcu paradoks brzmi: Czy 92 jest Richardem? Załóżmy, że 92 jest Richardem. Jest to możliwe tylko wtedy, gdy 92 nie ma właściwości wyznaczonej przez wyrażenie definiujące, z którym jest skorelowane. Innymi słowy, oznacza to, że 92 nie jest Richardem, co jest sprzeczne z naszymi założeniami. Jeśli jednak założymy, że 92 nie jest Richardem, to ma właściwość definiującą, której odpowiada. To z definicji oznacza, że ​​jest to Richardian, ponownie wbrew założeniu. Zatem stwierdzenie „92 to Richardian” nie może być konsekwentnie oznaczane jako prawdziwe lub fałszywe.

Związek z predykatywizmem

Inna opinia dotycząca paradoksu Richarda dotyczy predykatyzmu matematycznego . Zgodnie z tym poglądem, liczby rzeczywiste są definiowane etapami, przy czym każdy etap odnosi się tylko do poprzednich etapów i innych rzeczy, które zostały już zdefiniowane. Z predykatywnego punktu widzenia nie jest właściwe określanie ilościowe po wszystkich liczbach rzeczywistych w procesie generowania nowej liczby rzeczywistej, ponieważ uważa się, że powoduje to problem kołowości w definicjach. Teorie mnogości, takie jak ZFC, nie opierają się na tego rodzaju ramach predykatywnych i pozwalają na nieprecyzyjne definicje.

Richard (1905) przedstawił rozwiązanie paradoksu z punktu widzenia predykatiwizmu. Richard twierdził, że wadą paradoksalnej konstrukcji jest to, że wyrażenie na konstrukcję liczby rzeczywistej r nie definiuje w rzeczywistości jednoznacznie liczby rzeczywistej, ponieważ stwierdzenie to odnosi się do konstrukcji nieskończonego zbioru liczb rzeczywistych, z których samo r jest oprócz. Tak więc, mówi Richard, liczba rzeczywista r nie będzie uwzględniona jako dowolna r n , ponieważ definicja r nie spełnia kryteriów włączenia do ciągu definicji użytych do skonstruowania ciągu r n . Współcześni matematycy zgadzają się, że definicja r jest niepoprawna, ale z innego powodu. Uważają, że definicja r jest nieważna, ponieważ nie ma dobrze zdefiniowanego pojęcia, kiedy fraza angielska definiuje liczbę rzeczywistą, a zatem nie ma jednoznacznego sposobu skonstruowania ciągu r n .

Chociaż rozwiązanie paradoksu Richarda nie zyskało przychylności matematyków, predykatywizm jest ważną częścią badań nad podstawami matematyki . Predykatywizm został po raz pierwszy szczegółowo zbadany przez Hermanna Weyla w Das Kontinuum , w którym wykazał, że wiele elementarnych analiz rzeczywistych można przeprowadzić w sposób predykatywny, zaczynając od samych liczb naturalnych . Niedawno predykatywizm był badany przez Solomona Fefermana , który wykorzystał teorię dowodu do zbadania relacji między systemami predykatywnymi i predykatywnymi.

Zobacz też

Bibliografia

  1. ^ Salomon Feferman " Predicativity " (2002),
  • Fraenkel, Abraham; Bar-Hillel, Yehoshua & Levy, Azriel (1973). Podstawy teorii mnogości . Przy współpracy Dirka van Dalena (wyd. drugie). Amsterdam: Holandia Północna. Numer ISBN 0-7204-2270-1.
  • Dobrze, IJ (1966). „Uwaga na paradoks Richarda”. Umysł . 75 (299): 431. doi : 10.1093/umysł/LXXV.299.431 .
  • Richard, Jules (1905). Les Principes des Mathématiques et le Problème des Ensembles . Revue Générale des Sciences Pures et Appliquées.Przetłumaczone w Heijenoort, J. van, wyd. (1964). Książka źródłowa w logice matematycznej 1879-1931 . Cambridge, MA: Wydawnictwo Uniwersytetu Harvarda.

Linki zewnętrzne