Paradoks Richarda

Paradoks Richarda jest antynomią w teorii zbiorów i języku naturalnym po raz pierwszy opisaną w 1905 roku przez Julesa Richarda. Istnieje wiele sformułowań tego paradoksu, w oryginalnej postaci antynomia bazuje na modyfikacji metody przekątniowej Cantora. Paradoks Richarda jest często omawiany w kontekście rozróżnienia pomiędzy zdaniami matematyki i metamatematyki.

Paradoks

Rozważmy zbiór liczb rzeczywistych z przedziału [0,1], które mogą zostać jednoznacznie zdefiniowane w języku polskim, za pomocą sekwencji słów dowolnej skończonej długości. Nazwijmy ten zbiór $R.$ Jest to oczywiście zbiór przeliczalny, a więc możemy rozważyć pewną iterację po zbiorze $R.$ Zdefiniujmy teraz liczbę $r$ jako:

Taką liczbę rzeczywistą z przedziału [0,1], że n-ta cyfra rozwinięcia dziesiętnego tej liczby jest równa „cyklicznemu następnikowi” n-tej cyfry w rozwinięciu dziesiętnym n-tej liczby z tej iteracji (gdzie „cykliczny następnik” cyfry 0 to 1, cyfry 1 to 2, ..., cyfry 9 to 0)

Pomimo że liczba $r$ została zdefiniowana za pomocą skończonej sekwencji słów, nie należy do zbioru $R,$ ponieważ jej rozwinięcie dziesiętne różni się co najmniej jedną cyfrą, od każdej liczby ze zbioru $R.$

Analiza i rozwiązanie

Pozorna sprzeczność bierze się stąd, że podany wyżej opis liczby $r$ nie definiuje liczby rzeczywistej. Kompletna definicja wymagałaby określenia w skończonej liczbie słów procedury iteracyjnej zbioru $R.$ Warunkiem koniecznym i wystarczającym istnienia takiej procedury jest możliwość rozstrzygnięcia w skończonej liczbie kroków, czy dany ciąg słów stanowi definicje liczby rzeczywistej. Jeśli rozstrzygnięcie, czy dany ciąg słów definiuje liczbę rzeczywistą, byłoby możliwe w skończonej liczbie kroków, wówczas powyższe rozumowanie prowadziłoby do sprzeczności, zatem jest to dowód nie wprost, że nie jest to możliwe. Nie ma w tym nic dziwnego, ponieważ w związku z tw. Turinga o problemie stopu istnieje wiele zbiorów przeliczalnych, które nie są nawet rekurencyjnie przeliczalne. Jednym z takich zbiorów jest zbiór tych par liczb naturalnych $(n,m),$ że pierwsza z nich koduje maszynę Turinga, która działając na drugą, nie kończy pracy.

Liczby Richarda

Istnieje również wersja paradoksu wykorzystująca liczby naturalne zamiast rzeczywistych. Podobnie jak w pierwszej wersji, rozważamy skończone ciągi słów języka definiującego właściwości arytmetyczne liczb naturalnych. Na przykład zdanie „liczba naturalna posiadająca dokładnie dwa różne dzielniki całkowite: siebie samą i 1" definiuje właściwość bycia liczbą pierwszą. Wszystkie definicje można uporządkować w sposób leksykograficzny i tym samym przyporządkować każdej z nich liczbę naturalną odpowiadającą numerowi wystąpienia w tym porządku. Teraz definiujemy właściwość bycia liczbą Richarda jako „liczba naturalna n jest liczbą Richarda wtw. gdy nie posiada właściwości zdefiniowanej przez zdanie o numerze n”. Zdanie definiujące właściwość bycia liczbą Richarda posiada pewien numer $m$ określony poprzez wyżej przyjęte, leksykograficzne uporządkowanie wszystkich możliwych definicji. Teraz zadajmy pytanie: czy $m$ jest liczbą Richarda? Zgodnie z definicją liczb Richarda $m$ jest liczbą Richarda wtw. gdy nie posiada właściwości określonej przez definicje z numerem $m,$ a więc $m$ jest liczbą Richarda wtw. gdy $m$ nie jest liczbą Richarda.

Podobnie jak wyżej, pozorna sprzeczność bierze się stąd, że definicja właściwości bycia liczbą Richarda niejawnie zakłada, że podzbiór tych ciągów słów, które definiują właściwości liczb naturalnych jest rekurencyjnie przeliczalny. Ponieważ tak nie jest, nie można w sposób zupełny zdefiniować właściwości bycia liczbą Richarda, przy pomocy ustalonej, skończonej liczby słów.

Zobacz też

• antynomia Russella
• definicja niepredykatywna
• problem stopu

Bibliografia

• Abraham A. Fraenkel, Yehoshua Bar-Hillel, Azriel Levy: Foundations of Set Theory. Elsevier, Academic Press, 1973. ISBN 978-0-08-088705-0.
• Ernest Nagel, James R. Newman: Gödel’s Proof. London: Routledge and Kegan Paul, 1958. ISBN 0-415-35528-1.