Modelová teorie - Model theory

V matematické logice je modelová teorie studiem vztahu mezi formálními teoriemi (sbírka vět ve formálním jazyce vyjadřující tvrzení o matematické struktuře ) a jejich modely, které jsou brány jako interpretace, které uspokojují věty této teorie. Zkoumané aspekty zahrnují počet a velikost modelů teorie, vzájemný vztah různých modelů a jejich interakci se samotným formálním jazykem. Zejména teoretici modelu také zkoumají množiny, které lze definovat v modelu teorie, a vzájemný vztah těchto definovatelných množin. Jako samostatná disciplína, teorie modelů sahá až Alfred Tarski , který jako první použil termín „teorie modelů“ v publikaci v roce 1954. Od roku 1970, jejichž předmětem byla rozhodujícím způsobem utvářeny Saharon Sále ‚s teorie stability . Relativní důraz kladený na třídu modelů teorie na rozdíl od třídy definovatelných množin v rámci modelu kolísal v historii předmětu a tyto dva směry jsou shrnuty charakteristikami pithy z let 1973 a 1997:

teorie modelu = univerzální algebra + logika

kde univerzální algebra znamená matematické struktury a logika logické teorie; a

teorie modelu = algebraická geometrie - pole .

kde logické vzorce mají definovatelné množiny, jaké jsou rovnice pro odrůdy v poli.

Nicméně souhra tříd modelů a množin v nich definovatelných byla klíčová pro rozvoj teorie modelů v celé její historii. Například, zatímco stabilita byla původně zavedena ke klasifikaci teorií podle jejich počtu modelů v dané mohutnosti, teorie stability se ukázala klíčová pro pochopení geometrie definovatelných množin.

Ve srovnání s jinými oblastmi matematické logiky, jako je teorie důkazů, se teorie modelu často méně zabývá formální přísností a v duchu se blíží klasické matematice. To vyvolalo komentář, že „pokud je teorie důkazů o posvátných, pak teorie modelů je o profanech“ . Aplikace teorie modelu na algebraickou a diofantickou geometrii odrážejí tuto blízkost klasické matematiky, protože často zahrnují integraci algebraických a model-teoretických výsledků a technik.

Nejvýznamnější vědeckou organizací v oblasti teorie modelů je Asociace pro symbolickou logiku .

Pobočky

Tato stránka se zaměřuje na konečnou teorii modelu prvního řádu nekonečných struktur. Teorie konečných modelů , která se soustředí na konečné struktury, se výrazně liší od studia nekonečných struktur jak ve studovaných problémech, tak v použitých technikách. Teorii modelu v logice vyššího řádu nebo v infinitární logice brání skutečnost, že úplnost a kompaktnost obecně pro tyto logiky neplatí. V takové logice však bylo také provedeno velké množství studií.

Neformálně lze modelovou teorii rozdělit na klasickou teorii modelu, teorii modelu aplikovanou na skupiny a pole a teorii geometrického modelu. Chybějící dělení je teorie vypočítatelného modelu , ale toto lze pravděpodobně považovat za nezávislé logické pole.

Příklady prvních vět z klasické teorie modelu zahrnují Gödel úplnosti teorém , nahoru a dolů Löwenheim-Skolem věty , Vaught 's dvěma kardinální teorém, Scott to izomorfismus věta se vynechá typy věta , a Ryll-Nardzewski věta . Příklady prvních výsledků teorie modelů aplikován na pole jsou Tarski je eliminace kvantifikátorů za reálných uzavřených oblastech , Ax věta o pseudo-konečných polích , a Robinson je vývoj nestandardní analýzy . Důležitý krok v evoluci teorie klasického modelu nastal se zrodem teorie stability (prostřednictvím Morleyovy věty o nesporně kategorických teoriích a Shelahově klasifikačním programu), která vyvinula kalkul nezávislosti a hodnosti na základě syntaktických podmínek splněných teoriemi.

Během posledních několika desetiletí se teorie aplikovaného modelu opakovaně spojila s čistší teorií stability. Výsledek této syntézy se v tomto článku nazývá teorie geometrického modelu (která zahrnuje například o-minimalitu, stejně jako klasickou teorii geometrické stability). Příkladem důkazu z teorie geometrického modelu je Hrushovského důkaz o Mordellově – Langově domněnce pro funkční pole. Ambicí teorie geometrického modelu je poskytnout geografii matematiky tím, že se pustíme do podrobného studia definovatelných množin v různých matematických strukturách, za pomoci podstatných nástrojů vyvinutých při studiu teorie čistého modelu.

Základní pojmy teorie modelu prvního řádu

Logika prvního řádu

Vzorec prvního řádu je sestaven z atomových vzorců, jako je R ( f ( x , y ), z ) nebo y = x + 1, pomocí booleovských spojek a předpony kvantifikátorů nebo . Věta je vzorec, ve kterém je každý výskyt proměnné v rozsahu odpovídajícího kvantifikátoru. Příklady vzorců jsou φ (nebo φ (x) pro označení skutečnosti, že nanejvýš x je nevázaná proměnná v φ) a ψ definované následovně: ${\ Displaystyle \ neg, \ land, \ lor, \ rightarrow}$${\ displaystyle \ forall v}$${\ displaystyle \ existuje v}$

${\ Displaystyle {\ varphi \; = \; \ forall u \ forall v (\ existuje w (x \ times w = u \ times v) \ rightarrow (\ existuje w (x \ times w = u) \ lor \ existuje w (x \ times w = v))) \ land x \ neq 0 \ land x \ neq 1,}}$

${\ Displaystyle \ psi \; = \; \ forall u \ forall v ((u \ times v = x) \ rightarrow (u = x) \ lor (v = x)) \ land x \ neq 0 \ land x \ ne 1.}$

(Všimněte si, že symbol rovnosti zde má dvojí význam.) Je intuitivně jasné, jak převést takové vzorce do matematického významu. V σ _SMR -structure z přirozených čísel, například prvek n splňuje vzorec cp tehdy, když n je prvočíslo. Vzorec ψ podobně definuje neredukovatelnost. Tarski poskytl přísnou definici, někdy nazývanou „Tarskiho definice pravdy“ , pro vztah spokojenosti , takže člověk snadno dokáže: ${\ displaystyle {\ mathcal {N}}}$ ${\ displaystyle \ models}$

${\ Displaystyle {\ mathcal {N}} \ models \ varphi (n) \ iff n}$ je prvočíslo.

${\ Displaystyle {\ mathcal {N}} \ models \ psi (n) \ iff n}$ je neredukovatelný.

Soubor T vět se nazývá teorie (prvního řádu) . Teorie je splnitelná v případě, že má vzor , který splňuje všechny věty v sadě, tj strukturu (příslušného podpisu) T . Kompletní teorie je teorie, která obsahuje každou větu nebo její negaci. Kompletní teorie všech vět splněných strukturou se také nazývá teorie této struktury . ${\ displaystyle {\ mathcal {M}} \ models T}$

Gödelova věta o úplnosti (nezaměňovat s jeho větami o neúplnosti ) říká, že teorie má model tehdy a jen tehdy, je -li konzistentní , tj. Teorie neprokazuje žádný rozpor. Teoretici modelu proto často používají „konzistentní“ jako synonymum pro „uspokojivý“.

Základní model-teoretické koncepty

Podpis nebo jazyk je soubor non-logických symbolů tak, že každý symbol je buď symbol funkce nebo symbol vztah a má určený aritu . Struktura je sada společně s interpretací každý ze symbolů podpisu jako vztahů a funkcí na (neplést s interpretací jedné struktury v jiném). Běžným podpisem pro uspořádané prsteny je , kde a jsou 0-funkční funkční symboly (také známé jako konstantní symboly) a jsou symboly binárních funkcí, je symbolem unární funkce a je symbolem binární relace. Když jsou pak tyto symboly interpretovány tak, aby odpovídaly jejich obvyklému významu na (takže např. Je funkcí od do a je podmnožinou ), získá se struktura . Struktura údajně modeluje sadu vět prvního řádu v daném jazyce, pokud každá věta v je pravdivá s ohledem na interpretaci dříve specifikovaného podpisu . ${\ displaystyle M}$${\ displaystyle M}$${\ Displaystyle \ sigma _ {or} = \ {0,1,+, \ times,-, <\}}$${\ displaystyle 0}$${\ displaystyle 1}$${\ displaystyle +}$${\ displaystyle \ times}$${\ displaystyle -}$${\ displaystyle <}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle +}$${\ displaystyle \ mathbb {Q} ^{2}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle <}$${\ displaystyle \ mathbb {Q} ^{2}}$${\ displaystyle (\ mathbb {Q}, \ sigma _ {or})}$${\ displaystyle {\ mathcal {N}}}$${\ displaystyle T}$${\ displaystyle T}$${\ displaystyle {\ mathcal {N}}}$${\ displaystyle {\ mathcal {N}}}$

Spodní konstrukce z å strukturou je podmnožinou svém oboru, uzavřené v rámci všech funkcí v jeho podpis å, který je považován jako å-strukturu tím, že omezí všechny funkce a vztahy v å se podskupiny. To zobecňuje analogické pojmy z algebry; Podskupina je například substruktura v podpisu s násobením a inverzí. ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$

O substruktuře se říká, že je elementární, pokud pro jakýkoli vzorec prvního řádu φ a jakékoli prvky a ₁ , ..., a _n z , ${\ displaystyle {\ mathcal {A}}}$

${\ displaystyle {\ mathcal {A}} \ models \ varphi (a_ {1}, ..., a_ {n})}$kdyby a jen kdyby .${\ displaystyle {\ mathcal {B}} \ models \ varphi (a_ {1}, ..., a_ {n})}$

Zejména je -li φ věta a elementární substruktura , pak právě tehdy . Elementární spodní struktura je tedy modelem teorie přesně tehdy, když je nadstavba modelem. Proto zatímco pole algebraických čísel je elementární substrukturou pole komplexních čísel , racionální pole není, protože můžeme vyjádřit „Druhá odmocnina 2“ jako věta prvního řádu splněná, ale ne . ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$${\ displaystyle {\ mathcal {A}} \ models \ varphi}$${\ displaystyle {\ mathcal {B}} \ models \ varphi}$${\ displaystyle {\ overline {\ mathbb {Q}}}}$${\ displaystyle \ mathbb {C}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle \ mathbb {C}}$${\ displaystyle \ mathbb {Q}}$

Vkládání z å-struktury do další å strukturou je mapa f : → B mezi doménami, které je možno zapsat jako izomorfismu s spodní stavby . Pokud jej lze zapsat jako izomorfismus s elementární substrukturou, říká se mu elementární vkládání. Každé vložení je injektivní homomorfismus, ale opak platí pouze v případě, že podpis neobsahuje žádné vztahové symboly, například ve skupinách nebo polích. ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$

Pole nebo vektorový prostor lze považovat za (komutativní) skupinu pouhým ignorováním některé jeho struktury. Odpovídající pojem v modelové teorii je redukce struktury na podmnožinu původního podpisu. Opačný vztah se nazývá expanze - např. (Aditivní) skupinu racionálních čísel , považovanou za strukturu v podpisu {+, 0}, lze rozšířit na pole s podpisem {×,+, 1,0} nebo do seřazené skupiny s podpisem {+, 0, <}.

Podobně, pokud σ 'je podpis, který rozšiřuje další podpis σ, pak úplnou teorii σ'lze omezit na σ průsečíkem množiny jejích vět se sadou σ vzorců. Naopak úplnou σ-teorii lze považovat za σ'-teorii a lze ji rozšířit (více než jedním způsobem) na úplnou σ'-teorii. Termíny redukce a expanze se někdy vztahují i ​​na tento vztah.

Kompaktnost a Löwenheim-Skolemova věta

Tyto kompaktnost věta uvádí, že soubor vět S je splnitelná, pokud každý konečný podmnožina S je splnitelná. Analogický výrok s konzistentním namísto uspokojivého je triviální, protože každý důkaz může mít v důkazu použit pouze konečný počet předchůdců. Věta o úplnosti nám umožňuje přenést to na splnitelnost. Existuje však také několik přímých (sémantických) důkazů věty o kompaktnosti. Jako důsledek (tj. Jeho kontrapozitivní) věta o kompaktnosti říká, že každá neuspokojivá teorie prvního řádu má konečnou neuspokojitelnou podmnožinu. Tato věta má zásadní význam v modelové teorii, kde jsou slova „kompaktností“ běžná.

Dalším základním kamenem teorie modelu prvního řádu je Löwenheim-Skolemova věta. Podle Löwenheim-Skolemovy věty má každá nekonečná struktura v počitatelném podpisu spočitatelnou elementární substrukturu. A naopak, pro jakýkoli nekonečný kardinál κ může být každá nekonečná struktura v počitatelném podpisu, který má mohutnost menší než κ, elementárně vložena do jiné struktury mohutnosti κ (Existuje nesporné zobecnění nesčetných podpisů). Zejména Löwenheim-Skolemova věta naznačuje, že jakákoli teorie v počitatelném podpisu s nekonečnými modely má počitatelný model i libovolně velké modely.

V určitém smyslu upřesněném Lindströmovou větou je logika prvního řádu nejvýraznější logikou, pro kterou platí jak Löwenheim – Skolemova věta, tak věta kompaktnosti.

Definovatelnost

Definovatelné sady

V teorii modelu jsou definovatelné množiny důležitými předměty studia. Například ve vzorci ${\ displaystyle \ mathbb {N}}$

${\ Displaystyle \ forall u \ forall v (\ existuje w (x \ times w = u \ times v) \ rightarrow (\ existuje w (x \ times w = u) \ lor \ existuje w (x \ times w = v ))) \ pozemek x \ neq 0 \ pozemek x \ neq 1}$

definuje podmnožinu prvočísel, zatímco vzorec

${\ Displaystyle \ existuje y (2 \ times y = x)}$

definuje podmnožinu sudých čísel. Podobným způsobem definují vzorce s n volnými proměnnými podmnožiny . Například v poli vzorec ${\ displaystyle {\ mathcal {M}}^{n}}$

${\ Displaystyle y = x \ times x}$

definuje křivku všeho takového . ${\ displaystyle (x, y)}$${\ displaystyle y = x^{2}}$

Obě zde uvedené definice jsou bez parametrů , to znamená, že definující vzorce nezmiňují žádné prvky pevné domény. Lze však také zvážit definice s parametry z modelu . Například ve vzorci ${\ displaystyle \ mathbb {R}}$

${\ Displaystyle y = x \ times x+\ pi}$

používá parametr od definovat křivku. ${\ displaystyle \ pi}$${\ displaystyle \ mathbb {R}}$

Odstranění kvantifikátorů

Obecně lze definovatelné sady bez kvantifikátorů snadno popsat, zatímco definovatelné sady zahrnující případně vnořené kvantifikátory mohou být mnohem komplikovanější.

Díky tomu je eliminace kvantifikátoru klíčovým nástrojem pro analýzu definovatelných množin: Teorie T má eliminaci kvantifikátoru, pokud každý vzorec prvního řádu φ ( x ₁ , ..., x _n ) přes jeho podpis je ekvivalentní modulo T vzorci prvního řádu ψ ( x ₁ , ..., x _n ) bez quantifiers, tedy drží na všech modelů T . Pokud má teorie struktury eliminaci kvantifikátoru, každá množina definovatelná ve struktuře je definovatelná pomocí vzorce bez kvantifikátoru se stejnými parametry jako původní definice. Například teorie algebraicky uzavřených polí v podpisovém σ _prstenu = (×,+, -, 0,1) má eliminaci kvantifikátoru. To znamená, že v algebraicky uzavřeném poli je každý vzorec ekvivalentní booleovské kombinaci rovnic mezi polynomy. ${\ Displaystyle \ forall x_ {1} \ dots \ forall x_ {n} (\ phi (x_ {1}, \ dots, x_ {n}) \ leftrightarrow \ psi (x_ {1}, \ dots, x_ {n }))}$

Pokud teorie nemá eliminaci kvantifikátoru, lze k jejímu podpisu přidat další symboly, takže ano. Teorie raného modelu vynaložila velké úsilí na prokázání výsledků axiomatizovatelnosti a eliminace kvantifikátorů pro konkrétní teorie, zejména v algebře. Ale často místo eliminace kvantifikátoru stačí slabší vlastnost:

Teorie T se nazývá kompletní model, pokud každá substruktura modelu T, který je sám modelem T, je elementární substrukturou. Existuje užitečné kritérium pro testování, zda je spodní struktura elementární spodní strukturou, která se nazývá Tarski -Vaughtův test . Z tohoto kritéria vyplývá, že teorie T je úplná model právě tehdy, když každý vzorec prvního řádu φ ( x ₁ , ..., x _n ) přes jeho podpis je ekvivalentní modulo T k existenciálnímu vzorci prvního řádu, tj. vzorec následující formy:

${\ Displaystyle \ existuje v_ {1} \ tečky \ existuje v_ {m} \ psi (x_ {1}, \ tečky, x_ {n}, v_ {1}, \ tečky, v_ {m})}$,

kde ψ je bez kvantifikátoru. Teorie, která není úplná, může nebo nemusí mít dokončení modelu , což je příbuzná teorie úplného modelu , která obecně není rozšířením původní teorie. Obecnějším pojmem je modelový společník .

Minimalita

V každé struktuře je každá konečná podmnožina definovatelná pomocí parametrů: Jednoduše použijte vzorec ${\ displaystyle \ {a_ {1}, \ dots, a_ {n} \}}$

${\ Displaystyle x = a_ {1} \ vee \ tečky \ vee a_ {n}}$.

Protože tento vzorec můžeme negovat, je také vždy definovatelná každá cofinitová podmnožina (která zahrnuje všechny, ale nakonec mnoho prvků domény).

To vede ke konceptu minimální struktury . Struktura se nazývá minimální, pokud je každá podmnožina definovatelná pomocí parametrů konečná nebo kofinitová. Odpovídající koncept na úrovni teorií se nazývá silná minimalita : Teorie T se nazývá silně minimální, pokud je každý model T minimální. Struktura se nazývá silně minimální, pokud je teorie této struktury silně minimální. Ekvivalentně je struktura silně minimální, pokud je každé elementární rozšíření minimální. Protože teorie algebraicky uzavřených polí má eliminaci kvantifikátoru, je každá definovatelná podmnožina algebraicky uzavřeného pole definovatelná pomocí vzorce bez kvantifikátoru v jedné proměnné. Vzorce bez kvantifikátoru v jedné proměnné vyjadřují booleovské kombinace polynomiálních rovnic v jedné proměnné, a protože netriviální polynomická rovnice v jedné proměnné má pouze konečný počet řešení, je teorie algebraicky uzavřených polí silně minimální. ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle A \ subseteq {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$

Na druhé straně pole reálných čísel není minimální: Zvažte například definovatelnou množinu ${\ displaystyle \ mathbb {R}}$

${\ Displaystyle \ varphi (x) \; = \; \ existuje y (y \ times y = x)}$.

To definuje podmnožinu nezáporných reálných čísel, která není ani konečná, ani kofinitová. Ve skutečnosti lze použít k definování libovolných intervalů na řádku reálných čísel. Ukazuje se, že tyto postačí k reprezentaci každé definovatelné podmnožiny . Toto zobecnění minimality bylo velmi užitečné v modelové teorii uspořádaných struktur. Hustě totálně spořádaná struktura v podpisu, včetně symbolu vztahu pořadí se nazývá o-minimal -li každá podmnožina definovat parametry výrobku je konečná svaz bodů a intervalů. ${\ Displaystyle \ varphi}$${\ displaystyle \ mathbb {R}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle A \ subseteq {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$

Definovatelné a interpretovatelné struktury

Obzvláště důležité jsou ty definovatelné sady, které jsou také podstrukturami, tj. Obsahují všechny konstanty a jsou uzavřeny v rámci aplikace funkcí. Například lze studovat definovatelné podskupiny určité skupiny. Není však nutné omezovat se na substruktury ve stejném podpisu. Protože vzorce s n volnými proměnnými definují podmnožiny , lze definovat i n -ary relace. Funkce jsou definovatelné, pokud je funkční graf definovatelným vztahem, a konstanty jsou definovatelné, pokud existuje vzorec takový, že a je jediným takovým prvkem , který je pravdivý. Tímto způsobem lze například studovat definovatelné skupiny a pole v obecných strukturách, což bylo důležité v teorii geometrické stability. ${\ displaystyle {\ mathcal {M}}^{n}}$${\ displaystyle a \ in {\ mathcal {M}}}$${\ displaystyle \ varphi (x)}$${\ displaystyle {\ mathcal {M}}}$${\ Displaystyle \ varphi (a)}$

Lze dokonce jít ještě o krok dále a přesunout se za bezprostřední spodní stavby. Vzhledem k matematické struktuře existují velmi často přidružené struktury, které lze konstruovat jako podíl části původní struktury prostřednictvím vztahu ekvivalence. Důležitým příkladem je kvocient skupiny. Dalo by se říci, že k pochopení plné struktury je třeba porozumět těmto kvocientům. Když je vztah ekvivalence definovatelný, můžeme předchozí větě dát přesný význam. Říkáme, že tyto struktury jsou interpretovatelné . Klíčovým faktem je, že je možné překládat věty z jazyka interpretovaných struktur do jazyka původní struktury. Lze tedy ukázat, že pokud struktura interpretuje jinou, jejíž teorie je nerozhodnutelná, pak sama je nerozhodnutelná. ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$

Typy

Základní pojmy

Pro sekvence prvků konstrukce a podskupinu A o , lze uvažovat množinu všech prvního řádu vzorců s parametry A , které jsou uspokojeny . To se nazývá kompletní (N) Druh realizovaný přes . Pokud existuje automorphism ze které je konstantní na A a odešle se v tomto pořadí, pak a dosažení stejného kompletní typ přes A . ${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ Displaystyle \ varphi (x_ {1}, \ dots, x_ {n})}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$ ${\ displaystyle a_ {1}, \ tečky, a_ {n}}$ ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ Displaystyle b_ {1}, \ tečky, b_ {n}}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ Displaystyle b_ {1}, \ tečky, b_ {n}}$

V této sekci bude jako běžný příklad sloužit řádek se skutečným číslem , nahlížený jako na strukturu, která má pouze vztah pořadí {<}. Každý prvek přes prázdnou množinu splňuje stejný typ 1. To je jasné, protože jakákoli dvě reálná čísla a a b jsou spojena automatickým uspořádáním řádu, které posouvá všechna čísla o ba . Kompletní 2-typ přes prázdnou množinu realizovaný dvojicí čísel závisí na jejich pořadí: buď , nebo . Přes podmnožinu celých čísel závisí typ 1 neceločíselného reálného čísla a na jeho hodnotě zaokrouhlené dolů na nejbližší celé číslo. ${\ displaystyle \ mathbb {R}}$${\ displaystyle a \ in \ 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} \ subseteq \ mathbb {R}}$

Obecně, když je struktura a podmnožina , a (částečné) n-typu než A je sada vzorců p s u většiny n volných proměnných, které jsou realizovány v elementární prodloužení z . Pokud p obsahuje každý takový vzorec nebo jeho negaci, pak je p úplné . Sada úplných n typů přes A se často zapisuje jako . Pokud je prázdná množina, pak typ prostoru závisí pouze na teorii T části . Zápis se běžně používá pro sadu typů nad prázdné množiny v souladu s T . Pokud existuje jediný vzorec takový, že teorie implikace pro každý vzorec v p , pak p se nazývá izolovaný . ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {N}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle S_ {n}^{\ mathcal {M}} (A)}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle S_ {n} (T)}$${\ Displaystyle \ varphi}$${\ displaystyle {\ mathcal {M}}}$${\ Displaystyle \ varphi \ rightarrow \ psi}$${\ Displaystyle \ psi}$

Protože skutečná čísla jsou Archimedean , neexistuje skutečné číslo větší než každé celé číslo. Argument kompaktnosti však ukazuje, že existuje elementární rozšíření řádku reálných čísel, ve kterém je prvek větší než jakékoli celé číslo. Proto je sada vzorců 1 typu, který není realizován v řádku reálných čísel . ${\ displaystyle \ mathbb {R}}$${\ Displaystyle \ {n <x | n \ in \ mathbb {Z} \}}$${\ Displaystyle \ mathbb {Z} \ subseteq \ mathbb {R}}$${\ displaystyle \ mathbb {R}}$

Podskupina , který může být vyjádřen jako přesně ty prvky realizaci určitého typu nad A se nazývá typ nastavitelné přes A . Pro algebraický příklad předpokládejme, že je algebraicky uzavřené pole . Teorie má eliminaci kvantifikátoru. To nám umožňuje ukázat, že typ je přesně určen polynomiálními rovnicemi, které obsahuje. Proto je množina celých -types než subfield odpovídá sadu primárních ideálů na polynomu kruhu a typ definovatelné sady jsou přesně afinní odrůdy. ${\ displaystyle {\ mathcal {M}}^{n}}$${\ displaystyle {\ mathcal {M}}^{n}}$${\ displaystyle M}$${\ displaystyle n}$${\ displaystyle A}$ ${\ Displaystyle A [x_ {1}, \ ldots, x_ {n}]}$

Struktury a typy

I když ne každý typ je realizován v každé struktuře, každá struktura si uvědomuje své izolované typy. Pokud jsou jedinými typy přes prázdnou množinu, které jsou realizovány ve struktuře, izolované typy, pak se tato struktura nazývá atomová .

Na druhou stranu žádná struktura nerealizuje každý typ v každé sadě parametrů; pokud jeden bere vše jako sadu parametrů, pak každý 1 typ přes realizovaný v je izolován vzorcem ve tvaru a = x pro an . Jakékoli správné elementární rozšíření obsahuje prvek, který není in . Proto byl zaveden slabší pojem, který zachycuje myšlenku struktury realizující všechny typy, od kterých by se dalo očekávat, že je realizuje. Struktura se nazývá nasycená, pokud realizuje každý typ v sadě parametrů, která je menší mohutnosti než sama. ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle a \ in {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle A \ subset {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$

Zatímco automorphism která je konstantní v A se vždy zachovat typy přes A , není obecně platí, že jakékoliv dvě sekvence a které splňují stejný typ přes A, mohou být mapovány na sebe takovým automorfismus. Struktura, ve které tato konverzace platí, platí pro všechna A menší mohutnosti, než se nazývá homogenní . ${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ Displaystyle b_ {1}, \ tečky, b_ {n}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$

Řádek skutečného čísla je atomický v jazyce, který obsahuje pouze pořadí , protože všechny n -typy přes prázdnou množinu realizované pomocí in jsou izolovány vztahy pořadí mezi . Není však nasycený, protože si neuvědomuje žádný typ 1 přes spočítatelnou množinu, což znamená, že x je větší než jakékoli celé číslo. Racionální číselná řada je oproti tomu nasycená, protože je sama spočítatelná, a proto musí být nasycena pouze typy přes konečné podmnožiny. ${\ displaystyle <}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ displaystyle \ mathbb {R}}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ displaystyle \ mathbb {Z}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle \ mathbb {Q}}$

Kamenné mezery

Množina definovatelných podmnožin přes některé parametry je booleovská algebra . Podle Stoneovy reprezentační věty pro booleovské algebry existuje přirozený duální topologický prostor , který se skládá přesně z úplných typů . Topologie generovaná sadami formuláře pro jednotlivé vzorce . To se nazývá kámen prostor n typů nad . Tato topologie vysvětluje některé terminologie používané v modelové teorii: Věta o kompaktnosti říká, že Kamenný prostor je kompaktní topologický prostor a typ p je izolován právě tehdy, když p je izolovaným bodem v kamenné topologii. ${\ displaystyle {\ mathcal {M}}^{n}}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle A}$${\ Displaystyle \ {p | \ varphi \ in p \}}$${\ Displaystyle \ varphi}$

Zatímco typy v algebraicky uzavřených polích odpovídají spektru polynomiálního kruhu, topologie na typovém prostoru je konstruovatelná topologie : množina typů je základní otevřená, pokud je ve formě nebo ve formě . To je jemnější než topologie Zariski . ${\ Displaystyle \ {p: f (x) = 0 \ in p \}}$${\ Displaystyle \ {p: f (x) \ neq 0 \ in p \}}$

Kategoričnost

Teorie se původně nazývala kategorická, pokud určuje strukturu až do izomorfismu. Ukazuje se, že tato definice není užitečná, kvůli vážným omezením v expresivitě logiky prvního řádu. Věta Löwenheim – Skolem naznačuje, že pokud má teorie T nekonečný model pro nějaké nekonečné základní číslo , pak má model velikosti κ pro jakékoli dostatečně velké základní číslo κ. Protože dva modely různých velikostí nemohou být isomorfní, lze kategorickou teorií popsat pouze konečné struktury.

Slabší pojem κ-kategoricity pro kardinální κ se však stal klíčovým konceptem v modelové teorii. Teorie T se nazývá κ-kategorická, pokud jsou jakékoli dva modely T, které mají mohutnost κ, izomorfní. Ukazuje se, že otázka κ-kategoričnosti závisí kriticky na tom, zda κ je větší než mohutnost jazyka (tj.  + | Σ |, kde | σ | je mohutnost podpisu). Pro konečné nebo spočitatelné podpisy to znamená, že existuje zásadní rozdíl mezi -kardinalitou a κ -kardinalitou pro nepočitatelné κ. ${\ displaystyle \ aleph _ {0}}$${\ displaystyle \ omega}$

${\ displaystyle \ omega}$-kategorie

${\ displaystyle \ omega}$-kategorické teorie lze charakterizovat vlastnostmi jejich typového prostoru:

Pro úplnou teorii prvního řádu T v konečném nebo spočitatelném podpisu jsou následující podmínky ekvivalentní:

1. T je -kategorické.${\ displaystyle \ omega}$
2. Každý typ v S _n ( T ) je izolován.
3. Pro každé přirozené číslo n je S _n ( T ) konečné.
4. Pro každé přirozené číslo n je počet vzorců φ ( x ₁ , ..., x _n ) v n volných proměnných až do ekvivalenčního modulu T konečný.

Teorie , která je také teorií , je -kategorická, protože každý n -typ přes prázdnou množinu je izolován vztahem párových řádů mezi . To znamená, že každý spočitatelný hustý lineární řád je izomorfní k řadě racionálních čísel. Na druhé straně teorie , a jako pole nejsou -categorical. To vyplývá ze skutečnosti, že ve všech těchto polích může být libovolné nekonečně mnoho přirozených čísel definováno vzorcem formuláře . ${\ displaystyle (\ mathbb {Q}, <)}$${\ displaystyle (\ mathbb {R}, <)}$${\ displaystyle \ omega}$${\ displaystyle p (x_ {1}, \ dots, x_ {n})}$${\ displaystyle x_ {i}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle \ mathbb {R}}$${\ displaystyle \ mathbb {C}}$${\ displaystyle \ omega}$${\ displaystyle x = 1 +\ tečky +1}$

${\ displaystyle \ aleph _ {0}}$-kategorické teorie a jejich počitatelné modely mají také silné vazby na oligomorfní skupiny :

Kompletní teorie prvního řádu T v konečném nebo spočitatelném podpisu je -kategorická právě tehdy, pokud je její skupina automorfismu oligomorfní.${\ displaystyle \ omega}$

Ekvivalentní charcaterisations tohoto odstavce, v důsledku nezávisle Engeler , Ryll-Nardzewski a Svenonius , jsou někdy označovány jako Ryll-Nardzewski věta.

V kombinatorických podpisech jsou společným zdrojem -kategorických teorií Fraïssé limity , které jsou získány jako mez sloučení všech možných konfigurací třídy konečných relačních struktur. ${\ displaystyle \ omega}$

Nespočetná kategoričnost

Michael Morley v roce 1963 ukázal, že pro teorie v počitatelných jazycích existuje pouze jeden pojem nespočetné kategoričnosti .

Morleyova věta o kategoričnosti

Pokud je teorie prvního řádu T v konečném nebo spočitatelném podpisu κ-kategorická pro některé nespočetné kardinály κ, pak T je κ-kategorická pro všechny nepočítatelné kardinály κ.

Morleyův důkaz odhalil hluboké souvislosti mezi nespočetnou kategoričností a vnitřní strukturou modelů, které se staly výchozím bodem teorie klasifikace a teorie stability. Nesporně kategorické teorie jsou z mnoha úhlů pohledu nejlépe vychovanými teoriemi. Zejména úplné silně minimální teorie jsou nesporně kategorické. To ukazuje, že teorie algebraicky uzavřených polí dané charakteristiky je nesporně kategorická, přičemž stupeň transcendence pole určuje její typ izomorfismu.

Teorie, která je jak -kategorická, tak nesporně kategorická, se nazývá zcela kategorická . ${\ displaystyle \ omega}$

Vybrané aplikace

Mezi rané úspěchy modelové teorie patří Tarskiho důkazy o rozhodnutelnosti různých algebraicky zajímavých tříd, jako jsou skutečná uzavřená pole , booleovské algebry a algebraicky uzavřená pole dané charakteristiky .

V šedesátých letech vedly úvahy o nasycených modelech a konstrukci ultraproduktu k vývoji nestandardní analýzy Abrahama Robinsona .

V roce 1965 James Axe a Simon B. Kochen ukázali speciální případ Artinovy ​​domněnky o diofantických rovnicích, Ax-Kochenovu větu , opět pomocí ultraproduktové konstrukce.

V poslední době spojení mezi stabilitou a geometrií definovatelných množin vedlo k několika aplikacím z algebraické a diofantické geometrie, včetně důkazu Ehuda Hrushovského z roku 1996 o geometrické Mordell-Langově domněnce ve všech charakteristikách

V roce 2011 Jonathan Pila použil techniky kolem o-minimality, aby dokázal André-Oortovu domněnku o produktech modulárních křivek.

V samostatném řetězci šetření, které také vyrostlo kolem stabilních teorií, Laskowski v roce 1992 ukázal, že teorie NIP popisují přesně ty definovatelné třídy, které lze v teorii strojového učení naučit PAC .

Dějiny

Teorie modelu jako předmět existuje přibližně od poloviny 20. století. Některé dřívější výzkumy, zejména v matematické logice , jsou však zpětně často považovány za model teoretické povahy. Prvním významným výsledkem v dnešní modelové teorii byl speciální případ sestupné věty Löwenheim – Skolem, publikované Leopoldem Löwenheimem v roce 1915. Věta o kompaktnosti byla implicitně součástí práce Thoralfa Skolema , ale byla poprvé publikována v roce 1930 jako lemma v Kurtovi Gödelově důkazu jeho věty o úplnosti . Věta Löwenheim – Skolem a věta o kompaktnosti dostaly v letech 1936 a 1941 od Anatolije Maltseva příslušné obecné tvary . Rozvoj teorie modelu jako nezávislé disciplíny zahájil Alfred Tarski , člen lvovsko -varšavské školy během interbellum . Mezi další témata Tarskiho práce zahrnovaly logické důsledky , deduktivní systémy , algebru logiky, teorii definovatelnosti a sémantickou definici pravdy . Jeho sémantické metody vyvrcholily modelovou teorií, kterou on a řada jeho studentů z Berkeley vyvinuli v 50. a 60. letech.

V další historii disciplíny začaly vznikat různá vlákna a zaměření předmětu se posunulo. V 60. letech se techniky kolem ultraproduktů staly populárním nástrojem v modelové teorii. Ve stejné době výzkumníci jako James Ax zkoumali teorii modelu prvního řádu různých algebraických tříd a další, jako například H. Jerome Keisler, rozšiřovali koncepty a výsledky teorie modelu prvního řádu do dalších logických systémů. Poté práce Saharona Shelaha kolem kategoričnosti a Morleyova problému změnila komplex teorie modelu, což dalo vzniknout zcela nové třídě konceptů. Teorie stability (teorie klasifikace) Sále vytvořil od pozdní 1960 cíle klasifikovat teorií podle počtu různých modelů mají nějaké dané mohutnosti. Během příštích desetiletí bylo jasné, že výsledná hierarchie stability je úzce spojena s geometrií množin, které jsou v těchto modelech definovatelné; z toho vznikla subdisciplína nyní známá jako teorie geometrické stability.

Napojení na související větve matematické logiky

Teorie konečných modelů

Teorie konečných modelů (FMT) je podoblast teorie modelu (MT), která se zabývá jejím omezením na interpretace na konečných strukturách, které mají konečný vesmír.

Protože mnoho ústředních teorií modelu neplatí, pokud jsou omezeny na konečné struktury, FMT se svými metodami dokazování zcela liší od MT. Mezi centrální výsledky klasické modelové teorie, které podle FMT selhávají u konečných struktur, patří věta kompaktnosti , Gödelova věta o úplnosti a metoda ultraproduktů pro logiku prvního řádu .

Mezi hlavní oblasti aplikace FMT jsou deskriptivní teorii složitosti , teorie databází a teorie formálních jazyků .

Teorie množin

Jakákoli teorie množin (která je vyjádřena v počitatelném jazyce), pokud je konzistentní, má počitatelný model; toto je známé jako Skolemův paradox , protože v teorii množin existují věty, které postulují existenci nespočetných množin, a přesto jsou tyto věty v našem počítatelném modelu pravdivé. Zejména důkaz nezávislosti hypotézy kontinua vyžaduje zvážení množin v modelech, které se zdají být nepočitatelné při pohledu zevnitř modelu, ale jsou spočitatelné někomu mimo model.

Modelově teoretické hledisko bylo užitečné v teorii množin ; například v práci Kurta Gödla o konstruovatelném vesmíru, která spolu s metodou vynucování vyvinutou Paulem Cohenem může být ukázána k prokázání (opět filozoficky zajímavé) nezávislosti na axiomu volby a hypotéze kontinua na ostatních axiomech teorie množin.

V opačném směru lze samotnou teorii modelu formalizovat v rámci teorie množin ZFC. Formalizace uspokojení v ZFC se například provádí induktivně na základě Tarského T-schématu a pozorování, kde leží členové rozsahu variabilních přiřazení. Vývoj základů modelové teorie (jako je například věta o kompaktnosti) se opírá o zvolený axiom, přesněji o booleovskou primární ideální větu. Další výsledky v modelové teorii závisí na set-teoretických axiomech mimo standardní rámec ZFC. Pokud například platí hypotéza kontinua, pak každý spočitatelný model má ultrapower, která je nasycená (ve své vlastní mohutnosti). Podobně platí -li hypotéza generalizovaného kontinua, pak každý model má nasycené elementární rozšíření. Žádný z těchto výsledků není prokazatelný pouze v ZFC. Nakonec se ukázalo, že některé otázky vyplývající z modelové teorie (jako je kompaktnost pro infinitární logiku) jsou ekvivalentní velkým kardinálním axiómům.

Viz také

Poznámky

Reference

Kanonické učebnice

• Chang, Chen Chung ; Keisler, H. Jerome (1990) [1973]. Teorie modelu . Studie logiky a základy matematiky (3. vyd.). Elsevier. ISBN 978-0-444-88054-3.
• Hodges, Wilfrid (1997). Teorie kratšího modelu . Cambridge: Cambridge University Press . ISBN 978-0-521-58713-6.
• Kopperman, R. (1972). Teorie modelu a její aplikace . Boston: Allyn a Bacon .
• Marker, David (2002). Teorie modelu: Úvod . Absolventské texty z matematiky 217. Springer. ISBN 0-387-98760-6.

Další učebnice

• Bell, John L .; Slomson, Alan B. (2006) [1969]. Modely a ultraprodukty: Úvod (dotisk edice 1974). Dover Publications . ISBN 0-486-44979-3.
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Matematická logika . Springer . ISBN 0-387-94258-0.
• Hinman, Peter G. (2005). Základy matematické logiky . AK Peters . ISBN 1-56881-262-0.
• Hodges, Wilfrid (1993). Teorie modelu . Cambridge University Press . ISBN 0-521-30442-3.
• Manzano, María (1999). Teorie modelu . Oxford University Press . ISBN 0-19-853851-0.
• Poizat, Bruno (2000). Kurz teorie modelu . Springer. ISBN 0-387-98655-3.
• Rautenberg, Wolfgang (2010). Stručný úvod do matematické logiky (3. vyd.). New York : Springer Science+Business Media . doi : 10,1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
• Rothmaler, Philipp (2000). Úvod do teorie modelu (nové vydání). Taylor & Francis . ISBN 90-5699-313-5.
• Stan, Katrin ; Ziegler, Martin (2012). Kurz teorie modelu . Cambridge University Press . ISBN 9780521763240.
• Kirby, Jonathan (2019). Pozvánka do teorie modelu . Cambridge University Press . ISBN 978-1-107-16388-1.

Zdarma online texty

• Chatzidakis, Zoé (2001). Úvod do teorie modelu (PDF) . s. 26 stran.
• Pillay, Anand (2002). Lecture Notes - Model Theory (PDF) . s. 61 stran.
• „Modelová teorie“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Hodges, Wilfrid , teorie modelu . Stanfordská encyklopedie filozofie, E. Zalta (ed.).
• Hodges, Wilfrid , teorie modelu prvního řádu . Stanfordská encyklopedie filozofie, E. Zalta (ed.).
• Simmons, Harold (2004), Úvod do teorie starého dobrého modelu . Poznámky k úvodnímu kurzu pro postgraduální studenty (se cvičeními).
• J. Barwise a S. Feferman (editoři), Model-Theoretic Logics , Perspectives in Mathematical Logic, Volume 8, New York: Springer-Verlag, 1985.