Set rezolvabil

O mulțime rezolvabilă (de asemenea recursivă , calculabilă ) este o mulțime de numere naturale pentru care există un algoritm care primește ca intrare orice număr natural și, după un număr finit de pași, se termină prin a determina dacă aparține acestei mulțimi. Cu alte cuvinte, o mulțime este decidabilă dacă funcția sa caracteristică este calculabilă . O multime care nu este solubila se numeste indecidabila . Se poate vorbi și de o mulțime rezolvabilă constând din orice obiecte constructive codificate prin numere naturale. Orice set rezolvabil este enumerabil șiaritmetica . Mulțimile rezolvabile corespund nivelului ierarhiei aritmetice . $\Delta _{1}^{0}$

În cazul general, o submulțime a mulțimii de elemente constructive se numește decidabilă în raport cu , dacă există un algoritm care poate fi aplicat obiectelor din și, dacă este aplicat unui obiect , care răspunde la întrebarea dacă acest obiect aparține [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

Există seturi enumerabile care nu sunt decidabile. Mai mult, o mulțime enumerabilă este decidabilă dacă și numai dacă complementul său este și enumerabil. Proiecția unui set decidabil este enumerabilă, dar poate să nu fie decidabilă. Un subset al unui set decidabil poate să nu fie decidabil (și poate să nu fie nici măcar aritmetic).

Mulțimea tuturor submulților rezolvabile este numărabilă , iar mulțimea tuturor submulților nerezolvabile este nenumărabilă , deoarece mulțimea tuturor submulților de numere întregi pozitive este nenumărabilă. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Există o corespondență unu-la-unu între submulțimile calculabile și numerele reale calculabile [2] . $S\subset P$ $x\in [0,1]$

Exemple

Setul gol este determinabil.
Orice mulțime finită și complementul ei sunt mulțimi rezolvabile.
Există mulțimi infinite rezolvabile cu complement infinit. De exemplu, mulțimea tuturor numerelor pare și mulțimea tuturor numerelor prime sunt rezolvabile.
Complementul unei multimi decidabile este decidabil.
Unirea și intersecția unui număr finit de mulțimi rezolvabile sunt de asemenea rezolvabile.
Orice mulțime enumerabilă a cărei complement este și enumerabil este decidabilă ( teorema lui Post ).
Mulțimea numerelor raționale mai $\pi$ mici decât , este rezolvabilă.
O mulțime al cărei singur element este egal cu unu dacă ipoteza Riemann este adevărată și zero în caz contrar, este decidabilă (pentru că este finită).
Mulțimea numerelor de zerouri netriviale ale funcției ζ , pentru care este încălcată ipoteza Riemann , este decidabilă (deși nu se știe dacă este goală, finită sau infinită).
Setul de șiruri care sunt dovezi valide în ZFC este decidabil. Proiecția sa - setul de afirmații demonstrabile în ZFC - este enumerabilă, dar, cu condiția ca ZFC să fie consecvent , este indecidabilă.

Note

↑ Ebbinhouse, 1972 , p. 19.
↑ 1 2 Birkhoff G. , Barty T. Modern Applied Algebra. - M., Mir, 1976. - p. 375-376

Literatură

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turing machines and recursive functions. — M .: Mir, 1972. — 262 p.