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é.
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é. 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é:

Odkazy

Související články

Literatura

ŠVEJDAR, Vítězslav. Logika, neúplnost, složitost a nutnost. Praha: Academia, 2002. ISBN 80-200-1005-X.