Prawdziwa arytmetyka - True arithmetic

W logice matematycznej , prawda arytmetyczna jest zbiorem wszystkich prawdziwych pierwszego rzędu oświadczenia o arytmetyce z liczb naturalnych . Jest to teoria związana ze standardowego modelu z aksjomatów Peano w języku pierwszego rzędu Peano aksjomatów. Prawdziwa arytmetyka jest czasami nazywana arytmetyką Skolema, chociaż termin ten zwykle odnosi się do innej teorii liczb naturalnych z mnożeniem.

Definicja

Podpisu z Peano arytmetyki zawiera dodawania, mnożenia, i symbole funkcyjne następca równości i mniej niż symbole Związek, i symbol stałych dla 0. (dobrze uformowane) formułach języka pierwszego rzędu arytmetyki są zbudowane z tych symboli wraz z symbolami logicznymi w zwykły sposób logiki pierwszego rzędu .

Struktury określa się wzorem Peano arytmetyczną. ${\displaystyle {\mathcal {N}}}$

• Domeny dyskursu jest zbiorem 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.

Zdanie w języku pierwszego rzędu arytmetyki mówi się, że prawda w jeśli to prawda tylko w strukturze zdefiniowanej. Notacja służy do wskazania, że ​​zdanie jest prawdziwe w${\displaystyle {\mathcal {N}}}$${\ Displaystyle {\ mathcal {N}} \ modele \ varphi}$${\displaystyle \varphi}$${\displaystyle {\mathcal {N}}.}$

Prawdziwą arytmetykę definiuje się jako zbiór wszystkich zdań w języku arytmetyki pierwszego rzędu, które są prawdziwe w zapisie Th( ) . Ten zbiór jest równoważnie (pełną) teorią struktury . ${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

Niedefiniowalność arytmetyczna

Centralnym wynikiem prawdziwej arytmetyki jest twierdzenie o niedefiniowalności Alfreda Tarskiego (1936). Stwierdza, że ​​zbiór Th( )${\displaystyle {\mathcal {N}}}$ nie jest definiowalny arytmetycznie. Oznacza to, że w języku arytmetyki pierwszego rzędu nie ma formuły takiej, że dla każdego zdania θ w tym języku, ${\ Displaystyle \ varphi (x)}$

${\ Displaystyle {\ mathcal {N}} \ modele \ theta \ qquad}$ wtedy i tylko wtedy gdy ${\ Displaystyle {\ mathcal {N}} \ modele \ varphi ({\ podkreślenie {\ # (\ theta)}}).}$

Oto cyfra kanonicznej liczby Gödla zdania θ . ${\displaystyle {\podkreślenie {\#(\theta)}}}$

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

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

ale żadna pojedyncza formuła nie może zdefiniować Th _n ( )${\displaystyle {\mathcal {N}}}$ dla dowolnie dużego n .

Właściwości obliczeniowe

Jak omówiono powyżej, Th( )${\displaystyle {\mathcal {N}}}$ nie jest definiowalne arytmetycznie przez twierdzenie Tarskiego. Następstwem ustanawia twierdzenie Post że stopień Turing od Th ( )${\displaystyle {\mathcal {N}}}$ jest 0 ^(ω) , a więc Th ( )${\displaystyle {\mathcal {N}}}$ nie jest rozstrzygalne ani rekurencyjnie przeliczalny .

Th ( )${\displaystyle {\mathcal {N}}}$ jest ściśle związane z teorią Th ( )${\displaystyle {\mathcal {R}}}$ z rekurencyjnie przeliczalnych stopni Turinga , w celu podpisania częściowych zleceń . W szczególności istnieją funkcje obliczalne S i T takie, że:

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

Własności teoretyczne modelu

Prawdziwa arytmetyka jest teorią niestabilną , podobnie jak modele dla każdego niepoliczalnego kardynała . Ponieważ istnieje wiele typów kontinuum nad pustym zbiorem, prawdziwa arytmetyka ma również policzalne modele. Ponieważ teoria jest kompletna , wszystkie jej modele są elementarnie równoważne . ${\ Displaystyle 2 ^ {\ kappa}}$${\ Displaystyle \ kappa}$${\ Displaystyle 2 ^ {\ aleph _ {0}}}$

Prawdziwa teoria arytmetyki drugiego rzędu

Prawdziwa teoria arytmetyki drugiego rzędu składa się ze wszystkich zdań języka arytmetyki drugiego rzędu , które spełnia standardowy model arytmetyki drugiego rzędu, którego częścią pierwszego rzędu jest struktura, a część drugiego rzędu składa się z każdy podzbiór . ${\displaystyle {\mathcal {N}}}$${\ Displaystyle \ mathbb {N}}$

Prawdziwa teoria arytmetyki pierwszego rzędu, Th( )${\displaystyle {\mathcal {N}}}$ , jest podzbiorem prawdziwej teorii arytmetyki drugiego rzędu, a Th( )${\displaystyle {\mathcal {N}}}$ można zdefiniować 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 obliczalna z teorią porządku cząstkowego wszystkich stopni Turinga , w podpisie porządków cząstkowych i vice versa .

Uwagi

Bibliografia

• Boolos, George ; Burgess, John P .; Jeffrey, Richard C. (2002), Obliczalność i logika (4th ed.), Cambridge University Press, ISBN 978-0-521-00758-0.
• Bovykin, Andriej; Kaye, Richard (2001), "Na zamówienie typów modeli arytmetycznych", w Zhang, Yi (red.), Logika i algebra , Współczesna Matematyka, 302 , American Mathematical Society, s. 275-285, ISBN 978-0-8218-2984-4.
• Shore, Richard (2011), „The recursively enumerable degree”, w Griffor, ER (red.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, 140 , North-Holland (opublikowany 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 , Druga seria, 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 „Pojęcie prawdy w sformalizowanych językach” pojawia się w Corcoran, J., ed. (1983), Logic, Semantics and Metamatematics: Papers od 1923 do 1938 (2nd ed.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

Zewnętrzne linki

• Weisstein, Eric W. „Arytmetyka” . MatematykaŚwiat .
• Weisstein, Eric W. „Arytmetyka Peano” . MatematykaŚwiat .
• Weisstein, Eric W. „Twierdzenie Tarskiego” . MatematykaŚwiat .