Grundsats (beräknebarhet)

Inom beräkningsbarhetsteorin finns det ett antal grundsatser . Dessa satser visar att vissa typer av mängder alltid måste ha några medlemmar som, i termer av Turing-grad , inte är alltför komplicerade. En familj av bassatser rör icke-tomma, effektivt slutna mängder (det vill säga icke-tomma $\Pi _{1}^{0}$ mängder i den aritmetiska hierarkin ); dessa satser studeras som en del av klassisk beräkningsbarhetsteori. En annan familj av bassatser rör icke-tomma analytiska uppsättningar av lätta ytor (det vill säga $\Sigma _{1}^{1}$ i den analytiska hierarkin ); dessa satser studeras som en del av hyperaritmetisk teori .

Effektivt slutna set

Effektivt slutna uppsättningar är ett ämne för studier i klassisk beräkningsbarhetsteori. En effektivt sluten uppsättning är mängden av alla vägar genom något beräkningsbart underträd till det binära trädet $2^{<\omega }$ . Dessa uppsättningar är slutna, i topologisk mening , som delmängder av Cantor-rymden $2^{\omega }$ , och komplementet till en effektiv sluten uppsättning är en effektiv öppen uppsättning i betydelsen effektiva polska mellanrum . Kleene bevisade 1952 att det finns en icke-tom, effektivt sluten uppsättning utan någon beräkningsbar punkt (Cooper 1999, s. 134). Grundsatser visar att det måste finnas punkter som inte är "för långt" från att vara beräkningsbara, i informell mening.

En klass ${\mathcal {C}}\subseteq 2^{\omega }$ är en grund för effektivt slutna mängder om varje icke-tom effektivt sluten mängd innehåller en medlem av ${\mathcal { C}}$ (Cooper 2003, s. 329). Grundsatser visar att särskilda klasser är baser i denna mening. Dessa satser inkluderar (Cooper 1999, s. 134):

• Den låga bassatsen : varje icke-tom $\Pi _{1}^{0}$ uppsättning har en medlem som är av låg grad.
• Den hyperimmunfria bassatsen : varje icke-tom $\Pi _{1}^{0}$ uppsättning har en medlem som är av hyperimmunfri grad.
• Re -bassatsen : varje icke-tom $\Pi _{1}^{0}$ uppsättning har en medlem som är av rekursivt uppräknad (re) grad .

är en mängd $X\subseteq \mathbb {N}$ låg om dess Turing-hopp $X'=\varnothing '$ , graden av stoppproblemet . $X$ har hyperimmunfri grad om varje total $X$ -beräknarbar funktion $f\colon \mathbb {N} \to \mathbb {N}$ domineras av en total beräkningsbar funktion $g$ (betyder $f(n)\leq g(n)$ för alla $n$ ).

Inga två av ovanstående tre satser kan kombineras för uppsättningen av konsekventa avslutningar av PA (eller bara EFA ; Turing-graderna är desamma). Den enda re Turing-graden som beräknar en konsekvent komplettering av PA är 0'. Dock kan lågbassatsen och hyperimmunfria bassatsen var och en kombineras med konundvikande, dvs för varje icke beräknad X kan vi välja en medlem (som i satsen) som inte beräknar X . Satserna relativiserar också över en godtycklig reell.

Lightface analytiska set

Det finns också grundsatser för lightface $\Sigma _{1}^{1}$ uppsättningar. Dessa grundsatser studeras som en del av hyperaritmetisk teori . En sats är Gandys bassats, som är analog med lågbassatsen. Gandys bassats visar att varje icke-tom $\Sigma _{1}^{1}$ uppsättning har ett element som är hyperaritmetiskt lågt, det vill säga dess hyperhopp har samma hypergrad (och för satsen, till och med samma Turing-grad) som Kleenes uppsättning ${\mathcal {O}}$ .

•   Cooper, SB (1999). "Local degree theory", i Handbook of Computability Theory , ER Griffor (red.), Elsevier, s. 121–153. ISBN 978-0-444-89882-1
•   — (2003), Computability Theory , Chapman-Hall. ISBN 1-584-88237-9

externa länkar

• Simpson, S. " A survey of basis theorems ", bilder från Computability Theory and Foundations of Mathematics , Tokyo Institute of Technology, 18–20 februari 2013.