Il teorema del riso-Shapiro è bidirezionale?

Question

Il teorema di riso-Shapiro afferma che

Versione A.

Permettere $ Gamma $ essere un insieme di set computabilmente enumerabili e $ I = {e: w_e in gamma } $ Il suo indice impostato in un elemento ammissibile di set CE. Se $ I $ è ce, poi per tutti $ x $, $ x in i $ se e solo se c'è $ y in i $ tale che $ W_y $ è un sottoinsieme finito di $ W_x $.

O equivalentemente

$ I $ è ce $ Rightarrow $

$ ~~~~ (1): ~ forall x, y ~ (x in i land w_x sottoseteq w_y destrorrow y in i) $

$ land ~~ (2): ~ forall x ~ (x in i destrowarw esiste y ~ (y in i land w_y ~ text {è finito} land w_y sottoseteq w_x)) $

La mia domanda è se è vero anche il contrario, cioè, se (1) e (2) tieni, quindi $ I $ è ce

---

Quindi ho trovato un'altra formulazione (più debole) del teorema in H. Rogers Teoria delle funzioni ricorsive e calcolo efficace p. 324, che afferma:

Versione B.

$ I $ è ce $ iff ~ (3): ~ forall x (x in i leftrighrow esiste u (d_ {f (u)} sottoseteq w_x)) $ Per una funzione totalmente calcolabile $ f $

dove $ D $ è L'enumerazione canonica dei set finiti (Vedi Definizione 2.4).

(3) lo implica $ I $ è CE, perché è solo un $ Sigma_1 $ rappresentazione di $ I $. D'altra parte, se $ I $ è CE, di SMN Teorema Prendi la funzione totalmente calcolabile $ g $ essere definito tale che $ W_ {g (x)} = d_x $. Ora il set $ g^{-1} (i) = {x: esiste y (g (x) = y land y in i) } $ è anche CE, quindi ci deve essere una funzione totalmente calcolabile $ f $ tale che $ Intervallo (f) = g^{-1} (i) $. Quindi, dalla versione A del teorema, abbiamo anche (1) e (2), il che implica che questo $ f $ è la funzione che soddisfa (3).

---

Ho anche trovato queste Due Risposte che indicano il teorema in forma bidirezionale, ma con un'ulteriore condizione:

Versione C.

$ I $ è ce $ iff (1) Land (2) $

$ ~~~~~~~~~~~~~~~~~ Land (4): ~ {e: d_e in gamma } $ è ce

Ora questo impostato in (4) è solo il $ g^{-1} (i) $ definito sopra, dove abbiamo appena visto che è davvero CE dal solo fatto che $ I $ è CE, quindi la mia ipotesi primitiva è che (4) è l'ingrediente per dimostrare l'altra direzione.

---

Considerando tutte le osservazioni sopra, la mia domanda è se la direzione da destra a sinistra è generalmente, IE fa (1) e (2) implica $ I $ è CE? E c'è un controesempio se non riesce? Supponendo (4), possiamo deducarlo $ I $ è CE? E questo significa che il controesempio ricercato dovrebbe confutare (4)?