Věta o kompaktnosti - Compactness theorem

V matematické logiky je věta o kompaktnosti uvádí, že soubor z prvního řádu vět má model, právě tehdy, když každý konečný podskupina z nich má model. Tato věta je důležitým nástrojem v teorii modelů , protože poskytuje užitečnou (ale obecně neúčinnou) metodu pro konstrukci modelů jakékoli věty, která je konečně konzistentní .

Kompaktnost věta pro výrokové je důsledkem tichonovova věta (který říká, že výrobek z kompaktních prostorů je kompaktní), aplikovanou na kompaktní kamene mezery , odtud název Věta je. Podobně je to analogické s charakteristikou vlastnosti konečné křižovatky kompaktnosti v topologických prostorech : kolekce uzavřených množin v kompaktním prostoru má neprázdný průnik, pokud má každá konečná podkolekce neprázdný průnik.

Veta o kompaktnosti je jednou ze dvou klíčových vlastností spolu s Löwenheim-Skolemovou větou , která se v Lindströmově teorému používá k charakterizaci logiky prvního řádu. Ačkoli existují některé zevšeobecnění věty o kompaktnosti na logiku prvního řádu, samotná věta o kompaktnosti v nich neplatí, až na velmi omezený počet příkladů.

Dějiny

Kurt Gödel dokázal teorém o spočítatelné kompaktnosti v roce 1930. Anatoly Maltsev dokázal nespočetný případ v roce 1936.

Aplikace

Věta o kompaktnosti má v teorii modelů mnoho aplikací; zde je načrtnuto několik typických výsledků.

Kompaktnost teorém vyplývá princip Robinsona : V případě prvního řádu věta platí v každé oblasti z charakteristických nulu, pak existuje konstanta p taková, že věta platí pro všechny oblasti charakteristické větší než str . To lze vidět následovně: Předpokládejme, že φ je věta, která platí v každém poli charakteristické nuly. Pak její negace ¬φ, spolu s axiomy pole a nekonečnou posloupností vět 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0,…, není uspokojivá (protože neexistuje žádné pole charakteristiky 0, ve kterém ¬φ platí a nekonečná posloupnost vět zajišťuje, že jakýkoli model by byl polem charakteristiky 0). Proto existuje konečná podmnožina A těchto vět, která není uspokojivá. Můžeme předpokládat, že A obsahuje ¬φ, axiomy pole a pro některá k první k věty ve tvaru 1 + 1 + ... + 1 ≠ 0 (protože přidání více vět nezmění neuspokojivost). Nechť B obsahuje všechny věty A kromě ¬φ. Pak jakékoli pole s charakteristikou větší než k je modelem B a ¬φ společně s B není uspokojivé. To znamená, že φ musí platit v každém modelu B , což znamená přesně to, že φ platí v každém poli charakteristiky větším než k .

Druhá aplikace věty o kompaktnosti ukazuje, že každá teorie, která má libovolně velké konečné modely nebo jediný nekonečný model, má modely libovolně velké mohutnosti (jedná se o teorém Upward Löwenheim – Skolem ). Například existují nestandardní modely Peanoovy aritmetiky s nespočetně mnoha „přirozenými čísly“. Aby toho bylo dosaženo, nechť T je počáteční teorie a nechť κ jakékoli hlavní číslo . Přidejte k jazyku T jeden konstantní symbol pro každý prvek κ. Pak přidejte do T sbírku vět, které říkají, že objekty označené libovolnými dvěma odlišnými konstantními symboly z nové kolekce jsou odlišné (jedná se o sbírku vět ² ). Jelikož každá konečná podmnožina této nové teorie je uspokojitelná dostatečně velkým konečným modelem T nebo jakýmkoli nekonečným modelem, je uspokojivá celá rozšířená teorie. Ale jakýkoli model rozšířené teorie má mohutnost alespoň κ

Třetí aplikací věty o kompaktnosti je konstrukce nestandardních modelů reálných čísel, tj. Konzistentní rozšíření teorie reálných čísel, která obsahují „nekonečně malá“ čísla. Abychom to viděli, nechť Σ je axiomatizace prvního řádu teorie reálných čísel. Zvažte teorii získanou přidáním nového konstantního symbolu ε do jazyka a sousedícího s Σ axiomem ε> 0 a axiomy ε <1 / n pro všechna kladná celá čísla n . Je zřejmé, že standardní reálná čísla R jsou modelem pro každou konečnou podmnožinu těchto axiomů, protože reálná čísla uspokojují vše v Σ a vhodnou volbou ε je lze provést tak, aby uspokojila jakoukoli konečnou podmnožinu axiomů o ε. Podle věty o kompaktnosti existuje model * R, který splňuje Σ a také obsahuje nekonečně malý prvek ε. Podobný argument, sousedící s axiomy ω> 0, ω> 1 atd., Ukazuje, že existenci nekonečně velkých celých čísel nelze vyloučit žádnou axiomatizací Σ realit.

Důkazy

Jeden může dokázat teorém o kompaktnosti pomocí Gödelovy věty o úplnosti , která stanoví, že sada vět je uspokojivá právě tehdy, když z ní nelze prokázat žádný rozpor. Protože důkazy jsou vždy konečné, a proto zahrnují pouze konečně mnoho z uvedených vět, následuje věta o kompaktnosti. Ve skutečnosti je věta o kompaktnosti ekvivalentní Gödelově teorému o úplnosti a obě jsou ekvivalentní booleovské primární větě o ideálu , což je slabá forma axiomu volby .

Gödel původně dokázal teorém o kompaktnosti právě tímto způsobem, ale později byly nalezeny některé „čistě sémantické“ důkazy o teorémě o kompaktnosti, tj. Důkazy, které odkazují na pravdu, ale nikoli na prokazatelnost . Jeden z těchto důkazů se opírá o ultraprodukty závisející na axiomu výběru následovně:

Důkaz: Opravte jazyk prvního řádu L a nechte Σ být sbírkou vět L tak, aby každá konečná podkolekce vět L, z nichž i  has has má model . Nechť je také přímým produktem struktur a já kolekcí konečných podmnožin Σ. Pro každý i v I nechat _i  : = { j ∈ I  : j ⊇ i }. Rodina všech těchto sad _Ai generuje správný filtr , takže existuje ultrafilter U obsahující všechny sady tvaru _Ai . ${\ displaystyle {\ mathcal {M}} _ {i}}$${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i}}$

Nyní pro jakýkoli vzorec φ v Σ máme:

• množina A _{φ} je v U
• kdykoli j  ∈ A _{φ} , pak φ ∈  j , proto platí φ ${\ displaystyle {\ mathcal {M}} _ {j}}$
• množina všeho j s vlastností, kterou φ drží, je nadmnožinou A _{φ} , tedy také v U${\ displaystyle {\ mathcal {M}} _ {j}}$

Pomocí Łośovy věty vidíme, že φ platí v ultraproduktu . Takže tento ultraprodukt splňuje všechny vzorce v Σ. ${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i} / U}$

Viz také

• Barwise věta o kompaktnosti
• Herbrandova věta
• Seznam témat booleovské algebry  - článek seznamu Wikimedia
• Löwenheim – Skolemova věta  - Matematická věta

Poznámky

Reference

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Vyčíslitelnost a logika (čtvrté vydání). Cambridge University Press.
• Chang, CC; Keisler, H. Jerome (1989). Teorie modelu (třetí vydání). Elsevier. ISBN   0-7204-0692-7 .
• Dawson, John W. junior (1993). „Kompaktnost logiky prvního řádu: od Gödela po Lindström“. Dějiny a filozofie logiky . 14 : 15–37. doi : 10.1080 / 01445349308837208 .
• Hodges, Wilfrid (1993). Teorie modelů . Cambridge University Press. ISBN   0-521-30442-3 .
• Marker, David (2002). Teorie modelu: Úvod . Postgraduální texty z matematiky 217. Springer. ISBN   0-387-98760-6 .
• Truss, John K. (1997). Základy matematické analýzy . Oxford University Press. ISBN   0-19-853375-6 .