Prawdziwa arytmetyka

W logice matematycznej prawdziwa arytmetyka to zbiór wszystkich prawdziwych stwierdzeń pierwszego rzędu dotyczących arytmetyki liczb naturalnych . Jest to teoria związana ze standardowym modelem aksjomatów Peano w języku aksjomatów Peano pierwszego rzędu. Prawdziwa arytmetyka jest czasami nazywana arytmetyką Skolema, chociaż termin ten zwykle odnosi się do innej teorii liczb naturalnych z mnożeniem.

Definicja

Sygnatura arytmetyki Peano obejmuje symbole funkcji dodawania, mnożenia i następników, symbole równości i relacji mniej niż, a także stały symbol 0. (Dobrze uformowane) formuły języka arytmetyki pierwszego rzędu są zbudowane z tych symboli razem z symbolami logicznymi w zwykły sposób logiki pierwszego rzędu .

Struktura jest $sposób$ jako model arytmetyki Peano w następujący .

Dziedziną dyskursu jest zbiór liczb naturalnych, ${\ displaystyle \ mathbb {N}}$
Symbol 0 jest interpretowany jako liczba 0,
Symbole funkcji są interpretowane jako zwykłe operacje arytmetyczne na , ${\ Displaystyle \ mathbb {N}$ }
Symbole równości i relacji mniejszej niż są interpretowane jako zwykła relacja równości i porządku na ${\ displaystyle \ mathbb {N}}$ .

Ta struktura jest znana jako model standardowy lub zamierzona interpretacja arytmetyki pierwszego rzędu.

$, że$ w języku arytmetyki pierwszego rzędu jest prawdziwe, jeśli jest prawdziwe w właśnie zdefiniowanej strukturze. Notacja jest używana do wskazania, że zdanie jest prawdziwe w $N}} \ modele \ varphi$ ${\ Displaystyle {\ mathcal {N}}.}$ $\ mathcal {$

Prawdziwa arytmetyka jest zdefiniowana jako zbiór wszystkich zdań Th ( $displaystyle {\ mathcal {N}} }$ ) języku arytmetyki pierwszego rzędu, które są prawdziwe w pisanym ${\$ . Ten zestaw jest równoważnie (kompletną) teorią struktury. ${\ displaystyle {\ mathcal {N}}}$ .

Niedefiniowalność arytmetyczna

Centralnym wynikiem prawdziwej arytmetyki jest twierdzenie Alfreda Tarskiego o niedefiniowalności (1936). Stwierdza, że zbiór Th ( ) $definiowalny$ jest arytmetycznie. Oznacza to $, że$ w języku arytmetyki pierwszego rzędu nie ma takiej formuły, która każdego θ tym

{\ Displaystyle {\ mathcal {N}} \ modele \ theta \ quad {\ tekst {jeśli i tylko wtedy}} \ quad {\ mathcal {N}} \ modele \ varphi ({\ podkreślenie {\ # (\ theta) }}).}

Tutaj ${\ Displaystyle {\ podkreślenie {\ # (\ theta)}}}$ jest cyfrą kanonicznej liczby Gödla zdania θ .

Twierdzenie Posta jest ostrzejszą wersją twierdzenia o niedefiniowalności, które pokazuje związek między definiowalnością Th ( ${\ Displaystyle {\ mathcal {N}}} )$ a stopniami Turinga przy użyciu hierarchii arytmetycznej . Dla każdej liczby naturalnej n , niech N $\ Displaystyle$ T _{n (} ) będzie podzbiorem Th ( ${\ mathcal {N}}}$ ) składającym się tylko ze zdań, które ${\ Displaystyle \ Sigma _ {n} ^ {0}}$ lub niżej w hierarchii arytmetycznej. Twierdzenie Posta pokazuje, że dla każdego n , { T _n ( $)$ jest definiowalne arytmetycznie, ale tylko przez formułę o złożoności wyższej niż $Displaystyle \ Sigma _ {n} ^ {0}}$ . Zatem żadna pojedyncza formuła nie może zdefiniować Th ( ${\ displaystyle {\ mathcal {N}}}$ ) , ponieważ

{\ Displaystyle {\ mbox {Th}} ({\ mathcal {N}}) = \ bigcup _ {n \ w \ mathbb {N}} {\ mbox {Th}}_ {n}({\mathcal {N}})}

Th _n ( $)$ pojedyncza formuła nie może zdefiniować dla dowolnie dużego n .

Właściwości obliczalności

0 Jak omówiono powyżej, Th ( $nie$ jest definiowalny arytmetycznie przez twierdzenie Tarskiego. Następstwem twierdzenia Posta jest ustalenie, że stopień Turinga Th ( $)$ ) wynosi ^{( ω )} , więc Th ( ${\ displaystyle {\ mathcal {N}}$ } nie jest rozstrzygalne ani rekurencyjnie przeliczalne .

T ( $jest$ w . $ściśle$ , z teorią rekurencyjnie przeliczalnych stopni Turinga sygnaturze rzędów częściowych W szczególności istnieją obliczalne funkcje S i T takie, że:

Dla każdego zdania φ w sygnaturze arytmetyki pierwszego rzędu φ jest w Th ( ${\ displaystyle {\ mathcal {N}}}$ ) wtedy i tylko wtedy, gdy S ( φ ) jest w Th ( ${\ displaystyle {\ mathcal {\ mathcal} {R}}}$ ) .
Dla każdego zdania ψ w podpisie zamówień częściowych ψ jest w T ( ${\ displaystyle {\ mathcal {R}}}$ ) wtedy i tylko wtedy, gdy T ( ψ ) jest w T ( ${\ displaystyle {\ mathcal {N} }}}$ ) .

Właściwości teorii modeli

Prawdziwa arytmetyka jest $modele$ teorią , podobnie jak dla $nieprzeliczalnego$ . $Ponieważ$ w zbiorze pustym istnieje wiele typów kontinuum, arytmetyka ma również policzalne . Ponieważ teoria jest kompletna , wszystkie jej modele są elementarnie równoważne .

Prawdziwa teoria arytmetyki drugiego rzędu

Prawdziwa teoria arytmetyki drugiego rzędu składa się ze wszystkich zdań w języku arytmetyki drugiego rzędu , które są spełnione przez standardowy model arytmetyki drugiego rzędu, którego częścią pierwszego rzędu jest struktura ${\ displaystyle {\ mathcal { N}}}$ i którego część drugiego rzędu składa się z każdego podzbioru ${\ displaystyle \ mathbb {N}}$ .

Prawdziwa teoria arytmetyki pierwszego rzędu , jest podzbiorem prawdziwej teorii arytmetyki drugiego rzędu i Th ( ${\ displaystyle {\ mathcal {N}}} )$ Th ( ${\ displaystyle {\ mathcal {N}}} }}}$ ) jest definiowalny w arytmetyce drugiego rzędu. Jednak uogólnienie twierdzenia Posta na hierarchię analityczną pokazuje, że prawdziwej teorii arytmetyki drugiego rzędu nie da się zdefiniować żadnym pojedynczym wzorem w arytmetyce drugiego rzędu.

Simpson (1977) wykazał, że prawdziwa teoria arytmetyki drugiego rzędu jest obliczeniowo interpretowalna z teorią częściowego rzędu wszystkich stopni Turinga , w sygnaturze rzędów częściowych i odwrotnie .

Notatki

Boolos, George ; Burgess, John P .; Jeffrey, Richard C. (2002), Obliczalność i logika (wyd. 4), Cambridge University Press, ISBN 978-0-521-00758-0 .
Bowykin, Andriej; Kaye, Richard (2001), „O typach zamówień modeli arytmetyki”, w: Zhang, Yi (red.), Logic and algebra , Contemporary Mathematics, tom. 302, Amerykańskie Towarzystwo Matematyczne, s. 275–285, ISBN 978-0-8218-2984-4 .
Shore, Richard (2011), „The rekurencyjnie wyliczalne stopnie”, w: Griffor, ER (red.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, tom. 140, Holandia Północna (opublikowana 1999), s. 169–197, ISBN 978-0-444-54701-9 .
Simpson, Stephen G. (1977), „Teoria pierwszego rzędu stopni nierozwiązywalności rekurencyjnej”, Annals of Mathematics , Second Series, Annals of Mathematics, 105 (1): 121–139, doi : 10.2307/1971028 , ISSN 0003 -486X , JSTOR 1971028 , MR 0432435
Tarski, Alfred (1936), „Der Wahrheitsbegriff in den formalisierten Sprachen”. Angielskie tłumaczenie „The Concept of Truth in Formalized Languages” pojawia się w Corcoran, J., wyd. (1983), Logika, semantyka i metamatematyka: dokumenty od 1923 do 1938 (wyd. 2), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

Linki zewnętrzne

Weisstein, Eric W. „Arytmetyka” . MathWorld .
Weisstein, Eric W. „Arytmetyka Peano” . MathWorld .
Weisstein, Eric W. „Twierdzenie Tarskiego” . MathWorld .