L’idea della dimostrazione del teorema di completezza riposa sulla co- struzione di una categoria sintattica a partire da un insieme di sequenti del calcolo di Joyal: come si avr`a modo di apprezzare, una tale costruzione con- duce sempre alla definizione di un topos.
Il metodo che usiamo `e analogo alla costruzione dell’algebra di Lindenbaum di un sistema formale; tuttavia, mentre per una dimostrazione di completez- za di una teoria del primo ordine `e necessario usare una forma dell’assioma di scelta1, la costruzione di una categoria sintattica a partire dai sequenti del
nostro calcolo elude questo passaggio.
La costruzione che esibiamo corrobora l’affermazione fatta nell’introduzione del paragrafo 2.12 secondo la quale un topos ha la capacit`a intrinseca di po- ter essere pensato, oltre che come modello, anche come teoria logica. Questa propriet`a delle categorie di riuscire a sintettizzare aspetti sintattici e seman- tici `e risultata fondamentale nell’analisi dei rapporti fra logica matematica e teoria dei topos; vedremo nel prossimo capitolo (5.1) una costruzione che sottolinea pi`u precisamente questo aspetto.
Teorema 4.2.1. (Completezza) Se un sequente ~x: ~S φ ⇒ ψ `e conseguenza logica di un insieme di sequenti Γ, allora `e dimostrabile a partire da Γ:
Γ |= ~x: ~S φ ⇒ ψ implica Γ ` ~x: ~S φ ⇒ ψ
Dimostrazione. Dimostriamo il teorema esibendo la costruzione di una ca- tegoria di Lindembaum-Tarski : dato un insieme di sequenti Γ, mostriamo come costruire un modello, T op(Γ), ed un’interpretazione, [[ ]]T op(Γ), su tale
modello in modo tale che
[[ ]]T op(Γ)|= ~x: ~S φ ⇒ ψ se e solo se Γ ` ~x: ~S φ ⇒ ψ. (4.4)
Chiaramente, occorrer`a mostrare che la struttura che otterremo `e effettiva- mente un topos.
Conveniamo, d’ora in avanti, di indicare una dimostrazione formale del tipo Γ ` ~x: ~S > ⇒ φ con la scrittura pi`u semplice Γ ` φ(~x).
Costruiamo la categoria T op(Γ) prendendo come oggetti le formule [~x: ~S φ], con φ formula del linguaggio L in cui sono espressi i sequenti di Γ; per definire i morfismi di T op(Γ),
[~x: ~S φ] −→ [~y: ~T ψ],
introduciamo delle opportune classi di equivalenza sull’insieme delle formule Γ-funzionali: diremo che una formula, ~x: ~S, ~y: ~T α(~x, ~y), `e Γ-funzionale se
• Γ ` φ(~x) ↔ ∃ ~y α(~x, ~y); • Γ ` α(~x, ~y) → ψ(~y);
• Γ ` α(~x, ~y) ∧ α(~x, ~y0) → (~y = ~y0);
dove le variabili fra parentesi dopo ogni formula indicano tutte e sole le variabili tipate del sequente che occorrono in quella data formula.
Diremo che due formule Γ-funzionali, ~
x: ~S, ~y: ~T α(~x, ~y), ~z: ~S, ~w: ~T β(~z, ~w) sono equivalenti se
Γ ` α(~x, ~y) ↔ β(~x/~z, ~y/ ~w).
Definiamo la composizione di due formule Γ-funzionali, ~x: ~S, ~y: ~T α(~x, ~y) e ~ y: ~T , ~z: ~U β(~y, ~z) come ~ x: ~S, ~z: ~U ∃ ~y α(~x, ~y) ∧ β(~y, ~z). Un morfismo di T op(Γ) ~ x1: ~S, ~y2: ~T α( ~x1, ~y2): [~x: ~S φ] −→ [~y: ~T ψ]
`e una classe di equivalenza di formule Γ-funzionali.
Si verifica facilmente che la composizione cos`ı data `e associativa e per ogni oggetto ~x: ~S φ esiste il morfismo identico idφ(~x) dato dalla formula
~
che rispetta l’assioma dell’unit`a (assioma CAT2 della def. (2.2)); le defini- zioni date fanno quindi di T op(Γ) una categoria.
Osservazione 8. La definizione di morfismo che abbiamo dato coinvolge due variabili, ~x1 e ~y2, distinte dalle variabili libere che occorrono nel dominio e nel
codominio: ci`o `e essenziale affinch`e le variabili coinvolte rimangano disgiunte. Mostriamo che T op(Γ) `e un topos: vediamo come definire oggetto ter- minale, equalizzatori, e prodotti; da questi dedurremo l’esistenza di tutti i limiti finiti.
• L’oggetto terminale `e la formula x: ( ) >, dove ( ) indica il contesto vuoto.
• Prodotti: dati due oggetti [~x: ~S φ] e [~y: ~T ψ], con variabili distinte, definiamo il loro prodotto come la formula
~
x: ~S, ~y: ~T φ(~x) ∧ ψ(~y). • Equalizzatori Dati due morfismi
~
x: ~S, ~y: ~T α(~x, ~y), ~x: ~S, ~y: ~T β(~x, ~y)
fra gli oggetti [~x: ~S φ] e [~y: ~T ψ] il loro equalizzatore `e un morfismo ~
z: ~S, ~x: ~S e(~z, ~x): [~z: ~S θ(~z)] −→ [~x: ~S φ(~x)], definito dalla formula Γ-funzionale:
e(~z, ~x) ≡ ~x: ~S, ~z: ~S ∃ ~y (α(~x, ~y) ∧ β(~x, ~y)) ∧ ~x = ~z; infatti se
Γ ` ∃ ~y (α(~x, ~y) ∧ β(~x, ~y)) ∧ ~x = ~z.
allora, per la funzionalit`a di α (o equivalentemente di β), si ha: Γ ` e(~z, ~x) → φ(x) ∧ ~x = ~z.
• Un pullback di due morfismi con codominio comune si ottiene dall’e- qualizzatore delle due frecce parallele che si ottengono dal prodotto dei rispettivi domini.
Il classificatore di sottoggetti Ω `e caratterizzato dalla formula X: Ω >,
mentre il morfismo true: 1 → Ω `e dato dalla formula Γ-funzionale X: Ω X = >.
Verifichiamo quanto detto: in primo luogo diamo una caratterizzazione dei monomorfismi nella categoria T op(Γ).
Un monomorfismo di T op(Γ), ~x: ~S, ~y: ~T α(~x, ~y) `e univocamente determinato dalla formula Γ-funzionale
~x: ~S, ~x0: ~S, ~y: ~T α(~x, ~y) ∧ α(~x0, ~y) → (~x = ~x0). (4.5)
Infatti dato un morfismo ~
x: ~S, ~y: ~T α(~x, ~y): [~x: ~S φ] −→ [~y: ~T ψ], la sua coppia nucleo `e ottenuta dal seguente diagramma:
∃~yα(~x, ~y) ∧ α(~x0, ~y) φ(~x) φ(~x) ψ(~y) h h0 α(~x, ~y) α(~x, ~y)
dove le frecce h e h0 sono rappresentate rispettivamente dalle formule: ~
x: ~S, ~x0: ~S, ~z: ~S ∃ ~y(α(~x, ~y) ∧ α(~x0, ~y)) ∧ ~x = ~z,
~x: ~S, ~x0: ~S, ~z: ~S ∃ ~y(α(~x, ~y) ∧ α(~x0, ~y)) ∧ ~x0 = ~z.
Si ha allora che α `e mono (cio`e cancellabile a sinistra) se e solo se h = h0, ossia le due formule che definiscono h e h0 sono (Γ-)equivalenti:
Questa risulta equivalente a
Γ ` α(~x, ~y) ∧ α(~x0, ~y) → (~x = ~x0)
`e immediata.
Verifichiamo ora la propriet`a (iii) della definizione (2.13): per ogni mo- no ~x: ~S φ m(~−→ ~x,~y) y: ~T ψ esiste una ed una sola freccia in Ω tale che il diagramma φ(~x) ψ(~y) 1 Ω m(~x, ~y) ! χm true (4.6) sia un pullback. Sia χm la formula ~ y: ~T , X: Ω ∃~x m(~x, ~y) = X, (4.7) dove X `e una variabile di tipo Ω. Ragionando in maniera analoga a prima possiamo definire il pullback di true e χm come la formula
~
y: ~T ∃X (X = > ∧ (∃~x m(~x, ~y) = X)); Si ha allora
Γ ` ∃X (X = > ∧ (∃~x m(~x, ~y) = X)) ↔ ∃~x m(~x, ~y) = > ↔ ∃~x m(~x, ~y).
Ora osservando che ~x: ~S, ~y: ~T m(~x, ~y) `e sia mono che funzionale si ha che i due morfismi
[~x: ~S φ(~x)]m(~−→ [~x,~y) y: ~T ∃~x m(~x, ~y)], [~y: ~T ∃~x m(~y, ~x)]m(~−→ [~x,~y) x: ~S φ(~x)] sono uno l’inverso dell’altro, infatti
poich`e m(~x, ~y) `e mono, e
Γ ` ∃~x m(~x, ~y) ∧ m(~x, ~y0) ↔ ∃~x m(~x, ~y) ∧ ~y = ~y0,
perch`e m(~x, ~y) `e funzionale.
Risulta allora verificato che la formula (4.7) definisce effettivamente una frec- cia caratteristica del monomorfismo ~x: ~S, ~y: ~T m(~x, ~y).
Sia ζ(~y, X) un’altra freccia che produce il diagramma (4.6), cio`e tale che si abbia un diagramma di pullback
ζ(~y, >) ψ(~y) 1 Ω n(~x, ~y) ! ζ(~y, X) true (4.8) dove l’oggetto ζ(~y, >) `e rappresentato dalla formula
~
y: ~T ∃X: Ω(X = > ∧ ζ(~y, X)). Per ipotesi, il monomorfismo
ζ(~y, >) ∧ y = y0: [~y: ~T ζ(~y, >)] −→ [~y: ~T ψ(~y)] `e isomorfo a
∃~x m(~x, ~y) ∧ y = y0: [~y: ~T ∃~x m(~x, ~y)] −→ [~y: ~T ψ(~y)]. Per come sono scritti i monomorfismi si ottiene:
Γ ` ζ(~y, >) ↔ ∃~x m(~x, ~y); Questo `e equivalente a
Γ ` (ζ(~y, >) = X) ↔ (∃~x m(~x, ~y) = X). (4.9) Per provare che i due mono, χm e ζ(~y, X), sono Γ-equivalenti, ossia
basta provare, alla luce di (4.9), che
Γ ` (ζ(~y, >) = X) ↔ ζ(~y, X). (4.10) Dimostriamo quindi (4.10) grazie al teorema di deduzione (4.0.1):
Γ ` A ↔ B se e solo se Γ, A ` B e Γ, B ` A: (1) (Γ, B ` A) Γ, ζ(~y, X), X ` (X = >) ∧ ζ(~y, X); Γ, ζ(~y, X), X ` ζ(~y, >) (assioma S4); Γ, ζ(~y, X), ζ(~y, >) ` X = > (per funzionalit`a di ζ(~y, X)); Γ, ζ(~y, X), ζ(~y, >) ` X; Γ, ζ(~y, X) ` ζ(~y, >) = X. (2) (Γ, A ` B) Γ, ζ(~y, >) = X, ζ(~y, Y ) ` ζ(~y, >) = Y (per il punto (1)); Γ, ζ(~y, >) = X, ζ(~y, Y ), ζ(~y, >) = Y ` X = Y ; Γ, ζ(~y, >) = X, ζ(~y, Y ) ` ζ(~y, X) per funzionalit`a; Γ, ζ(~y, >) = X, ∃Y ζ(~y, Y ) ` ζ(~y, X); Γ, ζ(~y, >) = X ` ∃Y ζ(~y, Y ); Γ, ζ(~y, >) = X ` ζ(~y, X) regola R2.
Vediamo infine la propriet`a (iv) di (2.13): mostriamo che T op(Γ) ha oggetti potenza. Per ogni oggetto ~x: ~S φ definiamo un oggetto potenza
P(~x: ~S φ) ≡ ~x: ~S, X0
: Ω( ~S) X0 ⊆ {~x: ~S | φ} dove X0 `e una variabile di tipo Ω( ~S) mentre X
1 ⊆ X2 `e un’abbreviazione per
definiamo il monomorfismo
∈[~x: ~S φ]−→ [~m x: ~S φ] × [P(~x: ~S φ)], la cui freccia caratteristica `e il morfismo di valutazione
[~x: ~S φ] × [P(~x: ~S φ)]ev−→ Ω~x: ~S φ come: ∈[~x: ~S φ]≡ ~x0: ~S, ~x: ~S, ~X0: ~Ω( ~S) x~0 ∈ X0 ∧ X0 ⊆ {~ x: ~S | φ}; m(~x, X, X0) ≡ ~x: ~S, X: Ω( ~S), X0: Ω( ~S) ∈[~x: ~S φ]∧~x = ~x0∧ X = X0 . Dato un morfismo ~ z: ~V , ~x: ~S, ~y: ~T α(~z, ~x, ~y): [~z: ~V θ]−→ [~α x: ~S φ] × [~y: ~T ψ], se definiamo il morfismo r: [~y: ~T ψ] −→ [P(~x: ~S φ)] come
~
x: ~S, ~y: ~T , ~z: ~V , X: Ω( ~S) ψ ∧ X = {~x: ~S | ∃ ~z α(~z, ~x, ~y)}, si verifica facilmente che si ha un diagramma di pullback
θ(~z) ∈[φ] φ(~x) × ψ(~y) φ(~x) ×P(φ(~x)). m(~x, X, X0) α id[φ(~x)]× r (4.11) L’interpretazione diL dentro T op(Γ) si pu`o definire in maniera naturale sui termini ponendo
[[~x: ~S t]]T op(Γ) ≡ ~x: ~S (x1 = x1∧, . . . , ∧xn= xn) t(~x,x)
−→ x: S x = x, dove x `e una variabile del medesimo tipo di t (che supponiamo di tipo S) e t(~x, x) `e il morfismo
~x: ~S, x: S x1 = x1∧, . . . , ∧xn= xn∧ x = t.
Ora, la validit`a di un sequente in T op(Γ), secondo questa interpretazione, equivale esattamente alla sua derivabilit`a a partire dagli assiomi del calcolo di Joyal e dai sequenti di Γ; dal momento che l’interpretazione data risulta anche corretta si `e giunti a dimostrare l’equivalenza (4.4).
Aspetti intuizionisti della teoria
dei topos
Abiamo gi`a avuto modo di osservare nel corso del presente lavoro alcuni legami fra teoria dei topos e intuizionismo: nel capitolo 2 abbiamo visto come l’algebra dei sottoggetti di un qualsiasi oggetto in un topos debba essere, in generale un’algebra di Heyting; nel capitolo 4 abbiamo mostrato come sia possibile interpretare, all’interno di un topos, un sistema logico intuizionista, di ordine superiore, per linguaggi a pi`u sorte.
In questo capitolo riassumiamo alcuni aspetti di contatto fra teoria dei topos e intuizionismo che ancora non sono stati toccati:
• nel paragrafo 5.2 analizziamo i rapporti fra semantica dei prefasci e modelli di Krikpe: vedremo come ritrovare il forcing della semantica a mondi possibili per la llogica intuizionista come caso particolare della semantica di Krikpe-Joyal;
• nel paragrafo 5.3 mostriamo che esistono topos aventi un oggetto dei numeri reali, R, in cui tutte le funzioni R → R sono continue, ritro- vando cos`ı un celebre teorema di matematica intuizionista dimostrato da Brouwer.
Prima di esaminare in dettaglio questi punti introduciamo, nel paragrafo che segue, la costruzione del linguaggio associato ad un topos e del topos linguistico da esso derivante, nozioni fondamentali per un’analisi logica della teoria dei topos (nonch`e per un’analisi topos-teoretica della logica).
5.1
Il linguaggio associato ad un topos
Nella dimostrazione del teorema di completezza (4.2.1) abbiamo visto come sia possibile, dato un insieme di sequenti in un linguaggio L per il calcolo di Joyal, costruire il topos T op(Γ) avente per oggetti le formule diL . E’ ora naturale chiedersi, in maniera duale, se, dato un topos E , esiste un linguaggio L ed un insieme di sequenti Γ tale che le due categorie E e T op(Γ) siano fra loro equivalenti. La risposta a tale domanda `e affermativa: enunciamo tale risultato come teorema ([3], pag. 11).
Teorema 5.1.1. Dato un topos E , esiste un insieme di sequenti Γ tale che le categorie E e T op(Γ) sono fra loro equivalenti.
Dimostrazione. La dimostrazione del teorema consiste sostanzialmente nella costruzione del linguaggio tipatoLE, associato al toposE : come insieme del- le sorte prendiamo l’insieme degli oggetti di E , mentre l’insieme dei simboli funzionali sar`a dato dall’insieme delle frecce di E in maniera che dominio e codominio dei simboli funzionali coincidano con quelli delle frecce di E cor- rispondenti. Data una tale segnatura, esiste un unico linguaggio LE ad essa corrispondente; inoltre LE ammette un’interpretazione canonica dentro E . Per costruire l’insieme dei sequenti Γ ci baster`a allora prendere i sequenti di LE che sono validi secondo l’interpretazione canonica.
Dal momento che sia E che T op(Γ) sono categorie di Lindembaum-Tarski dell’insieme di sequenti Γ, o detto altrimenti rendono veri (secondo le rispet- tive interpretazioni canoniche) tutti i sequenti dimostrabili a partire da Γ, si verifica facilmente che il funtore
che associa ad ogni morfismo f : a → b di E , il morfismo (a = a)b=f (a)−→ b = b
di T op(Γ), stabilisce l’equivalenza di categorie cercata.
Il teorema appena dimostrato mostra che, associando ad ogni topos E un linguaggio tipato LE, esattamente come nella dimostrazione precedente, sia possibile avere a disposizione un potente apparato logico in grado di internalizzare diverse costruzioni matematiche. L’idea di topos come teoria logica (cfr. paragrafo 2.2) assume qui un senso preciso, confermando la tesi (cfr. [17], [23]) secondo cui lavorare in un topos equivalga a lavorare in un sistema logico intuizionista di ordine superiore (e nel caso in cui il topos abbia anche un oggetto dei numeri naturali sia equivalente a lavorare in un modello dell’ higher order Heyting arithmetic).