MATH 2090  Problem Set #2 (Sample Solutions)  October 2003

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #2 (Sample Solutions).

Posted October 21, 2003

Section A

Probl. 1. From the text p.213–215: Do the problems

(i) 11.7(c). Do ST ⊢ {b, c} = {b, e} ≡ c = e. Proof. The ⇐ is by “replacing equals for equals in terms” theorem applied to terms (see ToolBox for statement of theorem, or see “All about Leibniz” to see a proof). For the ⇒ note that by Part I (2.7) and definition of pair (Part II, 1.7) we need to prove

ST ⊢ (∀x)(x = b ∨ x = c ≡ x = b ∨ x = e) ⇒ c = e

OK, use ded-thm.

(1) (∀x)(x = b ∨ x = c ≡ x = b ∨ x = e) (assume)
(2) c = b ∨ c = c ≡ c = b ∨ c = e  ((1) and spec.)
(3) c = b ∨ c = e  ((2), c = c and red. true)
(4) e = b ∨ e = c ≡ e = b ∨ e = e  ((1) and spec.)
(5) e = b ∨ e = c  ((4), e = e and red. true)
(6) (c = b ∨ c = e) ∧ (e = b ∨ e = c)  ((3, 5) and taut. impl.)
(7) (c = b ∧ e = b) ∨ (c = b ∧ e = c) ∨ (c =e ∧ e = b) ∨ (c = e ∧ e = c)
((6) and taut. impl.)

Now (7) yields what we want by proof by cases: Case A. c = b ∧ e = b: Conclude c = e by transitivity of =. Case B. c = b ∧ e = c: Conclude c = e by taut. implica-

tion.^{∗} Case C. c = e∧e = b: Conclude c = e by taut. implication. Case D. c = e∧e = c: Conclude c = e by taut. implication.

∗Symmetry of = also used. This and transitivity are trivially provable from Ax5 and Ax6.

□

(ii) 11.12(a) Proof. (Informal) So, assume (use ded-thm) S ⊆ T and U ⊆ V and also let x ∈ S ∪ U. By def. of ∪, we have two cases:

Case 1. x ∈ S. Then x ∈ T by assumption, and also x ∈

T ∪ V by def. of ∪. Case 2. x ∈ U. Then x ∈ V by assumption, and also

x ∈ T ∪ V by def. of ∪.

(iii) 11.15: Prove (∃x)(x ∈ S ∧ x ∉ T) ⇒ S ≠ T. Proof. Prove the contrapositive: S = T ⇒ ¬(∃x)(x ∈ S ∧ x ∉ T). That is, prove S = T ⇒ (∀x)¬(x ∈ S ∧ x ∉ T). But that is S = T ⇒ (∀x)(x ∈ S ⇒ x ∈ T), i.e., a tautological consequence of the logical half of the Extensionality theorem. □

(iv) 11.18: Prove S ∈ 𝒫(S). Proof. We want S ∈ {x|x ⊆ S}.

S ∈ {x|x ⊆ S}

≡ ⟨by ∈-elim. Note that the next line is (x ⊆ S)[x := S]⟩

S ⊆ S

The previous line is a theorem. □

For 11.7(c) and 11.18 in the list above, formal proofs are required.

Also do

Probl. 2. Prove informally ST ⊢ (∀a, b, c, d)({a, {a, b}} = {c, {c, d}} ⇒ a = c ∧ b = d).

To avoid an embarrassing situation I note that the above is not the same problem that I assigned last year. Do you see the difference?

Proof. Suffices to prove this without the ∀ (I can then introduce the ∀ by generalisation, since ST has closed axioms).

Assume then {a, {a, b}} = {c, {c, d}}.

That is,

(∀x)(x = a ∨ x = {a, b} ≡ x = c ∨ x = {c, d})

By specialisation I get

c = a ∨ c = {a, b} ≡ c = c ∨ c = {c, d}  (1)

and

a = a ∨ a = {a, b} ≡ a = c ∨ a = {c, d}  (2)

Hence (see also proof on p.1)

c = a ∨ c = {a, b}  (3)

and

a = c ∨ a = {c, d}  (4)

(3) and (4) and taut. implication yield as on p.1

(c = a∧a = c)∨(c = a∧a = {c, d})∨(c = {a, b}∧a = c)∨(c = {a, b}∧a = {c, d})

(5)

The disjunction (5) yields just

a = c  (6)

by cases (by the 1st disjunct), since each of the other three disjuncts yield false by foundation: The 2nd yields c ∈ c; the 3rd yields a ∈ a and the 4th yields a ∈ c ∈ a.

(6) transforms our hypothesis to {a, {a, b}} = {a, {a, d}}. This by problem 11.7(c) yields {a, b} = {a, d} and one more application of problem 11.7(c) yields b = d. Done! □

Probl. 3. Give a formal proof of ST ⊢ S ⊂ T ⇒ (∃x)(x ∉ S).

Proof. Invoke the deduction theorem, and assume hypothesis (line (1) below).

(1) (∀x)(x ∈ S ⇒ x ∈ T) ∧ ¬(∀x)(x ∈ S ≡ x ∈ T) (assume)
(2) (∀x)(x ∈ S ⇒ x ∈ T)  ((1) and Post’s theorem)

(3) ¬(∀x)(x ∈ S ≡ x ∈ T)  ((1) and Post’s theorem)
(4) (∃x)(x ∈ S ≡ ¬x ∈ T)  ((3), Post and WLUS)
(5) z ∈ S ≡ ¬z ∈ T  (by (4): \underline{assume}; z fresh)
(6) z ∈ S ⇒ z ∈ T  ((2) and specialisation)
(7) z ∉ S  ((5,6) and Post)
(8) (∃x)x ∉ S  ((7) and A ⊢ ∃A-rule)

□

Probl. 4. Prove \underline{without using the axiom of foundation} that 1 ≠ \{1\} and ∅ ≠ {∅}.

For 1 ≠ {1} we argue as in GS, p.197: The lhs is type ℕ (atom) and the rhs is of type SET. So they cannot be equal.^{†}

As for ∅ ≠ {∅}, recall from class that ST ⊢ ∅ ≠ T ≡ (∃x)x ∈ T.

Well, from ∅ ∈ {∅} we get (∃x)x ∈ {∅} by the ∃-rule (A[t] ⊢ (∃x)A[x]). Thus, ∅ ≠ {∅}.

†This is informal, but common-sensically correct. The rigorous way to go about it is to have an axiom that says “x ∈ y is false for any y of type atom”—in symbols, ¬(∃y)y ∈ x for any atom-type x. This axiom captures the “obvious truth” that atoms have no set structure, they cannot contain any members. An atom is not equal to ∅ however, for the latter has type SET.