All Chapters Included
,1.2 Set and Cardinal Numbers 2
Chapter 1:
Sets, Numbers and Cardinals
1.1 Sets and Numbers.
Solutions of some exercises
2. Given a set X, show that the relation is an order of the set of all
subsets of X. For which sets X is this order linear?
Solution. If A, B X are such that A B and A B , then there is b B such that
b A . Consequently B is not a subset of A, and hence is antisymmetric. If A B
C
then obviously A C , and so is transitive.
If X has at least two elements, say a and b, then neither {a} {b} nor
{b} {a} , so the order is not linear. On the other hand if X has at most
one element, then the only subsets of X are X and , and we then readily
see that the order is linear.
3. Describe a linear order over (a) the set ℕ 2 , and (b) the set ℝ 2 .
Solution for (a). Define (n, m) ( p, q) if n p or ( n p and m q ).
The parentheses in the preceding sentence are to guarantee there is unique
interpretation of the statement that defines <. It is left to the reader to prove
this relation is antisymmetric and transitive.
4. Show that if ~ is an equivalence relation over a set X, then every two
equivalence classes are either disjoint or equal.
Solution. Suppose [x] and [y] are two equivalence classes, and suppose [x]
[y] . Then there is a [x] [y] . Take any z [x] . Then a ~ x ~ z ,
and hence a ~ z . On the other hand, a [y] implies that y ~ a . The
transitivity of ~ applied to y ~ a and a ~ z yields y ~ z . Hence z [y] . We
proved that [x] [y] . By the symmetry of the argument, it follows that [y]
[x] . Hence [x] [y] .
7. Let X be a non-empty set and let f : X Y be any mapping. Show that “ u
~ v if and only if f (u) f (v) ” defines an equivalence relation over X.
Solution. (i) Reflexivity: u ~ u for every u, since f (u) f (u) for every u.
,1.2 Set and Cardinal Numbers 3
(ii) Symmetry: Suppose u ~ v . Then f (u) f (v) , hence f (v) f (u) ,
hence v ~ u . (iii) Transitivity:
Suppose u ~ v and v ~ w . Then f (u) f (v) and f (v) f (w) . Hence f (u)
f (w), and we conclude that u ~ w .
1.2 Sets and Cardinal Numbers
Solutions of the odd-numbered exercises
1. Let X be an infinite set. Show that for every finite subset A of X, X \ A X .
Show
that there is a subset B of X such that B 0 and such that X \ B X .
Solution of the first claim. Denote A {a1, a2, , an } . Use the assumption
that X is infinite and induction to construct an infinite countable subset
A1 {a1, a2 , , an , an 1, } of X. The mapping f (ak ) ak n defines a bijection from
A1
onto A1 \ A {an 1, an 2 , } . Then the mapping to g : X X \ A defined by
f (x) if x A
g(x) is a bijection.
x if x X \ A
3. Let A A1 , B B1 , let S be the set of all mappings A B , and let S1 be the
set
of all mappings A1 B1 . Show that S1 S .
Solution. By assumption there exist bijections :A A1 and :B B1 . Define
:S S1 as follows: for every f S , ( f ) : A1 B1 (f) ∘ f∘ 1
.
Notice that
( f ) : A1 B1 .
We now check that is a bijection.
One-to-one: Suppose (f ) ( f ) . Then ∘ f ∘ 1
, so
∘ 1
∘ f
1 2 1 2
1
∘ ∘ f ∘ 1
∘ 1
∘ ∘ f ∘ 1
∘ , and so f f .
1 1 1 2
Onto: Choose any g S1 and let f 1
1
∘ g ∘ . Then
(f) ∘ 1
∘ g∘ ∘ 1
g.
5. Prove Proposition 4:
(a) If J is countable and if each Aj , j J , is countable, then so is ∪A j .
j J
, 1.2 Set and Cardinal Numbers 4
(b)If for every i {1, 2,..., n} the set Xi is countable, then so is the set
product
X1 X2 ... Xn .
Hint for part (a): Use an argument based on Illustration 1.4 and Proposition 2.
,1.2 Set and Cardinal Numbers 2
Chapter 1:
Sets, Numbers and Cardinals
1.1 Sets and Numbers.
Solutions of some exercises
2. Given a set X, show that the relation is an order of the set of all
subsets of X. For which sets X is this order linear?
Solution. If A, B X are such that A B and A B , then there is b B such that
b A . Consequently B is not a subset of A, and hence is antisymmetric. If A B
C
then obviously A C , and so is transitive.
If X has at least two elements, say a and b, then neither {a} {b} nor
{b} {a} , so the order is not linear. On the other hand if X has at most
one element, then the only subsets of X are X and , and we then readily
see that the order is linear.
3. Describe a linear order over (a) the set ℕ 2 , and (b) the set ℝ 2 .
Solution for (a). Define (n, m) ( p, q) if n p or ( n p and m q ).
The parentheses in the preceding sentence are to guarantee there is unique
interpretation of the statement that defines <. It is left to the reader to prove
this relation is antisymmetric and transitive.
4. Show that if ~ is an equivalence relation over a set X, then every two
equivalence classes are either disjoint or equal.
Solution. Suppose [x] and [y] are two equivalence classes, and suppose [x]
[y] . Then there is a [x] [y] . Take any z [x] . Then a ~ x ~ z ,
and hence a ~ z . On the other hand, a [y] implies that y ~ a . The
transitivity of ~ applied to y ~ a and a ~ z yields y ~ z . Hence z [y] . We
proved that [x] [y] . By the symmetry of the argument, it follows that [y]
[x] . Hence [x] [y] .
7. Let X be a non-empty set and let f : X Y be any mapping. Show that “ u
~ v if and only if f (u) f (v) ” defines an equivalence relation over X.
Solution. (i) Reflexivity: u ~ u for every u, since f (u) f (u) for every u.
,1.2 Set and Cardinal Numbers 3
(ii) Symmetry: Suppose u ~ v . Then f (u) f (v) , hence f (v) f (u) ,
hence v ~ u . (iii) Transitivity:
Suppose u ~ v and v ~ w . Then f (u) f (v) and f (v) f (w) . Hence f (u)
f (w), and we conclude that u ~ w .
1.2 Sets and Cardinal Numbers
Solutions of the odd-numbered exercises
1. Let X be an infinite set. Show that for every finite subset A of X, X \ A X .
Show
that there is a subset B of X such that B 0 and such that X \ B X .
Solution of the first claim. Denote A {a1, a2, , an } . Use the assumption
that X is infinite and induction to construct an infinite countable subset
A1 {a1, a2 , , an , an 1, } of X. The mapping f (ak ) ak n defines a bijection from
A1
onto A1 \ A {an 1, an 2 , } . Then the mapping to g : X X \ A defined by
f (x) if x A
g(x) is a bijection.
x if x X \ A
3. Let A A1 , B B1 , let S be the set of all mappings A B , and let S1 be the
set
of all mappings A1 B1 . Show that S1 S .
Solution. By assumption there exist bijections :A A1 and :B B1 . Define
:S S1 as follows: for every f S , ( f ) : A1 B1 (f) ∘ f∘ 1
.
Notice that
( f ) : A1 B1 .
We now check that is a bijection.
One-to-one: Suppose (f ) ( f ) . Then ∘ f ∘ 1
, so
∘ 1
∘ f
1 2 1 2
1
∘ ∘ f ∘ 1
∘ 1
∘ ∘ f ∘ 1
∘ , and so f f .
1 1 1 2
Onto: Choose any g S1 and let f 1
1
∘ g ∘ . Then
(f) ∘ 1
∘ g∘ ∘ 1
g.
5. Prove Proposition 4:
(a) If J is countable and if each Aj , j J , is countable, then so is ∪A j .
j J
, 1.2 Set and Cardinal Numbers 4
(b)If for every i {1, 2,..., n} the set Xi is countable, then so is the set
product
X1 X2 ... Xn .
Hint for part (a): Use an argument based on Illustration 1.4 and Proposition 2.
