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ödlaSzablon:Fakt, 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 $\text{Nr }A.$ Funkcja $\text{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ą:

$($	$)$	$\mathrm{\exists }$	$\mathrm{\forall }$	$\mathrm{\neg }$	$\Rightarrow$	$\vee$	$\wedge$	$\iff$	$0$	$S$	$<$	$+$	$\cdot$	$P$	$=$	$x$	${}_{\text{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 $\text{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\dots a_n$

można przyporządkować numer

$\text{Nr }A=2^{\mathrm{Nr}{a}_1}\cdot 3^{\mathrm{Nr}{a}_2}\cdot \dots \cdot p_n^{\mathrm{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

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę