Previous: Homework assignment 06Homework assignment 06 Up: Homework assignmentsHomework assignments Next: Homework assignment 08Homework assignment 08
Document also available in PDF, Postscript, DVI, pure text and LaTeX.

Homework assignment 07



3.1. Sets

Exercise 1  [6 p. 177]   Describe each of the following sets by giving a characterizing property:
  1. {1,2,3,4,5}
  2. {1,3,5,7,9,11,...}
  3. {Melchior,Gaspar,Balthazar}
  4. {0,1,10,11,100,101,110,111,1000,...}
Proof: [Correction]
  1. {1,2,3,4,5} is the set of integers from 1 to 5.
  2. {1,3,5,7,9,11,...} is the set of all odd integers.
  3. {Melchior,Gaspar,Balthazar} is the set of wise men.
  4. {0,1,10,11,100,101,110,111,1000,...} is the set of all non negative integers in binary notation.
Exercise 2  [29 p. 179]  
  1. Recall that ordered pairs must have the property that (x,y) = (u,v) if and only if x=u and y=v. Prove that {{x},{x,y}} = {{u},{u,v}} if and only if x=u and y=v. Therefore, although we know that (x,y)!= {x,y}, we can define the ordered pair (x,y) as the set {{x},{x,y}}.
  2. Show by an example that we cannot define the ordered triple (x,y,z) as the set {{x},{x,y},{x,y,z}}.
Proof: [Correction] It's clear that if (x,y)=(u,v), then {{x},{x,y}} = {{u},{u,v}}. Let's prove the converse.

Assume {{x},{x,y}} = {{u},{u,v}}. There are two cases to check.

Case 1: x=y. We have {{x},{x,y}} = {{x}}. Therefore, {{u},{u,v}} as only one element {x}. Then, {u}={x} and thus u=x. Also, {u,v}={u}, and thus v=u=x. Conclusion: (u,v)=(x,x)=(x,y).

Case 2: x y. We know that {u} belongs to {{x},{x,y}}. But since {x,y} has two elements, and {u} only one, we have necessarily {u}={x}, and thus u=x. By the same argument of size, we get that {x,y}={u,v}={x,v}, and it follows that v=y. Conclusion: (u,v)=(x,y).

Exercise 3  [44 p. 183]   Which of the following are true for all sets A, B, and C? Prove or give a counter example.
  1. A union A = A
  2. B intersect B = B
  3. (A intersect B)' = A' intersect B'
  4. (A')' = A
  5. A-B = (B-A)'
  6. (A-B)intersect (B-A) = Ø
  7. If A intersect B = Ø, then Aincluded in B.
  8. B× A = A × B
  9. Ø × A = Ø
  10. Ø intersect {Ø} = Ø
  11. (A-B)union(B-C) = A-C
  12. (A-C)intersect(A-B) = A - (B union C)
Proof: [Correction]
  1. A union A = A is true as
    A union A = {x|(xin A) (xin A)}   (by definition)
      = {x|xin A}   (by self reference)
      = A
  2. B intersect B = B is true as
    B intersect B = {x|(xin B) /\ (xin B)}   (by definition)
      = {x|xin B}
      = B
  3. (A intersect B)' = A' intersect B' is false.
    Counter example: Take A := {a, b, c}, B := {c, d, e}, and take S := {a,b,c,d,e} as universal set. Then, (A intersect B)' = {c}' = {a,b,d,e} whereas A' intersect B' = {d,e}intersect{a,b} = Ø.

  4. (A')' = A is true, as
    (A')' = {x|((xin A)')'}   (by definition)
      = {x | (xnot in A)'}
      = {x | xin A}    =    A

  5. A-B = (B-A)' is false.

    Counter example: Take A = {a, b, c}, B = {c, d, e}, and S = {a,b,c,d,e}. Then, A-B = {a,b} while (B-A)' = {d,e}' = {a,b,c}. This is because
    A-B = A intersect B' = (A' union B)' != (A' intersect B)' = (B-A)'.

  6. (A-B)intersect (B-A) = Ø is true, as
    (A-B)intersect (B-A) = (A intersect B') intersect (B intersect A')
      = (A intersect A') intersect (B intersect B')
      = Ø intersect Ø
      = Ø

  7. ``If A intersect B = Ø, then Aincluded in B'' is false.

    Counter example: Take A := {a}, B := {b}, then A intersect B = Ø, whereas A not includes inB.

  8. B× A = A × B is false because if we take A:={a} and B := {b} , then A× B = {(a,b)} != {(b,a)} = B × A.

  9. Ø × A = Ø is true, as
    Ø× A = {(x,y)|(xinØ) /\ (yin A)}   (by definition)
      = {(x,y)|False /\ (yin A)}
      = {(x,y)|False}
      = Ø

  10. Ø intersect {Ø} = Ø is true because,
    Ø intersect {Ø} = {x|(xinØ)/\(xin{Ø})}   (by definition)
      = {x|False /\ (xin{Ø})}
      = {x|False}
      = Ø

  11. (A-B)union(B-C) = A-C is false.

    Counter example: take A := {a,b}, B:=Ø, C := {b,c}, then (A-B) union (B-C) = {a,b} union Ø = {a,b}, whereas A-C = {a}.

  12. (A-C)intersect(A-B) = A - (B union C) is true as,
    (A-C)intersect(A-B) = (A intersect C') intersect (A intersect B') (by definition)
      = A intersect (B' intersect C')
      = A intersect (B union C)' (de Morgan's)
      = A - (B union C) (by definition)
Exercise 4  [49 p. 183]   Prove that (A)union(B)included in or equal to (Aunion B) where A and B are arbitrary sets.
Proof: [Correction] Let C be an element of (A)union(B). We just need to prove that C is also an element of (Aunion B).

Since Cin(A)union(B), we know that C belongs to (A) or to (B), or both. By symmetry, we can assume that C belongs to (A), i.e. C is a subset of A. Since A itself is a subset of Aunion B, we get that C is also a subset of Aunion B. Therefore, C is an element of (Aunion B).

Exercise 5  [75 p. 187]   Use Cantor's diagonalization method to show that the set of all infinite strings of the letters {a,b} is not countable.
Proof: [Correction] Assume that the set of all infinite strings of the letters {a,b} set is countable, and take s1,s2,··· to be an enumeration of its elements. We are going to construct an infinite string t of the letters {a,b} which is different from all the si, which will yield the desired contradiction.

For any k, let sk,k be the k-th letter of sk. Let t:=t1,...,tk,... be the string defined by tk:=a if sk,k=b and tk:=a if sk,k=a. By construction, t is different from all the si, as wanted.
Previous: Homework assignment 06Homework assignment 06 Up: Homework assignmentsHomework assignments Next: Homework assignment 08Homework assignment 08
Homework assignment 07 / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:29 2003