Cesko.wiki Věta o kompaktnosti
Author
Albert FloresAnimovaná ilustrace základního principu věty o kompaktnosti. Věta o kompaktnosti je jednou ze základních vět matematické logiky a teorie modelů. Poprvé ji dokázal rakouský logik Kurt Gödel.
Znění
Věta o kompaktnosti má dvě odlišné verze - pro výrokovou logiku a pro predikátovou logiku. Pro predikátovou verzi se běžně používá název pouze věta o kompaktnosti.
Věta o kompaktnosti pro výrokovou logiku
Nechť T je množina formulí. Je-li každá konečná podmnožina T splnitelná (tj. +more existuje-li ohodnocení atomů, přiřazující všem formulím z ní jedničku), pak je celá T splnitelná.
Věta o kompaktnosti pro predikátovou logiku
Pokud každá konečná podteorie teorie T má model, pak teorie T má model.
Důsledky a aplikace
Zásadním důsledkem věty o kompaktnosti je Löwenheim-Skolemova věta, dalšími jsou například věty o existenci kompaktních a saturovaných modelů.
Z (predikátové) věty o kompaktnosti například snadno plyne, že třída všech konečných struktur daného jazyka není axiomatizovatelná, tj. neexistuje teorie T, jejímiž modely jsou právě všechny konečné struktury daného jazyka. +more Pokud by totiž taková teorie T existovala, tak by byla uvažována teorie S vzniklá rozšířením T o nekonečně mnoho axiomů tvaru „existuje alespoň n prvků“ pro každé přirozené číslo n. Protože modelem T je jakákoli konečná struktura, má každá konečná část S model, tedy podle věty o kompaktnosti má model i celá S. Tento model je však zřejmě nekonečný a je zároveň modelem T, což je spor.
Důkazy
Věta o kompaktnosti má mnoho různých důkazů: * je přímým důsledkem Gödelovy věty o úplnosti (přesněji její výrokové resp. predikátové verze) * výroková verze je důsledkem Tichonovovy věty hovořící o kompaktnosti součinu kompaktních topologických prostorů * výrokovou verzi lze dokázat „konstruktivně“ transfinitní indukcí (přímo se zkonstruuje (s užitím axiomu výběru) hledané ohodnocení) * predikátová verze se dá dokázat užitím ultraproduktů