Mostriamo ora come costruire un modello insiemistico in cui sia possibile interpretare il calcolo di Joyal. L’idea che sta alla base di questa costruzione `e che, dato un modello di ZF, `e sempre possibile identificare un sottoinsieme di un dato insieme con la sua funzione caratteristica.
Supponiamo dunque di lavorare dentro un modello di ZF; conveniamo di indicare con {0, 1} l’interpretazione della formula
∀y (¬(y ∈ x)) ∨ ∀y (y ∈ x ↔ ∀z ¬(z ∈ y));
inoltre, dati gli insiemi A e B, con la scrittura BA si intender`a l’insieme delle
funzioni di dominio A e codominio B.
Un modello insiemistico del calcolo di Joyal consiste nel dare un insieme S ed una interpretazione, [[ ]]S, che associa:
(i) ad ogni sorta S un insieme A. Tale assegnazione si estende ai tipi ponendo:
[[Ω( ~S)]]S = {0, 1}([[S1]]S×...×[[Sn]]S).
L’interpretazione di Ω( ) sar`a dunque l’insieme {0, 1}( ) che identifi- chiamo con {0, 1}.
(ii) Per ogni simbolo funzionale f di dominio (S1, . . . , Sn) e codominio S
una funzione F :
F : [[S1]]S× . . . × [[Sn]]S −→ [[S]]S.
Come in 3.2 estendiamo tale interpretazione ai termini del linguaggio: se t `e un termine di tipo S nella cui definizione le variabili libere occorrono fra le variabili x1, . . . , xn di tipo rispettivamente S1, . . . , Sn allora l’interpre-
tazione di t `e data dalla funzione:
[[~x: ~S | t]]S: [[S1]]S× . . . × [[Sn]]S −→ [[S]]S.
Analogamente al caso generale, la definizione dell’interpretazione dei termini `e data, come in 3.2, per i 7 casi che definiscono termini e formule, ricordando che7:
• true = >: 1 → {0, 1}, ⊥: 0 → {0, 1};
• δA: A × A → Ω `e la funzione caratteristica di hidA, idAi : A → A × A;
• evA: A × {0, 1}A → {0, 1} `e la funzione caratteristica di ∈A,→ A ×
{0, 1}Adove ∈
A= {x, χX A×{0, 1}A| χX(x) = 1} e χX `e la funzione
caratteristica del sottoinsieme X di A ossia la funzione χX(x) =
(
1 se xX, 0 altrimenti.
• Per ogni funzione H: A × B → {0, 1} esiste una ed una sola funzione H∼: B → {0, 1}Atale che evA◦ (idA× H∼) = H ossia per ogni H esiste
H∼ tale che il diagramma
A × B
A × {0, 1}A {0, 1}
idA× H∼
evA
H
commuti.
Un sequente ~x: ~S φ ⇒ ψ sar`a detto valido secondo l’interpretazione [[ ]]S se per ogni assegnazione a1A1, . . . anAn alle variabili x1, . . . , xn risulta
[[φ(a1, . . . , an)]]S≤ [[ψ(a1, . . . , an)]]S.
Si osservi che tale definizione `e perfettamente coerente con quella data in 3.2: si ha infatti [[φ(a1, . . . , an)]]S ≤ [[ψ(a1, . . . , an)]]S se e solo se [[~x: ~S | φ]] =
Completezza del calcolo di
Joyal
In questo capitolo dimostriamo un teorema di completezza per il calcolo di Joyal. Questo ci permetter`a di concludere che:
• l’interpretazione data `e corretta, ossia i sequenti dimostrabili nel calcolo di Joyal sono validi per ogni interpretazione del nostro sistema formale in un topos;
• la semantica che abbiamo fornito `e completa, ossia i sequenti dimo- strabili nel nostro calcolo sono esattamente le formule vere in ogni topos.
Dato un insieme di sequenti Γ, diremo che il sequente ~x: ~S φ ⇒ ψ `e di- mostrabile a partire da Γ, e scriveremo Γ ` ~x: ~S φ ⇒ ψ, se esiste una dimostrazione formale di ~x: ~S φ ⇒ ψ in cui occorrono solo gli assiomi, le regole di inferenza del calcolo di Joyal e i sequenti di Γ.
Osservazione 7. E’ importante notare che il teorema di completezza che di- mostriamo vale per topos ‘piccoli’ (nei quali la collezione degli oggetti e quel- la dei morfismi sono insiemi). Per avere un risultato valido per tutti i topos (compresi quelli nei quali la collezione degli oggetti `e una classe propria) si
pu`o modificare la definizione 3.4 ammettendo come domini di interpretazio- ne classi proprie oltre che insiemi (anche se, in tal caso, non `e pi`u corretto definirli modelli).
Enunciamo alcuni risultati che ci saranno utili nel corso della dimostrazio- ne: il primo `e un teorema di deduzione, il secondo un lemma di sostituzione, entrambi formulati in maniera opportuna per il nostro calcolo.
Teorema 4.0.1. (di deduzione) Dato un insieme di sequenti Γ ed un sequente ~x: ~S φ ⇒ ψ si ha:
Γ ` ~x: ~S φ ⇒ ψ se e solo se Γ, (~x: ~S > ⇒ φ) ` ~x: ~S > ⇒ ψ. Lemma 4.0.2. (di sostituzione) Se ψ `e una formula con variabili libere ~
y: ~T , ~t `e una nupla di termini con variabili libere ~x: ~S, libere per ~y e ψ allora l’interpretazione della sostituzione ψ(~t/~y),
[[~x: ~S ψ(~t/~y)]], non `e altro che la composizione
[[~y: ~T ψ]] ◦ [[~x: ~S t]].
Il lemma si dimostra per induzione su ψ; in termini diagrammatici equi- vale ad affermare che, dati i due pullback
A [[ ~T ]] B [[ ~S]] 1 Ω, 1 Ω, f ! [[ψ]] true g ! [[ψ(~t/~y)]] true
esiste una ed una sola freccia h: B → A tale che il seguente diagramma
B A [[ ~S]] [[ ~T ]] h g f [[~t]] (4.1)
sia un pullback.
Il teorema 2.5.5 ha come utile corollario la seguente proposizione (che formu- liamo in una forma opportuna al contesto del nostro discorso):
Proposizione 4.0.3. Dati due diagrammi di pullback
A [[ ~S]] B [[ ~S]] 1 Ω 1 Ω, f ! [[φ]] true g ! [[ψ]] true
allora si ha anche un diagramma di pullback della forma: A ∩ B [[ ~S]] × [[ ~S]] Ω × Ω 1 Ω. f ∩ g ! h[[φ]], [[ψ]]i ∧ true (4.2)
4.1
Correttezza
Teorema 4.1.1. (Correttezza) Dati un linguaggio tipato a pi`u sorteL , come descritto in 3.1, un insieme di sequenti Γ ed un sequente ~x: ~S φ ⇒ ψ tale che Γ ` ~x: ~S φ ⇒ ψ, risulta
Γ |= ~x: ~S φ ⇒ ψ
ossia per ogni topos E e per ogni interpretazione [[ ]]E del linguaggio L ∪ Γ ∪ {~x: ~S φ ⇒ ψ}
Dimostrazione. La dimostrazione del teorema procede in modo standard, mostrando che gli assiomi S1-S6 sono universalmente validi e che le regole d’inferenza R1-R6 preservano la validit`a. Tali verifiche, dovendo far riferi- mento alla strutttura di un generico toposE , consisteranno in un’uguaglianza tra due morfismi con codominio comune un oggetto a, sfruttando propriet`a di esistenza ed unicit`a di tali frecce in E .
S1 ~x: ~S φ ⇒ φ. L’assioma `e universalmente valido se [[~x: ~S φ ∧ φ]] = [[~x: ~S φ]].
Dato il pullback di true lungo la freccia [[~x: ~S φ]] (che per semplicit`a indichiamo con [[φ]]) D [[ ~S]] 1 Ω ! [[φ]] true (4.3) si verifica facilmente che il diagramma
D [[ ~S]]
1 Ω × Ω
! h[[φ]], [[φ]]i
htrue, truei
`e un diagramma di pullback. Si consideri allora il diagramma
D [[ ~S]] 1 Ω × Ω 1 Ω, ! h[[φ]], [[φ]]i htrue, truei true id1 ∧
di cui il quadrato in basso `e il diagramma di pullback che definisce il connettivo ∧. Si ha, per il pullback lemma (in breve PBL, cfr. [8], cap. 3, par. 3.13), che il perimetro di tale diagramma `e un pullback; osservando che tale perimetro `e lo stesso del pullback (4.3), e questo `e unico per (iii) di 2.13, si ha la tesi.
S2 Vogliamo far vedere che
[[~x: ~S φ ∧ >]] = [[~x: ~S φ]].
Si considerino i diagrammi di pullback che definiscono l’interpretazione di > e di φ nel contesto delle variabili ~x: ~S
A [[ ~S]] [[ ~S]] [[ ~S]] 1 Ω 1 Ω f ! [[φ]] true id ! [[>]] true
allora, per la proposizione 4.0.3, si ha che il perimetro del seguente diagramma definisce anch’esso un pullback:
A ∩ [[ ~S]] [[ ~S]] Ω × Ω 1 Ω. f ∩ id ! h[[φ]], [[>]]i true ∧
D’altro canto si ha che f ⊆ id[[ ~S]]; per le propriet`a dell’intersezione nell’algebra di Heyting Sub([[ ~S]]), si ottiene f ∩ id[[ ~S]] ' f e quindi, per l’unicit`a espressa al punto (iii) della definizione (2.13), la tesi.
S3 x: S > ⇒ x = x. Si tratta di mostrare
[[x: S > ∧ x = x]] = [[x: S >]]. Si considerino i diagrammi di pullback
[[S]] [[S]] [[S]] [[S]] [[S]] [[S]] × [[S]] 1 Ω. 1 Ω, id id h [[x ]], [[x ]]i hid, idi δS true [[x = x ]] ! id ! [[>]] true
Ragionando come prima (proposizione 4.0.3) otteniamo un diagramma di pullback [[S]] ∩ [[S]] [[S]] 1 Ω id ∩ id ! ∧ ◦ h[[x = x]], [[>]]i true
e, chiaramente, id ∩ id ' id, da cui, per l’unicit`a del pullback delle frecce verso Ω, la tesi.
S4 ~x: ~S, y: S, z: S φ ∧ y = z ⇒ φ(z/y) se z `e una variabile libera per y, φ. Vogliamo far vedere che
[[~x: ~S, y: S, z: S (φ ∧ y = z) ∧ (φ(z))]] = [[~x: ~S, y: S, z: S φ ∧ y = z]]. Si ha:
(a) [[~x: ~S, y: S, z: S φ ∧ y = z]] =
(b) [[~x: ~S, y: S, z: S (φ ∧ y = z) ∧ (φ(z))]] =
[[ ~S]] × [[S]] × [[S]] h[[φ∧y=z]],[[φ(z)]]i−→ Ω × Ω−→ Ω.∧ Per mostrare che (a)=(b) ci baster`a mostrare che i due pullback
A [[ ~S]]×[[S]]×[[S]] B [[ ~S]]×[[S]]×[[S]] Ω × Ω Ω × Ω 1 Ω, 1 Ω f ! h[[φ]], [[y = z]]i ∧ true g h[[φ ∧ y = z]], [[φ(z)]]i true ! ∧
sono uguali, ossia A ∼= B e f ' g. Il lemma di sostituzione (4.0.2) ci permette di concludere immediatamente la dimostrazione: dal momen- to che nell’assioma S4 occorre la sostituzione della variabile y: S con la variabile z: S il diagramma (4.1) si banalizza ad un pullback i cui lati sono morfismi d’identit`a, id[[S]]; si ha allora [[x: S φ]] = [[z: S φ(z/x)]].
Per l’assioma S1 si ha la tesi.
S5,S6 (Joyal ) Mostriamo che gli assiomi S5 e S6 sono universalmente va- lidi: supponiamo quindi che le variabili libere di {~y: ~T | φ} siano fra x1, . . . , xn e ~y = (y1, . . . , ym) siano variabili di tipo rispettivamente
~
T = (T1, . . . , Tm). Ci baster`a mostrare che
[[~y: ~T , ~x: ~S φ]] = [[~y: ~T , ~x: ~S ~y ∈ {~y: ~T | φ}]]. Si ha per la regola 4 di 3.2 [[~y: ~T , ~x: ~S ~y: ~T ∈ {(y1, . . . , ym) | φ}]] = ev[[T1]]×...[[Tn]]◦ ([[~y: ~T , ~x: ~S | y1]], . . . , [[~y: ~T , ~x: ~S {~y: ~T | φ}]]) = ev[[T1]]×...[[Tn]]◦ D id[[T1]]×...[[Tn]], [[~y: ~T , ~x: ~S {~y: ~T | φ}]] E =
(regola 5 di 3.2) ev[[T1]]×...[[Tn]]◦ D id[[T1]]×...[[Tn]], [[~y: ~T , ~x: ~S φ]] E∼ = [[~y: ~T , ~x: ~S φ]].
L’ultima uguaglianza pu`o essere meglio visualizzata ricordando il dia- gramma commutativo che definisce la propriet`a universale dell’espo- nenziale: [[T1]]×,...,×[[Tm]]×[[ ~S]] [[T1]]×,...,×[[Tm]]×P([[T1]]×,...,×[[Tm]]) Ω. id[[T1]]×,...,×[[Tm]], [[φ]] ∼ ev[[T1]]×,...,×[[Tm]] [[φ]]
Vediamo ora la correttezza delle regole d’inferenza: R1 Dimostriamo per induzione che se
[[x1: S1, . . . , xn: Sn φ ∧ ψ]] = [[x1: S1, . . . , xn: Sn φ]],
allora per ogni m ≥ n si ha
[[x1: S1, . . . , xm: Sm φ ∧ ψ]] = [[x1: S1, . . . , xm: Sm φ]]
Il caso m = n `e banalmente vero. Supponiamo allora sia vero per m > n e mostriamo che l’uguaglianza continua a valere per m + 1 Dati i pullback, uguali per ipotesi:
A [[S1]]×,...,×[[Sm]] A [[S1]]×,...,×[[Sm]] 1 Ω 1 Ω f ! [[φ]] true f ! [[φ ∧ ψ]] true
A×[[Sm+1]] [[S1]]×,...,×[[Sm]]×[[Sm+1]] 1 Ω D f, idSm+1E ! [[φ]] true
che `e ancora un pullback.
R2 Ragioniamo in termini puramente logici, sfruttando la propriet`a asso- ciativa della congiunzione: per ipotesi si ha
[[~x: ~S φ]] = [[~x: ~S φ ∧ ψ]], [[~x: ~S ψ]] = [[~x: ~S ψ ∧ θ]] quindi
[[~x: ~S φ]] = [[~x: ~S φ ∧ (ψ ∧ θ)]] = [[~x: ~S (φ ∧ ψ) ∧ θ]] = [[~x: ~S φ ∧ θ]] che `e la nostra tesi.
R3 Immediato.
R4 Si sfrutta la propriet`a associativa della congiunzione, analogamente a quanto fatto per dimostrare R2.
R5 E’ il lemma di sostituzione (4.0.2).
R6 Basta osservare che la propriet`a universale che definisce l’esponenzia- le permette di dedurre l’isomorfismo fra le frecce di valutazione che interpretano le due formule
~