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 editovat
Rozhodnutelná teorie editovat
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 editovat
Struktura se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za model.
Vlastnosti editovat
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é.
- 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 editovat
Důsledky nerozhodnutelnosti Robinsonovy aritmetiky editovat
Robinsonova aritmetika je nerozhodnutelná teorie. Dokonce každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné. 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 editovat
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 editovat
Související články editovat
Literatura editovat
- ŠVEJDAR, Vítězslav. Logika, neúplnost, složitost a nutnost. Praha: Academia, 2002. ISBN 80-200-1005-X.