Věta o kompaktnosti

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Nechť T je množina formulí. Je-li každá konečná podmnožina T splnitelná (tj. 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[editovat | editovat zdroj]

Pokud každá konečná podteorie teorie T má model, pak teorie T má model.

Důsledky a aplikace[editovat | editovat zdroj]

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. Pokud by totiž taková teorie T existovala, uvažovali bychom teorii S vzniklou 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[editovat | editovat zdroj]

Věta o kompaktnosti má mnoho různých důkazů:

Související články[editovat | editovat zdroj]