Řešitelná sada

Řešitelná množina (také rekurzivní , vyčíslitelná ) je množina přirozených čísel , pro něž existuje algoritmus , který přijímá jakékoli přirozené číslo jako vstup a po konečném počtu kroků končí určením, zda do této množiny patří. Jinými slovy, množina je rozhodnoutelná, pokud je její charakteristická funkce vyčíslitelná . Soubor, který není rozpustný, se nazývá nerozhodnutelný . Lze také hovořit o řešitelné množině skládající se z libovolných konstruktivních objektů zakódovaných přirozenými čísly. Jakákoli rozhoditelná množina je spočetná a aritmetická . Rozložitelné množiny odpovídají úrovni aritmetické hierarchie . ${\displaystyle \Delta _{1}^{0))$

V obecném případě se podmnožina množiny konstruktivních prvků nazývá rozhodnutelná s ohledem na , pokud existuje algoritmus, který lze aplikovat na objekty z a je-li aplikován na nějaký objekt , který odpovídá na otázku, zda tento objekt patří [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

Existuje nespočet množin, které nelze rozhodnout. Kromě toho je vyčíslitelná množina rozhodnoutelná právě tehdy, když je spočetný i její doplněk . Projekce rozhodnoutelné množiny je spočetná, ale nemusí být rozhodnoutelná. Podmnožina rozhodnoutelné množiny nemusí být rozhodnoutelná (a nemusí být ani aritmetická).

Množina všech řešitelných podmnožin je spočetná a množina všech neřešitelných podmnožin je nepočitatelná , protože množina všech podmnožin kladných celých čísel je nespočetná. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Mezi vyčíslitelnými podmnožinami a vyčíslitelnými reálnými čísly existuje vzájemná korespondence [2] . $S\podmnožina P$ $x\in [0,1]$

Příklady

O prázdné množině lze rozhodnout.
Jakákoli konečná množina a její doplněk jsou řešitelné množiny.
Existují nekonečné řešitelné množiny s nekonečným doplňkem. Řešitelná je například množina všech sudých čísel a množina všech prvočísel.
Doplněk rozhodnutelné množiny je rozhodnoutelný.
Řešitelné je i sjednocení a průnik konečného počtu řešitelných množin.
Jakákoli vyčíslitelná množina, jejíž doplněk je také vyčíslitelný, je rozhodnoutelná (Postova věta ).
Množina racionálních čísel menších $\pi$ než , je řešitelná.
Množina, jejíž jediný prvek je roven jedné, je-li Riemannova hypotéza pravdivá, a jinak nula, je rozhodnoutelná (protože je konečná).
Množina čísel netriviálních nul ζ-funkce , pro kterou je porušena Riemannova hypotéza , je rozhodnoutelná (ačkoli není známo, zda je prázdná, konečná nebo nekonečná).
O množině řetězců, které jsou platnými důkazy v ZFC , lze rozhodnout. Jeho projekce - soubor prohlášení prokazatelných v ZFC - je spočetný, ale za podmínky, že je ZFC konzistentní , je nerozhodnutelný.

Poznámky

↑ Ebbinhouse, 1972 , s. 19.
↑ 1 2 Birkhoff G. , Barty T. Moderní aplikovaná algebra. - M., Mir, 1976. - str. 375-376

Literatura

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingovy stroje a rekurzivní funkce. — M .: Mir, 1972. — 262 s.