Teoria modeli - Model theory

W logice matematycznej , teorii modelu jest badanie relacji między formalnych teorii (zbiór zdań w języku formalnym wyrażającego oświadczenia o strukturze matematycznej ), a ich modele, traktowane jako interpretacje , które spełniają zdania tej teorii. Badane aspekty obejmują liczbę i rozmiar modeli teorii, wzajemne relacje różnych modeli oraz ich interakcję z samym językiem formalnym. W szczególności teoretycy modeli badają również zbiory, które można zdefiniować w modelu teorii, oraz relacje takich definiowalnych zbiorów względem siebie. Jako odrębnej dyscypliny, teoria modelu sięga Alfred Tarski , który jako pierwszy użył terminu „Theory of Models” w publikacji w roku 1954. Od 1970 roku, podmiot został ukształtowany zdecydowanie za Saharon Shelah „s teorii stabilności . Względny nacisk kładziony na klasę modeli teorii w przeciwieństwie do klasy zbiorów definiowalnych w ramach modelu podlegał fluktuacjom w historii przedmiotu, a oba kierunki podsumowują zwięzłe charakterystyki odpowiednio z lat 1973 i 1997:

teoria modeli = algebra uniwersalna + logika

gdzie algebra uniwersalna oznacza struktury matematyczne, a logikę teorie logiczne; oraz

teoria modeli = geometria algebraiczna − pola .

gdzie formuły logiczne są dla zbiorów definiowalnych, czym równania dla rozmaitości nad ciałem.

Niemniej jednak wzajemne oddziaływanie klas modeli i definiowalnych w nich zbiorów było kluczowe dla rozwoju teorii modeli w całej jej historii. Na przykład, podczas gdy stabilność została pierwotnie wprowadzona, aby klasyfikować teorie według liczby modeli w danej kardynalności, teoria stabilności okazała się kluczowa dla zrozumienia geometrii zbiorów definiowalnych.

W porównaniu z innymi dziedzinami logiki matematycznej, takimi jak teoria dowodu, teoria modeli jest często mniej związana z rygorem formalnym i bliższa w duchu matematyki klasycznej. To skłoniło do komentarza, że „jeśli teoria dowodu dotyczy sacrum, to teoria modelowa dotyczy profanum” . Zastosowania teorii modeli do geometrii algebraicznej i diofantycznej odzwierciedlają tę bliskość matematyki klasycznej, ponieważ często wiążą się z integracją wyników i technik algebraicznych i teorii modeli.

Najbardziej znaną organizacją naukową w dziedzinie teorii modeli jest Association for Symbolic Logic .

Gałęzie

Ta strona skupia się na finitary pierwszego rzędu modelu teorii nieskończonych struktur. Teoria modeli skończonych , która koncentruje się na strukturach skończonych, znacznie odbiega od badania struktur nieskończonych, zarówno w badanych problemach, jak i stosowanych technikach. Teoria modeli w logikach wyższego rzędu lub logice nieskończoności jest utrudniona przez fakt, że kompletność i zwartość na ogół nie mają zastosowania do tych logik. Jednak przeprowadzono również wiele badań dotyczących takiej logiki.

Nieformalnie teorię modeli można podzielić na klasyczną teorię modeli, teorię modeli stosowaną do grup i pól oraz teorię modeli geometrycznych. Brakujący podpodział to teoria modeli obliczeniowych , ale można go prawdopodobnie postrzegać jako niezależną poddziedzinę logiki.

Przykłady pierwszych twierdzeń z klasyczną teorią modelu to kompletności twierdzenie Gödla , w górę i w dół Löwenheim-Skolem twierdzenia , Vaught jest dwu-kard twierdzenie, Scott jest Izomorfizm twierdzenie, że pominięto rodzaje twierdzenie , a twierdzenie Ryll-Nardzewski . Przykłady pierwszych wyników teorii modelu zastosowano do pola są Tarski jest wyeliminowanie kwantyfikatorów w rzeczywistych zamkniętych obszarach , Ax jest twierdzenie pola pseudo skończone i Robinson rozwoju „s niestandardowym analizy . Ważny krok w ewolucji klasycznej teorii modeli nastąpił wraz z narodzinami teorii stabilności (poprzez twierdzenie Morleya o nieskończenie kategorycznych teoriach i program klasyfikacji Shelaha ), która rozwinęła rachunek niezależności i rang oparty na warunkach syntaktycznych spełnianych przez teorie.

W ciągu ostatnich kilkudziesięciu lat stosowana teoria modeli wielokrotnie łączyła się z bardziej czystą teorią stabilności. Wynikiem tej syntezy jest w tym artykule nazwana teoria modeli geometrycznych (która obejmuje na przykład o-minimalność, a także klasyczną teorię stabilności geometrycznej). Przykładem dowodu z teorii modeli geometrycznych jest dowód Hrushovski'ego na hipotezę Mordella-Langa dla pól funkcyjnych. Ambicją teorii modeli geometrycznych jest zapewnienie geografii matematyki poprzez szczegółowe badanie definiowalnych zbiorów w różnych strukturach matematycznych, z pomocą istotnych narzędzi opracowanych w badaniach nad czystą teorią modeli.

Podstawowe pojęcia teorii modeli pierwszego rzędu

Logika pierwszego rzędu

Formuła pierwszego rzędu jest zbudowana z formuł atomowych, takich jak R ( f ( x , y ), z ) lub y = x + 1 za pomocą spójników boolowskich i przedrostków kwantyfikatorów lub . Zdanie to formuła, w której każde wystąpienie zmiennej mieści się w zakresie odpowiedniego kwantyfikatora. Przykładami formuł są φ (lub φ(x), aby zaznaczyć fakt, że co najwyżej x jest zmienną niezwiązaną w φ) oraz ψ zdefiniowane w następujący sposób: ${\displaystyle \neg,\ziemia,\lor,\rightarrow }$${\displaystyle \forall v}$${\displaystyle \istnieje v}$

${\displaystyle {\varphi \;=\;\forall u\forall v(\istnieje w(x\razy w=u\razy v)\rightarrow (\istnieje w(x\razy w=u)\lub \istnieje w(x\times w=v)))\land x\neq 0\land x\neq 1,}}$

${\ Displaystyle \ psi \; = \; \ dla wszystkich u \ dla wszystkich v ((u \ razy v = x) \ rightarrow (u = x) \ lub (v = x)) \ ziemi x \ neq 0 \ ziemi x \ n. 1.}$

(Zauważ, że symbol równości ma tutaj podwójne znaczenie.) Jest intuicyjnie jasne, jak przetłumaczyć takie formuły na znaczenie matematyczne. Na _{przykład w} strukturze σ _smr liczb naturalnych element n spełnia formułę φ wtedy i tylko wtedy, gdy n jest liczbą pierwszą. Wzór ψ podobnie definiuje nieredukowalność. Tarski podał ścisłą definicję, czasami nazywaną „definicją prawdy Tarskiego” , dla relacji zadowolenia , aby łatwo udowodnić: ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \modele}$

${\ Displaystyle {\ mathcal {N}} \ modele \ varphi (n) \ jeśli n}$ jest liczbą pierwszą.

${\ Displaystyle {\ mathcal {N}} \ modele \ psi (n) \ jeśli n}$ jest nieredukowalny.

Zbiór T zdań nazywa się teorią (pierwszego rzędu) . Teoria jest spełnialna, jeśli posiada model , tj. strukturę (o odpowiedniej sygnaturze), która spełnia wszystkie zdania zbioru T . Kompletna teoria to teoria zawierająca każde zdanie lub jego negację. Kompletna teoria wszystkich zdań spełnianych przez strukturę nazywana jest również teorią tej struktury . ${\displaystyle {\mathcal {M}}\modele T}$

Twierdzenie o zupełności Gödla (nie mylić z jego twierdzeniami o niezupełności ) mówi, że teoria ma model wtedy i tylko wtedy, gdy jest niesprzeczny , tj. żadna sprzeczność nie jest udowodniona przez teorię. Dlatego teoretycy modeli często używają słowa „spójny” jako synonimu „spełniającego”.

Podstawowe koncepcje teorii modeli

Sygnatura lub język jest zestaw symboli nie logicznych takich, że każdy symbol jest albo symbol funkcji lub symbol zależność i ma określoną liczbę operandów . Struktura jest zbiorem wraz z interpretacjami każdy z symboli podpisu jako relacji i funkcji na (nie mylić z interpretacją jednej struktury w innym). Wspólną sygnaturą dla uporządkowanych pierścieni jest , gdzie i są symbolami funkcji 0-argumentowymi (znanymi również jako symbole stałe) i są symbolami funkcji binarnych, jest symbolem funkcji jednoargumentowej i jest symbolem relacji binarnej. Następnie, gdy te symbole są interpretowane tak, aby odpowiadały ich zwykłemu znaczeniu on (tak, że np. jest funkcją od do i jest podzbiorem ), otrzymuje się strukturę . Mówi się, że struktura modeluje zbiór zdań pierwszego rzędu w danym języku, jeśli każde zdanie w jest prawdziwe w odniesieniu do interpretacji podpisu określonego wcześniej dla . ${\ Displaystyle M}$${\ Displaystyle M}$${\ Displaystyle \ sigma _ {lub} = \ {0,1, +, \ razy, -, <\}}$${\ Displaystyle 0}$${\ Displaystyle 1}$${\displaystyle +}$${\displaystyle \times}$${\displaystyle -}$${\styl wyświetlania <}$${\ Displaystyle \ mathbb {Q}}$${\displaystyle +}$${\ Displaystyle \ mathbb {Q} ^ {2}}$${\ Displaystyle \ mathbb {Q}}$${\styl wyświetlania <}$${\ Displaystyle \ mathbb {Q} ^ {2}}$${\ Displaystyle (\ mathbb {Q} , \ sigma _ {lub})}$${\displaystyle {\mathcal {N}}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

Podłoże z Ď strukturze jest podzbiorem jego domeny zamknięte we wszystkich funkcji w Ď podpisu, który jest uważany za Ď strukturze ograniczając wszystkie funkcje i zależności Ď do podzbioru. To uogólnia analogiczne pojęcia z algebry; Na przykład podgrupa to podstruktura w sygnaturze z mnożeniem i odwrotnością. ${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle {\ Mathcal {B}}}$

Podbudowie mówi się, że podstawowy jeśli z jakiegoś rzędu pierwszego wzorze cp a także wszystkie elementy ₁ , ..., _n o , ${\ Displaystyle {\ Mathcal {A}}}$

${\ Displaystyle {\ mathcal {A}} \ modele \ varphi (a_ {1}, ..., a_ {n})}$wtedy i tylko wtedy, gdy .${\ Displaystyle {\ mathcal {B}} \ modele \ varphi (a_ {1}, ..., a_ {n})}$

W szczególności, jeśli φ jest zdaniem i elementarną podstrukturą , to wtedy i tylko wtedy, gdy . Zatem elementarna podkonstrukcja jest modelem teorii dokładnie wtedy, gdy modelem jest nadbudowa. Zatem, podczas gdy ciało liczb algebraicznych jest elementarną podstrukturą ciała liczb zespolonych , ciało wymierne nie jest, ponieważ możemy wyrazić „Istnieje pierwiastek kwadratowy z 2” jako zdanie pierwszego rzędu spełnione przez , ale nie przez . ${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle {\ Mathcal {B}}}$${\ Displaystyle {\ mathcal {A}} \ modele \ varphi}$${\ Displaystyle {\ mathcal {B}} \ modele \ varphi}$${\displaystyle {\overline {\mathbb {Q}}}}$${\ Displaystyle \ mathbb {C}}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {C}}$${\ Displaystyle \ mathbb {Q}}$

Osadzanie z Ď strukturze do innego Ď strukturze jest mapą F : → B między domenami, które mogą być zapisywane jako izomorfizm z substruktury . Jeśli można go zapisać jako izomorfizm z elementarną podstrukturą, nazywa się to osadzaniem elementarnym. Każde osadzanie jest homomorfizmem iniekcyjnym , ale odwrotność obowiązuje tylko wtedy, gdy podpis nie zawiera symboli relacji, takich jak grupy lub pola. ${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle {\ Mathcal {B}}}$${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle {\ Mathcal {B}}}$

Pole lub przestrzeń wektorową można uznać za (przemienną) grupę, po prostu ignorując część jej struktury. Odpowiednim pojęciem w teorii modeli jest redukcja struktury do podzbioru oryginalnej sygnatury. Relacja przeciwstawna nazywana jest rozwinięciem - np. grupę (dodatkową) liczb wymiernych , traktowaną w sygnaturze jako strukturę {+,0} można rozwinąć do pola o sygnaturze {×,+,1,0} lub do uporządkowanej grupy z podpisem {+,0,<}.

Podobnie, jeśli σ' jest sygnaturą, która rozszerza inną sygnaturę σ, to kompletną teorię σ' można ograniczyć do σ, przecinając zbiór jej zdań ze zbiorem formuł σ. I odwrotnie, kompletną teorię σ można uznać za teorię σ' i można ją rozszerzyć (na więcej niż jeden sposób) do pełnej teorii σ'. Terminy redukcja i ekspansja są czasami stosowane również do tej relacji.

Zwartość i twierdzenie Löwenheima-Skolema

W twierdzenie o zwartości stwierdza, że zbiór zdań S spełnialna jeśli każdy skończony podzbiór S jest spe. Analogiczne stwierdzenie ze spójnym zamiast spełnialnym jest trywialne, ponieważ każdy dowód może mieć tylko skończoną liczbę poprzedników użytych w dowodzie. Twierdzenie o zupełności pozwala nam przenieść to na spełnialność. Istnieje jednak również kilka bezpośrednich (semantycznych) dowodów twierdzenia o zwartości. Jako wniosek (tj. jego przeciwieństwo) twierdzenie o zwartości mówi, że każda niesatysfakcjonowana teoria pierwszego rzędu ma skończony podzbiór niesatysfakcjonowany. Twierdzenie to ma kluczowe znaczenie w teorii modeli, gdzie słowa „przez zwartość” są powszechne.

Kolejnym kamieniem węgielnym teorii modeli pierwszego rzędu jest twierdzenie Löwenheima-Skolema. Zgodnie z twierdzeniem Löwenheima-Skolema każda nieskończona struktura w policzalnej sygnaturze ma policzalną elementarną podstrukturę. I odwrotnie, dla każdego nieskończonego kardynała κ każda nieskończona struktura w policzalnej sygnaturze, która ma liczność mniejszą niż κ, może być elementarnie osadzona w innej strukturze liczności κ (istnieje proste uogólnienie na niepoliczalne sygnatury). W szczególności twierdzenie Löwenheima-Skolema implikuje, że każda teoria w sygnaturze przeliczalnej z modelami nieskończonymi ma zarówno model przeliczalny, jak i dowolnie duże modele.

W pewnym sensie sprecyzowanym przez twierdzenie Lindströma , logika pierwszego rzędu jest najbardziej ekspresyjną logiką, dla której obowiązuje zarówno twierdzenie Löwenheima-Skolema, jak i twierdzenie o zwartości.

Definiowalność

Definiowalne zestawy

W teorii modeli ważnymi przedmiotami badań są zbiory definiowalne . Na przykład w formule ${\ Displaystyle \ mathbb {N}}$

${\ Displaystyle \ forall u \ forall v (\ istnieje w (x \ razy w = u \ razy v) \ rightarrow ( \ istnieje w (x \ razy w = u) \ lub \ istnieje w (x \ razy w = v )))\teren x\neq 0\teren x\neq 1}$

definiuje podzbiór liczb pierwszych, natomiast formuła

${\ Displaystyle \ istnieje y (2 \ razy y = x)}$

definiuje podzbiór liczb parzystych. W podobny sposób formuły z n wolnymi zmiennymi definiują podzbiory . Na przykład w polu formuła ${\ Displaystyle {\ Mathcal {M}} ^ {n}}$

${\displaystyle y=x\razy x}$

definiuje krzywą wszystkich takich, które . ${\displaystyle (x,y)}$${\ Displaystyle y = x ^ {2}}$

Obie wymienione tutaj definicje są bezparametrowe , co oznacza, że ​​formuły definiujące nie wspominają o żadnych stałych elementach domeny. Można jednak wziąć pod uwagę również definicje z parametrami z modelu . Na przykład w , formuła ${\ Displaystyle \ mathbb {R}}$

${\displaystyle y=x\razy x+\pi}$

używa parametru od do zdefiniowania krzywej. ${\displaystyle \pi}$${\ Displaystyle \ mathbb {R}}$

Eliminowanie kwantyfikatorów

Ogólnie, zbiory definiowalne bez kwantyfikatorów są łatwe do opisania, podczas gdy zbiory definiowalne zawierające potencjalnie zagnieżdżone kwantyfikatory mogą być znacznie bardziej skomplikowane.

To sprawia, że eliminacja kwantyfikatora jest kluczowym narzędziem do analizy zbiorów definiowalnych: Teoria T ma eliminację kwantyfikatora, jeśli każda formuła pierwszego rzędu φ( x ₁ , ..., x _n ) nad jej sygnaturą jest równoważna modulo T dla formuły pierwszego rzędu ψ ( x ₁ , ..., x _n ) bez kwantyfikatorów, tzn. obowiązuje we wszystkich modelach T . Jeśli teoria struktury ma eliminację kwantyfikatora, każdy zbiór definiowalny w strukturze można zdefiniować za pomocą formuły bez kwantyfikatora na tych samych parametrach, co pierwotna definicja. Na przykład teoria ciał algebraicznie domkniętych w sygnaturze _pierścienia σ = (×,+,−,0,1) ma eliminację kwantyfikatora. Oznacza to, że w algebraicznie domkniętym ciele każda formuła jest równoważna logicznej kombinacji równań między wielomianami. ${\ Displaystyle \ forall x_ {1} \ kropki \ forall x_ {n} (\ phi (x_ {1}, \ kropki, x_ {n}) \ leftrightarrow \ psi (x_ {1}, \ kropki, x_ {n }))}$

Jeśli teoria nie ma eliminacji kwantyfikatora, można dodać dodatkowe symbole do jej sygnatury, aby tak się stało. Wczesna teoria modeli poświęciła wiele wysiłku na udowodnienie wyników aksjomatyzowalności i eliminacji kwantyfikatora dla określonych teorii, zwłaszcza w algebrze. Ale często zamiast eliminacji kwantyfikatora wystarczy słabsza właściwość:

Teorię T nazywamy modelem zupełnym, jeśli każda podstruktura modelu T, który sam jest modelem T, jest podkonstrukcją elementarną. Istnieje przydatne kryterium badania, czy podbudowa jest podkonstrukcją elementarną, zwane testem Tarskiego-Vaughta . Z tego kryterium wynika, że ​​teoria T jest modelowo zupełna wtedy i tylko wtedy, gdy każda formuła pierwszego rzędu φ( x ₁ , ..., x _n ) nad jej sygnaturą jest równoważna modulo T egzystencjalnej formule pierwszego rzędu, tj. formuła o następującej postaci:

${\ Displaystyle \ istnieje v_ {1} \ kropki \ istnieje v_ {m} \ psi (x_ {1}, \ kropki, x_ {n}, v_ {1}, \ kropki, v_ {m})}$,

gdzie ψ jest wolne od kwantyfikatora. Teoria, która nie zawiera kompletnego modelu, może, ale nie musi, mieć uzupełnienie modelu , które jest pokrewną teorią pełnego modelu , która na ogół nie jest rozszerzeniem oryginalnej teorii. Bardziej ogólnym pojęciem jest model towarzysza .

Minimalność

W każdej strukturze każdy skończony podzbiór można zdefiniować za pomocą parametrów: po prostu użyj wzoru ${\ Displaystyle \ {a_ {1}, \ kropki, a_ {n} \}}$

${\ Displaystyle x = a_ {1} \ vee \ kropki \ vee a_ {n}}$.

Ponieważ możemy zanegować ten wzór, każdy cofinite podzbiór (który zawiera wszystkie, ale skończenie wiele elementów domeny) jest również zawsze definiowalny.

Prowadzi to do koncepcji minimalnej struktury . Strukturę nazywamy minimalną, jeśli każdy podzbiór definiowalny za pomocą parametrów z jest albo skończony, albo koskończony. Odpowiednie pojęcie na poziomie teorii nazywamy silną minimalnością : teorię T nazywamy silnie minimalną, jeśli każdy model T jest minimalny. Strukturę nazywamy silnie minimalną, jeśli teoria tej struktury jest silnie minimalna. Równoważnie struktura jest silnie minimalna, jeśli każde elementarne rozszerzenie jest minimalne. Ponieważ teoria ciał algebraicznie domkniętych ma eliminację kwantyfikatora, każdy definiowalny podzbiór ciała algebraicznie domkniętego można zdefiniować za pomocą wzoru bez kwantyfikatora w jednej zmiennej. Wzory bez kwantyfikatorów w jednej zmiennej wyrażają kombinacje logiczne równań wielomianowych w jednej zmiennej, a ponieważ nietrywialne równanie wielomianowe w jednej zmiennej ma tylko skończoną liczbę rozwiązań, teoria ciał algebraicznie domkniętych jest mocno minimalna. ${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle A\subseteq {\mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$

Z drugiej strony pole liczb rzeczywistych nie jest minimalne: Rozważmy na przykład zbiór definiowalny ${\ Displaystyle \ mathbb {R}}$

${\ Displaystyle \ varphi (x) \; = \; \ istnieje r (y \ razy y = x)}$.

Definiuje podzbiór nieujemnych liczb rzeczywistych, który nie jest ani skończony, ani koskończony. W rzeczywistości można użyć do zdefiniowania dowolnych przedziałów na osi liczb rzeczywistych. Okazuje się, że te wystarczą do reprezentowania każdego definiowalnego podzbioru . To uogólnienie minimalizmu było bardzo przydatne w teorii modelowej struktur uporządkowanych. Gęsto uporządkowany struktura w podpis tym symbol stosunku rzędu nazywa O-minimalny , jeśli każdy podzbiór definiowanych z parametrów z skończony związek punktów i odstępach czasu. ${\displaystyle \varphi}$${\ Displaystyle \ mathbb {R}}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle A\subseteq {\mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$

Definiowalne i interpretowalne struktury

Szczególnie ważne są te definiowalne zbiory, które są jednocześnie podstrukturami, tzn. zawierają wszystkie stałe i są zamykane w aplikacji funkcji. Na przykład można badać możliwe do zdefiniowania podgrupy pewnej grupy. Nie ma jednak potrzeby ograniczania się do podstruktur w tej samej sygnaturze. Ponieważ formuły z n wolnymi zmiennymi definiują podzbiory , można również definiować n -arne relacje. Funkcje są definiowalne, jeśli wykres funkcji jest definiowalną relacją, a stałe są definiowalne, jeśli istnieje formuła taka, że a jest jedynym elementem takiej, która jest prawdziwa. W ten sposób można np. badać definiowalne grupy i pola w strukturach ogólnych, co jest ważne w teorii stabilności geometrycznej. ${\ Displaystyle {\ Mathcal {M}} ^ {n}}$${\displaystyle a\in {\mathcal {M}}}$${\ Displaystyle \ varphi (x)}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle \ varphi (a)}$

Można nawet pójść o krok dalej i wyjść poza bezpośrednie podstruktury. Biorąc pod uwagę strukturę matematyczną, bardzo często istnieją struktury powiązane, które można skonstruować jako iloraz części oryginalnej struktury poprzez relację równoważności. Ważnym przykładem jest grupa ilorazowa grupy. Można powiedzieć, że aby zrozumieć całą strukturę, trzeba zrozumieć te ilorazy. Kiedy relacja równoważności jest możliwa do zdefiniowania, możemy nadać poprzedniemu zdaniu dokładne znaczenie. Mówimy, że te struktury są interpretowalne . Kluczowym faktem jest to, że można przetłumaczyć zdania z języka interpretowanych struktur na język oryginalnej struktury. W ten sposób można pokazać, że jeśli struktura interpretuje inną, której teoria jest nierozstrzygalna, to sama jest nierozstrzygalna. ${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$

Rodzaje

Podstawowe pojęcia

Dla sekwencji elementów o strukturze oraz podzbioru A o , można rozważyć zbiór wszystkich wzorach pierwszego rzędu z parametrów A , która jest objęta . Nazywa się to typem kompletnym (n-) realizowanym przez over A . Jeśli jest automorfizmem stanowi , że jest stała na A i wysyła do odpowiednio, wtedy i realizować ten sam typ kompletny nad A . ${\displaystyle a_{1},\kropki,a_{n}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle \ varphi (x_ {1}, \ kropki, x_ {n})}$${\displaystyle a_{1},\kropki,a_{n}}$ ${\displaystyle a_{1},\kropki,a_{n}}$ ${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle a_{1},\kropki,a_{n}}$${\displaystyle b_{1},\kropki,b_{n}}$${\displaystyle a_{1},\kropki,a_{n}}$${\displaystyle b_{1},\kropki,b_{n}}$

Linia liczb rzeczywistych , postrzegana jako struktura z tylko relacją kolejności {<}, posłuży jako bieżący przykład w tej sekcji. Każdy element spełnia ten sam typ 1 w pustym zestawie. Jest to jasne, ponieważ dowolne dwie liczby rzeczywiste a i b są połączone automorfizmem rzędów, który przesuwa wszystkie liczby o ba . Kompletny typ 2 nad pustym zestawem realizowanym przez parę liczb zależy od ich kolejności: albo , albo . W podzbiorze liczb całkowitych typ 1 niecałkowitej liczby rzeczywistej a zależy od jej wartości zaokrąglonej w dół do najbliższej liczby całkowitej. ${\ Displaystyle \ mathbb {R}}$${\ Displaystyle a \ w \ mathbb {R} }$${\displaystyle a_{1},a_{2}}$${\displaystyle a_{1}<a_{2}}$${\displaystyle a_{1}=a_{2}}$${\displaystyle a_{2}<a_{1}}$${\ Displaystyle \ mathbb {Z} \ podseteq \ mathbb {R}}$

Mówiąc bardziej ogólnie, gdy jest struktura i podzbiorem , (częściowe) typu n nad A jest zestaw wzorach P o co najwyżej n wolnych zmiennych, które są realizowane w podstawowej przedłużenia o . Jeśli p zawiera każdą taką formułę lub jej negację, to p jest zupełne . Zbiór kompletnych n- typów nad A jest często zapisywany jako . Jeśli jest zbiorem pustym, to przestrzeń rodzaj zależy tylko na teorii T o . Notacja jest powszechnie używana dla zbioru typów nad zbiorem pustym zgodnym z T . Jeśli istnieje pojedyncza formuła taka, że ​​teoria implikuje dla każdej formuły w p , wtedy p nazywamy izolowanym . ${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle {\mathcal {N}}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle S_ {n} ^ {\ matematyka {M}} (A)}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle S_ {n} (T)}$${\displaystyle \varphi}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle \varphi \rightarrow \psi}$${\ Displaystyle \ psi}$

Ponieważ liczby rzeczywiste są Archimedesa , nie ma liczby rzeczywistej większej niż każda liczba całkowita. Jednak argument zwartości pokazuje, że istnieje elementarne rozszerzenie osi liczb rzeczywistych, w którym znajduje się element większy niż dowolna liczba całkowita. W związku z tym zestaw formuł jest typu 1, który nie jest realizowany w linii liczb rzeczywistych . ${\ Displaystyle \ mathbb {R}}$${\ Displaystyle \ {n < x | n \ w \ mathbb {Z} \}}$${\ Displaystyle \ mathbb {Z} \ podseteq \ mathbb {R}}$${\ Displaystyle \ mathbb {R}}$

Podzbiór tego, który może być wyrażony jako dokładnie te elementy realizacji pewnego typu przez A, jest nazywany definiowalnym typem przez A . Dla przykładu algebraicznego załóżmy, że jest ciałem algebraicznie domkniętym . Teoria ma eliminację kwantyfikatora. To pozwala nam pokazać, że typ jest dokładnie określony przez zawarte w nim równania wielomianowe. W ten sposób zestaw kompletnych -types ponad podpole odpowiada zestaw ideał pierwszy w pierścień wielomianów i zestawów typu definiowane są dokładnie afiniczne odmiany. ${\ Displaystyle {\ Mathcal {M}} ^ {n}}$${\ Displaystyle {\ Mathcal {M}} ^ {n}}$${\ Displaystyle M}$${\ Displaystyle n}$${\ Displaystyle A}$ ${\displaystyle A[x_{1},\ldots,x_{n}]}$

Struktury i typy

Chociaż nie każdy typ jest realizowany w każdej strukturze, każda struktura realizuje swoje izolowane typy. Jeśli jedynymi typami nad pustym zbiorem, które są realizowane w strukturze, są typy izolowane, wówczas struktura nazywa się atomic .

Z drugiej strony żadna struktura nie realizuje każdego typu w każdym zestawie parametrów; jeśli przyjmiemy wszystkie jako zestaw parametrów, to każdy typ 1 nad zrealizowany w jest izolowany przez formułę postaci a = x dla . Jednak każde właściwe rozszerzenie elementarne zawiera element, który nie znajduje się w . Dlatego wprowadzono słabsze pojęcie, które ujmuje ideę struktury realizującej wszystkie typy, jakich można się spodziewać. Strukturę nazywamy nasyconą, jeśli realizuje każdy typ w zestawie parametrów, który ma mniejszą kardynalność niż ona sama. ${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle a\in {\mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle A \ podzbiór {\ matematyka {M}}}$${\ Displaystyle {\ Mathcal {M}}}$

Choć automorfizmem że jest stała na A zawsze zachować rodzajów ponad A , to generalnie nie jest prawdą, że dowolne dwie sekwencje i które spełniają ten sam typ nad A może być odwzorowany na siebie taką automorfizmem. Struktura, w której ta odwrotność dotyczy wszystkich A o mniejszej kardynalności niż nazywana jest jednorodną . ${\displaystyle a_{1},\kropki,a_{n}}$${\displaystyle b_{1},\kropki,b_{n}}$${\ Displaystyle {\ Mathcal {M}}}$${\ Displaystyle {\ Mathcal {M}}}$

Linia liczb rzeczywistych jest atomowa w języku, który zawiera tylko porządek , ponieważ wszystkie n- typy w zbiorze pustym realizowane przez in są izolowane przez relacje porządku między . Nie jest jednak nasycony, ponieważ nie realizuje żadnego typu 1 w zbiorze policzalnym, który implikuje, że x jest większe niż jakakolwiek liczba całkowita. W przeciwieństwie do tego, wymierna oś liczbowa jest nasycona, ponieważ sama jest policzalna i dlatego musi realizować typy w skończonych podzbiorach, aby zostać nasycona. ${\styl wyświetlania <}$${\displaystyle a_{1},\kropki,a_{n}}$${\ Displaystyle \ mathbb {R}}$${\displaystyle a_{1},\kropki,a_{n}}$${\ Displaystyle \ mathbb {Z}}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {Q}}$

Kamienne przestrzenie

Zbiór definiowalnych podzbiorów kilku parametrów jest algebrą Boole'a . Według twierdzenia Stone'a o reprezentacji dla algebr Boole'a istnieje naturalna dualna przestrzeń topologiczna , która składa się dokładnie z kompletnych typów ponad . Topologia generowana przez zestawy postaci dla pojedynczych formuł . Nazywa się to przestrzenią Stone n-typów nad A . Ta topologia wyjaśnia niektóre terminy stosowane w teorii modeli: Twierdzenie o zwartości mówi, że przestrzeń kamienia jest zwartą przestrzenią topologiczną, a typ p jest izolowany wtedy i tylko wtedy, gdy p jest izolowanym punktem w topologii Stone. ${\ Displaystyle {\ Mathcal {M}} ^ {n}}$${\ Displaystyle A}$${\ Displaystyle n}$${\ Displaystyle A}$${\ Displaystyle \ {p | \ varphi \ w p \}}$${\displaystyle \varphi}$

Podczas gdy typy w polach algebraicznie domkniętych odpowiadają widmu pierścienia wielomianowego, topologia w przestrzeni typów jest topologią konstruktywną : zbiór typów jest podstawowy otwarty, jeśli ma formę lub formę . To jest lepsze niż topologia Zariskiego . ${\ Displaystyle \ {p: f (x) = 0 \ w p \}}$${\ Displaystyle \ {p: f (x) \ neq 0 \ w p \}}$

Kategoria

Teoria była pierwotnie nazywana kategoryczną, jeśli określa strukturę aż do izomorfizmu. Okazuje się, że ta definicja nie jest przydatna ze względu na poważne ograniczenia w wyrazistości logiki pierwszego rzędu. Twierdzenie Löwenheima-Skolema implikuje, że jeśli teoria T ma nieskończony model dla pewnej nieskończonej liczby kardynalnej , to ma model o rozmiarze κ dla dowolnej wystarczająco dużej liczby kardynalnej κ. Ponieważ dwa modele o różnych rozmiarach nie mogą być izomorficzne, tylko skończone struktury można opisać za pomocą teorii kategorycznej.

Jednak słabsze pojęcie κ-kategorii dla kardynalnego κ stało się kluczowym pojęciem w teorii modeli. Teorię T nazywamy κ-kategoryczną, jeśli dowolne dwa modele T o kardynalności κ są izomorficzne. Okazuje się, że kwestia κ-kategorii zależy krytycznie od tego, czy κ jest większe od liczności języka (czyli  + |σ|, gdzie |σ| jest licznością podpisu). W przypadku sygnatur skończonych lub przeliczalnych oznacza to, że istnieje zasadnicza różnica między -licznością a κ-licznością dla niepoliczalnych κ. ${\displaystyle \aleph_{0}}$${\ Displaystyle \ omega}$

${\ Displaystyle \ omega}$-kategoria

${\ Displaystyle \ omega}$-teorie kategoryczne można scharakteryzować właściwościami ich przestrzeni typów:

Dla pełnej teorii pierwszego rzędu T w sygnaturze skończonej lub przeliczalnej następujące warunki są równoważne:

1. T jest kategoryczny.${\ Displaystyle \ omega}$
2. Każdy typ w S _n ( T ) jest izolowany.
3. Dla każdej liczby naturalnej n , S _n ( T ) jest skończone.
4. Dla każdej liczby naturalnej n liczba formuł φ( x ₁ , ..., x _n ) w n wolnych zmiennych, aż do równoważności modulo T , jest skończona.

Teoria , która jest również teorią , jest kategoryczna, ponieważ każdy n- typ nad zbiorem pustym jest izolowany przez relację kolejności par między . Oznacza to, że każdy policzalny gęsty rząd liniowy jest rzędem izomorficzny z wymierną linią liczbową. Z drugiej strony, teorie , i jako pola nie są -categorical. Wynika to z faktu, że we wszystkich tych polach każdą z nieskończenie wielu liczb naturalnych można określić wzorem postaci . ${\ Displaystyle (\ mathbb {Q} , <)}$${\ Displaystyle (\ mathbb {R} , <)}$${\ Displaystyle \ omega}$${\displaystyle p(x_{1},\kropki,x_{n})}$${\displaystyle x_{i}}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {R}}$${\ Displaystyle \ mathbb {C}}$${\ Displaystyle \ omega}$${\displaystyle x=1+\kropki +1}$

${\displaystyle \aleph_{0}}$teorie kategoryczne i ich modele policzalne mają również silne powiązania z grupami oligomorficznymi :

Kompletna teoria pierwszego rzędu T w skończonej lub przeliczalnej sygnaturze jest kategoryczna wtedy i tylko wtedy, gdy jej grupa automorfizmu jest oligomorficzna.${\ Displaystyle \ omega}$

Równoważne schkateryzacje tego podrozdziału, niezależnie od Engelera , Rylla-Nardzewskiego i Svenoniusa , są czasami określane jako twierdzenie Rylla-Nardzewskiego.

W sygnaturach kombinatorycznych powszechnym źródłem teorii kategorycznych są granice Fraïssé , które uzyskuje się jako granicę łączenia wszystkich możliwych konfiguracji klasy skończonych struktur relacyjnych. ${\ Displaystyle \ omega}$

Niepoliczalna kategoria

Michael Morley wykazał w 1963 roku, że istnieje tylko jedno pojęcie niepoliczalnej kategoryczności teorii w policzalnych językach.

Twierdzenie Morleya o kategoryczności

Jeśli teoria pierwszego rzędu T w skończonej lub przeliczalnej sygnaturze jest κ-kategoryczna dla jakiejś niepoliczalnej liczby kardynalnej κ, to T jest κ-kategoryczna dla wszystkich niepoliczalnych kardynałów κ.

Dowód Morleya ujawnił głębokie powiązania między niepoliczalną kategoryzacją a wewnętrzną strukturą modeli, które stały się punktem wyjścia teorii klasyfikacji i teorii stabilności. Nieskończenie kategoryczne teorie są z wielu punktów widzenia teoriami najbardziej grzecznymi. W szczególności, nieskończenie kategoryczne są kompletne teorie zdecydowanie minimalne. Pokazuje to, że teoria ciał algebraicznie domkniętych o danej charakterystyce jest niepoliczalnie kategoryczna, a stopień transcendencji ciała określa jego typ izomorfizmu.

Teorię, która jest zarówno -kategoryczna, jak i niepoliczalnie kategoryczna, nazywa się całkowicie kategoryczną . ${\ Displaystyle \ omega}$

Wybrane aplikacje

Wśród wczesnych sukcesów teorii modeli są dowody Tarskiego rozstrzygalności różnych algebraicznie interesujących klas, takich jak ciała domknięte rzeczywiste , algebry Boole'a i ciała algebraicznie domknięte o danej charakterystyce .

W 1960 roku, Rozważania wokół nasycony modele i ultraprodukt prowadzenie budowy do Abraham Robinson rozwoju „z dnia niestandardowym analizy .

W 1965 roku James Ax i Simon B. Kochen pokazali specjalny przypadek hipotezy Artina na temat równań diofantycznych, twierdzenie Axa-Kochena , ponownie używając konstrukcji ultraproduktu.

Ostatnio związek między stabilnością a geometrią zbiorów definiowalnych doprowadził do kilku zastosowań geometrii algebraicznej i diofantycznej, w tym do dowodu Ehuda Hrushovski'ego z 1996 r. na temat geometrycznej hipotezy Mordella-Langa we wszystkich charakterystykach.

W 2011 roku Jonathan Pila zastosował techniki związane z minimalizacją o, aby udowodnić hipotezę André-Oorta dla produktów o krzywych modułowych.

W osobnym wątku dociekań, który również narastał wokół teorii stabilnych, Laskowski wykazał w 1992 roku, że teorie NIP opisują dokładnie te definiowalne klasy, których można się nauczyć w teorii uczenia maszynowego przez PAC .

Historia

Teoria modeli jako przedmiot istnieje od około połowy XX wieku. Jednak niektóre wcześniejsze badania, zwłaszcza w logice matematycznej , są często uważane z perspektywy czasu za teoretyczno-modelowe. Pierwszy znaczący wynik w jakiej jest teraz modelem teorii był szczególny przypadek twierdzenia spadkowej Löwenheim-Skolem, opublikowane przez Leopold Löwenheim w 1915. Twierdzenie zwartość była niejawna w pracy przez Thoralf Skolem , ale została po raz pierwszy opublikowana w 1930 roku jako lemat w dowodzie twierdzenia Kurta Gödla o zupełności . Twierdzenie Löwenheima-Skolema i twierdzenie o zwartości otrzymały swoje odpowiednie formy ogólne w 1936 i 1941 roku od Anatolija Maltseva . Rozwój teorii modeli jako samodzielnej dyscypliny zapoczątkował Alfred Tarski , członek szkoły lwowsko-warszawskiej w okresie międzywojennym . Prace Tarskiego obejmowały między innymi konsekwencję logiczną , systemy dedukcyjne , algebrę logiki, teorię definiowalności i semantyczną definicję prawdy . Kulminacją jego metod semantycznych była teoria modeli, którą on i wielu jego studentów z Berkeley rozwinęli w latach pięćdziesiątych i sześćdziesiątych.

W dalszej historii dyscypliny zaczęły pojawiać się różne wątki, a punkt ciężkości przedmiotu uległ zmianie. W latach 60. techniki dotyczące ultraproduktów stały się popularnym narzędziem w teorii modeli. W tym samym czasie badacze tacy jak James Ax badali teorię modeli pierwszego rzędu różnych klas algebraicznych, a inni, tacy jak H. Jerome Keisler , rozszerzali koncepcje i wyniki teorii modeli pierwszego rzędu na inne systemy logiczne. Następnie praca Saharona Shelaha nad kategorycznością i problemem Morleya zmieniła złożoność teorii modeli, dając początek zupełnie nowej klasie pojęć. Teoria stabilności (teoria klasyfikacja) Szela rozwijany od końca 1960 ma na celu sklasyfikowanie teorii przez wielu różnych modeli mają z danym liczności. W ciągu następnych dziesięcioleci stało się jasne, że wynikająca z tego hierarchia stabilności jest ściśle powiązana z geometrią zbiorów, które można zdefiniować w tych modelach; dało to początek subdyscyplinie znanej obecnie jako teoria stabilności geometrycznej.

Połączenia z powiązanymi gałęziami logiki matematycznej

Teoria modeli skończonych

Teoria modeli skończonych (FMT) to podobszar teorii modeli (MT), który zajmuje się jej ograniczeniem do interpretacji struktur skończonych, które mają skończony wszechświat.

Ponieważ wiele centralnych twierdzeń teorii modeli nie obowiązuje, gdy ogranicza się je do struktur skończonych, metoda FMT różni się od MT pod względem metod dowodowych. Centralne wyniki klasycznej teorii modeli, które nie dla struktur skończonych pod FMT zawierać twierdzenia kompaktowość , kompletności twierdzenie Gödla i metody ultraproducts dla logiki pierwszego rzędu .

Główne obszary zastosowania FMT są opisowej teorii złożoności , teorii baz danych i teorii języków formalnych .

Teoria mnogości

Każda teoria mnogości (wyrażona w języku policzalnym ), jeśli jest niesprzeczna, ma model policzalny; jest to znane jako paradoks Skolema , ponieważ w teorii mnogości istnieją zdania, które postulują istnienie zbiorów niepoliczalnych, a mimo to zdania te są prawdziwe w naszym modelu przeliczalnym. W szczególności dowód na niezależność hipotezy continuum wymaga uwzględnienia zbiorów w modelach, które wydają się niepoliczalne patrząc z wnętrza modelu, ale są policzalne dla kogoś spoza modelu.

Punkt widzenia teorii modeli był przydatny w teorii mnogości ; na przykład w Kurt Gödel „s prace nad uniwersum konstruowalne, które wraz z metodą zmuszając opracowany przez Paula Cohena można wykazać, udowodnić (znowu filozoficznie interesujący) niezależność z aksjomatu wyboru i hipotezy continuum od pozostałych aksjomatów teorii mnogości.

W przeciwnym kierunku sama teoria modeli może zostać sformalizowana w ramach teorii mnogości ZFC. Na przykład, formalizacja satysfakcji w ZFC odbywa się indukcyjnie, w oparciu o schemat T Tarskiego i obserwację, gdzie leżą elementy zakresu przyporządkowań zmiennych. Rozwój podstaw teorii modeli (takich jak twierdzenie o zwartości) opiera się na aksjomacie wyboru, a dokładniej na twierdzeniu Boole'a o ideałach pierwotnych. Inne wyniki w teorii modeli zależą od aksjomatów teorii mnogości wykraczających poza standardowe ramy ZFC. Na przykład, jeśli Hipoteza Continuum jest słuszna, to każdy policzalny model ma ultramoc, która jest nasycona (w swojej własnej kardynalności). Podobnie, jeśli hipoteza uogólnionego kontinuum jest słuszna, to każdy model ma nasycone elementarne rozszerzenie. Żaden z tych wyników nie jest możliwy do udowodnienia w samym ZFC. Wreszcie, niektóre pytania wynikające z teorii modeli (takie jak zwartość dla logiki nieskończoności) okazały się równoważne z dużymi aksjomatami kardynalnymi.

Zobacz też

Uwagi

Bibliografia

Podręczniki kanoniczne

• Chang, Chen Chung ; Keisler, H. Jerome (1990) [1973]. Teoria modeli . Studia w logice i podstawach matematyki (3rd ed.). Elsevier. Numer ISBN 978-0-444-88054-3.
• Hodges, Wilfrid (1997). Krótsza teoria modeli . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-58713-6.
• Kopperman, R. (1972). Teoria modeli i jej zastosowania . Boston: Allyn i Bacon .
• Marker, David (2002). Teoria modeli: wprowadzenie . Teksty magisterskie z matematyki 217. Springer. Numer ISBN 0-387-98760-6.

Inne podręczniki

• Bell, John L.; Slomson, Alan B. (2006) [1969]. Modele i Ultraprodukty: Wprowadzenie (przedruk z 1974 ed.). Publikacje Dover . Numer ISBN 0-486-44979-3.
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Logika matematyczna . Springer . Numer ISBN 0-387-94258-0.
• Hinman, Peter G. (2005). Podstawy logiki matematycznej . AK Petersa . Numer ISBN 1-56881-262-0.
• Hodges, Wilfrid (1993). Teoria modeli . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-30442-3.
• Manzano, Maria (1999). Teoria modeli . Wydawnictwo Uniwersytetu Oksfordzkiego . Numer ISBN 0-19-853851-0.
• Poizat, Bruno (2000). Kurs teorii modeli . Skoczek. Numer ISBN 0-387-98655-3.
• Rautenberg, Wolfgang (2010). Zwięzłe wprowadzenie do logiki matematycznej (3rd ed.). Nowy Jork : Springer Science+Business Media . doi : 10.1007/978-1-4419-1221-3 . Numer ISBN 978-1-4419-1220-6.
• Rothmaler, Filip (2000). Wprowadzenie do teorii modeli (nowe wyd.). Taylor i Franciszek . Numer ISBN 90-5699-313-5.
• Namiot Katrin ; Ziegler, Marcin (2012). Kurs teorii modeli . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 9780521763240.
• Kirby, Jonathan (2019). Zaproszenie do teorii modeli . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-1-107-16388-1.

Darmowe teksty online

• Chatzidakis, Zoé (2001). Wprowadzenie do teorii modeli (PDF) . str. 26 stron.
• Pillay, Anand (2002). Notatki do wykładu – teoria modeli (PDF) . str. 61 stron.
• „Teoria modeli” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Hodges, Wilfrid , Teoria modeli . The Stanford Encyclopedia of Philosophy, E. Zalta (red.).
• Hodges, Wilfrid , teoria modeli pierwszego rzędu . The Stanford Encyclopedia of Philosophy, E. Zalta (red.).
• Simmons, Harold (2004), Wprowadzenie do dobrej, staromodnej teorii modeli . Notatki z kursu wprowadzającego dla doktorantów (z ćwiczeniami).
• J. Barwise i S. Feferman (redaktorzy), Model-Theoretic Logics , Perspectives in Mathematical Logic, tom 8, New York: Springer-Verlag, 1985.