Arytmetyzacja języka
Z Wikipedii
Arytmetyzacja języka - w logice matematycznej efektywne ponumerowanie wszystkich wyrażeń języka badanej teorii za pomocą liczb naturalnych. Aby każdemu wyrażeniu przyporządkować pewną liczbę, przyporządkowuje się najpierw pewne liczby elementarnym znakom teorii (znaki stałe, znaki zmienne), a następnie dowolnym wyrażeniom, czyli ciągom skończonym znaków elementarnych. W rezultacie każde wyrażenie teorii A, czy jest nim znak elementarny, czy ciąg znaków (formuła), czy też ciąg ciągów znaków (ciąg formuł) posiada przyporządkowany mu jednoznacznie numer Nr (A) = N. Funkcja Nr (A) = N przekształca wyrażenia teorii w pewien zbiór liczb naturalnych. Zamiast mówić o własnościach zbioru wyrażeń (obliczalność, rekurencyjna przeliczalność) można mówić o własnościach zbiorów ich numerów.