5.3 Un teorema alla Rasiowa-Sikorski
In questa sezione studieremo i risultati che ci permetteranno di ottenere il teorema di completezza per il calcolo predicativo intuizionista. Dimostreremo in particolare che ogni algebra di Heyting numerabile si pu`o immergere in una opportuna algebra di Heyting costruita su uno spazio topologico in maniera tale che una quantit`a numerabile di suprema venga rispettata.
Iniziamo quindi ricordando la definizione di algebra di Heyting che avevamo proposto nel ca-pito 3: un algebra di Heyting H ≡ hH, 0, 1, ∨, ∧, →i `e una struttura tale che hH, 0, 1, ∨, ∧i `e un reticolo distributivo con minimo elemento 0 e massimo elemento 1 tale che per ogni x, y, z ∈ H, x ∧ y ≤ z iff x ≤ y → z dove intendiamo che la relazione d’ordine ≤ sia quella definita ponendo x ≤ y ≡ (x = x ∧ y).
Si noti che la presenza dell’implicazione permette di dimostrare immediatamente che l’opera-zione ∧ di minimo si distribuisce su tutti i supremi esistenti e non solo su quelli finiti; infatti, se supponiamo che T ⊆ H abbia supremo in H allora x ∧W{t : t ∈ T } ≤ W{x ∧ t : t ∈ T } perch`e, per ogni t ∈ T , x ∧ t ≤ W{x ∧ t : t ∈ T } che implica che t ≤ x → W{x ∧ t : t ∈ T }, e quindi W{t : t ∈ T } ≤ x → W{x ∧ t : t ∈ T } che a sua volta porta a x ∧ W{t : t ∈ T } ≤ W{x ∧ t : t ∈ T };
l’altra disuguaglianza `e immediata.
L’esempio canonico di algebra di Heyting (completa) si ottiene considerando la famiglia degli aperti di un qualsiasi spazio topologico τ su un insieme X, la cui base sia Bτ, ponendo:
0τ ≡ ∅
1τ ≡ X
O1∧τO2 ≡ O1∩ O2 O1∨τO2 ≡ O1∪ O2
O1→τ O2 ≡ S{O ∈ τ : O1∩ O ⊆ O2} =S{b ∈ Bτ: O1∩ b ⊆ O2}
Lo scopo del nostro prossimo teorema `e quello di far vedere che ogni algebra di Heyting numerabile si pu`o immergere in un algebra di Heyting costruita su uno spazio topologico.
Iniziamo questo lavoro ricordando la definizione di filtro e di filtro primo di un algebra di Heyting.
Definition 5.3.1 (Filtro) Sia H una algebra di Heyting. Allora un sottoinsieme F di H `e un filtro se:
1 ∈ F x ∈ F x ≤ y y ∈ F
x ∈ F y ∈ F x ∧ y ∈ F
Definition 5.3.2 (Filtro primo) Sia H una algebra di Heyting e F un suo filtro. Allora F `e un filtro primo se quando x ∨ y ∈ F accade che x ∈ F o y ∈ F .
Per ottenere il nostro risultato ci basta concentrarci su una particolare famiglia di filtri primi, vale a dire quelli che rispettano una famiglia numerabile di sottoinsiemi di H.
Definition 5.3.3 (Filtro che rispetta un sottoinsieme) Sia H una algebra di Heyting, F uno dei suoi filtri e T un sottoinsieme di H dotato di supremo in H. Allora F rispetta T se quando W T ∈ F esiste b ∈ T tale che b ∈ F .
Il nostro scopo `e ora far vedere che in ogni algebra di Heyting esistono filtri che rispettano una quantit`a numerabile di sottoinsiemi.
Theorem 5.3.4 Sia H una algebra di Heyting, x, y ∈ H due elementi di H tali che x 6≤ y e T1, . . . , Tn, . . . una famiglia numerabile di sottoinsiemi di H dotati di supremo. Allora esiste un filtro F di H che contiene x, non contiene y e rispetta tutti i sottoinsiemi T1, . . . , Tn, . . . .
Proof. Costruiremo il filtro richiesto con una procedura che richiede una quantit`a numerabile di passi partendo dal filtro1 F0 =↑ x ≡ {z ∈ H | x ≤ z} e estendendolo via via ad un filtro che rispetta tutti i sottoinsiemi T1, . . . , Tn, . . . . La prima cosa da fare per essere sicuri di ottenere il risultato desiderato `e quella di costruire una nuova lista, ancora numerabile, che contenga ciascuno
1Esercizio: dimostrare che si tratta di un filtro.
dei sottoinsiemi T1, . . . , Tn, . . . una quantit`a numerabile di volte; infatti pu`o ben succedere che il filtro costruito al passo n rispetti il sottoinsieme Tk per il semplice motivo che il suo supremo non gli appartiene mentre potrebbe entrare in un passo successivo e quindi dopo ogni passo deve essere possibile verificare per ogni sottoinsieme Tk la condizione che il filtro considerato lo rispetti.
Al fine di costruire questa nuova lista di sottoinsiemi possiamo semplicemente seguire il metodo noto come “l’abergo di Hilbert” (si veda ad esempio [LeoTof07]), cio`e possiamo considerare la lista W1= T1, W2= T1, W3= T2, W4= T1, W5= T2, W6= T3, . . . .
Poniamo ora c0= x, e quindi F0=↑ c0, e supponiamo, per ipotesi induttiva di aver definito un elemento cn tale che cn 6≤ y e un filtro Fn=↑ cn; definiamo allora
cn+1=
cn se W Wn 6∈ Fn
cn∧ bn se W Wn ∈ Fn
in modo tale che bn sia un elemento di Wn tale che cn∧ bn 6≤ y; di fatto un tale elemento esiste perch`e seW Wn∈ Fn allora, per definizioneW Wn∈↑ cn, e quindi cn≤W Wn; ora se fosse vero che per tutti gli elementi b ∈ Wn accadesse che cn∧ b ≤ y allora cn= cn∧W Wn=W
b∈Wncn∧ b ≤ y che contraddice l’ipotesi induttiva. Quindi (prova classica!) deve esistere almeno un elemento bn ∈ Wn
che soddisfa l’ipotesi richiesta.
Ora possiamo definire il filtro Fn+1 ponendo Fn+1 =↑ cn+1 ed `e immediato verificare che Fn ⊆ Fn+1 e che y 6∈ Fn+1 visto che cn+1 6≤ y. Siamo ora in grado di concludere visto che possiamo dimostrare che il filtro F richiesto nell’enunciato del teorema altro non che F = ∪i∈ωFi. Infatti, F `e un filtro visto che `e il risultato dell’unione di una catena di filtri ognuno contenuto nel sucessivo (esercizio: verificare che questa propriet`a vale); inoltre x ∈ F visto che x ∈ F0 ⊆ F mentre y 6∈ F = ∪i∈ωFi perch`e altrimenti dovrebbe esserci un indice i ∈ ω tale che y ∈ Fi mentre il modo in cui abbiamo definito i filtri della catena esclude che questo possa accadere. Infine F rispetta tutti i sottoinsiemi T1, . . . , Tn, . . . perch`e se ∨Tn ∈ F = ∪i∈ωFi allora c’`e un indice i ∈ ω tale che ∨Tn ∈ Fi e quindi, visto che ogni Tn appare una quantit`a numerabile di volte nella lista W1, . . . , Wm, . . ., per qualche h ≥ i deve accadere che Wh= Tn e quindi ∨Wh= ∨Tn∈ Fi ⊆ Fhe perci`o esiste bh∈ Tn tale che bh∈ Fh+1⊆ F .
Pu`o essere utile notare che il teorema, quando applicato considerando gli elementi 1 e 0, assicura l’esistenza di un filtro che rispetta una quantit`a numerabile di supremi visto che la condizione 1 6≤ 0 vale sempre.
Il precedente teorema pu`o essere utilizzato per dimostrare l’esistenza di un filtro primo che rispetta una quantit`a numerabile di supremi se l’algebra di Heyting che stiamo considerando `e numerabile.
Corollary 5.3.5 (Teorema fondamentale) Sia H una algebra di Heyting numerabile, x e y siano due elmenti di H tali che x 6≤ y e T1, . . . , Tn, . . . sia una quantit`a numerabile di sottoinsiemi di H dotati di supremo in H. Allora esiste un filtro primo che contiene x, non contiene y e rispetta tutti i sottoinsiemi T1, . . . , Tn, . . . .
Dimostrazione. Per ottenere la prova di questo teorema basta osservare che nel caso di un algebra di Heyting numerabile c’`e una quantit`a numerabile di supremi binari e quindi si pu`o ancora utilizzare il precedente teorema per costruire un filtro che rispetti la quantit`a numerabile di supremi binari e la quantit`a numerabile dei supremi dei sottoinsiemi T1, . . . , Tn, . . . visto che mettendo assieme due insiemi numerabili si ottiene ancora un insieme numerabile. Ma allora `e ovvio che quel che si ottiene `e un filtro primo visto che rispetta tutti i supremi binari esistenti.
Il fatto che esistano filtri primi che rispettano una quantit`a numerabile di supremi `e il risultato fondamentale che permette di immergere una algebra di Heyting numerabile nella famiglia degli aperti di uno spazio topologico tramite un morfismo che rispetta tali supremi.
Infatti, se chiamiamo Pt(H) la collezione di tutti i filtri primi di H che rispettano i sottoinsiemi T1, . . . , Tn, . . . e τH allora possiamo costruire la topologia su Pt(H) avente per base BτH i sottoin-siemi ext(x) = {P ∈ Pt(H) | x ∈ P } per x ∈ H. Infatti `e facile verificare che BτH `e una base per
5.3. UN TEOREMA ALLA RASIOWA-SIKORSKI 51
Abbiamo cos`ı visto che la mappa ext `e una mappa dall’algebra di Heyting H all’algebra di Heyting (su) τH che rispetta 0H, 1H e ∧H. Per vedere che si tratta proprio di un morfismo, che rispetta cio`e tutte le operazioni di algebra di Heyting, `e conveniente verificare prima di tutto che
ext(x) ⊆ ext(y) se e solo se x ≤ y.
Possiamo farlo nel modo che segue. Se x ≤ y allora, per ogni filtro P ∈ ext(x), i.e. tale che x ∈ P , otteniamo che y ∈ P , cio`e, P ∈ ext(y); d’altra parte, sex 6≤ y allora per il corollario 5.3.5 esiste un filtro primo P che rispetta tutti i supremi considerati e tale che contiene x e non contine y, cio`e, tale che P ∈ ext(x) ma P 6∈ ext(y).
Finalmente possiamo dimostrare che ext(−) `e una immersione dell’algebra di Heyting H nella topologia τH. Infatti
Inoltre, visto il modo in cui abbiamo definito gli elementi di Pt(H), possiamo dimostrare che ext(−) rispetta anche tutti i supremi dei sottoinsiemi T1, . . . , Tn, . . . che stiamo considerando.
Infine `e interessante notare che sono rispettati non solo i supremi dei sottoinsiemi T1, . . . , Tn, . . . ma anche tutti gli infimi esistenti. Infatti
ext(V
Per concludere la dimostrazione che ext(−) `e una immersione di H in τH dobbiamo ancora dimostrare che `e una mappa iniettiva, vale a dore che se x 6= y allora ext(x) 6= ext(y). Ma questo
`e ovvio visto che se x 6= y allora x 6≤ y o y 6≤ x e quindi ext(x) 6⊆ ext(y) o ext(y) 6⊆ ext(x).