meta-theorems-of-predicate-logic.md (1512B)
1 +++ 2 template = 'page-math.html' 3 title = 'Meta-Theorems of Predicate Logic' 4 +++ 5 # Meta-Theorems of Predicate Logic 6 Entailment syntactically (⊢) and semantically (⊨) 7 * Γ ⊢ ψ: there is natural deduction derivation of ψ that only uses premises in Γ 8 * Γ ⊨ ψ: for all M and l, if M ⊨l Φ for every Φ ∈ Γ, then M ⊨ ψ 9 10 Soundness and completeness: 11 * Γ ⊢ Φ ⇔ Γ ⊨ Φ 12 * for all formulas Φ, every set Γ of formulas 13 * soundness (correctness): left-to-right (⇒) 14 * completeness: right-to-left (⇐) 15 16 soundness theorem: 17 * Γ ⊢ Φ ⇒ Γ ⊨ Φ 18 * if there is natural deduction derivation of Φ from Γ, then there's no model M in which all formulas of Γ are true, but Φ is false 19 * "correct" means not possible to derive false conclusion Φ from true premises Γ 20 * prove by induction on derivation lengths 21 22 completeness theorem: 23 * Γ ⊨ Φ ⇒ Γ ⊢ Φ 24 * derivations are strong enough to derive all valid semantic entailment statements 25 * "complete" means more derivation rules are not necessary 26 * proof is non-trivial 27 28 consistency and syntactical consistency 29 * Γ is consistent ⇔ Γ is syntactically consistent 30 * Γ has a model ⇔ there is no derivation of ⊥ from Γ 31 32 semantical consistency: 33 * set Γ of formulas is consistent if there is model M and environment l such that M ⊨ Φ for all Φ ∈ Γ 34 35 syntactical consistency: 36 * set Γ of formulas is syntactically consistent if Γ ⊬ ⊥ 37 38 compactness theorem: 39 * Γ is consistent ⇔ every finite subset Γ₀ ⊆ Γ si consistent 40