Logic 1, WS 2004. Homework 4, given Oct 28, due Nov 04

1. Consider the sequent calculus definded by the axioms:

A = {Φ ⊢ Ψ | Φ ∩ Ψ¬ = ∅},

and by the rules:

\frac{Φ, φ_{1}, φ_{2} ⊢ Ψ}{Φ, φ_{1} ∧ φ_{2} ⊢ Ψ} (∧ ⊢) \frac{Φ ⊢ Ψ, φ_{1} Φ ⊢ Ψ, φ_{2}}{Φ ⊢ Ψ, φ_{1} ∧ φ_{2}} (⊢ ∧)

\frac{Φ ⊢ Ψ, φ}{Φ, ¬φ ⊢ Ψ} (¬ ⊢) \frac{Φ, ψ ⊢ Ψ}{Φ ⊢ Ψ, ¬ψ} (⊢ ¬)

\frac{Φ, φ′ ⊢ Ψ}{Φ, φ ⊢ Ψ} if φ ≡ φ′ (≡⊢) \frac{Φ ⊢ Ψ, ψ′}{Φ ⊢ Ψ, ψ} if ψ ≡ ψ′ (⊢≡)

Using this calculus, prove the correctness of the following sequent rules (that is “eliminate” them, by showing how they can be simulated by the rules of the above calculus):

(a) \frac{Φ, ψ_{1} ⊢ Ψ, ψ_{2}}{Φ ⊢ Ψ, ψ_{1} ⇒ ψ_{2}}

(b) \frac{Φ, ψ_{1} ⊢ Ψ, ψ_{2} Φ, ψ_{2} ⊢ Ψ, ψ_{1}}{Φ ⊢ Ψ, ψ_{1} ⇔ ψ_{2}}

You may use the rule for “⇒” when eliminating the rule for “⇔”.

2. Using the same calculus as above, eliminate the rules:

(c) \frac{Φ, φ_{1}, φ_{2} ⊢ Ψ}{Φ, φ_{1}, (¬φ_{1}) ∨ φ_{2} ⊢ Ψ}

(d) \frac{Φ, ¬ψ_{1} ⊢ Ψ, ψ_{2}}{Φ ⊢ Ψ, ψ_{1} ∨ ψ_{2}}

3. Write the following definition in the standard prefix syntax of predicate logic:

A function f is continuous if and only if:

∀_{ϵ>0} ∃_{δ>0} ∀_{y} (|y − x| < δ ⇒ |f(y) − f(x)| < ϵ)

4. Construct an interpretation for the formula:

((∀_{x}P (x) ⇒ P (f(x))) ∧ P (a)) ⇒ P (f(f(a))).

5. Find an example of subformulae ϕ and ψ for which the following equivalence does not hold: ∀_{x}(ϕ ∨ ψ) ≡ (∀_{x}ϕ) ∨ (∀_{x}ψ).