Set enumerat

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 mai 2021; verificările necesită 7 modificări .

O mulțime enumerabilă ( numerabilă efectiv , enumerabilă recursiv , mulțime semi-decidabilă [1] ) este o mulțime de obiecte constructive (de exemplu, numere naturale ), toate elementele cărora pot fi obținute folosind un algoritm . Complementul unei mulțimi enumerabile se numește corecursiv enumerabil [2] . Fiecare mulţime enumerabilă este aritmetică . Un set corecursiv enumerabil poate să nu fie enumerabil, dar este întotdeauna aritmetic. enumerate corespund ierarhiei $\Sigma _{1}^{0}$ $\Pi _{1}^{0}.$

Fiecare set rezolvabil este enumerabil. Un set enumerabil este decidabil dacă și numai dacă complementul său este și el enumerabil. Cu alte cuvinte, o mulțime este decidabilă dacă și numai dacă este atât enumerabilă, cât și corecursiv enumerabilă. Un subset al unui set enumerabil poate să nu fie enumerabil (și poate să nu fie nici măcar aritmetic).

Setul tuturor submulților enumerabile este o mulțime numărabilă , iar setul tuturor submulților nenumerabile este nenumărabil . $\mathbb {N}$ $\mathbb {N}$

Variante ale definiției

Diferitele formalizări ale conceptului de algoritm corespund diferitelor definiții formale ale conceptului de mulțime enumerabilă, care se dovedesc a fi echivalente. Astfel, pe baza conceptului de funcție recursivă , seturile enumerabile de numere naturale pot fi definite ca imagini ale funcțiilor parțial recursive ale unei variabile (prin urmare, seturile enumerabile de numere naturale sunt uneori numite „mulțimi enumerabile recursiv”). În mod similar, seturi enumerabile de cuvinte din alfabetul A pot fi introduse ca seturi de ieșiri ale mașinilor Turing cu alfabet extern A sau ca seturi de cuvinte din alfabetul A de ieșiri ale algoritmilor normali pe alfabetul A .

În teoria algoritmilor , se dovedește afirmația că mulțimile enumerabile și numai mulțimile enumerabile pot servi ca domenii ale algoritmilor. Acest lucru ne permite să introducem un alt mod echivalent de definire a conceptului de mulțime enumerabilă. Astfel, mulțimi enumerabile de numere naturale pot fi considerate intervalele de funcții recursive, mulțimi de cuvinte - zonele de aplicabilitate ale mașinilor Turing sau algoritmi normali cu alfabetele corespunzătoare.

Exemple

Setul gol este enumerabil.
Orice mulțime decidabilă (în special, orice mulțime finită ) este enumerabilă.
Setul de numere al mașinilor Turing care se opresc la o intrare goală este, de asemenea, enumerabil (deși nu este decidabil , deoarece complementul său este nenumerabil).
Proiecția unui set enumerabil este enumerabilă.
Unirea și intersecția unui număr finit de mulțimi enumerabile sunt de asemenea enumerabile.
Mulțimea numerelor naturale a căror notație zecimală apare ca subșir în notația zecimală a numărului π este enumerabilă, iar dacă π este normală , chiar și trivial rezolvabilă (întregul set de numere naturale).
Mulțimea numerelor raționale mai mici decât constanta lui Khaitin Ω este enumerabilă, dar nu decidabilă.
Dar mulțimea numerelor raționale mai mare decât constanta lui Khaitin Ω este nenumerabilă (deși este enumerabilă aritmetic și corecursiv).
Setul de afirmații demonstrabile în aritmetica de ordinul întâi este enumerabil.
Dar setul de afirmații adevărate din aritmetica de ordinul întâi nu este nici enumerabil, nici corecursiv enumerabil (și nici măcar nu este aritmetic, ceea ce constituie aserțiunea teoremei lui Tarski asupra inexprimabilității adevărului în aritmetică).

Diophantine

Orice set enumerabil de numere întregi (sau tupluri de numere întregi) are o reprezentare diofantină , adică este o proiecție a mulțimii tuturor soluțiilor unei ecuații algebrice diofantine.

Aceasta înseamnă, în special, că orice mulțime enumerabilă coincide cu setul de valori pozitive luate pentru parametrii întregi de către un polinom cu coeficienți întregi. Acest rezultat a fost stabilit de Yuri Matiyasevich .

Vezi și

Set imunitar

Note

↑ A. E. Pentus, M. R. Pentus, Teoria matematică a limbajelor formale, Cursul 14: Probleme algoritmice // Intuit.ru, 07/09/2007
↑ Barwise, Kenneth John. Carte de referință despre logica matematică. Partea 3: teoria recursiunii. — M .: Nauka, 1982.

Literatură

Rogers H. Teoria funcțiilor recursive și a calculabilității efective : [trad. din engleză. ] / ed. V. A. Uspenski: per. din engleza. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. — M .: Mir, 1972.