2.3 Gradi dialettici, gradi quasidialettici, gradi di Turing e gradi di enu-
2.4.2 Insiemi dialetici e gerachia di Ershov
Caratterizziamo ora i livelli a ∈ O della gerarchia di Ershov contenenti insiemi dialettici Σ−1
a . Il primo punto del Teorema 2.4.5 è essenzialmente dovuto a Bernardi
[10].
Teorema 2.4.5. Valgono le seguenti proprietà:
1. Se Ad è un insieme dialettico, allora Ad è ω-c.e.;
2. per ogni n con 2 ≤ n ≤ ω, esiste un insieme dialettico proprio n-c.e..
Dimostrazione. Iniziamo dal dimostrare il punto (1). La proposizione segue dal fatto che se Ad è dialettico allora Ad ≤tt ∅0 ([10]), e dall’altro lato, ogni insieme
B ≤tt ∅0 è ω-c.e. (cf. [122]). Diamo ora una prova diretta del fatto che Ad è ω-c.e.,
dove ci riferiamo all’approssimazione {Ad,s}s∈ω di Ad, data dall’insieme delle tesi
provvisorie. Sia σ(y, s) la stringa di lunghezza y + 1, σ(y, s)(i) = 1, if fi ∈ Ls(y + 1), 0 if fi ∈ L/ s(y + 1).
Dimostriamo che per ogni y, σ(y, s) può cambiare al massimo 2y+1 volte. Questa
vale banalmente per y = 0. Se t0 è il minimo passo al quale σ(y, s) non cambia più,
allora dopo t0, σ(y + 1, s) può cambiare nuovamente al cambiare di χAd,s(fy+1). Ma
questo può avvenire al massimo altre due volte. Dunque σ(y + 1, s) può cambiare al massimo 2y+2 volte. Da questo segue banalmente che, in generale, χ
Ad,s(fy) e
dunque σ(y, s) può cambiare al massimo 2y+1 volte. Questo conclude la prova di
(1).
Mostriamo ora il punto (2). Sia 2 ≤ n < ω e sia {Ve : e ∈ ω} una enumerazione
computabile degli insiemi (n−1)-c.e. nel senso della definizione del Lemma 2.4.3 (1), e corrispondentemente sia {Ve,s : e, s ∈ ω}una sequenza computabile di insiemi finiti
tali che, per ogni e, {Ve,s : s ∈ ω}è una approssimazione (n − 1) a Ve. Prendiamo
dove ci riferiamo alla coppia di funzioni computabili hge, heiche testimoniano che Ve
è in Σ−1
n−1, come nel Lemma 2.4.3 (1); notiamo che, per ogni x,
|{s : χVe,s(x) 6= χVe,s+1(x)}| ≤ n − 1.
Costruiamo un sistema dialettico d tale che Ad6= Ve, per ogni e e Ad∈ Σ−1n . Il nostro
sistema dialettico sarà della forma d = hH, f, ci, dove noi costruiremo H, mentre f è la funzione di identità, cioè fx = x e c = 1. Al fine di rendere la costruzione
più semplice da descrivere, l’operatore di enumerazione H che costruiremo non sarà un operatore di chiusura. Tuttavia, applicando la procedura dialettica al fine di determinare l’insieme delle tesi finali (che non utilizza il fatto che l’operatore di enumerazione è un operatore di chiusura), la definizione di Ad rimane legittima:
proveremo, nel Lemma 2.4.10, che Ad= Ad0 dove d0= hH0, f, cie H0 è un operatore
di chiusura.
Descrizione informale della costruzione La costruzione è per passi. Al passo s definiamo:
1. una approssimazione Hs all’operatore di enumerazione H;
2. i valori g(x, s) di una funzione computabile; la costruzione garantirà che per ogni x, esiste limsg(x, s), e di fatto |{s : g(x, s) 6= g(x, s + 1)}| ≤ n (quindi
A = {x : limsg(x, s) = 1}è in Σ−1n ) e A 6= Ve per ogni e.
In altre parole, costruiamo un insieme A con la proprietà desiderata che A sia n- c.e., ma non (n − 1)-c.e.; contemporaneamente, costruiamo H, dal definire passo dopo passo una approssimazione computabile a H; osserviamo che A = Ad, dove
d = hH, f, ci.
Richieste. In aggiunta alle richieste generali che A = Ad, e A è n-c.e., le richieste
da soddisfare sono, per ogni e ∈ ω:
Pe: A 6= Ve.
Strategia per soddisfare Pe. Nominiamo un testimone be, dove inizialmente
be∈ A(quindi inizialmente, cambiamo χA(be)(o, piuttosto, il valore corrente χAs(be)
di χA(be)) dal valore 0 al valore 1); allora, ogni vola che χA(be) = χVe(be), rispon-
diamo cambiando χA(be), così da avere χA(be) 6= χVe(be). Fintanto che χVe(be) può
cambiare al massimo n − 1 volte, segue che χA(be) cambierà al massimo n volte,
entrambi gli insiemi A e Ve finiranno con i valori finali χA(be) 6= χVe(be), come desi-
Dunque, ciò che dobbiamo veramente spiegare è come costruire simultaneamente H, in modo da ottenere A = Ad. A tal fine, un testimone per Pe è un intervallo
chiuso I(e) = [ae, be], dove definiamo be = ae+ n − 2. Supponiamo che per ogni e,
ae+1= ae+ n − 1, così che gli insiemi I(e) sono a due a due disgiunti. Supponiamo
inoltre che a0= 2 = c + 1.
Quando designiamo I(e), momentaneamente poniamo I(e) ⊆ A, e eseguiamo il seguente algoritmo, dove i numeri di cicli sono contati da ie:
1. poni ie= n − 1;
2. se be ∈ Ve, togli be da A e aggiungi l’assioma hc, {ae+ j, be: j < ie}i ∈ H; poni
ie= ie− 1; vai a (3);
3. se be ∈ V/ e, allora inserisci be in A; elimina a + ie da A e aggiungi l’assioma
hc, {ae + ie}i ∈ H (dal quale segue che ae+ ie non appartiene a Ad); poni
ie= ie− 1; vai a (2).
Analisi dei risultati della strategia per Pe. Analizziamo più in dettaglio i
risultati della strategia per Pe. Segnatamente verifichiamo la strategia per ottenere
A = Ad, dove d = hH, f, ci.
Se ie= n − 1è il valore finale di ie, allora non aggiungiamo nessun assioma in H che
involve elementi di I(e), dunque be∈ Ad e ae+ j ∈ Ad, per ogni j < n − 2. Questi
valori di Ad coincidono con quelli di A relativamente agli elementi di I(e).
Supponiamo che il valore di ie decresce a ie = i da ie = i + 1. Usiamo il Lemma
2.2.30, il Corollario 2.2.32, un semplice argomento induttivo su i e la definizione di H. Assumiamo per induzione che non siano stati dati assiomi hc, {ae+ j}i ∈ H,
per ogni j < i; nessun assioma hc, {ae+ j, be : j < i}i ∈ H; e ci siano già assiomi
hc, {ae+ j}i ∈ H, per ogni i < j < n − 2.
1. se be è tolto da A, allora aggiungiamo l’assioma hc, {ae+ j, be : j < i}i ∈ H;
concludiamo che se questo è il valore finale di ie, allora be ∈ A/ d, fintanto
{ae+ j : j < i} ⊆ Ad, e quindi c ∈ H(L(be) ∪ {be}); inoltre ae + j /∈ Ad,
per ogni i ≤ j < n − 2; il corrispondente valore di χAd sugli elementi di I(e)
coincide con quelli di χA;
2. se be è reinserito in A, allora aggiungiamo l’assioma hc, {ae+ i}i ∈ H, dunque
ae+ i sarà fuori Ad; quindi l’assioma hc, {ae+ j, be : j < i + 1}i ∈ H non si
applica e se i è il valore finale di ie, allora be ∈ Ad poiché c /∈ H(L(be) ∪ {be}).
Inoltre abbiamo che {ae+j : j < i} ⊆ Ad, e ae+j /∈ Ad, per ogni i < j < n−1;
il corrispondente valore di χAd sugli elementi di I(e) coincide con quelli di χA.
La costruzione. La costruzione è per passi. Faremo uso dei parametri ie,s, ap- prossimando al passo s il numero ie come nella sezione 2.4.2.
Definizione 2.4.6. Un richiedente Pe richiede attenzione al passo s, se s > 0, e
(nell’ordine) ie,s non è definito oppure be∈ Ve,s se e solo se be∈ As−1.
Passo 0. Sia H0 = {h0, ∅i, hc, {c}i}. (Abbiamo 0 ∈ H(∅) al fine di soddisfare la
definizione di sistema dialettico, che chiede H(∅) 6= ∅; chiediamo invece hc, {c}i ∈ H0
poiché avremmo immediatamente c ∈ H(X) se c ∈ X.) Sia anche g(x, 0) = 0, per ogni x. Poniamo ie,0 indefinito, per ogni e.
Passo s + 1. Consideriamo tutti gli e ≤ s tali che Pe richiedono attenzione al passo
s + 1.
1. Se ie,s non è definito, allora poniamo ie,s+1= n − 1. Poniamo I(e) ⊆ As+1 dal
definire g(x, s + 1) = 1, per ogni numero x ∈ I(e).
2. Altrimenti (necessariamente, ie,s > 0) definiamo ie,s+1= ie,s− 1, e:
(a) se be∈ Ve,s+1allora aggiungiamo l’assioma hc, {ae+ j, be: j < ie,s}i ∈ H,
definiamo g(be, s + 1) = 0;
(b) se be ∈ V/ e,s+1allora aggiungiamo l’assioma hc, {ae+ ie,s}i ∈ H, definiamo
g(ae+ ie,s, s + 1) = 0, g(be, s + 1) = 1.
Poniamo Hs+1 come Hs più gli assiomi per H aggiunti al passo s + 1. Sia inoltre
g(0, s + 1) = 1. A meno che non esplicitamente ridefiniti durante il passo s + 1, tutti i restanti parametri e valori mantengono lo stesso valore del passo s. In particolare g(c, s + 1) = 0. Vai al passo s + 2.
Verifica. La verifica si basa sui seguenti lemmi. Lemma 2.4.7. Aè n-c.e..
Dimostrazione. Se un numero x cade in qualche I(e), allora è chiaro che χAs(x) =
g(x, s)può cambiare al massimo n volte, come abbiamo già visto nella sezione 2.4.2. Altrimenti, x ∈ {0, 1}: allora χAs(x) cambia da 0 a 1 esattamente una volta, se
x = 0, e χAs(x) non cambia mai, se x = 1 = c.
Lemma 2.4.8. Per ogni e, A soddisfa Pe.
Dimostrazione. Cambiamo il valore χAs(be) tante volte quanto è necessario diago-
nalizzare contro il valore finale χVe(be).
Dimostrazione. Per induzione su x, possiamo facilmente mostrare che χA(x) =
χAd(x). Questo è certamente vero per x = 0, 1. Supponiamo che questo valga
per ogni x < ae. Non appena Ls(ae) si stabilizza, la procedura dialettica simula il
modulo per Pe, anche se non in modo sincronizzato, e in modo più lento dal momento
che i numeri devono essere proposti e scartati uno per uno in diversi passi. Come è chiaro dalla discussione in sezione 2.4.2, gli assiomi che aggiungiamo a H in modo da soddisfare Pe raggiungeranno l’obiettivo desiderato di porre χA(x) = χAd(x)per
ogni x ∈ I(e).
Lemma 2.4.10. Esiste un sistema dialettico d0 tale che Ad= Ad0.
Dimostrazione. Prendiamo
H0= H ∪ {hx, {x}i : x ∈ ω} ∪ {hx, Di : x ∈ ω, hc, Di ∈ H}.
È facile vedere che H0 è un operatore di chiusura, e ovviamente c ∈ H0(X)se e solo
se c ∈ H(X), dal modo in cui abbiamo definito gli assiomi di H che coinvolgono c. Quindi, d0 = hH0, f, ciè il sistema dialettico desiderato.
Infine mostriamo brevemente come dimostrare il punto (2) quando n = ω.
Iniziamo dal prendere un elenco effettivo di tutti gli insiemi n-c.e., per i vari n ≥ 1: per esempio, prendiamo Zhe,ni = Ven, dove {Ven}e∈ω,n≥1 è una lista computabile di
tutti gli insiemi n-c.e..
Un testimone per il requisito Phe,ni (con e ≥ 0 e n ≥ 1) è ora un intervallo chiuso
I(he, ni) = [ahe,ni, ahe,ni+ n − 1]: questi intervalli sono scelti in modo che ahe,ni≥ 2,
e tali da formare una partizione di ω. Il resto della prova è esattamente come prima, con la sola differenza che i testimoni sono ora intervalli chiusi di lunghezza variabile.
Nota 2.4.11. Notiamo che la prova di (2) del teorema precedente non utilizza alcuna funzione di priorità. Ogni requisito mantiene il proprio testimone per sempre e non vi è alcuna interferenza tra le diverse strategie per i vari requisiti.
Nota 2.4.12. Il punto (2) del Teorema 2.4.5 non può essere esteso in modo da includere il caso n = 1, perché ogni insieme dialettico c.e. è decidibile ([88]) e quindi ogni insieme dialettico 1-c.e. è anche 0-c.e..