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[potrzebny przypis], pojawia się w dowodzie twierdzenia nazwanego jego nazwiskiem[1].
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 Funkcja 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 edytuj
Dziewiętnastu znakom teorii arytmetyki można przyporządkować 19 kolejnych liczb naturalnych zgodnie z tabelą:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Jeżeli jest jednym z powyżej wypisanych 19 znaków podstawowych, to przez oznaczymy przyporządkowaną mu liczbę w tabeli. Każdemu wyrażeniu będącemu ciągiem symboli podstawowych
można przyporządkować numer
gdzie oznacza -tą liczbę pierwszą. Na przykład wyrażeniu „ ” odpowiada numer
Przypisy edytuj
- ↑ arytmetyzacja języka, [w:] Encyklopedia PWN [dostęp 2022-10-16] .
Bibliografia edytuj
- 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.