Transcript
Lezione 21 e Lezione 22
Venerd`ı 24 Aprile 2009
Teorema 1 (Teorema di Completezza). Sia L un linguaggio del primo ordine. Sia Γ un insieme di formule, φ una formula. Se Γ |= φ allora Γ ` φ. Noi daremo solo una traccia della dimostrazione, lasciando alcuni enunciati senza dimostrazione. La prima parte della dimostrazione segue da vicino la dimostrazione del Teorema di Completezza per la logica proposizionale. Definizione 2. Un insieme di formule Γ ´e detto essere consistente se Γ 0 ⊥. Proposizione 3. Se esiste (D, s) che soddisfa tutte le formule in Γ, allora Γ ´e consistente. Dimostrazione. Sia (D, s) come nell’enunciato. Per assurdo, si supponga che Γ ` ⊥. Per il Teorema di Validit`a, si ha che Γ |= ⊥. Visto che (D, s) soddisfa tutte le formule in Γ, si avrebbe che J⊥Ks = 1 , che ´e impossibile. L’implicazione opposta a quella contenuta nella proposizione precedente ´e contenuta nel seguente lemma. Lemma 4 (Lemma di Esistenza dei Modelli). Se Γ ´e un insieme consistente, allora esiste (D, s) che soddisfa tutte le formule in Γ. Lasceremo il Lemma di Esistenza dei Modelli senza dimostrazione. Mostriamo, invece, come da esso sia possibile dimostrare il Teorema di Completezza. Proposizione 5. Le seguenti affermazioni sono equivalenti: 1. Γ 0 φ 2. Esiste (D, s) che soddisfa tutte le formule in Γ, ma tale che JφKs = 0. Dimostrazione. Abbiamo che: Γ0φ
sse sse sse
Γ ∪ {¬φ} ´e consistente esiste (D, s) che soddisfa tutte le formule in Γ ∪ {¬φ} esiste (D, s) che soddisfa tutte le formule in Γ t.c. JφKs = 0,
come volevasi dimostrare.
1
Dimostrazione del Teorema di Completezza. Assumiamo che Γ |= φ. Dobbiamo dimostrare che Γ ` φ. Per assurdo, si supponga che Γ 0 φ. Dalla proposizione precedente, si ha che esiste (D, s) che soddisfa tutte le formule in Γ e tale che JφKs = 0. Ma, visto che Γ |= φ e che (D, s) soddisfa tutte le formule in Γ, deve valere che JφKs = 1, una contraddizione. Quindi Γ ` ⊥, come volevasi dimostrare. Nonostante la dimostrazione del Lemma di Esistenza dei Modelli non sia parte del programma del corso, vogliamo dare un’idea di come sia possibile darne una dimostrazione. Dato un insieme di formule Γ, vogliamo costruire un modello (D, s). L’idea ´e di costruire un modello a partire dal linguaggio L. A tal fine, si potrebbe fissare D =def {t | t termine di L} Con s : VarL → D data da s(x) = x. Proseguendo con questa idea, ci sono due problemi da risolvere: (i) Dobbiamo decidere come assegnare valori di verit`a alle formule di L, in modo da rendere valida ogni formula di Γ. (ii) Nel caso Γ ` ∃xφ(x), la struttura D deve contenere un elemento d ∈ D, ovvero un termine del linguaggio, tale che Jφ(x)Ks[x7→d] = 1. Per risolvere il primo problema, ´e sufficiente considerare, come nel caso della logica proposizionale, insiemi massimalmente consistenti che contengano Γ. Per risolvere il secondo problema, invece, ´e necessario estendere il linguaggio con nuove costanti, in modo da garantire l’esistenza di termini che siano dei ‘testimoni’ per asserzioni esistenziali derivabili da Γ. Questo secondo problema viene risolto tramite il metodo delle cosiddette teorie di Henkin, in cui non ci addentreremo.
2
