Funkcja β Gödla

W logice matematycznej funkcja β Gödla jest funkcją używaną do kwantyfikacji skończonych ciągów liczb naturalnych w formalnych teoriach arytmetyki . Funkcja β jest używana w szczególności do pokazania, że klasa funkcji definiowalnych arytmetycznie jest zamknięta w ramach rekurencji pierwotnej, a zatem obejmuje wszystkie prymitywne funkcje rekurencyjne .

Funkcję β ( wprowadzono bez nazwy w dowodzie pierwszego z twierdzeń Gödla o niezupełności Gödel 1931). Podany poniżej lemat funkcji β jest istotnym krokiem tego dowodu. Gödel nadał funkcji β swoją nazwę w (Gödel 1934).

Definicja

Funkcja przyjmuje jako argumenty trzy liczby $naturalne$ Określa się jako

{\ Displaystyle \ beta (x_ {1}, x_ {2}, x_ {3}) = \ operatorname {rem} (x_ {1}, 1 + (x_ {3} + 1) \ cdot x_ {2}) =\mathrm {rem} (x_{1},(x_{3}\cdot x_{2}+x_{2}+1)),}

gdzie ${\ Displaystyle \ operatorname {rem} (x, y)}$ oznacza resztę po dzieleniu liczb całkowitych przez ${\ Displaystyle x}$ przez ${\ Displaystyle y}$ (Mendelson 1997: 186).

Nieruchomości

Funkcja β jest definiowalna arytmetycznie w oczywisty sposób, ponieważ używa tylko operacji arytmetycznych i funkcji reszty, która jest definiowalna arytmetycznie. Dlatego można go przedstawić w arytmetyce Robinsona i silniejszych teoriach, takich jak arytmetyka Peano . Ustalając odpowiednio pierwsze dwa argumenty, można ustawić, aby wartości otrzymane przez zmianę ostatniego argumentu od 0 do n przechodziły przez dowolną określoną ( n + 1) -krotkę liczb naturalnych ( β lemat opisany szczegółowo poniżej). Pozwala to na symulację kwantyfikacji na sekwencjach liczb naturalnych o dowolnej długości, czego nie można wykonać bezpośrednio w języku arytmetyki, poprzez kwantyfikację tylko na dwóch liczbach, które mają być użyte jako pierwsze dwa argumenty funkcji β .

₀₀ Na przykład, jeśli f jest funkcją zdefiniowaną przez pierwotną rekurencję na parametrze n , powiedzmy przez f (0) = c i f ( n +1) = g ( n , f ( n )), to aby wyrazić f ( n ) = y chciałoby się powiedzieć: istnieje ciąg a , a ₁ , …, a _n taki, że a = c , _{ja za} n = y i dla wszystkich ja < n jeden ma g ( ja _, za _ja ) = za +1 . Chociaż nie jest to możliwe bezpośrednio, można zamiast tego powiedzieć: istnieją liczby naturalne a i b takie, że β ( a , b , 0) = c , β ( a , b , n ) = y i dla wszystkich i < n jeden ma g ( ja , β ( a , b , ja )) = β ( a , b , ja +1).

o funkcji β

Użyteczność funkcji β wynika z następującego wyniku (Gödel 1931, Hilfssatz 1, s.192-193), który jest celem funkcji β w dowodzie niezupełności Gödla. Wynik ten jest wyjaśniony bardziej szczegółowo niż w dowodzie Gödla w (Mendelson 1997:186) i (Smith 2013:113-118).

₀0 Lemat o funkcji β . Dla dowolnego ciągu liczb naturalnych ( k , k ₁ , …, k _n ) istnieją liczby naturalne b i c takie, że dla każdej liczby naturalnej ≤ i ≤ n , β ( b , c , i ) = k _i .

Na przykład sekwencja (2,0,2,1) może być zakodowana przez b = 3 412 752 i c = 24, ponieważ

{\ Displaystyle {\ rozpocząć {tablica} {llllll} \ operatorname {rem} (3412752, (1 + (0 + 1) * 24)} & = & \ operatorname {rem} (3412752,25) & = & 2 &, \ \\mathrm {rem} (3412752,(1+(1+1)*24))&=&\mathrm {rem} (3412752,49)&=&0&,\\\mathrm {rem} (3412752,(1 +(2+1)*24))&=&\mathrm {rem} (3412752,73)&=&2&,{\text{ and}}\\\mathrm {rem} (3412752,(1+(3+) 1)*24))&=&\mathrm {rem} (3412752,97)&=&1&.\\\end{tablica}}}

Dowód lematu o funkcji β wykorzystuje chińskie twierdzenie o resztach .

Zobacz też

Martina Davisa , wyd. (1965). Nierozstrzygalne - podstawowe artykuły o zdaniach nierozstrzygalnych, problemach nierozwiązywalnych i funkcjach obliczalnych . Publikacje Dover . ISBN 9-780-48643-2281 .
Kurta Godela (1931). "Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme I". Monatshefte für Mathematik und Physik (w języku niemieckim). 28 : 173–198. w (Gödel 1986)
Kurta Godela (1934). „O nierozstrzygalnych twierdzeniach formalnych systemów matematycznych”. Notatki sporządzone przez Stpehena C. Kleene i Johna B. Rossera podczas wykładów w Institute for Advanced Study. Przedruk w (Davis 1965)
Kurta Godela (1986). Salomona Fefermana; Johna W. Dawsona Jr.; Stephena C. Kleene; Gregory'ego H. Moore'a; Roberta M. Solovaya; Jean van Heijenoort (red.). Kurt Gödel – Collected Works (w języku niemieckim i angielskim). Tom. I – Publikacje 1929-1936. Oxford University Press . ISBN 0-195-14720-0 .
Elliotta Mendelsona (1997). Wprowadzenie do logiki matematycznej (wyd. 4). CRC Naciśnij . ISBN 0-412-80830-7 .
Wolfganga Rautenberga (2010). Zwięzłe wprowadzenie do logiki matematycznej (wyd. 3). Nowy Jork : Springer Science+Business Media . P. 244. doi : 10.1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6 .
Petera Smitha (2013). Wprowadzenie do twierdzeń Gödla (wyd. 2). Wielka Brytania : Cambridge University Press . ISBN 978-1-107-02284-3 .