MATH 1090.03D

Fall 2000

Posted: Nov. 16, 2000

Due: Dec. 4, 2000—▶In class◀

Problem Set No. 5—The last one! (On Ch.9 of “GS”).

In the following problems you can use any tools that we have (e.g., Calculational/Equational proofs, Modus Ponens, Generalization/Specialization, Hilbertstyle proofs, Post’s Theorem, Deduction Theorem, Proof by contradiction, Monotonicity, etc.). Before you start a proof, think about the problem and choose the most convenient approach.

You should remember (and use, when appropriate) the following fact from class:

A ≡ B ⊢ A ⇒ B and A ≡ B ⊢ B ⇒ A

and

A ⇒ B, B ⇒ A ⊢ A ≡ B

which means that to prove Γ ⊢ A ≡ B you can do so by proving two things: Γ ⊢ A ⇒ B and Γ ⊢ B ⇒ A.

• Do the following problems from the text, Chapter 9.

• 9.5, 9.7, 9.8, 9.9, 9.17, 9.19, 9.26, 9.28.

There is a typo in the text: In Problem 9.28 it says “x does not occur free in P ”. Please correct this to say: “x does not occur free in Q”.

Also prove (these use Ax5 and Ax6):

• Prove ⊢ x ≈ y ⇒ y ≈ x.

• Prove ⊢ x ≈ y ∧ y ≈ z ⇒ x ≈ z.