Løseligt sæt

Et løsbart sæt (også rekursivt , beregneligt ) er et sæt af naturlige tal, for hvilket der er en algoritme , der modtager et hvilket som helst naturligt tal som input og, efter et endeligt antal trin, slutter med at bestemme, om det hører til dette sæt. Med andre ord kan et sæt bestemmes, hvis dets karakteristiske funktion kan beregnes . Et sæt, der ikke er opløseligt, kaldes uafgøreligt . Man kan også tale om et opløseligt sæt bestående af alle konstruktive objekter kodet af naturlige tal. Ethvert afgørbart sæt er tælleligt og aritmetisk . Opløselige mængder svarer til niveauet af det aritmetiske hierarki . $\Delta _{1}^{0}$

I det generelle tilfælde kaldes en delmængde af sættet af konstruktive elementer afgørbar med hensyn til , hvis der er en algoritme, der kan anvendes på objekter fra og, hvis den anvendes på et eller andet objekt , som besvarer spørgsmålet om, hvorvidt dette objekt tilhører [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

Der er utallige sæt, der ikke kan afgøres. Desuden kan et optalligt sæt afgøres, hvis og kun hvis dets komplement også kan optælles. Projektionen af et afgøreligt sæt er talværdigt, men kan ikke bestemmes. En delmængde af et afgørbart sæt er muligvis ikke afgørbart (og er måske ikke engang aritmetisk).

Mængden af alle opløselige delmængder kan tælles , og mængden af alle uopløselige delmængder er utællelige , da mængden af alle delmængder af positive heltal er utellelige. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Der er en en-til-en overensstemmelse mellem beregnelige delmængder og beregnelige reelle tal [2] . $S\undersæt P$ $x\in [0,1]$

Eksempler

Det tomme sæt kan bestemmes.
Enhver endelig mængde og dens komplement er opløselige mængder.
Der er uendelige opløselige sæt med uendelig komplement. For eksempel er mængden af alle lige tal og mængden af alle primtal opløselige.
Komplementet af et afgøreligt sæt er afgørligt.
Foreningen og skæringspunktet mellem et endeligt antal opløselige mængder er også opløselige.
Ethvert tælleligt sæt, hvis komplement også kan tælles, kan afgøres ( Posts sætning ).
Sættet af rationelle tal mindre $\pi$ end , er løseligt.
En mængde, hvis eneste element er lig med én, hvis Riemann-hypotesen er sand, og nul ellers, kan afgøres (fordi den er endelig).
Sættet af tal af ikke-trivielle nuller af ζ-funktionen , for hvilke Riemann-hypotesen er overtrådt , kan bestemmes (selvom det ikke vides, om det er tomt, endeligt eller uendeligt).
Sættet af strenge, der er gyldige beviser i ZFC , kan bestemmes. Dens projektion - sættet af udsagn, der kan bevises i ZFC - er talrigt, men under forudsætning af, at ZFC er konsistent , er det uafgørligt.

Noter

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

Litteratur

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turing-maskiner og rekursive funktioner. — M .: Mir, 1972. — 262 s.