Formal MethodsKey to Homework Assignment 6, Part 2March 5, 200731. A student is asked to prove that for any sets A, B, and C,A − (B ∪ C) = (A − B) ∩ (A − C).The student writes: “Let x ∈ A −(B ∪C). Then x ∈ A and x 6∈ B or x 6∈ C. Therefore,x ∈ A − B and x ∈ A − C. Thus A − (B ∪ C) = (A − B) ∩ (A − C).” What, if anythingis wrong with this proof?There are (at least) a couple of problems with this proof. First, if x ∈ A − (B ∪ C),then x ∈ A and x 6∈ (B ∪ C). Nowx 6∈ (B ∪ C) ⇔ ¬(x ∈ B ∪ C)⇔ ¬[(x ∈ B) ∨ (x ∈ C)]⇔ [¬(x ∈ B)] ∧ [¬(x ∈ C)]⇔ (x 6∈ B) ∧ (x 6∈ C).So if x ∈ A − (B ∪ C), then x ∈ A and x 6∈ B and x 6∈ C. So the statement “Thenx ∈ A and x 6∈ B or x 6∈ C,” is incorrect.Since this first deduction is incorrect and the conclusion is (part of) a correct res ult,there must be an additional “cancelling” error. It’s in the statement “Therefore, x ∈A − B and x ∈ A − C .” This isn’t implied by the preceding statement. (Why not?)A second problem with this is that even if the student’s argument were correct, shewould have only showed x ∈ A − (B ∪ C) implies x ∈ (A − B) ∩ (A − C). That is,A−(B ∪C) ⊆ (A−B)∩(A−C). She would also need to show that (A−B)∩(A−C) ⊆A − (B ∪ C).32.(a) Prove Theorem 2.6(a): Let A and B be subsets of some universal set U. Then (A∪B)0=A0∩ B0.We could prove this by showing that one set is a subset of the other and vice-versa.However, a proof that uses the correspondence between logical operators and set op-erations is a little easier:x ∈ (A ∪ B)0⇔ ¬(x ∈ A ∪ B)1⇔ ¬[(x ∈ A) ∨ (x ∈ B)]⇔ ¬(x ∈ A) ∧ ¬(x ∈ B)⇔ (x 6∈ A) ∧ (x 6∈ B)⇔ (x ∈ A0) ∧ (x ∈ B0)⇔ x ∈ (A0∩ B0)35.(b) Prove that for any sets A and B, A ∩ B and A − B are disjoint.We need to see that (A ∩ B) ∩ (A − B) = ∅. So we look at what happens if there’s anelement in (A ∩ B) ∩ (A − B) :x ∈ (A ∩ B) ∩ (A − B) ⇔ (x ∈ A) ∧ (x ∈ B) ∧ (x ∈ A) ∧ (x 6∈ B)⇔ (x ∈ A) ∧ [(x ∈ B) ∧ ¬(x ∈ B)]⇔ (x ∈ A) ∧ F⇔ FIn other words, the assumption that x ∈ (A ∩ B) ∩ (A − B) leads to a contradiction.So it must be the case that (A ∩ B) ∩ (A − B) = ∅.40.(a) Prove that for any s ets A and B, A − (A ∩ B0) = A ∩ B.Once again, we use the close relation between set operations and logic operators:x ∈ A − (A ∩ B0) ⇔ (x ∈ A) ∧ (x 6∈ A ∩ B0)⇔ (x ∈ A) ∧ ¬(x ∈ A ∩ B0)⇔ (x ∈ A) ∧ ¬[(x ∈ A) ∧ ¬(x ∈ B)]⇔ (x ∈ A) ∧ [¬(x ∈ A) ∨ (x ∈ B)]⇔ [(x ∈ A) ∧ ¬(x ∈ A)] ∨ [(x ∈ A) ∧ (x ∈ B)]⇔ F ∨ [(x ∈ A) ∧ (x ∈ B)]⇔ x ∈ A ∩ B53. For each natural number n, let An= {7, n}. Find ∪n∈NAnand ∩n∈NAn.(a) We see that every positive integer belongs to ∪n∈NAnsince n ∈ An, for all positiveintegers n. Furthermore, the union contains no other values, since each Ancontainsonly positive integers.(b) ∩n∈NAn= {7}. Clearly 7 ∈ Anfor all positive integers n. Furthermore, if k is anyother positive integer, then k ∈ Ak, but k 6∈ Am, for all m 6= k. So k 6∈ ∩n∈NAn.54. For each natural number n, let An= {k ∈ N : k ≥ n}. Find ∪n∈NAnand ∩n∈NAn.2(a) ∪n∈NAn= N. A1= N. So every positive integer belongs to the union. Since eachAncontains only positive integers, there can’t be any other elements in the union.(b) ∩n∈NAn= ∅. If m is any positive integer, then m 6∈ Am+1. So m 6∈ ∩n∈NAn.55. For each natural numb er n, let An= [−1/n, 1/n] and Bn= (−1/n, 1/n). Find ∩n∈NAnand ∩n∈NBn.(a) ∩n∈NAn= {0}. 0 ∈ [−1/n, 1/n], for all positive integers n. So 0 ∈ ∩n∈NAn. If xis any positive real number, there exists a positive integer m such that 1/m < x.So x 6∈ Amand x 6∈ ∩n∈NAn. A completely analogous argument shows that nonegative reals are in the intersection.(b) ∩n∈NBn= {0}. Perhaps surprisingly, the arguments are almost identical to thosegiven in part (a).56. For each natural number n, let An= [1 − 1/n, 1 + 1/n]. Find ∪n∈NAnand ∩n∈NAn.(a) ∪n∈NAn= [0, 2]. A1= [0, 2], and if n ≥ 2, then An⊆ A1.(b) ∩n∈NAn= {1}. The reasoning here is very similar to the reasoning in 55(a): inthis problem the An’s have just been shifted one unit to the right on the real