MATH 2090  Problem Set #1 (On Ch.9)  September 2003

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #1. Posted September 2, 2003

Due in the Course Box by 2:00pm, September 30, 2003

Section A

In your proofs it is \underline{required} that you clearly state what tools you use from those among the posted “Logic ToolBox”

1. (5 MARKS) In class we have proved that ⊢ (∃x)(∀y)A ⇒ (∀y)(∃x)A

using the Auxiliary Variable Metatheorem.

Now prove the same thing but \underline{without} the help of the Auxiliary Vari-

able Metatheorem, instead exploiting monotonicity.

2. (5 MARKS) Prove that ⊢ ((∀x)B ⇒ A) ≡ (∃x)(B ⇒ A), provided x is

not free in A.

Use an equational proof!

3. (5 MARKS) Let ∘ be a function symbol of arity 2.

Prove that ⊢ x = y ⇒ x ∘ z = y ∘ z no matter what variables x, y, z you use.

Careful! Do not just say that this “follows” from Chapter 1 stuff. It doesn’t. This is a Predicate Calculus exercise—and I mean this in the strict sense! That is, you do not need any axioms about the symbol “∘” in order to prove this.

4. Let P be any predicate of arity 2.

(a) (2 MARKS) Explain WHY (∀x)(∀y)P (x, y) ⇒ (∀y)P (y, y) is NOT an instance of Ax2.

(b) (5 MARKS) Nevertheless, prove that (∀x)(∀y)P (x, y) ⇒ (∀y)P (y, y) IS an absolute theorem.

5. (5 MARKS) Prove (absolutely) the formula (∃x)A ∧ (∀x)B ⇒ (∃x)(A ∧ B).

6. (5 MARKS) For any predicate P of arity 2 prove

⊢ (∀x)(∀y)P (x, y) ≡ (∀y)(∀x)P (y, x)

Supplementary question: Precisely how is this different from ⊢ (∀x)(∀y)A ≡ (∀y)(∀x)A the we proved in class?