Arytmetyka pierwszego rzędu — First-order arithmetic

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:

  1. , czyli dodawanie jest asocjacyjne .
  2. , czyli dodawanie jest przemienne .
  3. , czyli mnożenie jest asocjacyjne.
  4. , czyli mnożenie jest przemienne.
  5. , tj. mnożenie rozkłada się na dodawanie.
  6. , czyli zero jest identycznością dla dodawania i elementem absorbującym dla mnożenia.
  7. , czyli jeden jest tożsamością do mnożenia.
  8. , tzn. operator „<” jest przechodni .
  9. , tzn. operator „<” jest niezwrotny .
  10. , czyli zamówienie spełnia trichotomię .
  11. , tzn. kolejność jest zachowana po dodaniu tego samego elementu.
  12. , tzn. kolejność jest zachowana przy mnożeniu przez ten sam dodatni element.
  13. , tj. przy dowolnych dwóch odrębnych elementach, większy jest mniejszy plus kolejny element.
  14. , czyli zero i jedynka są różne i nie ma między nimi elementu.
  15. , 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 .

0 / IΣ 1

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

  1. ^ van Heijenoort, Jean (1967). Od Frege do Gödla . P. 83. Numer ISBN 978-0-67-432449-7.
  2. ^ Kaye Richard (1991). Modele arytmetyki Peano . s. 16-18.