Number 
Due 
Problems 
Solutions 
1  9/19  Do (but don't need to turn in): Section 2.1, 1, 2, 4, 8
Section 2.2: 3, 6, 8
Turn in: Section 2.2, 2, 11, 12 
Solutions 
2  10/3  Section 2.2, 9, 21, 24
Gives deductions in Natural Deduction of:
a) (φ∨ψ)∧(φ∨ρ)→φ∨(ψ∧ρ)
b) (φ→ψ)→(¬ψ→¬φ)
c) (¬ψ→¬φ)→(φ→ψ)
d) ((φ→ψ)→φ)→φ  Solutions 
3  10/17 
 Prove the following: Suppose u is substitutable for y in φ. Then ⊨_{𝔐}φ[u/y][s] iff ⊨_{𝔐}φ[s(y→s̅(u))].
 Two ways of stating the completeness theorem are: "Whenever Γ⊨φ, also Γ⊦φ" and "Whenever Γ is consistent, Γ is satisfiable". Prove that these two formulations are equivalent.
 Consider the language of arithmetic with constant symbol 0, unary function symbol S, binary relations < and =, and a new unary relation P. Let T consist of the following six axioms:
 ∀y(y≠0→∃x y=Sx)
 ∀x∀y(x<Sy↔x≤y)
 ∀x ¬x<0
 ∀x∀y (x<y∨x=y∨y<x)
 ∀x∀y(x<y→¬y<x)
 ∀x∀y∀z(x<y→y<z→x<z)
We will later see that these axioms are sufficient that T⊦σ if and only if σ is true in the standard model of the natural numbers (where 0 is interpreted as the number 0, S as the successor function, and < as the less than relation).
Let Γ consist of the formulas {∃x Px,¬P0,¬PS0,¬PSS0,...}. Then T+Γ is consistent. Why is this possible? Give a model of T+Γ

Solutions 
4  11/12  Section 2.2, 14, 15, 18, 19  Solutions 
  Midterm  Solutions 
5  12/5  Section 2.6, 1, 2, 9
Section 3.2, 2
Section 3.3, 1
Turn in: Section 3.2, Problem 4; Section 3.3, Problem 3
