Numeracja Gödla
W formalnej teorii liczb numeracja Gödla jest funkcją, która każdemu symbolowi i formule pewnego języka formalnego przypisuje unikalną liczbę naturalną zwaną liczbą Gödla (GN). Koncepcja ta została po raz pierwszy użyta przez Kurta Gödla do dowodu jego twierdzenia o niezupełności.
Numeracja Gödla może być interpretowana jako kodowanie, w którym każdemu symbolowi notacji matematycznej przyporządkowana jest liczba, a strumień liczb naturalnych może reprezentować pewną formę lub funkcję. Numeracja zbioru funkcji obliczalnych może być wtedy reprezentowana przez strumień liczb Gödla (zwanych też liczbami efektywnymi). Twierdzenie równoważności Rogersa podaje kryteria, dla których te numeracje zbioru funkcji obliczalnych są numeracjami Gödla.
Definicja
Biorąc pod uwagę zbiór przeliczalny S, numeracja Gödla jest funkcją wtrętową
f : S → N { {displaystyle f:S do \mathb {N} } 
przy czym zarówno f jak i f - 1 {displaystyle f^{-1}} (odwrotność f) są funkcjami obliczalnymi. 
(odwrotność f) są funkcjami obliczalnymi.
Przykłady
Notacja bazowa i ciągi znaków
Jeden z najprostszych schematów numeracji Gödla jest używany na co dzień: Zgodność między liczbami całkowitymi a ich reprezentacjami jako ciągów symboli. Na przykład, ciąg 2 3 jest rozumiany, przez pewien zestaw reguł, jako odpowiadający liczbie dwadzieścia trzy. Podobnie, ciągi symboli z pewnego alfabetu składającego się z N symboli mogą być kodowane przez identyfikację każdego symbolu z liczbą od 0 do N i odczytanie ciągu jako reprezentacji liczby całkowitej w bazie N+1.
Pytania i odpowiedzi
P: Co to jest numeracja Gödla?
O: Numeracja Gödla to funkcja, która przypisuje unikalną liczbę naturalną do każdego symbolu i formuły języka formalnego, zwaną liczbą Gödla (GN).
P: Kto pierwszy użył pojęcia numeracji Gödla?
O: Kurt Gödel po raz pierwszy użył koncepcji numeracji Gödla w dowodzie swojego twierdzenia o niekompletności.
P: Jak możemy interpretować numerację Gödla?
O: Możemy interpretować numerację Gödla jako kodowanie, w którym każdemu symbolowi notacji matematycznej przypisana jest liczba, a strumień liczb naturalnych może reprezentować pewną formę lub funkcję.
P: Jak nazywamy liczby naturalne przypisane przez numerację Gödla?
O: Liczby naturalne przypisane przez numerację Gödla nazywamy liczbami Gödla lub liczbami efektywnymi.
P: Co mówi twierdzenie Rogersa o równoważności?
O: Twierdzenie Rogersa o równoważności określa kryteria, dla których te numeracje zbioru funkcji obliczalnych są numeracjami Gödla.
P: Co jest reprezentowane przez strumień liczb Gödla?
O: Numeracja zbioru funkcji obliczalnych może być reprezentowana przez strumień liczb Gödla.
P: Dlaczego numeracja Gödla jest ważna w formalnej teorii liczb?
O: Numeracja Gödla jest ważna w formalnej teorii liczb, ponieważ zapewnia sposób reprezentowania formuł matematycznych i funkcji jako liczb naturalnych, co pozwala na dowód ważnych twierdzeń, takich jak twierdzenie o niekompletności.
