SOLUTION SET 2—DUE 2/6/2008Please report any errors in this document to Ian Sammis ([email protected]).Problem 1 (#2.1.8). Determine whether these statements are true or false.a) ∅ ∈ {∅}b) ∅ ∈ {∅, {∅}}c) {∅} ∈ {∅}d) {∅} ∈ {{∅}}e) {∅} ⊂ {∅, {∅}}f) {{∅}} ⊂ {∅, {∅}}g) {{∅}} ⊂ {{∅}, {∅}}Solution.a) True—the empty set is actually a member of the set on the right.b) True again—once again, the empty set is actually in the set on the right.c) This one’s false. The empty set is in the set on the right, but the set containingthe empty set is not.d) This is true—the se t containing the empty se t is an element (in fact, the onlyelement) of the set on the right.e) True—since the empty set is in the set on the right, every element of the firstset is in the co ntaining set.f) True again, for the same reason.g) False. The set on the right is nothing but a deeply stupid way of writing{{∅}}. Thus the two sets are actually equal. In this book (remember—not in allbooks!) A ⊂ B is false if A = B.Problem 2 (#2.1.16). Find two sets A and B such that A ∈ B and A ⊆ B.Solution. From the previous problem, A = {∅}, B = {∅, {∅}} works.Problem 3 (#2.1.32). Explain why (A ×B) ×(C ×D) and A ×(B ×C) ×D arenot the same.Solution. Let a, b, c, d b e members of A, B, C, D, res pectively. A typical elementof (A × B) × (C × D) is ((a, b), (c, d))—an ordered pair of two ordered pairs. Atypical element of A × (B × C) × D is (a, (b, c), d)—an ordered triplet, the centerelement of which is an or dered pair. Although each contains the same information(one element each from A, B, C, and D), the information is organized differently ineach case.Problem 4 (#2.1.34). Translate each of these quantifications into English anddetermine its truth value.a) ∃x ∈ R(x36= −1).b) ∃x ∈ Z(x + 1 > x).c) ∀x ∈ Z(x −1 ∈ Z).d) ∀x ∈ Z(x2∈ Z).Solution. In English:12 SOLUTION SET 2—DUE 2/6/2008a) There exists some real number whose cube is no t -1. Obviously true (0, forexample).b) There exists an integer such that the next integer is Yes–in fact all of them.c) One less than every integer is, in fact, an integer. Again... obviously, yes.d) The square of every integer is an integer. Of course it is.Problem 5 (#2.1.36). Find the truth set of each of these predicates where thedomain is the set of integers.a) P (x) : “x3≥ 1”b) Q(x) : “x2= 2”c) R(x) : “x < x2”Solution. It’s impor tant here to remember that we’re on the integers, not the reals.a) Since every integer except zero has a cube that’s at le ast one, the truth set isZ \{0}.b) There aren’t any integers that square to 2, so the truth set is just ∅.c) Every negative integer is less than its (positive) square, as is every integer 2or larger. The truth set is N \ {0, 1}.Problem 6 (#2.1.38). This exercise presents Russell’s paradox. Let S be theset that containsa set x if the set x does not belong to itself, so S = {x|x 6∈ x}.a) Show that the assum ption that S is a member of S leads to a contradiction.b) Show tha t the assumption that S is not a member of S leads to a contradic-tion.Solution. Russell’s paradox boils down to a set-theory version of “This propositionis false.”a) Suppose S were in S. Then, by the definition of S, S would not be in S.Contradiction.b) Suppose S were not in S. Then, by the definition of S, S must be a memberof S. Contradiction.(These days set theory doesn’t allow the universal set to include anything soabsurdly vast as “all sets.”)Problem 7 (#2.2.2). Suppose that A is the set of sophomores at your school andB is the set of students in discrete mathematics at your school. Express each ofthese sets in terms of A and B.a) The set of sophomores taking discrete mathematics in your school.b) The set of sophomores in your school who are not taking discrete mathematics.c) The set of students at your school who are either sophomores or are takingdiscrete mathematics.d) The set of students at your school who are either not sophomores or are nottaking discrete mathematics.Solution. These are simple enough to not need much further comment:a) A ∩ B.b) A \ B.c) A ∪ B.d)A ∪ BProblem 8 (#2.2.8). Prove the idempotent laws by showinga) A ∪ A = A.SOLUTION SET 2—DUE 2/6/2008 3b) A ∩ A = A.Solution. In each case, we want to move back to logic, where we already have theidempo tent laws.a) A ∪A = {x|(x ∈ A) ∨(x ∈ A)}. But we know p ∨p = p, so this is just the set{x|x ∈ A} , or A itself.b)A ∩A = {x|(x ∈ A) ∧(x ∈ A)}. But we know p ∧p = p, so this is just the set{x|x ∈ A} , or A itself.Problem 9 (#2.2.16). Let A and B be sets. Show thata) (A ∩ B) ⊆ A.b) A ⊆ (A ∪ B).c) A \ B ⊆ A.d) A ∩ (B \ A) = ∅.e) A ∪(B \ A) = A ∪ B.Proof. Again, write the sets using s ymbolic logic.a) For x ∈ (A ∩ B), x ∈ A and x ∈ B. So, x ∈ A. Since x ∈ (A ∩ B) ⇒ x ∈ A,we have (A ∩ B) ⊆ A.b) Suppose x ∈ A. Then certainly (x ∈ A) ∨ (x ∈ B). So, x ∈ A ∪ B. Sincex ∈ A ⇒ x ∈ A ∪B, we have A ⊆ A ∪ Bc) Suppos e x ∈ A \B. Then (x ∈ A)∧(x 6∈ B). So x ∈ A. Thus (x ∈ (A\B)) ⇒x ∈ A, so A \ B ⊆ A.d) Suppose x ∈ A ∩ (B \ A). So x ∈ A and x ∈ B \ A. Since x ∈ B \ A, x ∈ Band x 6∈ A. But x ∈ A! Contradiction, so our assumption x ∈ A ∩(B \ A) must bewrong. Thus A ∩ (B \A) must be empty.e) Suppose x ∈ A ∪ (B \ A). Then x ∈ A or x ∈ B \ A. If x ∈ B \ A,(x ∈ B) ∨ (x 6∈ A), so x ∈ B. So x ∈ A or x ∈ B, which implies x ∈ A ∪ B. Thus,x ∈ A ∪ (B \ A) ⇒ x ∈ A ∪ B, or A ∪ (B \ A) ⊆ A ∪ B.Now, suppose x ∈ A ∪ B. Either x ∈ A or x 6∈ A. If x 6∈ A, then x ∈ B bydisjunctive syllogism. Thus, x ∈ A, or (x 6∈ A) ∧ (x ∈ B), so x ∈ A ∪ (B \ A).Thus, A ∪B ⊆ A ∪(B \A). Since A ∪ B ⊆ A ∪(B \A) and A ∪(B \A) ⊆ A ∪B),A ∪ B = A ∪ (B \ A).Problem 10 (#2.4 .30). Can you conclude that A = B, if A, B,, and C …