Mathematics 220 — Homework 11
1. Determine if the set of all functions f : {0, 1} → N is countable.
Solution: The set is countable.
Proof. Let F be the set of all functions from {0, 1} to N.
Consider the function which sends f : {0, 1} → N to the tuple (f (0), f (1)). Namely,
we define
Φ:F →N×N by
Φ(f ) = (f (0), f (1)) .
Then, we see that
this function Φ is surjective. (This is because, given a pair (a, b) ∈ N × N, we
can define the function f : {0, 1} → N by f (0) = a and f (1) = b and it satisfies
Φ(f ) = (a, b)).
this function Φ is injective: let f, g ∈ F such that Φ(f ) = Φ(g). It means that
(f (0), f (1)) = (g(0), g(1)) so f (0) = g(0) and f (1) = g(1) which means exactly
that f = g.
Therefore, we have a bijection between F and N × N. Since the latter is known to
be countable, we see that F is countable as well.
2. Prove the following statements
(a) If A is countable but B is uncountable, then B − A is uncountable.
Solution:
Proof. Assume for a contradiction that B − A is countable. Since A ∩ B ⊆ A is
countable, we see that B = (A ∩ B) ∪ (B − A) is a union of two countable sets
and thus countable. This gives a contradiction and proves the first assertion.
(b) Between any real numbers a, b such that a < b there are uncountably many irra-
tionals.
Solution: Let A = Q and B = (a, b) (ie the open interval from a to b). Then
we know that B is uncountable (it is in bijection with R), while Q is countable.
Mathematics 220 — Homework 11
By the result in (a) above, we know that B − A, which is the set of irrational
numbers between a and b, is uncountable.
3. Let S, T be sets. Prove the following
(a) If |S| ≤ |T | then |P (S) | ≤ |P (T ) |.
Solution:
Proof. Assume that |S| ≤ |T | and hence there is an injection from f : |S| → |T |.
We must construct an injection from P (S) → P (T ).
Let g : P (S) → P (T ) be defined by
g(A) = f (A) = {f (a) | a ∈ A} where A ∈ P (S)
ie - we just apply f to each element of A.
Now let A, B ∈ P (S) and assume that g(A) = g(B). We now show A = B.
Let x ∈ A. Hence f (x) = y ∈ f (A) = g(A). Since g(A) = g(B) we must
have y ∈ g(B). Thus there is some z ∈ B so that y = f (z). But then since
f is injective, x = z and so x ∈ B. Hence A ⊆ B.
The reverse inclusion is similar. Let z ∈ B. Hence f (z) = y ∈ f (B) =
g(B). Since g(A) = g(B) we must have y ∈ g(A). Thus there is some
x ∈ A so that y = f (x). But then since f is injective, x = z and so z ∈ A.
Hence B ⊆ A.
Thus g is injective and the result follows.
(b) If |S| = |T | then |P (S) | = |P (T ) |.
Solution:
Proof. Assume |S| = |T |. Hence there is a bijection f : S → T . We must
construct an injection from P (S) → P (T ). We use the same function as above.
Let g : P (S) → P (T ) be defined by
g(A) = f (A) = {f (a) | a ∈ A} where A ∈ P (S)
By the previous question we know that g is injective. It suffices to prove that
g is also surjective. Let B ∈ P (T ) and since f is a bijection, its inverse exists
and we may set
A = f −1 (b) | b ∈ B
We must now prove that g(A) = B.
Page 2
Mathematics 220 — Homework 11
Let x ∈ g(A). Then x = f (a) for some a ∈ A. But then a = f −1 (b) for
some b ∈ B. Hence x = f (f −1 (b)) = b. So x ∈ B.
Now let x ∈ B. By construction f −1 (x) ∈ A. Hence f (f −1 (x)) ∈ f (A) =
g(A). But f (f −1 (x)) = x, so x ∈ g(A)
Thus g is surjective and we are done.
4. Show that there exist infinitely many pairs of distinct natural numbers a, b such that
17a − 17b is divisible by 2025.
Hint: Pigeons can help.
Solution:
Proof. Consider the set
{171 , 172 , . . . , 172026 }.
If we consider their remainders when dividing by 2025, we see that there are at
most 2025 possible remainders, but 2026 numbers in the set. So by the pigeonhole
principle, there exists distinct integers a and b such that 17a ≡ 17b (mod 2025). This
implies that their difference is divisible by 2025.
We then repeat this process on sets of the form
Sk := {171+2026k , 172+2026k , . . . , 172024+2026k },
for each natural number k, so as to obtain infinitely many such pairs.
5. Assume that R and√R+ = {x ∈ R | x > 0} are equinumerous.
Prove that (−∞, − 29) and R are equinumerous.
Solution: √
We construct a function g : R → (−∞, − 29) made up of three components:
• Given the assumption, there exists a bijective function f : R → R+ .
• Let h : R+ → (−∞, 0), where h(x) = −x. This has inverse h1 (y) = −y where we
note that h ◦ h1 (y) = y and h1 ◦ h(x) = x so h1 is indeed the (two-sided) inverse of
h. Therefore, h is bijective. √ √
• Let j : (−∞,
√ 0) → (−∞, − 29), where j(y) = y − 29. This has inverse
j1 (z) = z + 29, where note that j ◦ j1 (z) = z and j1 ◦ j(y) = y so j1 is the in-
verse of j. So j is bijective.
Page 3
Mathematics 220 — Homework 11
Now define g = j ◦ h ◦ f .
Since f, h, j are all bijective, from a theorem
√ in PLP (Theorem 10.5.3) we conclude
that g is also bijective. Therefore, (−∞, − 29) and R are equinumerous.
6. Prove or disprove: for any non-empty sets A, B, C, if |A × B| = |A × C| then |B| = |C|.
Solution:
Proof. The statement is false. Take A = N, B = {1} and C = {1, 2}. Then we have
|A × B| = |N × {1}| = |N| (find an easy bijection between N × {1} and N).
|A × C| = |N × {1, 2}| = |N| because (two possible arguments):
– N × {1, 2} ⊆ N × N so it is denumerable as an infinite subset of a denu-
merable set.
– N × {1, 2} = A1 ∪ A2 where
A1 = {(n, b) ∈ N × {1, 2} : b = 1} and A2 = {(n, b) ∈ N × {1, 2} : b = 2}.
It is easy to see (find bijections) that |A1 | = |N| and |A2 | = |N|. As a
union of denumerable sets, A × C is denumerable.
So we get that |A × B| = |A × C|, but |B| < |C|.
7. Let A be a finite set and f : R → A. Show that there exists some a ∈ A such that
f −1 ({a}) is uncountable.
Solution:
Proof. Let us argue by contradiction and assume that for all a ∈ A the set f −1 ({a})
is countable. We can write
[
R= f −1 ({a})
a∈A
Since R is a finite union of countable sets, then R is countable. This is a contradiction.
8. For a set X we define the set
FX
Page 4
Mathematics 220 — Homework 11
to be the set of all functions X → {0, 1}.
For each subset Y ⊆ X, define fY to be the function
fY : X −→ ({0, 1}
1 if x ∈ Y
x 7−→
0 if x ∈ X − Y .
This is an element of FX . It is called the characteristic function of Y .
(a) When X = R, draw the graph of fY in the three following cases:
1. Y = [0, 1],
2. Y = [0, +∞),
3. Y = [−1, 2] ∪ [3, 4].
Reflect on the fact that fY keeps track of the elements of X which lie in Y .
(b) Now back to the general case of an arbitrary set X. Prove that the function
F : P(X) −→ FX
Y 7−→ fY
is a bijection by giving the inverse of F .
Take an arbitrary function g in FX and express in terms of g the set Y such that
F (Y ) = g.
Solution: We define the following function:
G : FX → P(X)
g 7→ g −1 ({1})
We prove that F ◦ G = idFX and G ◦ F = idP(X) .
• Proof that F ◦ G = idFX :
Let g ∈ FX . By definition, F ◦ G(g) = F (g −1 ({1})) is the function
X −→ ({0, 1}
1 if x ∈ g −1 ({1}), namely if g(x) = 1
x 7−→
/ g −1 ({1}), namely if g(x) =
0 if x ∈ ̸ 1, i.e., if g(x) = 0
so we see that for all x ∈ X, we have F ◦ G(g) (x) = g(x). This means
F ◦ G(g) = g.
• Proof that G ◦ F = idP(X) :
Let Y ∈ P(X) namely Y ⊆ X. By definition,
G ◦ F (Y ) = G(F (Y )) = G(fY ) = fY−1 ({1}) = {x ∈ X : fY (x) = 1}.
Page 5
Mathematics 220 — Homework 11
But by definition of fY , we have Y = {x ∈ X : fY (x) = 1} (fY is precisely
the function that takes value 1 at elements of Y and value 0 outside of Y ). So
G ◦ F (Y ) = Y .
(c) Prove that FN is not countable.
Solution: Question (b) shows that |FN | = |P(N)| and we know that P(N) is
not countable. So FN is not countable.
(d) For n ∈ N, what is the cardinality of the power set of {1, 2, . . . , n}? Justify your
answer using question (b).
Solution:
– Question (b) shows that |P({1, 2, . . . , n})| = |F{1,2,...,n} |.
– By a standard combinatorial argument, we know that |F{1,2,...,n} | = 2n (to
each element of {1, 2, . . . , n} we assign value 0 or 1...).
– So |P({1, 2, . . . , n})| = 2n .
Remark: one can also prove |P({1, 2, . . . , n})| = 2n by induction.
Page 6