Homework assignment 06
Homework assignments
Homework assignment 08
Document also available in PDF, Postscript, DVI, pure text and LaTeX.
3.1. Sets
Exercise 1 [6 p. 177]
Describe each of the following sets by giving a characterizing
property:
-
{1,2,3,4,5}
- {1,3,5,7,9,11,...}
- {Melchior,Gaspar,Balthazar}
- {0,1,10,11,100,101,110,111,1000,...}
Proof: [Correction]
-
{1,2,3,4,5} is the set of integers from 1 to 5.
- {1,3,5,7,9,11,...} is the set of all odd integers.
- {Melchior,Gaspar,Balthazar} is the set
of wise men.
- {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]
-
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}}.
- 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.
-
A union A = A
- B intersect B = B
- (A intersect B)' = A' intersect B'
- (A')' = A
- A-B = (B-A)'
- (A-B)intersect (B-A) = Ø
- If A intersect B = Ø, then Aincluded in B.
- B× A = A × B
- Ø × A = Ø
- Ø intersect {Ø} = Ø
- (A-B)union(B-C) = A-C
- (A-C)intersect(A-B) = A - (B union C)
Proof: [Correction]
-
A union A = A is true as
A union A |
= {x|(xin A) (xin A)} |
|
(by definition) |
|
= {x|xin A} |
|
(by self reference) |
|
= A |
- B intersect B = B is true as
B intersect B |
= {x|(xin B) /\ (xin B)} |
|
(by definition) |
|
= {x|xin B} |
|
= B |
- (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} =
Ø.
- (A')' = A is true, as
(A')' |
= {x|((xin A)')'} |
|
(by definition) |
|
= {x | (xnot in A)'} |
|
= {x | xin A} = A |
- 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)'.
- (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 Ø |
|
= Ø |
- ``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.
- B× A = A × B is false because if we take A:={a}
and B := {b} , then A× B = {(a,b)} != {(b,a)} = B
× A.
- Ø × A = Ø is true, as
Ø× A |
= {(x,y)|(xinØ) /\ (yin A)} |
|
(by definition) |
|
= {(x,y)|False /\ (yin A)} |
|
= {(x,y)|False} |
|
= Ø |
- Ø intersect {Ø} = Ø is true because,
Ø intersect {Ø} |
=
{x|(xinØ)/\(xin{Ø})} |
|
(by definition) |
|
= {x|False /\ (xin{Ø})} |
|
= {x|False} |
|
= Ø |
- (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}.
- (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.
Homework assignment 06
Homework assignments
Homework assignment 08
Homework assignment 07 /
CSM MACS-358 /
Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:29 2003