Jagodowy paradoks - Berry paradox

Berry paradoksu jest autoreferencyjna paradoksem wynikająca z ekspresji, takich jak „najmniejsza dodatnia nieokreślone w ramach sześćdziesięciu litery” (wyrażenia z pięćdziesięciu siedmiu liter).

Bertrand Russell , pierwszy omówić paradoks w druku, przypisuje go do GG Berry (1867-1928), młodszy bibliotekarz w Oxford „s Bodleian biblioteki . Russell nazwał Berry'ego „jedyną osobą w Oksfordzie, która rozumiała logikę matematyczną”.

Przegląd

Rozważ wyrażenie:

„Najmniejsza dodatnia liczba całkowita, której nie można zdefiniować w mniej niż sześćdziesięciu literach”.

Ponieważ w alfabecie angielskim jest tylko dwadzieścia sześć liter, istnieje skończenie wiele fraz o długości poniżej sześćdziesięciu liter, a zatem skończenie wiele dodatnich liczb całkowitych, które są zdefiniowane przez frazy poniżej sześćdziesięciu liter. Ponieważ istnieje nieskończenie wiele dodatnich liczb całkowitych, oznacza to, że istnieją dodatnie liczby całkowite, których nie można zdefiniować za pomocą fraz o długości poniżej sześćdziesięciu liter. Jeśli istnieją liczby całkowite dodatnie, które spełniają daną właściwość, to istnieje najmniejsza liczba całkowita dodatnia, która spełnia tę właściwość; w związku z tym istnieje najmniejsza dodatnia liczba całkowita spełniająca właściwość „niedefiniowalna w sześćdziesięciu literach”. Jest to liczba całkowita, do której odnosi się powyższe wyrażenie. Ale powyższe wyrażenie jest tylko pięćdziesiąt siedem liter długo, dlatego jest definiowane w ramach sześćdziesiąt listów, i to nie najmniejsza dodatnia nieokreślone w ramach sześćdziesiąt listów, i nie określa tego wyrażenia. Jest to paradoks: musi istnieć liczba całkowita zdefiniowana przez to wyrażenie, ale ponieważ wyrażenie to jest wewnętrznie sprzeczne (każda liczba całkowita, którą definiuje, można zdefiniować w mniej niż sześćdziesięciu literach), nie może być przez nie zdefiniowanej żadnej liczby całkowitej.

Być może inną pomocną analogią do paradoksu Berry'ego byłoby wyrażenie „nieopisane uczucie”. Jeśli uczucie jest rzeczywiście nie do opisania, to żaden opis tego uczucia nie byłby prawdziwy. Ale jeśli słowo „nie do opisania” komunikuje coś o uczuciu, to można je uznać za opis: jest to wewnętrznie sprzeczne.

Matematyk i informatyk Gregory J. Chaitin w The Unknowable (1999) dodaje następujący komentarz: „No cóż, meksykański historyk matematyki Alejandro Garcidiego zadał sobie trud odnalezienia tego listu [od Berry'ego, z którego Russell napisał swoje uwagi] i jest to raczej inny paradoks. List Berry'ego mówi o pierwszej liczbie porządkowej, której nie można nazwać skończoną liczbą słów. Zgodnie z teorią Cantora taka liczba porządkowa musi istnieć, ale właśnie nazwaliśmy ją skończoną liczbą słów, co jest sprzecznością”.

Rezolucja

Sformułowany powyżej paradoks Berry'ego wynika z systematycznej dwuznaczności słowa „definiowalny”. W innych sformułowaniach paradoksu Berry'ego, takich jak ten, który zamiast tego brzmi: „…nie da się nazwać w mniej…” termin „nazwalny” jest również taki, który ma tę systematyczną dwuznaczność. Terminy tego rodzaju rodzą błędne koło . Inne terminy z tego rodzaju niejednoznacznością to: spełnialność, prawda, fałsz, funkcja, własność, klasa, relacja, kardynał i porządkowy. Rozwiązanie jednego z tych paradoksów oznacza dokładne wskazanie, gdzie nasze użycie języka poszło nie tak i wprowadzenie ograniczeń w używaniu języka, które mogą ich uniknąć.

Ta rodzina paradoksów może zostać rozwiązana poprzez włączenie do języka stratyfikacji znaczeń. Terminy o systematycznej niejednoznaczności mogą być pisane z indeksami wskazującymi, że w ich interpretacji jeden poziom znaczenia ma wyższy priorytet niż inny. „Liczba nie dająca się nazwać 0 w mniej niż jedenastu słowach” może być nazwana 1 w mniej niż jedenastu słowach w ramach tego schematu.

Formalne analogi

Używając programów lub dowodów o ograniczonej długości, możliwe jest skonstruowanie analogu wyrażenia Berry'ego w formalnym języku matematycznym, jak to zrobił Gregory Chaitin . Chociaż formalny analog nie prowadzi do logicznej sprzeczności, to jednak dowodzi pewnych niemożliwości.

George Boolos (1989) zbudował na sformalizowanej wersji paradoksu Berry'ego, aby udowodnić twierdzenie Gödla o niezupełności w nowy i znacznie prostszy sposób. Podstawową ideą jego dowodu jest to, że zdanie, które zawiera x wtedy i tylko wtedy, gdy x = n dla pewnej liczby naturalnej n można nazwać definicją dla n i że zbiór {( n , k ): n ma definicję, która czy k symboli jest długich} można pokazać jako reprezentowalne (przy użyciu liczb Gödla ). Wtedy zdanie " m jest pierwszą liczbą niedefiniowalną w mniej niż k symbolach" może zostać sformalizowane i pokazane jako definicja we wspomnianym przed chwilą sensie.

Związek ze złożonością Kołmogorowa

Na ogół nie da się jednoznacznie określić, jaka jest minimalna liczba symboli potrzebnych do opisu danego ciągu (przy określonym mechanizmie opisu). W tym kontekście terminy ciąg i liczba mogą być używane zamiennie, ponieważ liczba jest w rzeczywistości ciągiem symboli, np. słowem angielskim (jak słowo „jedenaście” użyte w paradoksie), podczas gdy z drugiej strony jest to możliwe odnosić się do dowolnego słowa z liczbą, np. przez numer jego pozycji w danym słowniku lub przez odpowiednie kodowanie. Niektóre długie łańcuchy można dokładnie opisać przy użyciu mniejszej liczby symboli niż jest to wymagane przez ich pełną reprezentację, co często osiąga się przy użyciu kompresji danych . Złożoność danego ciągu jest następnie definiowana jako minimalna długość, jakiej wymaga opis, aby (jednoznacznie) odnosić się do pełnej reprezentacji tego ciągu.

Złożoność Kołmogorowa jest definiowana za pomocą języków formalnych lub maszyn Turinga, co pozwala uniknąć niejasności co do tego, który ciąg znaków wynika z danego opisu. Można udowodnić, że złożoność Kołmogorowa nie jest obliczalna. Dowód przez sprzeczność pokazuje, że gdyby można było obliczyć złożoność Kołmogorowa, to byłoby też możliwe systematyczne generowanie paradoksów podobnych do tego, tj. opisów krótszych niż wynika to ze złożoności opisywanego ciągu. To znaczy, definicja liczby Berry'ego jest paradoksalna, ponieważ w rzeczywistości nie można obliczyć, ile słów potrzeba do zdefiniowania liczby, a wiemy, że takie obliczenie nie jest możliwe z powodu paradoksu.

Zobacz też

Uwagi

Bibliografia

Zewnętrzne linki