Arytmetyzacja języka

Arytmetyzacja języka lub arytmetyzacja składni – metoda efektywnego numerowania wszystkich wyrażeń języka badanej teorii za pomocą liczb naturalnych. Wprowadzona przez Kurta Gödla, pojawia się w dowodzie twierdzenia nazwanego jego nazwiskiem.

Aby każdemu wyrażeniu przyporządkować pewną liczbę, przyporządkowuje się najpierw pewne liczby podstawowym 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 A rozważanej teorii – niezależnie 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 pewien numer ${\mbox{Nr }}A.$ Funkcja ${\mbox{Nr}}$ przekształca w sposób wzajemnie jednoznaczny wyrażenia teorii w pewien podzbiór zbioru liczb naturalnych. Zamiast mówić o własnościach zbioru wyrażeń (obliczalność, rekurencyjna przeliczalność) można mówić o własnościach zbioru ich numerów.

Przykład

Dziewiętnastu znakom teorii arytmetyki można przyporządkować 19 kolejnych liczb naturalnych zgodnie z tabelą:

$($	$)$	$\exists$	$\forall$	$\neg$	$\Rightarrow$	$\vee$	$\wedge$	$\Leftrightarrow$	$0$	$S$	$<$	$+$	$\cdot$	$P$	$=$	$x$	$_{\mbox{I}}$	$,$
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Jeżeli $a$ jest jednym z powyżej wypisanych 19 znaków podstawowych, to przez ${\mbox{Nr }}a$ oznaczymy przyporządkowaną mu liczbę w tabeli. Każdemu wyrażeniu $A$ będącemu ciągiem symboli podstawowych

$A=a_{1}a_{2}\ldots a_{n}$

można przyporządkować numer

${\mbox{Nr }}A=2^{\operatorname {Nr} \,a_{1}}\cdot 3^{\operatorname {Nr} \,a_{2}}\cdot \ldots \cdot p_{n}^{\operatorname {Nr} \,a_{n}},$

gdzie $p_{n}$ oznacza $n$-tą liczbę pierwszą. Na przykład wyrażeniu „$x=0$” odpowiada numer

$2^{17}\cdot 5^{16}\cdot 7^{10}.$

Bibliografia

• Andrzej Grzegorczyk: Zarys logiki matematycznej. Warszawa: Państwowe Wydawnictwo Naukowe, 1961, s. 365–367.
• Logika formalna. Zarys encyklopedyczny. Witold Marciszewski (red.). Warszawa: PWN, 1987, s. 145. ISBN 83-01-04998-7.