Comment comprendre la définition de $ \ pick $ en hiérarchie arithmétique

Question

Je lisons un texte sur la théorie de la calculable et, selon le texte, à chaque niveau $ K $ de la hiérarchie arithmétique, nous avons deux ensembles, $ \ sigma_k $ et $ \ pi_k $ , où $ \ pi_k $ est défini comme suit:

$$ \ Pi_k= co- \ sigma_k $$

de sorte que pour $ k= 0 $ , nous avons la classe des ensembles critiquables et $ \ sigma_0=pi_0 $ , et pour $ k= 1 $ , nous avons $ \ sigma_1 $ comme le Classe d'ensembles de manière complète (CE) (CE) $ \ PI_1 $ Comme la classe des ensembles non compensables (non CE) ....

let $ l (m_e) $ désigne la langue reconnue par Turing machine $ m_e $ avec godel Numéro $ E $ . Je suis tombé sur la langue suivante $ e $ , où:

$$ e={e | l (m_e)=sigma ^ * \} $$

I.e. $ E $ est la langue de toutes les codes de machine Turing $ E $ qui sont de manière complète. Par un argument de diagonalisation, il peut être montré que $ e $ n'est pas c.e. Cela implique que:

$$ E \ in \ pi_1 $$

Cependant, si $ E \ in \ pi_1 $ , cela signifie que $ e= co-a $ , pour certains $ A \ in \ sigma_1 $ , en utilisant la définition dans la déclaration ci-dessus ... Toutefois, le complément de $ E $ est:

$$ \ Overline {e}=Overline {\ {e | L (m_e)=sigma ^ * \}} $$

qui (je suppose) signifie que $ \ overline {e} $ est la langue de toutes les machines Turing e $ e $ tel que sur certaines entrées, $ e $ diverge ... Cependant, il a été montré que $ \ Overline {e} \ equiv_m k ^ {2} $ , c'est-à-dire $ \ overline {e} \ équiv_m k ^ k $ , de sorte que Compte tenu de deux ensembles $ A $ A $ et $ B $ , nous avons $ A \ equiv_m b $ iff $ a \ leq_m b $ et $ b \ leq_m a $ < / span>, et $ \ leq_m $ fait référence à une réduction de plusieurs à une:

$$ \ Overline {e} \ equiv_m k ^ k \ in \ sigma_2 $$

étant donné que $ \ sigma_2 \ neq \ sigma_1 $ $ , il ressemble à ce $ \ ot} $ < / span> n'est pas compatissement énumérable ... mais cela ne contredit pas la définition de $ \ pi_1 $ qui indique que le complément d'un non-CE ensemble est C.e. ?

Je pense que je manque quelque chose dans ma compréhension des définitions ...

Answer 1

pour $ k $ même, une langue $ l $ est dans $ \ pi_k $ s'il existe un prédicat récursif $ r $ telle que $$ x \ in l \ longleftrightarrow \ Forall y_1 \ Exist y_2 \ CDOTS \ FORAC Y_ {K-1} \ Existe y_k \, r (x, y_1, \ ldots, y_k) $$ Les quantifiers alternent entre $ \ Forall $ et $ \ existent $

.

.

quand $ k $ est impair, la même définition fonctionne, mais le dernier quantificateur est $ \ Forall $ : $$ x \ in l \ longleftrightarrow \ Forall Y_1 \ Existe y_2 \ CDOT \ Existe y_ {k-1} \ Forall y_k \, r (x, y_1, \ ldots, y_k) $$

Par exemple, la langue de toutes les machines Turn Turing est $ \ PI_2 $ depuis $$ x \ in \ mathsf {tot} \ longleftrightarrow \ forall y \ existez z \, \ text {"machine $ x $ s'arrête sur une entrée $ Y $ à moins de $ z $ étapes"} $$

la classe $ \ sigma_k $ est défini de la même manière, avec le premier quantifier étant $ \ existez $ < / span> plutôt que $ \ Forall $ .

Si vous complétez une langue dans $ \ sigma_k $ vous obtenez un dans $ \ pi_k $ , et vice versa. Cela est dû à la législation de De Morgan pour les quantifiers et du fait que la négation d'un prédicat récursif est également récursive.

Par exemple, la langue de non -Total machines de Turing est $ \ sigma_2 $ depuis $$ x \ in \ in \ mathsf {ntot} \ longleftrightarrow x \ notin \ mathsf {TOT} \ Forallftrightarrow \ Existe y \ Forall Z \, \ Text {"Machine $ x $ x $ Ne pas arrêter d'entrée en entrée $ chez $ z $ Steps "} $$