W teorii mnogości i logice matematycznej arytmetyka pierwszego rzędu jest zbiorem systemów aksjomatycznych formalizujących liczby naturalne i podzbiory liczb naturalnych. Jest to wybór teorii aksjomatycznej jako podstawa wielu matematyki, ale nie wszystkich. Podstawowym aksjomatem pierwszego rzędu jest arytmetyka Peano , stworzona przez Giuseppe Peano :
-
: 0 to liczba naturalna.
-
: Równość jest refleksyjna .
-
: Równość jest symetryczna .
-
: Równość jest przechodnia .
-
: Liczby naturalne są zamknięte pod równością.
-
: Liczby naturalne są zamknięte pod S (operacja następnika).
-
: S to zastrzyk .
-
: Nie ma liczby naturalnej, której następcą jest zero.
-
: Jeśli K jest zbiorem takim, że 0 jest w K i dla każdej liczby naturalnej n, n będące w K implikuje, że S(n) jest w K, to K zawiera każdą liczbę naturalną.
Arytmetyka Peano ma teoretyczną liczbę porządkową .
Więcej o arytmetyce Peano
Różne aksjomaty arytmetyki Peano są różne, ale równoważne. Podczas gdy niektóre aksjomatyzacje, jak opisana niedawno (definicja pierwotna) używają sygnatury zawierającej tylko symbole 0, następnika, dodawania i mnożenia, inne aksjomatyzacje używają uporządkowanego języka półpierścieniowego, w tym symbolu relacji dodatkowego porządku. Jedna z takich aksjomatyzacji zaczyna się od następujących aksjomatów opisujących dyskretnie uporządkowany semiring:
-
, czyli dodawanie jest asocjacyjne .
-
, czyli dodawanie jest przemienne .
-
, czyli mnożenie jest asocjacyjne.
-
, czyli mnożenie jest przemienne.
-
, tj. mnożenie rozkłada się na dodawanie.
-
, czyli zero jest identycznością dla dodawania i elementem absorbującym dla mnożenia.
-
, czyli jeden jest tożsamością do mnożenia.
-
, tzn. operator „<” jest przechodni .
-
, tzn. operator „<” jest niezwrotny .
-
, czyli zamówienie spełnia trichotomię .
-
, tzn. kolejność jest zachowana po dodaniu tego samego elementu.
-
, tzn. kolejność jest zachowana przy mnożeniu przez ten sam dodatni element.
-
, tj. przy dowolnych dwóch odrębnych elementach, większy jest mniejszy plus kolejny element.
-
, czyli zero i jedynka są różne i nie ma między nimi elementu.
-
, czyli zero jest elementem minimalnym.
Te aksjomaty są znane jako PA − ; teorię PA uzyskuje się przez dodanie schematu indukcji pierwszego rzędu . Ważną cechą PA − jest to, że każda struktura spełniająca tę teorię ma początkowy segment (uporządkowany przez ) izomorficzny z . Elementy w tym segmencie nazywane są elementami standardowymi, podczas gdy inne elementy nazywane są elementami niestandardowymi.
arytmetyka Robinsona Q
Arytmetyka Robinsona to skończenie zaksjomatyzowany fragment pierwszego rzędu arytmetyki Peano (PA), wyprodukowany po raz pierwszy w 1950 roku przez RM Robinsona . Jest często określany jako Q. Q jest prawie identyczny z PA bez matematycznego schematu aksjomatu indukcji (PA - ). Q jest słabsze niż PA, ale ich język jest taki sam, a obie teorie są niekompletne . Logika tła Q jest logiką pierwszego rzędu z tożsamością, oznaczoną przez wrostek „=”. Indywidua, zwane liczbami naturalnymi, są członkami zbioru o nazwie N z wyróżnionym elementem 0, zwanym zerem. Istnieją trzy operacje nad N:
- Jednoargumentowa operacja zwana następcą i oznaczona przedrostkiem S;
- Dwie operacje binarne, dodawanie i mnożenie, oznaczone odpowiednio przez wrostek + i ·.
Aksjomaty to:
-
: 0 nie jest następcą żadnej liczby.
-
: Jeśli następca x jest identyczny z następnikiem y, to x i y są identyczne.
-
Każda liczba naturalna to albo 0, albo następczyni jakiejś liczby.
Arytmetyka Robinsona ma teoretyczną liczbę porządkową .
Iterowane definicje indukcyjne
System indukcyjnych definicji iterowanych razy jest hierarchią silnych systemów matematycznych opracowanych przez niemieckiego matematyka Wilfrieda Buchholza, znanego z tworzenia funkcji psi Buchholza . ID ν rozszerza PA o ν iterowane najmniej ustalone punkty operatorów monotonicznych. Jeśli ν = ω, aksjomaty są następujące:
- Aksjomaty z arytmetyki Peano
-
dla każdego L ID - formuła F(x)
Dla ν ≠ ω aksjomaty to:
- Aksjomaty z arytmetyki Peano
-
dla każdego L ID -formuła F(x) i wszystkie u < ν
to osłabiona wersja . W systemie , zbiór jest zamiast tego nazywany indukcyjnie zdefiniowanym, jeśli dla pewnego operatora monotonicznego , jest punktem stałym , a nie najmniej stałym punktem. Ta subtelna różnica znacznie osłabia system: , while .
jest jeszcze bardziej osłabiony. W , nie tylko używa punktów stałych, a nie najmniej stałych, ale ma również indukcję tylko dla formuł dodatnich. Ta subtelna różnica sprawia, że system jest jeszcze słabszy: , while .
to najsłabszy ze wszystkich wariantów , oparty na typach W. Ilość osłabienia w porównaniu do regularnych iterowanych definicji indukcyjnych jest identyczna z usuwaniem indukcji prętowej przy określonym podsystemie arytmetyki drugiego rzędu . , natomiast .
to „rozwijające się” wzmocnienie . Nie jest to dokładnie system arytmetyczny pierwszego rzędu, ale oddaje to, co można uzyskać dzięki rozumowaniu predykatywnemu opartemu na v-krotnej iteracji uogólnionych definicji indukcyjnych. Wielkość wzrostu siły jest identyczna ze wzrostem od do : , while .
jest automorfizmem od . , ale nadal jest słabszy niż .
jest automorfizmem od . , ale nadal jest słabszy niż .
jest automorfizmem . , gdzie jest hierarchią Veblen z przeliczalnie iterowanymi najmniej ustalonymi punktami.
Inne systemy pierwszego rzędu
PA –
PA – jest teorią pierwszego rzędu nieujemnej części dyskretnie uporządkowanego pierścienia. Pierścień jest zbiorem wyposażonym w dwie operacje binarne: (dodawanie) i (mnożenie) spełniające następujące trzy zbiory aksjomatów, zwanych aksjomatami pierścieniowymi:
-
jest łączne, jest przemienne, jest tożsamość dodatek i jest dodatek odwrotny od .
-
jest skojarzeniowa i jest tożsamością multiplikatywną .
-
dla wszystkich , a w .
-
dla wszystkich , a w .
PA – ma teoretyczno-teoretyczną liczbę porządkową .
RFA
RFA to podstawowa arytmetyka funkcji . Funkcja podstawowa to funkcja, którą można uzyskać z następujących operacji:
-
jest szczątkowy
-
jest szczątkowy
-
jest szczątkowy
- Każda kompozycja podstawowych funkcji jest rudymentarna
-
jest szczątkowy
Dla dowolnego zbioru M niech rud( M ) będzie najmniejszym zbiorem zawierającym M ∪{ M } zamknięty w ramach operacji elementarnych. RFA to wersja arytmetyki oparta na podstawowych funkcjach. RFA ma teoretyczną liczbę porządkową 2 .
IΔ 0 / IΣ 1
IΔ 0 i IΣ 1 są podstawowymi obliczeniami arytmetycznymi z indukcją odpowiednio dla Δ 0 - i Σ 1 -predykatów. Zauważ, że kiedy ludzie odwołują się do IΔ 0 , IΔ 0 jest podstawową arytmetyką z indukcją dla Δ 0 -predykatów, ale bez aksjomatu stwierdzającego, że potęgowanie jest całkowite , podczas gdy IΔ 0 z takim aksjomatem jest określane jako IΔ 0 + . IΔ 0 n 1 <n <Ohm jest IΔ 0 + zwiększona przez zapewnienie pewnik, że każdy element n -tym poziomu w hierarchii Grzegorczyków jest całkowite. IΔ 0 ma teoretyczną liczbę porządkową 2 . IΔ 0 + . ma teoretyczną liczbę porządkową 3 . IΔ 0 n ma teoretyczną liczbę porządkową n . IΣ 1 ma teoretyczną liczbę porządkową ω .
NNKT
EFA to elementarna arytmetyka funkcji. Jego język zawiera:
- dwie stałe 0, 1,
- trzy operacje binarne +, ×, exp, z exp( x , y ) zwykle zapisywanymi jako x y ,
- symbol relacji binarnej < (Nie jest to naprawdę konieczne, ponieważ można go zapisać w kategoriach innych operacji i czasami jest pomijane, ale jest wygodne przy definiowaniu kwantyfikatorów ograniczonych).
Kwantyfikatory ograniczone to te o postaci ∀(x<y) i ∃ (x<y), które są skrótami dla ∀ x (x<y)→... i ∃x (x<y)∧... w zwykłym sposób. Aksjomaty EFA to:
- Aksjomaty arytmetyki Robinsona dla 0, 1, +, ×, <
- Aksjomaty potęgowania: x 0 = 1, x y +1 = x y × x .
- Indukcja dla formuł, których wszystkie kwantyfikatory są ograniczone (ale które mogą zawierać wolne zmienne).
PRA
PRA to prymitywna arytmetyka rekurencyjna, czyli pozbawiona kwantyfikatorów formalizacja liczb naturalnych . Język PRA składa się z:
Logiczne aksjomaty PRA to:
Logiczne zasady PRA to modus ponens i substytucja zmiennych .
Nielogiczne aksjomaty to:
i rekurencyjne definiowanie równań dla każdej pierwotnej funkcji rekurencyjnej według potrzeb.
Bibliografia
-
^
van Heijenoort, Jean (1967). Od Frege do Gödla . P. 83. Numer ISBN 978-0-67-432449-7.
-
^ Kaye Richard (1991). Modele arytmetyki Peano . s. 16-18.