Rozhodnutelnost
Rozhodnutelnost (A je - není větší, než B, formule W je pravdivá – nepravdivá, a je - není prvkem množiny Y, Turingův stroj zastaví - nezastaví...) je vlastnost exaktního světa (matematika, geometrie, Turingův stroj, exaktní hry např. šachy,...), v němž veškeré entity mají exaktní interpretaci. Rozhodnutelnost nelze instalovat v mlze vágnosti přirozeného světa vágní, emocionální a subjektivní lidské psýchy, používající přirozený jazyk s vágní (vnitřní vágnost), emocionální a subjektivní interpretací měnící se od člověka k člověku a u každého z nich v čase, které se říká konotace. Nemůže proto existovat např. logika postavená nad přirozeným jazykem, může existovat pouze formální logika postavená nad umělým formálním jazykem, který má z principu exaktní (s nulovou vnitřní vágností) interpretaci.
Rozhodnutelnost logického systému
[editovat | editovat zdroj]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 | editovat zdroj]Rozhodnutelná teorie
[editovat | editovat zdroj]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 | editovat zdroj]Struktura se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za model.
Vlastnosti
[editovat | editovat zdroj]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 | editovat zdroj]Důsledky nerozhodnutelnosti Robinsonovy aritmetiky
[editovat | editovat zdroj]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 | editovat zdroj]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 | editovat zdroj]Související články
[editovat | editovat zdroj]Literatura
[editovat | editovat zdroj]- ŠVEJDAR, Vítězslav. Logika, neúplnost, složitost a nutnost. Praha: Academia, 2002. ISBN 80-200-1005-X.