Lösbar uppsättning

En lösbar mängd (även rekursiv , beräkningsbar ) är en uppsättning naturliga tal för vilka det finns en algoritm som tar emot vilket naturligt tal som helst som indata och, efter ett ändligt antal steg, slutar med att avgöra om det tillhör denna mängd. Med andra ord är en mängd avgörbar om dess karakteristiska funktion är beräkningsbar . En mängd som inte är löslig kallas oavgörlig . Man kan också tala om en lösbar mängd som består av alla konstruktiva objekt kodade av naturliga tal. Varje avgörbar uppsättning är uppräknad och aritmetisk . Lösbara mängder motsvarar nivån för den aritmetiska hierarkin . ${\displaystyle \Delta _{1}^{0))$

I det allmänna fallet kallas en delmängd av uppsättningen konstruktiva element avgörbar med avseende på , om det finns en algoritm som kan appliceras på objekt från och, om den tillämpas på något objekt , som svarar på frågan om detta objekt tillhör [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

Det finns otaliga uppsättningar som inte går att avgöra. Dessutom är en uppräknad mängd avgörbar om och endast om dess komplement också är uppräknelig. Projektionen av en avgörbar uppsättning är uppräknad, men kanske inte avgörbar. En delmängd av en avgörbar mängd kanske inte är avgörbar (och kanske inte ens aritmetisk).

Mängden av alla lösbara delmängder är räkningsbar och mängden av alla olösbara delmängder är oräknelig , eftersom mängden av alla delmängder av positiva heltal är oräknelig. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Det finns en en-till-en-överensstämmelse mellan beräkningsbara delmängder och beräkningsbara reella tal [2] . $S\delmängd P$ $x\in [0,1]$

Exempel

Den tomma uppsättningen är avgörbar.
Varje finit mängd och dess komplement är lösbara mängder.
Det finns oändliga lösbara uppsättningar med oändligt komplement. Till exempel är mängden av alla jämna tal och mängden av alla primtal lösbara.
Komplementet av en avgörbar uppsättning är avgörbar.
Unionen och skärningspunkten mellan ett ändligt antal lösbara mängder är också lösbara.
Varje uppräknad mängd vars komplement också är uppräknbar är avgörbar ( Posts sats ).
Mängden rationella tal mindre $\pi$ än , är lösbar.
En mängd vars enda element är lika med ett om Riemann-hypotesen är sann, och noll annars, kan avgöras (eftersom den är finit).
Uppsättningen av siffror av icke-triviala nollor i ζ-funktionen , för vilka Riemann-hypotesen kränks , kan avgöras (även om det inte är känt om det är tomt, ändligt eller oändligt).
Uppsättningen av strängar som är giltiga bevis i ZFC kan avgöras. Dess projektion - uppsättningen av påståenden som kan bevisas i ZFC - är uppräknad, men under förutsättning att ZFC är konsekvent är den oavgjord.

Anteckningar

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

Litteratur

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingmaskiner och rekursiva funktioner. — M .: Mir, 1972. — 262 sid.