Megoldható készlet

A megoldható halmaz ( rekurzív , kiszámítható ) természetes számok halmaza , amelyre létezik egy algoritmus , amely tetszőleges természetes számot kap bemenetként, és véges számú lépés után meghatározza, hogy ebbe a halmazba tartozik-e. Más szóval, egy halmaz akkor eldönthető, ha a jellemző függvénye kiszámítható . A nem oldható halmazt eldönthetetlennek nevezzük . Feloldható halmazról is beszélhetünk, amely természetes számokkal kódolt bármely konstruktív objektumból áll. Minden eldönthető halmaz megszámlálható és aritmetikus . A feloldható halmazok az aritmetikai hierarchia szintjének felelnek meg . $\Delta _{1}^{0}$

Általános esetben a konstruktív elemek halmazának egy részhalmazát tekintve eldönthetőnek nevezzük , ha van olyan algoritmus, amely alkalmazható objektumokra, és ha valamilyen objektumra alkalmazzuk, akkor megválaszolja azt a kérdést, hogy ez az objektum tartozik-e [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

Vannak felsorolható halmazok, amelyek nem eldönthetők. Ráadásul egy felsorolható halmaz akkor és csak akkor dönthető el, ha a komplementere is megszámlálható. Egy eldönthető halmaz vetülete megszámlálható, de lehet, hogy nem eldönthető. Előfordulhat, hogy egy eldönthető halmaz egy részhalmaza nem eldönthető (és még csak nem is aritmetikai).

Az összes megoldható részhalmaz halmaza megszámlálható , a feloldhatatlan részhalmazé pedig megszámlálhatatlan , mivel a pozitív egészek összes részhalmaza megszámlálhatatlan. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Egy az egyhez megfelelés van a kiszámítható részhalmazok és a kiszámítható valós számok között [2] . $S\alhalmaz P$ $x\in [0,1]$

Példák

Az üres halmaz eldönthető.
Bármely véges halmaz és komplementere megoldható halmaz.
Vannak végtelen megoldható halmazok végtelen komplementerrel. Például az összes páros szám halmaza és az összes prímszám halmaza megoldható.
Egy eldönthető halmaz komplementere eldönthető.
Véges számú megoldható halmaz egyesülése és metszéspontja is megoldható.
Minden olyan felsorolható halmaz, amelynek komplementere is megszámlálható, eldönthető ( Post tétele ).
A , -nál kisebb racionális számok halmaza megoldható. $\pi$
Az a halmaz, amelynek egyetlen eleme eggyel egyenlő, ha a Riemann-hipotézis igaz, egyébként nulla, eldönthető (mivel véges).
A ζ-függvény nem triviális nulláinak számkészlete, amelyre a Riemann-hipotézis megsértődik , eldönthető (bár nem tudni, hogy üres, véges vagy végtelen).
A ZFC -ben érvényes bizonyítási karakterláncok halmaza eldönthető. Projekciója - a ZFC-ben bizonyítható állítások halmaza - megszámlálható, de a ZFC konzisztens feltétele mellett eldönthetetlen.

Jegyzetek

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

Irodalom

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turing-gépek és rekurzív függvények. — M .: Mir, 1972. — 262 p.