2.2 Sistemi dialettici e sistemi quasidialettici: definizione e primi risultati
2.2.2 Sistemi dialettici rivisitati
Riformuliamo ora la definizione originale di Magari in un linguaggio più conveniente ai nostri scopi. Nel resto di questo capitolo denoteremo f(i) con fi. C’è un modo
preciso in cui possiamo descrivere l’operatore H associato ad un sistema dialettico come un operatore di enumerazione. Ricordiamo che un operatore di enumerazione può essere composto in modo uniforme: dato un operatore di enumerazione Ψ, sia
Ψn la composizione di Ψ con se stesso iterato n volte, cioè Ψn+1(X) = Ψ(Ψn(X)), dove
Ψ0 = { hx, { x }i : x ∈ ω } . Allora la relazione hx, Di ∈ Ψn (in n, x, D) è c.e..
Posto
Ψω= {hx, Di : (∃n)[hx, Di ∈ Ψn]} vale il seguente:
Lemma 2.2.7. Se Ψ è un operatore di enumerazione tale che Ψ(Y ) ⊇ Y per ogni Y, allora per ogni X, Ψω(X) è il minimo punto fisso Y di Ψ, con Y ⊇ X. Inoltre,
Ψω è un operatore di enumerazione di chiusura algebrico. Inversamente, se Ψ è un operatore di enumerazione di chiusura algebrico, allora Ψ = Ψω.
Dimostrazione. Notiamo che:
Ψω(X) ⊆ Ψ(Ψω(X)),
dunque assumiamo che per ogni Y , Y ⊆ Ψ(Y ). Se x ∈ Ψ(Ψω(X)) allora esiste un
insieme finito D e un numero n, tale che
hx, Di ∈ Ψ & D ⊆ Ψn(X), quindi x ∈ Ψn+1(X)e allora x ∈ Ψω(X).
Assumiamo ora che X ⊆ Y e Ψ(Y ) = Y . Per induzione su n è facile vedere che per ogni n, Ψn(X) ⊆ Y, quindi Ψω(X) ⊆ Y. Le rimanenti asserzioni del lemma sono
immediate.
Sia d = hh, f, ci un sistema dialettico e sia H l’operatore di chiusura associato a d. Lemma 2.2.8. H è un operatore di enumerazione e per ogni insieme X, H(X) è il minimo punto fisso Y ⊇ X dell’operatore di enumerazione Ψ = Φ ∪ {hx, {x}i : x ∈ ω}, dove
Φ = { hx, Di : x ∈ Wh(D)} .
Dimostrazione. In cioè che segue { Φs: s ∈ ω }è un’approssimazione computabile di
Φ. Prima di tutto, poiché per ogni insieme Y , Y ⊆ Ψ(Y ), è chiaro che H(X) ⊆ Ψ(H(X)). Per mostrare Ψ(H(X)) ⊆ H(X), notiamo che:
x ∈ Ψ(H(X)) ⇒ (∃E ∈ 2<ω)[E ⊆ H(X) & x ∈ Ψ(E)]
⇒ (∃E ∈ 2<ω)(∃D ∈ 2<ω)(∃s)[D ⊆ X & E ⊆ Ks(D)
& [x ∈ Φs+1(E) ∨ x ∈ E]]
⇒ (∃D ∈ 2<ω)[D ⊆ X & x ∈ Ks+1(D)]
La seconda implicazione è motivata dal fato che per ogni e ∈ E, dove E è un insieme finito, esistono un s e un insieme finito D tali che e ∈ Ks(D), ma allora usando la
proprietà di monotonicità di Ks(D) (K aumenta al crescere di s e di D: vedi [88])
esistono almeno un s e un ⊆-minimale D, tale che E ⊆ Ks(D).
In virtù del Lemma 2.2.7, basta ora mostrare che H(X) ⊆ Ψω(X). Per ogni insieme
finito D, usando il fatto che per ogni insieme Y , Φ ⊆ Ψ e Y ⊆ Ψ(Y ), è facile vedere per induzione su s che Ks(D) ⊆ Ψs+1(D). Ora, se x ∈ H(X) allora esistono un
s e un insieme finito D tale che x ∈ Ks(D): questo implica che esiste un insieme
finito E tale che x ∈ Φs+1(E) e E ⊆ Ks(D); quindi x ∈ Ψ(Ψs+1(D)), che implica
x ∈ Ψω(X).
Sistemi dialettici rivisitati: definizione
Nella prossima definizione introduciamo i sistemi dialettici rivisitati. Nel Teore- ma 2.2.13 mostreremo l’equivalenza tra questi e i sistemi dialettici come definiti da Magari.
Definizione 2.2.9. Un sistema dialettico rivisitato è una tripla d = hH, f, ci, dove f è una permutazione computabile di ω, c ∈ ω e H è un operatore di enumerazione tale che H(∅) 6= ∅, H({c}) = ω e inoltre H è un operatore di chiusura algebrico, cioè per ogni X ⊆ ω, H soddisfa le seguenti proprietà:
• X ⊆ H(X);
• H(X) ⊇ H(H(X)). Insiemi dialettici rivisitati
Sia d = hH, f, ci un sistema dialettico rivisitato e sia {Hs}s∈ω una approssimazione
computabile a H (il Lemma 2.2.12 (3) stabilirà l’indipendenza dell’approssimazione). Definizione 2.2.10. Dati d e {Hs}s∈ω come sopra, definiamo per induzione i se-
guenti parametri computabili: As (un insieme finito), rs (una funzione tale che per
ogni x, rs(x) = ∅ oppure rs(x) = {fx}), p(s) (un numero, il più grande numero m
tale che rs(m) 6= ∅), h(s) (un numero). In aggiunta definiremo alcuni parametri
derivati: Ls(x) =
S
y<xrs(y) e per ogni i < p(s), χs(i) =
S j≤iHs(Ls(j)). Passo 0. Definiamo p(0) = 0, h(0) = 0, r0(x) = {f0} se x = 0, ∅ se x > 0; e poniamo A0 = ∅.
Passo s + 1.
Sia p(s) = m. Distinguiamo i seguenti casi:
1. non esistono z ≤ m tali che c ∈ χs(z): in questo caso poniamo p(s+1) = m+1
e definiamo rs+1(x) = rs(x) x ≤ m, {fm+1} se x = m + 1, ∅ se x > m + 1;
2. esistono z ≤ m tali che c ∈ χs(z): in questo caso poniamo p(s + 1) = z + 1 e
definiamo rs+1(x) = rs(x) se x < z, {fz+1} se x = z + 1, ∅ se x = z or x > z + 1.
Infine definiamo h(s+1) = p(s+1) se si applica la Clausola (1), altrimenti h(s+1) = p(s + 1) − 1 e poniamo
As+1=
[
i<h(s+1)
χs+1(i)(= Hs+1(Ls+1(h(s + 1) − 1)))
(dove As+1 = ∅, se h(s + 1) = 0). Quest’ultima uguaglianza è giustificata dalla
monotonia rispetto alla inclusione di Hs+1.
La figura 2.1 e la figura 2.2 illustrano il passaggio dal passo s al passo s+1, in accordo, rispettivamente, alla Clausola (1) e alla Clausola (2) della Definizione 2.2.10. Nelle figure, se fv è posizionato sopra v allora r(v) = {fv}, altrimenti r(v) = ∅.
Figura 2.1: Dal passo s (configurazione prima sequenza) al passo s+1 (configurazione seconda sequenza) utilizzando la Clausola (1).
Definizione 2.2.11. Chiamiamo As l’insieme delle tesi provvisorie di d al passo s. L’insieme Ad, definito nel seguente modo:
Figura 2.2: Dal passo s (configurazione prima sequenza) al passo s+1 (configurazione seconda sequenza) utilizzando la Clausola (2).
è chiamato l’insieme delle tesi finali di d. Spesso scriveremo Ad,s = As quando
vogliamo specificare il sistema dialettico rivisitato d. Un insieme A ⊆ ω è chiamato dialettico rivisitato se A = Ad per qualche sistema dialettico rivisitato d.
Sebbene la sequenza {Ad,s}s∈ω dipende dalla scelta dell’approssimazione ad H, dal
Lemma 2.2.12 segue che lo stesso non vale per l’insieme Ad. Le dimostrazioni dei
punti (1) e (2) sono posticipate alla Sezione 2.2.4, dove proveremo la stessa pro- posizione per i sistemi quasidialettici, dei quali, come vedremo, i sistemi dialettici rivisitati sono un caso particolare.
Lemma 2.2.12. Sia d = hH, f, ci un sistema dialettico rivisitato. Per ogni x, 1. esiste Ad(x) = limsAs(x);
2. esiste r(x) = limsrs(x); fx ∈ Ad se e solo se r(x) = {fx}; ponendo L(x) =
S
y<xr(y) segue che
fx∈ Ad⇔ c /∈ H(L(x) ∪ {fx});
3. r(x), L(x), e l’insieme Ad non dipendono dalla scelta dell’approssimazione
computabile ad H.
Dimostrazione. La dimostrazione di (1) e (2) sono posticipate alla Sezione 2.2.4: (1) seguirà dal Corollario 2.2.32; (2) sarà invece una conseguenza del Lemma 2.2.22, Lemma 2.2.28 e del Lemma 2.2.30.
Infine il punto (3) segue facilmente da (2) per induzione su x. Difatti L(0) = ∅ e f0 ∈ Ad se e solo se r(0) = {f0}, se e solo se c /∈ H({f0}). Assumiamo l’ipotesi per
x, allora L(x + 1) = L(x) ∪ r(x) e dunque fx+1∈ Ad se e solo se r(x + 1) = {fx+1}
2.2.3 Equivalenza tra sistemi dialettici e sistemi dialettici rivisitati Non è difficile vedere che i sistemi dialettici rivisitati sono equivalenti ai sistemi dialettici come definiti originariamente da Magari. In questa sezione mostriamo infatti che tali sistemi danno origine alla stessa classe di insiemi dialettici.
Teorema 2.2.13. Possiamo passare uniformemente da una funzione computabile h ad un operatore di chiusura algebrico H tale che: per ogni coppia f, c (dove f è una funzione computabile e c ∈ ω) se d = hh, f, ci è un sistema dialettico allora d0 = hH, f, ci è un sistema dialettico rivisitato tale che Ad = Ad0. Inversamente,
possiamo passare uniformemente da un operatore di enumerazione H a una funzione computabile h tale che: per ogni coppia f, c (dove f è una funzione computabile e c ∈ ω) se d0 = hH0, f, ci è un sistema dialettico rivisitato allora d = hh, f, ci è un sistema dialettico tale che Ad0 = Ad.
Dimostrazione. Data una funzione computabile h, come H prendiamo l’operatore di enumerazione associato a d. Notiamo che, anche in mancanza del sistema dialettico d, possiamo costruire in modo uniforme un tale H da h (basta infatti prendere H = Ψω, dove Ψ è costruito da h come nella prova del Lemma 2.2.8).
Inversamente, dato un operatore di enumerazione H0, sia h una funzione computabile
tale che h(D) è un indice c.e. di H0(D), per ogni insieme finito D. Sia ora d0 =
hH0, f, ci un sistema dialettico rivisitato e sia Ψ = Φ ∪ {hx, {x}i : x ∈ ω}, dove
Φ = { hx, Di : x ∈ Wh(D)} .
Allora, per le assunzioni su H0, Ψ(D) = Φ(D) = H0(D)per ogni insieme finito D e
Ψω = Ψ = H0. D’altro canto, per il Lemma 2.2.8, l’operatore di chiusura algebrico
H associato a d = hh, f, ci soddisfa H = Ψω, quindi H = H0.
Il resto della prova segue dalla monotonicità dell’operatore di enumerazione, dalle loro approssimazioni e dagli operatori Ks introdotti nella definizione di Magari. Al
passo n + 1 esiste una ovvia correlazione tra la sequenza hhx0, X0i, hx1, X1i, . . . , hxm, Xmii
considerata nella Definizione 2.2.1 e la sequenza
hhx0, χn(x0)i, hx1, χn(x1)i, . . . , hxm, χn(m)ii
che segue dalla Definizione 2.2.9, dove, in quest’ultimo caso, hx0, . . . , xmi è la lista,
in ordine crescente, di tutti gli i tali che rn(i) 6= ∅. Se d e d0 sono rispettivamente
un sistema dialettico (come definito da Magari) e un sistema dialettico rivisitato tra loro connessi come ora visto, allora al passo s abbiamo Ad,s 6= Ad0,s ma, come
è facile vedere dal Lemma 2.2.5 (che caratterizza Ad) e dal Lemma 2.2.12 (2) (che
In virtù del Teorema 2.2.13, nel resto del capitolo, i sistemi dialettici saranno sem- pre presentati come sistemi dialettici rivisitati, cioè come triple hH, f, ci dove H è un operatore di chiusura algebrico; oppure come una tripla hH, f, ci dove H è un operatore di enumerazione tale che X ⊆ H(X), per ogni insieme X. In quest’ultimo caso, usando il Teorema 2.2.13, ci riferiremo di fatto a d = hHω, f, ci. Notiamo che la
richiesta X ⊆ H(X), per ogni X, non elimina l’effettività. Possiamo difatti sempre passare in modo effettivo da H all’operatore di enumerazione H ∪{ hx, {x}i : x ∈ ω }, il quale, per ogni X ⊆ ω, soddisfa la richiesta X ⊆ H(X). Conseguentemente gli insiemi dialettici saranno sempre presentati come insiemi dialettici rivisitati. Lemma 2.2.14 ([88]). Se A ∈ Π01 e A 6= ω, allora esiste un sistema dialettico d tale che A = Ad.
Dimostrazione. Se A = ∅ allora A = Adper ogni sistema dialettico d = hH, f, ci tale
che c ∈ H(∅). Sia allora A 6= ∅ e assumiamo che A ∈ Π0
1 e Ac6= ∅. Siano a ∈ A e
b ∈ Ac. Definiamo
H = {hy, {x}i : x /∈ A, y ∈ ω} ∪ {ha, ∅i} ∪ {hx, {x}i : x ∈ ω}.
(Poniamo ha, ∅i ∈ H per soddisfare H(∅) 6= ∅.) Notiamo che H è un operatore di chiusura algebrico. Infatti, sia X ⊆ ω: chiaramente X ⊆ H(X). D’altro canto, se X ∩ Ac6= ∅ allora H(X) = ω, quindi H(X) = H(H(X)). Se X ⊆ A, allora H(X) = X ∪ {a}, da cui segue ancora che H(X) = H(H(X)). Prendiamo d = hH, f, bi, dove f è la funzione di identità. È facile vedere che d è il sistema dialettico desiderato. Sebbene ogni insieme co-c.e.5, differente da ω, sia dialettico, è interessante osservare
(vedi [88]) che nessun insieme c.e. è dialettico a meno che non sia decidibile. Dal momento che gli insiemi dialettici che rappresentano una teoria formale corrispon- dono al completamento di tale teoria (vedi la Nota 2.2.6), questa osservazione non è sorprende poiché corrisponde al ben noto fatto che ogni teoria c.e. completa è de- cidibile. Notiamo inoltre che ω non è un sistema dialettico poiché, per ogni sistema dialettico d, non può mai accadere che c ∈ Ad.