Arytmetyzacja języka

Arytmetyzacja języka lub arytmetyzacja składni – w logice matematycznej, wprowadzona przez Kurta Gödla metoda efektywnego numerowania 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 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

Dziwię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_1a_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: PWN, 1961, s. 365-367. 
• Witold Marciszewski: (red.) Logika formalna. Zarys encyklopedyczny. Warszawa: PWN, 1987, s. 145. ISBN 83-01-04998-7.