Teoremi e dimostrazioni

Page 1

Theorems with demonstrations for the midterms of Algebra and Mathematical Logic Politecnico di Milano January 13, 2016 Contents 1 First midterm 1 1.1 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Hilbert Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Resolution Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Relations and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Final 10 2.1 First Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Hilbert Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Algebraic theories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1 First midterm 1.1 Propositional Logic Theorem 1.1.1 (Induction Principle - Slide 8). Suppose P is a property that formulas of a language L may or may not have; write P ϕ to indicate ϕ has the property P . Suppose that: 1. every atomic formula has the property P , 2. if P ϕ, then P(¬ϕ) 3. if P ϕ and P ψ, then P(ϕ2ψ) Then every formula of L has the property P Proof. Let M = {ϕ∈ L ∶ P ϕ}. Observe that 1. All atomic formuas are in M by hypothesis 1 1 2. If ϕ∈ M, then (¬ϕ)∈ M by hypothesis 2 3. If ϕ, ψ∈ M, then (ϕ2ψ)∈ M by hypothesis 3 Since L is the smallest set satisfying these conditions, L⊆ M. Therefore, all formulas of L satisfy P Theorem 1.1.2 (Deduction theorem - Semantical Form - Slide 26). Given Γ, ϕ and ψ Γ/uni22A7ϕ→ ψ⇔ Γ, ϕ/uni22A7ψ Proof. Γ /slash.left/uni22A7ϕ→ ψ ⇔ there exists…