Lista teorii pierwszego rzędu - List of first-order theories

W logice matematycznej teorię pierwszego rzędu podaje zbiór aksjomatów w jakimś języku. W tym wpisie wymieniono niektóre z bardziej powszechnych przykładów stosowanych w teorii modeli i niektóre z ich właściwości.

Czynności wstępne

Dla każdej naturalnej struktury matematycznej istnieje sygnatura σ zawierająca stałe, funkcje i relacje teorii wraz z ich wartościami , tak że obiekt jest naturalnie strukturą σ . Mając daną sygnaturę σ, istnieje unikalny język L σ pierwszego rzędu, który może być użyty do uchwycenia wyrażalnych faktów pierwszego rzędu dotyczących struktury σ.

Istnieją dwa typowe sposoby określania teorii:

  1. Wymień lub opisz zbiór zdań w języku L σ , zwanych aksjomatami teorii.
  2. Podaj zbiór struktur σ i zdefiniuj teorię jako zbiór zdań w L σ utrzymujący się we wszystkich tych modelach. Na przykład „teoria ciał skończonych” składa się ze wszystkich zdań w języku pól, które są prawdziwe we wszystkich ciałach skończonych.

Teoria L σ może:

Teorie czystej tożsamości

Podpis czystej teorii tożsamości jest pusty, bez funkcji, stałych czy relacji.

Teoria czystej tożsamości nie ma (nielogicznych) aksjomatów. To jest rozstrzygalne.

Jedną z niewielu interesujących właściwości, które można stwierdzić w języku teorii czystej tożsamości, jest nieskończoność. Daje to nieskończony zbiór aksjomatów stwierdzających, że są co najmniej 2 elementy, są co najmniej 3 elementy i tak dalej:

  • ∃ x 1 ∃ x 2 ¬ x 1 = x 2 , ∃ x 1 ∃ x 2 ∃ x 3 ¬ x 1 = x 2 ∧ ¬ x 1 = x 3 ∧ ¬ x 2 = x 3 , ...

Te aksjomaty definiują teorię zbioru nieskończonego .

Przeciwnej właściwości bycia skończonym nie można stwierdzić w logice pierwszego rzędu dla żadnej teorii, która ma dowolnie duże modele skończone: w rzeczywistości każda taka teoria ma nieskończone modele według twierdzenia o zwartości . Ogólnie rzecz biorąc, jeśli właściwość może być określona za pomocą skończonej liczby zdań logiki pierwszego rzędu, wówczas właściwość przeciwną można również określić w logice pierwszego rzędu, ale jeśli właściwość wymaga nieskończonej liczby zdań, nie można określić jej właściwości przeciwnej w logice pierwszego rzędu.

Dowolna instrukcja teoretycznej tożsamości czystego jest równa albo Ď ( N ) lub ¬σ ( N ) dla pewnej ograniczonej podzbioru N z nieujemne liczby całkowite , w których σ ( N ) jest stwierdzenie, że liczba elementów jest N . Możliwe jest nawet opisanie wszystkich możliwych teorii w tym języku w następujący sposób. Każda teoria jest albo teorią wszystkich zbiorów o liczności w N dla pewnego skończonego podzbioru N nieujemnych liczb całkowitych, albo teorią wszystkich zbiorów, których liczność nie jest w N , dla pewnego skończonego lub nieskończonego podzbioru N nieujemnych liczby całkowite. (Nie ma teorii, których modele są dokładnie zbiorami o liczności N, jeśli N jest nieskończonym podzbiorem liczb całkowitych). Teorie kompletne to teorie zbiorów o liczności n dla pewnego skończonego n oraz teoria zbiorów nieskończonych.

Szczególnym tego przykładem jest niespójna teoria zdefiniowana przez aksjomat ∃ x ¬ x = x . Jest to doskonała teoria z wieloma dobrymi właściwościami: jest kompletna, rozstrzygalna, ostatecznie aksjomatyzowalna i tak dalej. Jedynym problemem jest to, że w ogóle nie ma modeli. Zgodnie z twierdzeniem Gödla o zupełności jest to jedyna teoria (dla danego języka) bez modeli. To nie to samo, co teoria zbioru pustego (w wersjach logiki pierwszego rzędu, które pozwalają modelowi być pustym): teoria zbioru pustego ma dokładnie jeden model, który nie ma elementów.

Relacje jednoargumentowe

Zbiór relacji jednoargumentowych P i dla i w pewnym zbiorze I nazywany jest niezależnym, jeśli dla każdych dwóch rozłącznych podzbiorów skończonych A i B w I istnieje taki element x , że P i ( x ) jest prawdziwe dla i w A i fałszywe dla i w B . Niezależność można wyrazić za pomocą zestawu stwierdzeń pierwszego rzędu.

Teoria wielu policzalnych niezależnych stosunków jednoargumentowych jest kompletna, ale nie ma modeli atomowych . Jest to również przykład teorii superstabilnej, ale nie całkowicie transcendentalnej .

Relacje równoważności

Sygnatura relacji równoważności ma jeden binarny symbol relacji wrostek ~, żadnych stałych i żadnych funkcji. Relacje równoważności spełniają aksjomaty:

Oto niektóre właściwości relacji równoważności pierwszego rzędu:

  • ~ ma nieskończoną liczbę klas równoważności ;
  • ~ ma dokładnie n klas równoważności (dla dowolnej ustalonej liczby całkowitej dodatniej n );
  • Wszystkie klasy równoważności są nieskończone;
  • Wszystkie klasy równoważności mają rozmiar dokładnie n (dla dowolnej stałej dodatniej liczby całkowitej n ).

Teoria relacji równoważności z dokładnie 2 nieskończonymi klasami równoważności jest łatwym przykładem teorii, która jest ω-kategoryczna, ale nie jest kategoryczna dla żadnego większego kardynała .

Relacji równoważności ~ nie należy mylić z symbolem tożsamości „=”: jeśli x = y, to x ~ y , ale odwrotność niekoniecznie jest prawdą. Teorie relacji równoważności nie są wcale takie trudne ani interesujące, ale często podają łatwe przykłady lub kontrprzykłady dla różnych stwierdzeń.

Poniższe konstrukcje są czasami używane do tworzenia przykładów teorii z określonymi widmami ; w rzeczywistości przez zastosowanie ich do niewielkiej liczby jawnych teorii T otrzymuje się przykłady kompletnych policzalnych teorii ze wszystkimi możliwymi niepoliczalnymi widmami. Jeśli T jest teorią w jakimś języku, definiujemy nową teorię 2 T , dodając nową relację binarną do języka i dodając aksjomaty stwierdzające, że jest to relacja równoważności, tak że istnieje nieskończona liczba klas równoważności, z których wszystkie są modele z T . Możliwe jest iterowanie tej konstrukcji w nieskończoność : biorąc pod uwagę porządkową α, zdefiniuj nową teorię, dodając relację równoważności E β dla każdego β <α, wraz z aksjomatami stwierdzającymi, że ilekroć β <γ to każda klasa równoważności E γ jest sumą nieskończenie wiele E p równoważność klas, a każdy E 0 równoważności klasa jest modelem T . Nieformalnie można wizualizować modele tej teorii jako nieskończenie rozgałęzione drzewa o wysokości α z modelami T dołączonymi do wszystkich liści.

Zamówienia

Podpis zleceń nie ma stałych ani funkcji, a jeden symbol relacji binarnej ≤. (Oczywiście zamiast tego można użyć ≥, <lub> jako podstawowej relacji, z oczywistymi drobnymi zmianami w aksjomatach.) Definiujemy x ≥ y , x < y , x > y jako skróty dla y ≤ x , x ≤ y ∧¬ y ≤ x , y < x ,

Niektóre właściwości zamówień pierwszego rzędu:

  • Przechodni : ∀ x ∀ y ∀ z x ≤ y ∧ y ≤ z → x ≤ z
  • Odruchowy : ∀ x x ≤ x
  • Antysymetryczny : ∀ x ∀ y x ≤ y ∧ y ≤ x → x = y
  • Częściowe : przechodnie ∧ refleksyjne ∧ antysymetryczne;
  • Liniowy (lub całkowity ): Częściowy ∧ ∀ x ∀ y x ≤ y ∨ y ≤ x
  • Gęsty : ∀ x ∀ z x < z → ∃ y x < y ∧ y < z („Pomiędzy dowolnymi 2 różnymi elementami jest inny element”)
  • Jest najmniejszy element: ∃ x ∀ y x ≤ y
  • Jest największy element: ∃ x ∀ y y ≤ x
  • Każdy element ma bezpośredniego następcę: ∀ x ∃ y ∀ z x < z ↔ y ≤ z

Teoria DLO gęstych rzędów liniowych bez punktów końcowych (tj. Bez najmniejszego lub największego elementu) jest kompletna, ω-kategoryczna, ale nie kategoryczna dla żadnego niepoliczalnego kardynała. Istnieją trzy inne bardzo podobne teorie: teoria gęstych rzędów liniowych z:

  • Najmniejszy, ale nie największy element;
  • Największy, ale nie najmniejszy element;
  • Największy i najmniejszy element.

Są uporządkowane ( „każdy niepusty podzbiór ma minimalny elementu”) jest właściwością pierwszego rzędu; zwykła definicja obejmuje kwantyfikację wszystkich podzbiorów .

Kraty

Kraty można rozpatrywać albo jako specjalne rodzaje zbiorów częściowo uporządkowanych, z sygnaturą składającą się z jednego symbolu relacji binarnej ≤, albo jako struktury algebraiczne z sygnaturą składającą się z dwóch operacji binarnych ∧ i ∨. Te dwa podejścia można powiązać, definiując a ≤ b jako oznaczające a ∧ b = a .

Dla dwóch operacji binarnych aksjomatami dla kraty są:

Prawa przemienne :
Prawa stowarzyszeniowe :
Prawa absorpcji :

Dla jednej relacji ≤ aksjomaty to:

  • Aksjomaty stwierdzające ≤ to porządek częściowy, jak wyżej.
  • (istnienie c = a∧b)
  • (istnienie c = a∨b)

Właściwości pierwszego rzędu obejmują:

  • ( kraty rozdzielcze )
  • ( kraty modułowe )

Algebry heytowe można zdefiniować jako kraty z pewnymi dodatkowymi właściwościami pierwszego rzędu.

Kompletność nie jest właściwością pierwszego rzędu krat.

Wykresy

Główny artykuł: Logika grafów

Sygnatura grafów nie ma stałych ani funkcji, a jeden symbol relacji binarnej R , gdzie R ( x , y ) odczytuje się jako „istnieje krawędź od x do y ”.

Aksjomaty teorii grafów to

Teorią losowych wykresów ma następujące dodatkowe axioms dla każdej dodatniej liczby całkowitej N :

  • Dla dowolnych dwóch rozłącznych skończonych zbiorów o rozmiarze n istnieje punkt połączony ze wszystkimi punktami pierwszego zbioru i żadnym punktem z drugiego zbioru. (Dla każdego ustalonego n łatwo jest napisać to stwierdzenie w języku wykresów).

Teoria grafów losowych jest ω jakościowa, kompletna i rozstrzygalna, a jej policzalny model nazywa się grafem Rado . Stwierdzenie w języku grafów jest prawdziwe w tej teorii wtedy i tylko wtedy, gdy prawdopodobieństwo, że n -vertex losowy wykres modeluje stwierdzenie ma tendencję do 1 na granicy, gdy n dąży do nieskończoności.

Algebry Boole'a

Istnieje kilka różnych sygnatur i konwencji używanych w algebrach Boole'a :

  1. Podpis ma dwie stałe, 0 i 1, oraz dwie funkcje binarne ∧ i ∨ („i” i „lub”) oraz jedną funkcję jednoargumentową ¬ („nie”). Może to być mylące, ponieważ funkcje używają tych samych symboli, co funkcje zdaniowe logiki pierwszego rzędu.
  2. W teorii mnogości powszechną konwencją jest to, że język ma dwie stałe, 0 i 1 oraz dwie funkcje binarne · i + oraz jedną funkcję jednoargumentową -. Te trzy funkcje mają taką samą interpretację, jak funkcje w pierwszej konwencji. Niestety ta konwencja źle koliduje z następną konwencją:
  3. W algebrze zwykle obowiązuje konwencja, że ​​język ma dwie stałe, 0 i 1 oraz dwie funkcje binarne · i +. Funkcja · ma to samo znaczenie co ∧, ale a + b oznacza a ∨ b ∧¬ ( a ∧ b ). Powodem tego jest to, że aksjomaty algebry Boole'a są wtedy tylko aksjomatami dla pierścienia z 1 dodać ∀ x x 2 = x . Niestety jest to sprzeczne ze standardową konwencją w teorii mnogości podaną powyżej.

Aksjomaty to:

  • Aksjomaty dla sieci dystrybucyjnej (patrz wyżej)
  • ∀a a ∧¬ a = 0, ∀a a ∨¬ a = 1 (własności negacji)
  • Niektórzy autorzy dodają dodatkowy aksjomat ¬0 = 1, aby wykluczyć trywialną algebrę z jednym elementem.

Tarski udowodnił, że teoria algebr Boole'a jest rozstrzygalna.

Piszemy x ≤ y jako skrót dla x ∧ y = x , a atom ( x ) jako skrót dla ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = x , czytaj jako „ x jest atomem ", innymi słowy niezerowy element bez niczego między nim a 0. Oto kilka właściwości pierwszego rzędu algebr Boole'a:

  • Atomowy : ∀ x x = 0 ∨ ∃ y y ≤ x ∧ atom ( y )
  • Bezatomowy : ∀ x ¬atom ( x )

Teoria bezatomowych algebr Boole'a jest ω-kategoryczna i kompletna.

Dla każdej algebry Boole'a B istnieje kilka niezmienników zdefiniowanych w następujący sposób.

  • idealne I ( B ) składa się z pierwiastków, które są sumą pierwiastka atomowego i bezatomowego (pierwiastka bez atomów poniżej).
  • Algebry ilorazowe B i z B są zdefiniowane indukcyjnie przez B 0 = B , B k +1 = B k / I ( B k ).
  • Niezmienna m ( B ) jest najmniejszą liczbą całkowitą, taką, że B m +1 jest trywialne lub ∞, jeśli taka liczba nie istnieje.
  • Jeśli m ( B ) jest skończone, niezmiennikiem n ( B ) jest liczba atomów B m ( B ), jeśli ta liczba jest skończona, lub ∞, jeśli ta liczba jest nieskończona.
  • Niezmiennik l ( B ) wynosi 0, jeśli B m ( B ) jest atomowy lub jeśli m ( B ) jest równe ∞, a 1 w innym przypadku.

Wtedy dwie algebry Boole'a są elementarnie równoważne wtedy i tylko wtedy, gdy ich niezmienniki l , m i n są takie same. Innymi słowy, wartości tych niezmienników klasyfikują możliwe uzupełnienia teorii algebr Boole'a. Zatem możliwe kompletne teorie to:

  • Trywialna algebra (jeśli jest to dozwolone; czasami 0 ≠ 1 jest uwzględniane jako aksjomat).
  • Teoria z m = ∞
  • Teorie, w których m jest liczbą naturalną, n liczbą naturalną lub ∞ i l = 0 lub 1 (gdzie l = 0, jeśli n = 0).

Grupy

Sygnatura teorii grup ma jedną stałą 1 (tożsamość), jedną funkcję liczby 1 (odwrotność), której wartość t jest oznaczona przez t −1 , i jedną funkcję liczby 2, która jest zwykle pomijana w terminach. Dla dowolnej liczby całkowitej n , t n jest skrótem od oczywistego terminu n- tej potęgi t .

Grupy są określone przez aksjomaty

  • Tożsamość : ∀ x 1 x = x ∧ x 1 = x
  • Odwrotność : ∀ x x −1 x = 1 ∧ xx −1 = 1
  • Łączność : ∀ x ∀ Y ∀ z ( XY ), z = x ( YZ )

Niektóre właściwości grup, które można zdefiniować w języku pierwszego rzędu, to:

  • Abel : ∀ x ∀ y xy = yx .
  • Bez skręcania : ∀ x x 2 = 1 → x = 1, ∀ x x 3 = 1 → x = 1, ∀ x x 4 = 1 → x = 1, ...
  • Podzielna : ∀ x ∃ y y 2 = x , ∀ x ∃ y y 3 = x , ∀ x ∃ y y 4 = x , ...
  • Nieskończony (jak w teorii tożsamości)
  • Wykładnik n (dla dowolnej ustalonej dodatniej liczby całkowitej n ): ∀ x x n = 1
  • Nilpotent klasy n (dla dowolnej ustalonej dodatniej liczby całkowitej n )
  • Rozwiązalny klasy n (dla dowolnej stałej dodatniej liczby całkowitej n )

Teoria grup abelowych jest rozstrzygalna. Teoria nieskończonych podzielnych, wolnych od skrętów grup abelowych jest kompletna, podobnie jak teoria nieskończonych grup abelowych z wykładnikiem p (dla p liczby pierwszej ).

Teoria grup skończonych to zbiór zdań pierwszego rzędu w języku grup, które są prawdziwe we wszystkich grupach skończonych (istnieje wiele nieskończonych modeli tej teorii). Znalezienie takiego stwierdzenia, które nie jest prawdziwe dla wszystkich grup, nie jest całkowicie trywialne: jeden przykład to „dane dwa elementy rzędu 2, albo są one sprzężone, albo istnieje nietrywialny element dojeżdżający do pracy z nimi obiema”.

Właściwości bycia skończonym, swobodnym , prostym lub skręcaniem nie są pierwszego rzędu. Dokładniej, teoria pierwszego rzędu wszystkich grup z jedną z tych właściwości ma modele, które nie mają tej właściwości.

Pierścienie i pola

Sygnatura pierścieni (jedności) ma dwie stałe 0 i 1, dwie funkcje binarne + i × oraz opcjonalnie jedną jednoargumentową funkcję negacji -.

Pierścienie

Aksjomaty: Dodawanie sprawia, że ​​pierścień jest grupą abelową, mnożenie jest asocjacyjne i ma tożsamość 1, a mnożenie jest dystrybucyjne po lewej i po prawej stronie.

Pierścienie przemienne

Aksjomaty pierścieni plus ∀ x ∀ y xy = yx .

Pola

Aksjomaty pierścieni przemiennych plus ∀ x (¬ x = 0 → ∃ y xy = 1) i ¬ 1 = 0. Wiele z podanych tutaj przykładów ma tylko aksjomaty uniwersalne lub algebraiczne . Klasy struktur spełniające taką teorię, ma właściwość jest zamknięty pod podbudowy. Na przykład podzbiór grupy zamkniętej w ramach działań grupowych mnożenia i odwrotności jest ponownie grupą. Ponieważ sygnatura pól zwykle nie zawiera multiplikatywnej i addytywnej odwrotności, aksjomaty odwrotności nie są uniwersalne, a zatem podstruktura pola zamkniętego przez dodawanie i mnożenie nie zawsze jest polem. Można temu zaradzić, dodając do języka jednoargumentowe funkcje odwrotne.

Dla każdej dodatniej liczby całkowitej n właściwość, że wszystkie równania stopnia n mają pierwiastek, można wyrazić za pomocą pojedynczego zdania pierwszego rzędu:

  • ∀ a 1 ∀ a 2 ... ∀ a n ∃ x (... (( x + a 1 ) x + a 2 ) x + ...) x + a n = 0

Doskonałe pola

Aksjomaty dla pól plus aksjomaty dla każdej liczby pierwszej p stwierdzające, że jeśli p  1 = 0 (tj. Pole ma charakterystykę p ), to każdy element pola ma pierwiastek p- ty.

Algebraicznie zamknięte pola o charakterystyce p

Aksjomaty dla pól plus dla każdego dodatniego n aksjomat, że wszystkie wielomiany stopnia n mają pierwiastek, plus aksjomaty ustalające charakterystykę. Klasyczne przykłady kompletnych teorii. Kategoryczny u wszystkich niezliczonych kardynałów. Teoria ACF P ma uniwersalne własności domeny , w tym sensie, że każda struktura N spełniającą uniwersalne aksjomaty ACF p jest podłoże wystarczająco duże pole algebraicznie zamkniętym i dodatkowo dowolne dwa takie zanurzeń N → M indukuje automorfizm z M .

Pola skończone

Teoria ciał skończonych jest zbiorem wszystkich zdań pierwszego rzędu, które są prawdziwe we wszystkich ciałach skończonych. Znaczące przykłady takich stwierdzeń można podać, na przykład, stosując twierdzenie Chevalley-Warning na polach pierwszych . Nazwa jest trochę myląca, ponieważ teoria ma wiele nieskończonych modeli. Ax udowodnił, że teoria jest rozstrzygalna.

Formalnie prawdziwe pola

Aksjomaty dla pól plus, dla każdej dodatniej liczby całkowitej n , aksjomat:

  • ∀ a 1 ∀ a 2 ... ∀ a n a 1 a 1 + a 2 a 2 + ... + a n a n = 0 → a 1 = 0∧ a 2 = 0∧ ... ∧ a n = 0.

Oznacza to, że 0 nie jest nietrywialną sumą kwadratów.

Prawdziwie zamknięte pola

Aksjomaty dla pól formalnie rzeczywistych plus aksjomaty:

  • ∀ x ∃ y ( x = yy ∨ x + yy = 0);
  • dla każdej nieparzystej liczby całkowitej dodatniej n aksjomat stwierdzający, że każdy wielomian stopnia n ma pierwiastek.

Teoria rzeczywistych pól zamkniętych jest skuteczna i kompletna, a zatem rozstrzygalna ( twierdzenie Tarskiego – Seidenberga ). Dodanie kolejnych symboli funkcji (np. Funkcji wykładniczej, funkcji sinus) może zmienić rozstrzygalność .

p -adic pola

Ax i Kochen (1965) wykazali, że teoria pól p- adycznych jest rozstrzygalna i podali dla niej zbiór aksjomatów.

Geometria

Aksjomaty dla różnych systemów geometrii zwykle używają języka maszynopisowego, z różnymi typami odpowiadającymi różnym obiektom geometrycznym, takim jak punkty, proste, okręgi, płaszczyzny i tak dalej. Podpis będzie często składał się z binarnych relacji incydentów między obiektami różnych typów; na przykład relacja, że ​​punkt leży na prostej. Podpis może mieć bardziej skomplikowane relacje; na przykład uporządkowana geometria może mieć trójskładnikową relację „między” dla 3 punktów, która mówi, czy jeden leży między dwoma innymi, lub relację „zgodności” między 2 parami punktów.

Niektóre przykłady układów axiomatized geometrii obejmują uporządkowane geometrii , geometrii absolutnej , geometrii afinicznej , geometrii euklidesowej , geometrii rzutowej i geometrii hiperbolicznej . Dla każdej z tych geometrii istnieje wiele różnych i nierównomiernych układów aksjomatów dla różnych wymiarów. Niektóre z tych systemów aksjomatów zawierają aksjomaty „kompletności”, które nie są pierwszego rzędu.

Jako typowy przykład, aksjomaty geometrii rzutowej używają 2 typów, punktów i linii oraz binarnej relacji występowania między punktami i prostymi. Jeśli zmienne punktowe i liniowe są oznaczone małą i dużą literą, a zdarzenie A jest zapisane jako aA , to jeden zestaw aksjomatów jest

  • (Istnieje linia przechodząca przez dowolne 2 różne punkty a , b ...)
  • (... co jest wyjątkowe)
  • (Aksjomat Veblena: jeśli ab i cd leżą na przecinających się liniach, to tak samo jak ac i bd .)
  • (Każda linia ma co najmniej 3 punkty)

Euklides nie podał wyraźnie wszystkich aksjomatów geometrii euklidesowej, a pierwszą pełną listę podał Hilbert w aksjomatach Hilberta . Nie jest to aksjomatyzacja pierwszego rzędu, ponieważ jeden z aksjomatów Hilberta jest aksjomatem kompletności drugiego rzędu. Aksjomaty Tarskiego to aksjomatyzacja pierwszego rzędu geometrii euklidesowej. Tarski wykazał, że ten system aksjomatów jest kompletny i rozstrzygalny, odnosząc go do pełnej i rozstrzygalnej teorii rzeczywistych pól zamkniętych.

Algebra różniczkowa

Podpis składa się z pól (0, 1, +, -, ×) wraz z jednoargumentową funkcją ∂, pochodną. Aksjomaty dotyczą pól razem z

Do tego jedna z teorii można dodać warunek, że charakterystyka jest p , głównym lub zero, aby uzyskać teorii DF p o zróżnicowanych dziedzinach charakterystycznym p (i podobnie z innymi teoriami poniżej).

Jeśli K jest polem różniczkowym, to pole stałych Teoria pól różniczkowo doskonałych jest teorią pól różniczkowych wraz z warunkiem, że pole stałych jest doskonałe; innymi słowy, dla każdej liczby pierwszej p ma aksjomat:

(Nie ma sensu żądać, aby całe pole było polem idealnym , ponieważ w charakterystyce niezerowej oznacza to różnicę równą 0.) Z przyczyn technicznych związanych z eliminacją kwantyfikatora czasami wygodniej jest wymusić stałe pole być doskonałym, dodając nowy symbol r do podpisu z aksjomatami

Dodanie

Teoria liczb naturalnych z funkcją następcy ma podpis składają stałą 0 i funkcji jednoargumentowy S ( „następca”: S ( x ) jest interpretowany jako x +1) i ma axioms:

  1. ∀x ¬ Sx = 0
  2. ∀x∀y Sx = Sy → x = y
  3. Niech P ( x ) będzie formułą pierwszego rzędu z pojedynczą wolną zmienną x . Zatem następujący wzór jest aksjomatem:
( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

Ostatni aksjomat (indukcja) można zastąpić aksjomatami

  • Dla każdej liczby całkowitej n > 0, aksjomat ∀x SSS ... Sx ≠ x (z n kopiami S )
  • ∀x ¬ x = 0 → ∃y Sy = x

Teoria liczb naturalnych z funkcją następcy jest kompletna i rozstrzygalna i jest kategorią κ dla niepoliczalnego κ, ale nie dla policzalnego κ.

Arytmetyka presburgera to teoria dodawania liczb naturalnych, z sygnaturą składającą się ze stałej 0, funkcji jednoargumentowej S i funkcji binarnej +. Jest kompletny i możliwy do rozstrzygnięcia. Aksjomaty są

  1. ∀x ¬ Sx = 0
  2. ∀x∀y Sx = Sy → x = y
  3. ∀xx + 0 = x
  4. ∀x∀yx + Sy = S (x + y)
  5. Niech P ( x ) będzie formułą pierwszego rzędu z pojedynczą wolną zmienną x . Zatem następujący wzór jest aksjomatem:
( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

Arytmetyka

Wiele z opisanych powyżej teorii pierwszego rzędu można rozszerzyć, aby uzupełnić rekurencyjnie wyliczalne spójne teorie. Nie jest to już prawdą w przypadku większości poniższych teorii; zwykle mogą kodować zarówno mnożenie, jak i dodawanie liczb naturalnych, co daje im wystarczającą moc do kodowania siebie, co oznacza, że ma zastosowanie twierdzenie Gödla o niezupełności i teorie nie mogą być już zarówno kompletne, jak i rekurencyjnie wyliczalne (chyba że są niespójne).

Podpis teorii arytmetyki ma:

Niektórzy autorzy przyjmują, że podpis zawiera stałą 1 zamiast funkcji S , a następnie definiują S w sposób oczywisty jako St = 1 + t .

Arytmetyka Robinsona (zwana także Q ). Aksjomaty (1) i (2) rządzą wyróżnionym elementem 0. (3) zapewnia, że S jest zastrzykiem . Aksjomaty (4) i (5) to standardowa rekurencyjna definicja dodawania; (6) i (7) robią to samo dla mnożenia. Arytmetykę Robinsona można traktować jako arytmetykę Peano bez indukcji. Q jest słabą teorią, której dotyczy twierdzenie o niezupełności Gödla . Aksjomaty:

  1. ∀ x ¬ S x = 0
  2. ∀ x ¬ x = 0 → ∃ y S y = x
  3. ∀ x ∀ y S x = S y → x = y
  4. ∀ x x + 0 = x
  5. ∀ x ∀ y x + S y = S ( x + y )
  6. ∀ x x x 0 = 0
  7. ∀ x ∀ y x × S y = ( x × y ) + x .

IΣ n jest arytmetyką Peano pierwszego rzędu z indukcją ograniczoną do Σ n formuł (dla n = 0, 1, 2, ...). Teoria IΣ 0 jest często oznaczana przez IΔ 0 . To seria coraz potężniejszych fragmentów arytmetyki Peano. Przypadek n  = 1 ma mniej więcej taką samą siłę jak prymitywna arytmetyka rekurencyjna (PRA). Arytmetyka funkcji wykładniczej (EFA) to IΣ 0 z aksjomatem stwierdzającym, że x y istnieje dla wszystkich x i y (ze zwykłymi właściwościami).

Arytmetyka Peano pierwszego rzędu , PA . „Standardowa” teoria arytmetyki. Aksjomaty są aksjomatami arytmetyki Robinsona powyżej, wraz z aksjomatem schematu indukcji:

  • dla dowolnej formuły φ w języku PA . φ może zawierać wolne zmienne inne niż x .

Praca Kurta Gödla z 1931 r. Dowiodła, że PA jest niekompletna i nie zawiera spójnych rekurencyjnie wyliczalnych uzupełnień.

Kompletna arytmetyczna (znany również jako prawdziwy arytmetyczne ) jest teoria standardowego modelu arytmetyki liczb naturalnych N . Jest kompletna, ale nie ma rekurencyjnie wyliczalnego zestawu aksjomatów.

W przypadku liczb rzeczywistych sytuacja jest nieco inna: przypadek, który obejmuje tylko dodawanie i mnożenie, nie może zakodować liczb całkowitych, a zatem twierdzenie o niezupełności Gödla nie ma zastosowania . Przy dodawaniu kolejnych symboli funkcji (np. Potęgowanie) pojawiają się komplikacje .

Arytmetyka drugiego rzędu

Arytmetyka drugiego rzędu może odnosić się do teorii pierwszego rzędu (pomimo nazwy) z dwoma typami zmiennych, uważanymi za zmienne względem liczb całkowitych i podzbiorów liczb całkowitych. (Istnieje również teoria arytmetyki w logice drugiego rzędu, zwana arytmetyką drugiego rzędu. Ma ona tylko jeden model, w przeciwieństwie do odpowiadającej mu teorii w logice pierwszego rzędu, który jest niekompletny). Podpisem będzie zazwyczaj sygnatura 0, S , +, X arytmetyki, wraz z relacją przynależności ∈ między liczbami całkowitymi i podzbiorami (choć istnieje wiele pomniejszych odchyleń). Aksjomaty są aksjomatami arytmetyki Robinsona , razem z aksjomatami schematów indukcji i rozumienia .

Istnieje wiele różnych podteorii arytmetyki drugiego rzędu, różniących się tym, które formuły są dozwolone w schematach wprowadzania i rozumienia. W kolejności rosnącej siły jest pięć najpopularniejszych systemów

  • , Zrozumienie rekurencyjne
  • , Słaby lemat Königa
  • , Rozumienie arytmetyczne
  • , Arytmetyczna rekursja pozaskończona
  • , zrozumienie

Zostały one szczegółowo określone w artykułach dotyczących arytmetyki drugiego rzędu i matematyki odwrotnej .

Teorie zbiorów

Zwykła sygnatura teorii mnogości ma jedną relację binarną ∈, nie ma stałych ani funkcji. Niektóre z poniższych teorii to „teorie klas”, które mają dwa rodzaje obiektów, zbiorów i klas. Istnieją trzy typowe sposoby radzenia sobie z tym w logice pierwszego rzędu:

  1. Użyj logiki pierwszego rzędu z dwoma typami.
  2. Użyj zwykłej logiki pierwszego rzędu, ale dodaj nowy jednoargumentowy predykat „Zbiór”, gdzie „Zestaw ( t )” oznacza nieformalnie „ t jest zbiorem”.
  3. Użyj zwykłej logiki pierwszego rzędu i zamiast dodawać nowy predykat do języka, traktuj „Set ( t )” jako skrót od „∃ y t ∈ y ”

Niektóre teorie zbiorów pierwszego rzędu obejmują:

Niektóre dodatkowe aksjomaty pierwszego rzędu, które można dodać do jednego z nich (zwykle ZF), obejmują:

Zobacz też

Bibliografia

Dalsza lektura