Rozhodnutelnost

Rozhodnutelnost je matematický pojem z oblasti matematické logiky. Vyjadřuje, zda existuje konečný algoritmus, který pro každou formuli určí, zda je v dané teorii dokazatelná nebo není. Teorie, pro niž takový algoritmus existuje, se nazývá rozhodnutelná, v opačném případě pak nerozhodnutelná. Problematika rozhodnutelnosti úzce souvisí s Gödelovými větami o neúplnosti.

Definice

Rozhodnutelná teorie

Teorie je rozhodnutelná, pokud množina všech formulí v ní dokazatelných je rekurzivní. Není-li teorie rozhodnutelná, nazývá se nerozhodnutelná.

Silně nerozhodnutelná struktura

Struktura se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za model.

Vlastnosti

Rozhodnutelnost či nerozhodnutelnost se přenáší mezi teoriemi, mezi nimiž je určitý vztah. Nejpoužívanější tvrzení, která o tomto hovoří, jsou následující: * Rozšíření rozhodnutelné teorie o konečně mnoho axiomů v témže jazyce je rozhodnutelné. +more * Rozšíření rozhodnutelné teorie o definice je rozhodnutelné. * Teorie, v níž je interpretovatelná nerozhodnutelná teorie, je také nerozhodnutelná. * Konzervativní rozšíření nerozhodnutelné teorie je nerozhodnutelné.

O silně nerozhodnutelných strukturách platí: * Je-li v nějaké struktuře definovatelná silně nerozhodnutelná struktura, pak je tato struktura také silně nerozhodnutelná.

Dále se často používá: * Rekurzivně axiomatizovatelná nerozhodnutelná teorie je neúplná.

Příklady

Důsledky nerozhodnutelnosti Robinsonovy aritmetiky

Robinsonova aritmetika je nerozhodnutelná teorie. Dokonce každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné. +more Tato dvě tvrzení mají mnoho důsledků: * Protože je Robinsonova aritmetika konečně axiomatizovatelná, je nerozhodnutelná také prázdná teorie v jazyce aritmetiky. * Peanova aritmetika je nerozhodnutelná a protože je rekurzivně axiomatizovatelná, je neúplná. * Standardní model aritmetiky (struktura přirozených čísel) je silně nerozhodnutelná struktura. * Teorie standardního modelu (jejími axiomy jsou všechny formule platné ve standardním modelu) je nerozhodnutelná, protože je však úplná, nemůže být rekurzivně axiomatizovatelná. * Protože jsou přirozená čísla definovatelná v celých (např. pomocí Lagrangeovy věty o čtyřech čtvercích) a celá v racionálních, jsou struktury celých a racionálních čísel také silně nerozhodnutelné struktury. Odtud dále plyne: ** Teorie okruhů, komutativních okruhů, oborů integrity, těles, komutativních těles či těles charakteristiky 0, jsou nerozhodnutelné.

Rozhodnutelné teorie

Následující teorie jsou rozhodnutelné: * teorie hustých lineárních uspořádání * teorie abelovských grup * teorie booleových algeber * teorie algebraicky uzavřených těles * Presburgerova aritmetika

Odkazy

Související články

Rekurzivní množina * Gödelovy věty o neúplnosti

Literatura

Kategorie:Matematická logika Kategorie:Neřešitelné úlohy