MATH 2090  Problem Set #1 (On Ch.9)  January 2002

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #1. Posted January 19, 2002

Due in the Tutorial of Friday, January 25, 2002

Section N

In your proofs it is imperative to clearly state what tools you use (e.g., WLUS, SLCS, MP, PSL, Monotonicity, Deduction Theorem, Weak Generalization, which axiom(s), etc.)

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 Variable Metatheorem.

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 f be a function symbol of arity 1. Prove that ⊢ x ≈ y ⇒ fx ≈ fy.

Careful! Do not just say that this “follows” from Chapter 1 stuff. It doesn’t. This is a Predicate Calculus exercise!

4. (5 MARKS) Prove the metatheorem “∀ commutativity (symmetry)” below.

⊢ (∀x)(∀y)A ≡ (∀y)(∀x)A

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

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

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

A may have free x occurrences!

8. (5 MARKS) Let x, y, z be distinct variables and P, Q predicates of one variable.

Prove the formula

Q(x) ⇒ (∀y)(Q(y) ⇒ (∀z)P (z)) ⇒ (∀x)P (x)

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

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

This is different from problem #4. (How?)