| 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
|
