Discrete Mathematics

Exercises 8 – Solutions with Commentary

Marcelo Fiore Ohad Kammar Dima Szamozvancev

11. On surjections and injections

11.1. Basic exercises
1. Give two examples of functions that are surjective, and two examples of functions that are not.

Surjective. Absolute value function to the naturals |−|: Z ↠ N; natural log function
ln: R+0 ↠ R; first projection function from the Cartesian product of two (nonempty) sets
π1 : A × B ↠ A.
Not surjective. Integer squaring function on the naturals: (−)2 : N → N (only returns perfect
squares); constant function c b : A → B with value b ∈ B (always outputs b if B is not the
singleton set); successor function (−) + 1: N → N (0 is not the successor of any number).

2. Give two examples of functions that are injective, and two examples of functions that are not.

Injective. The inclusion/injection function ι : S ↣ A for any subset S of A; exponential

function x 7→ e x : R ↣ R; perfect hash function.

Not injective. Integer squaring function: (−)2 : Z → Z (since x 2 = (−x)2 ); quotient function
q(a) = [a] E : A → A/E for an equivalence relation E (related elements map to the same
equivalence class); sin(x): [0, 2π] → [−1, 1] since sin(0) = sin(2π) = 0.

11.2. Core exercises

1. Explain and justify the phrase injections can be undone.

Every injection (from a non-empty domain) has a retraction which “undoes” its effect. If
i : A ↣ B is an injection, every b in B is mapped to by at most a ∈ A; thus, a retraction can
be defined as (
a if ∃a ∈ A. i(a) = b
r(b) =
a0 otherwise
where a0 is any element of A. This is total, since every b is either mapped to the source a
for which i(a) = b, or to the fixed a0 . It is also functional, since there may only be at most
one a for which i(a) = b. By construction, r ◦ i = idA, so the two form a section-retraction
pair.

The implication holds in the other direction as well: every section s : A → B (with a retraction
r : B → A) is an injection. To see this, consider a, a′ ∈ A and assume s(a) = s(a′ ). But since
r ◦ s = idA, we have that r(s(a)) = r(s(a′ )) implies a = a′ , so s must be an injection.

2. Show that f : A → B is a surjection if and only if for all sets C and functions g, h: B → C ,
g ◦ f = h ◦ f implies g = h.
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

(⇒) Let f : A ↠ B be a surjection: for all b ∈ B there exists an a ∈ A such that f (a) = b.
Furthermore, let g, h: B → C be functions and assume ⃝ 1 g ◦ f = h ◦ f . We need to show
that g = h, that is, for all b ∈ B , g(b) = h(b). But by assumption any b ∈ B is equal to
f (a) for some a ∈ A, so the condition is equivalent to g( f (a)) = h( f (a)), which is just ⃝
1 .

(⇐) We show the contrapositive: if f : A ↠ B is not surjective, then there exists a C and
functions g, h: B → C such that g ◦ f = h ◦ f but g ̸= h. If f is not surjective, there exists
a b0 ∈ B such that for all a ∈ A, f (a) ̸= b0 . We can therefore choose two functions g and h
such that they match on the range of f , but differ on b0 . For example, take C to be B with
a new distinguished element ⋆ added: C = B ∪ { ⋆ }. Let g : B → B ∪ { ⋆ } be the inclusion
g(b) = b, and let h(b0 ) = ⋆ and h(b) = b for all b ̸= b0 . Then, g ◦ f = h ◦ f , since g and h
defined to be equal for all elements in the range of f , but they differ on the element b0
not “covered” by f , hence g ̸= h.

The (⇐) direction can be presented as a non-contrapositive argument as well. Let

f : A ↠ B be a function and assume for all g, h: B → C , if g ◦ f = h ◦ f then g = h.
We need to show that for all b ∈ B there exists an a ∈ A such that f (a) = b. Choose
−
→
C = [2] = { 0, 1 } and define g = χB and h = χ −→ f (A)
, where f (A) ⊆ B is also called the
range of f , i.e. the set { f (a) ∈ B | a ∈ A}. That is, g(b) = 1 for all b, and h(b) = 1 for
all b in the range of f , and 0 otherwise. Now, for all a ∈ A, g( f (a)) = h( f (a)), but by
assumption this implies that g = h. This is only possible if the range of f is B itself, i.e. f
is surjective.

What would be an analogous condition for injections?

Injectivity is equivalent to left-cancellability: f : B → C is an injection iff for all sets A and

functions g, h: A → B , if f ◦ g = f ◦ h then g = h.

(⇒) Assume f : B ↣ C is an injection, and suppose that f ◦ g = f ◦h for some g, h: A → B .

We need to show that for all a ∈ A, g(a) = h(a). Injectivity means that for all b1 , b2 ∈ B , if
f (b1 ) = f (b2 ) then b1 = b2 . Instantiating this for g(a), h(a) ∈ B , and using the assumption
f ◦ g = f ◦ h, we deduce that f (g(a)) = f (h(a)) implies g(a) = h(a). Since a ∈ A was
arbitrary, we have that g = h.

(⇐) Assume that for all A and g, h: A → B , ⃝ 1 f ◦ g = f ◦ h implies g = h. We need to

show that for all b1 , b2 ∈ B , if f (b1 ) = f (b2 ) then b1 = b2 . Take b1 , b2 ∈ B and assume
2 f (b1 ) = f (b2 ); for A = { () } the singleton set, define g, h: A → B as g() = b1 , and
that ⃝
h() = b2 . Then, by ⃝
2 , f (g()) = f (b1 ) = f (b2 ) = f (h()), but then by ⃝ 1 g = h so b1 = b2 .

12. On images
12.1. Basic exercises
1. Let R2 = { (m, n) | m = n2 }: N → Z be the integer square-root relation. What is the direct
image of N under R2 ? And what is the inverse image of N?
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

By the definition of the direct and inverse relational images, we have:

−→ ←−
R2 (N) = Z R2 (N) = { 0 } ∪ { n ∈ N | n is not square }

This may well be called a “trick question”, since the answer could hardly be more coun-
terintuitive – then again, it follows directly from the definition of inverse relation images so
there is not much to argue about! R2 relates every integer (on the right) with its square (on
the left), a natural number: R2 = { (0, 0), (1, −1), (1, 1), (4, 2), (4, −2), (9, −3), (9, 3), . . . }.
The direct image of the natural numbers is therefore Z itself, since the square of every
integer is in N. It may seem intuitively obvious that the inverse image of N ⊆ Z the square
root relation would be the set of square numbers, but this is distinctly not the case. Recall
the definition of inverse relational images:
←
−
R (Y ⊆ B) ≜ { a ∈ A | ∀b ∈ B. a R b ⇒ b ∈ Y }

For R2 , and Y = N ⊆ Z, this becomes:

←−
R2 (N) ≜ { m ∈ N | ∀n ∈ Z. m = n2 ⇒ n ∈ N }
←−
In other words, if there are any integers that square to an element of R2 (N), they all have
to be natural numbers. 0 is certainly in the inverse image, since the only number that
squares to 0 is 0 itself, and it is in N. The problems start with nonzero square numbers like
1, 4, 9, etc.: there are exactly two integers that square to the same perfect square number,
namely the square root, and the negative of the square root. Only one of these is a natural
number, the other violates m = n2 ⇒ n ∈ N and therefore cannot be an element of the
inverse image. Thus, the inverse image of natural numbers under the square-root relation
contains no square numbers other than 0. Even worse is that every natural number which
is not a perfect square (and therefore isn’t related to any integers) vacuously satisfies the
condition: for any n ∈ Z, 2 ̸= n2 so the hypothesis is never satisfied and the implication
holds! As a result, the inverse image contains all the non-square natural numbers and 0.

You may rightly ask: why do we define inverse images in such a way? The answer is simply
−
→
that this is the most natural way to define it as a dual of the direct image R (X ) ≜ { b ∈
B | ∃x ∈ X . x R b }. Indeed, if we slightly rephrase the condition ∃x ∈ X . x R b to separate
existence and membership of X , and compare it to the inverse image definition, we get:
−
→
R (X ) ≜ { b ∈ B | ∃x ∈ A. x R b ∧ x ∈ X }
←
−
R (Y ) ≜ { a ∈ A | ∀ y ∈ B. a R y ⇒ y ∈ Y }

As is often the case with mathematics, symmetry and simplicity takes precedence over
intuition, and trying to define the inverse image to yield the “expected” results would
needlessly complicate the definition. In fact, what we intuitively expect the inverse image
of N under R2 to be (the set of perfect squares) is nothing more than the direct image of N
op
under the opposite relation R2 .
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

2. For a relation R: A → B , show that:

−
→ −
→
a) R (X ) = R ({ x }) for all X ⊆ A
S
x∈X

Let X be a subset of A. We calculate as follows:

−
→
R (X ) = { b ∈ B | ∃x ∈ X . x R b }

= b ∈ B ∃x ∈ X . ∃ y ′ ∈ { x }. y ′ R b
 −→
= b ∈ B ∃x ∈ X . b ∈ R ({ x })
[ −→
= R ({ x })
x∈X

←
−  −
→
b) R (Y ) = a ∈ A R ({ a }) ⊆ Y for all Y ⊆ B .

Let Y be a subset of B . We calculate as follows:

←
−
R (Y ) = { a ∈ A | ∀ y ∈ B. a R y ⇒ y ∈ Y }


= a ∈ A ∀ y ∈ B. ∃a′ ∈ { a }. a′ R y ⇒ y ∈ Y
 −
→
= a ∈ A ∀ y ∈ B. y ∈ R ({ a }) ⇒ y ∈ Y
 −
→
= a ∈ A R ({ a }) ⊆ Y

This equivalent characterisations of inverse images highlights the requirement

that every y ∈ B related to an a ∈ A has to be in Y , not just at least one.

12.2. Core exercises

−
→
1. For X ⊆ A, prove that the direct image f (X ) ⊆ B under an injective function f : A ↣ B is in
−
→
= f (X ).
bijection with X ; that is, X ∼

Let f : A → B be an injective function and let X be a subset of A. We show that the direct
∼ −
→
=
image of X under f is isomorphic to X by constructing a bijection h: X −→ f (X ). Define
h as
−
→
h(x ∈ X ) = f (x) ∈ f (X )
−
→
By construction, h is a function from X to f (X ) because every output of f for an input in
X ends up in the direct image. We show that h is surjective and injective. Take any element
−
→
y ∈ f (X ); by definition, there must exist an element x ∈ X such that f (x) = h(x) = y ,
which is the condition for surjectivity of h. Now, take x 1 , x 2 ∈ X and assume that h(x 1 ) =
h(x 2 ). Then, f (x 1 ) = f (x 2 ), but f is injective, so x 1 = x 2 – proving that h is injective too.
−→
As a direct corollary, the range of an injection is isomorphic to the domain: f (A) ∼ = A.

This is a situation where proving injectivity and surjectivity is more convenient than
−
→
trying to precisely formulate an inverse function that maps y ∈ f (X ) to “the element in X
that got uniquely mapped to y ” and using this to calculate the inverse laws.
−
→
2. Prove that for a surjective function f : A ↠ B , the direct image function f : P (A) → P (B) is
surjective.
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

Assume f : A ↠ B is a surjection: for all b ∈ B , there exists an a ∈ A such that f (a) = b.

We need to prove that for any element Y ∈ P (B) there exists an X ∈ P (B) such that
−
→
f (X ) = Y . Thus, take a subset Y ⊆ A, and let the corresponding subset of A be the inverse
←− −
→€← − Š
image f (Y ) ⊆ A. We now need to show that f f (Y ) = Y , for which we calculate:
−
→€←
− Š ←−
f f (Y ) = { b ∈ B | ∃a ∈ f (Y ). f (a) = b }
= { b ∈ B | ∃a ∈ A. f (a) ∈ Y ∧ f (a) = b }
= { b ∈ Y | ∃a ∈ A. f (a) = b }

but the last set is precisely Y since f is surjective and therefore the comprehension
condition holds for all b ∈ Y . As a direct corollary, the range of a surjection is equal to the
−
→ −
→
= f (A) = B .
codomain: f (A) = B . A bijection is both an injection and a surjection, so A ∼

3. Show that any function f : A → B can be decomposed into an injection and a surjection: that
is, there exists a set X , a surjection s : A ↠ X and an injection i : X ↣ B such that f = i ◦ s.

Let f : A → B be a function, not necessarily a surjection or injection. Take X to be the

−
→
range of f , that is, the direct image of its domain: X = f (A) ⊆ B . Then, by definition, every
−
→
element b ∈ f (A) has an associated element a ∈ A such that f (a) = b, so f with its
−
→
codomain restricted to its range is a surjection – hence, s(a) = f (a): A ↠ f (A). The range
−
→
of f is a subset of the codomain, so we have the canonical inclusion i(b) = b : f (A) ↣ B
which is an injection. For all a ∈ A, i(s(a)) = i( f (a)) = f (a), so the composite i ◦ s is
indeed equal to f , as required.

When A = B (and f : A → A is an endofunction), the construction of course still works.

In fact, it gives one half of the idempotent-splitting example §9.2.1, in which an idempotent
−
→
endofunction e : A → A is split through its range { e(b) | b ∈ B } = e (B) into functions r
and s as s◦ r = e which, thanks to the idempotence condition, form a section-retraction pair:
r ◦ s = idB . Sections are always injections, and the constructed retraction is a surjection,
matching the result shown in this exercise..

4. For a relation R: A → B , prove that

−
→ S
S −→
a) R F = R (X ) X ∈ F for all F ⊆ P (A)

Let F ⊆ P (A) be a family of subsets. We have the following calculation:

−
→
[
[
b∈ R F ⇐⇒ ∃a ∈ F . a R b
⇐⇒ ∃X ∈ F . ∃a ∈ X . a R b
−
→
⇐⇒ ∃X ∈ F . b ∈ R (X )
 −→
⇐⇒ ∃Y ∈ R (X ) X ∈ F . b ∈ Y
[ −→
⇐⇒ b ∈ R (X ) X ∈ F
←
− T
T ←−
b) R G = R (Y ) Y ∈ G for all G ⊆ P (B)
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

Let F ⊆ P (A) be a family of subsets. We have the following calculation:

←
−
\
\
a∈R G ⇐⇒ ∀b ∈ B. a R b ⇒ a ∈ G
⇐⇒ ∀b ∈ B. a R b ⇒ ∀Y ∈ G . a ∈ Y
⇐⇒ ∀Y ∈ G . ∀b ∈ B. a R b ⇒ a ∈ Y
←
−
⇐⇒ ∀Y ∈ G . a ∈ R (Y )
 ←−
⇐⇒ ∀X ∈ R (Y ) Y ∈ G . a ∈ X
\ ←−
⇐⇒ a ∈ R (Y ) Y ∈ G

5. Show that, by the inverse image, every map A → B induces a Boolean algebra map P (B) → P (A).
That is, for every function f : A → B , its inverse image preserves set operations:
←
−
• f (;) = ;
←
−
a ∈ f (;) ⇔ f (a) ∈ ; ⇔ false ⇔ a ∈ ;
←
−
• f (B) = A
←
−
a ∈ f (B) ⇔ f a ∈ B ⇔ true ⇔ a ∈ A
←
− ←
− ←
−
• f (X ∪ Y ) = f (X ) ∪ f (Y )
←
−
a ∈ f (X ∪ Y ) ⇔ f (a) ∈ (X ∪ Y ) ⇔ f (a) ∈ X ∨ f (a) ∈ Y
←
− ←
− ←
− ←
−
⇔ a ∈ f (X ) ∨ a ∈ f (X ) ⇔ a ∈ f (X ) ∪ f (Y )
←
− ←
− ←
−
• f (X ∩ Y ) = f (X ) ∩ f (Y )
←
−
a ∈ f (X ∩ Y ) ⇔ f (a) ∈ (X ∩ Y ) ⇔ f (a) ∈ X ∧ f (a) ∈ Y
←
− ←
− ←
− ←
−
⇔ a ∈ f (X ) ∧ a ∈ f (X ) ⇔ a ∈ f (X ) ∩ f (Y )

←
− €←− Šc
• f (X c ) = f (X )

←− ←− €←− Šc
a ∈ f (X c ) ⇔ f (a) ∈ X c ⇔ ¬( f (a) ∈ X ) ⇔ ¬(a ∈ f (X )) ⇔ a ∈ f (X )

13. On countability
13.1. Basic exercises
1. Prove that every finite set is countable.

If the set is empty, it is countable by definition. Otherwise, if A is finite, it has at most

#A = n > 0 elements. Thus, an enumeration N ↠ A can be constructed by mapping the
first n natural numbers to distinct elements of A (e.g. by putting them in some order and
assigning k : [0..n−1] to the {kth } element), and the rest of the naturals to a single element
a0 ∈ A. The mapping is surjective by construction (the {kth } element of A is listed at k) so
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

it is an enumeration.
2. Demonstrate that N, Z, Q are countable sets.

N is enumerated by the identity function, which is in particular a surjection.

Z is enumerated by alternating between positive and negative numbers: 0, 1, −1, 2, −2, . . ..
Explicitly, e : N ↠ Z is the enumeration
(
n+1
2 if n is odd
e(n) ≜ n
− 2 if n is even

Q is enumerable using the traversal of the coordinate plane demonstrated on Slide 398.

13.2. Core exercises

1. Let A be an infinite subset of N. Show that A ∼
= N. Hint: Adapt the argument shown in the proof
of Proposition 168, showing that the map N → A is both injective and surjective.
= ∼
Let A be an infinite subset of N. We construct a bijection N −→ A to show that they are
isomorphic. To this end, define the function µ: N → A as follows:

µ(0) ≜ min(A) µ(n + 1) ≜ min{ k ∈ A | µ(n) < k } = min(A \ { µ(k) | k ≤ n })

We will denote the set A \ { µ(k) | k ≤ n } as An , so that µ(n + 1) = min(An ).

To show that µ is an injection, we need to prove that if µ(m) = µ(n) then m = n. We

equivalently prove the contrapositive: if m ̸= n, then µ(m) ̸= µ(n). Without loss of
generality, assume that m < n; then, µ(m) ∈ { µ(k) | k ≤ n − 1 }, so µ(m) ∈
/ { µ(k) | k ≤
n − 1 }c = A \ { µ(k) | k ≤ n − 1 }. On the other hand, µ(n) is an element of the latter set
(its minimum), which means that µ(m) cannot equal µ(n).

To show that µ is a surjection, we let a be an arbitrary element of A and show that there
is an i ∈ N such that µ(i) = a. Consider the set { k ∈ N | µ(k) < a } of numbers which
get mapped to an element below a in A, and let N be the size of this set (which, by the
Pigeonhole Principle, must be at most a). Now, AN is the subset of A obtained by removing
its N least elements, and by construction, its least element is a. But if a = min(AN ), then it
is equal to µ(N + 1) by the definition of µ, so we indeed have the natural number i = N + 1
such that µ(i) = a.

2. For an infinite set A, prove that the following are equivalent:

= ∼
a) There is a bijection N −→ A.
b) There is a surjection N ↠ A.
c) There is an injection A ↣ N.
= ∼ = ∼
(a) ⇒ (b), (c) Every bijection f : N −→ A has an inverse f −1 : A −→ N which is itself a
bijection. Every bijection is a surjection (giving N ↠ A from f ) and an injection (giving
A ↣ N from f −1 ).
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

(b) ⇒ (c) Let s : N ↠ A be a surjection. We need to construct an injection i : A ↣ N,

assigning a unique numeric code to every element of A. As s is a surjection, the inverse
images of the singleton subsets of A (also called the set of fibres of elements of A)
are all non-empty, and as they are subsets of the natural numbers, they must have
a minimal element. Thus, define i : A → N as a function that maps an x ∈ A to the
smallest natural number that maps to x :
←
−


i(x) = min s ({x}) = min{ n ∈ N | s(n) = x }

This encodes an element x ∈ A by the position of its first occurrence in the enumeration
given by s. We can see that i is injective as s acts as its retraction: for any x ∈ S ,
s(i(x)) = s(n) where n is the smallest natural number such that s(n) = x so clearly
s(i(x)) = s(n) = x and s ◦ i = idA, as required.
= ∼
(c) ⇒ (a) Let i : A ↣ N be an injection. We need to construct a bijection A −→ N, or
equivalently, show that A and N are isomorphic. By §12.2.1, the direct image of the
−
→
domain under the injection i (i.e. the range of i ) is isomorphic to the domain: i (A) ∼
= A.
−→
By assumption, A is infinite, so i (A) ⊆ N is infinite as well. But then it is an infinite
subset of the natural numbers, and by §13.2.1, it is isomorphic to N. Hence we have
−
→ ∼
= i (A) ∼
=
the chain A ∼ = N, establishing the bijection N −→ A.

If you look at other resources on countability, you will face several competing, but equi-
valent (but sometimes not quite equivalent) definitions which make translating between
various statements and proofs a bit of a chore – especially since the same terms are used
by different authors for different purposes. This course uses enumerable for sets which
have a surjection N ↠ A, and countable for sets which are enumerable or empty (since
one can’t have a function into the empty set so this needs to be handled as a special case).
Other literature (e.g. Wikipedia) calls sets which are isomorphic to N countably infinite,
and sets which are either finite or countably infinite are called countable. The countability
condition can be equivalently stated as the set being isomorphic to some subset of the
natural numbers, i.e. coming with an injection A ↣ N. Yet other terms used for the above
notions are at most countable, enumerable, denumerable, equinumerous, listable, etc.

As this exercise shows, the bijection/surjection/injection notions are equivalent when the
set A is infinite, and appropriate connections can be made when the sets are empty or
finite. This gives us two equivalent ways of showing that a set is enumerable: either by
constructing an enumeration N ↠ A, or by defining an encoding function A ↣ N that maps
every element of A to a unique natural number. This is related to a concept called Gödel
encoding which will be covered in more detail in the IB Computation Theory course.

3. Prove that:

a) Every subset of a countable set is countable.

D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

Assume S ⊆ A for some sets A. If A is finite, so is S and it is countable. If A is infinite

and S is finite, S is countable. If S is also infinite, we can show that it is enumerable by
providing an injection S ↣ N. But by assumption we have an injection f : A ↣ N and
subsets come with a canonical injective inclusion function ι : S ↣ A, so the composite
S ↣ A ↣ N is an injection.

b) The product and disjoint union of countable sets is countable.

Assume A and B are countable sets.

If either is empty, the Cartesian product will be empty too and therefore countable.
In the general case, assume they are enumerable and there are injections f : A ↣ N
and g : B ↣ N that uniquely encode the elements of the sets. We define a function
p : A × B → N as follows:
p(a, b) = 2 f (a) · 3 g(a)

By the Fundamental Theorem of Arithmetic, the mapping is injective: the output of

this mapping will have a unique prime decomposition, and the number of 2 and 3
factors will give the unique code of elements of A and B , respectively. By §13.2.2, the
injection p will imply that A × B is enumerable.

If both sets are empty, their disjoint union will be empty and therefore countable.
If either is empty, the disjoint union will be isomorphic to the other set, which is
countable by assumption. In the general case, assume A and B are enumerable and
come with injections f : A ↣ N and g : B ↣ N. We define the function u: A ⊎ B → N
as follows:
u(0, a) = 2 f (a) u(1, b) = 3 g(b)

Again, by the Fundamental Theorem of Arithmetic, the prime decomposition of the

output of u will uniquely determine the output of f (a) or g(b) which in turn uniquely
determine the input a and b by assumption. By §13.2.2, the injection u will imply that
A ⊎ B is enumerable.
Constructing unique encodings using products of primes is a useful alternative
to the visually descriptive “diagonal traversal” enumeration which is often quite
difficult to define explicitly. The specific choice of encoding can of course vary (e.g. we
could have encoded disjoint unions via even and odd numbers) but there is no
reason to look for the most “efficient” solution since all we care about is whether the
enumeration/encoding is possible or not.

4. For a set A, prove that there is no injection P (A) ↣ A.

We suppose there is an injection f : P (A) ↣ A and derive a contradiction. By §11.2.1, the

injection f has a retraction r : A → P (A) which must be a surjection since it undoes the
application of f on any element of A. But then r would be a surjection from a set to its
powerset, which is impossible due to Cantor’s Theorem.
D I S C R E T E M AT H E M AT I C S E X E R C I S E S 8 – S O L U T I O N S W I T H C O M M E N TA R Y

13.3. Optional advanced exercise

1. Prove that if A and B are countable sets then so are A∗ , Pfin (A) and PFunfin (A, B).

All the results follow from Proposition 154: an enumerable indexed disjoint union of
enumerable sets is enumerable. An enumeration-style proof is presented in the notes, but
U
an encoding-style argument is straightforward too: we can encode elements of i∈I Ai as

d(i ∈ I, a ∈ Ai ) = p(c(i), ci (a)) = 2c(i) · 3ci (a)

where c : I ↣ N is the encoding of the index set, and ci : Ai ↣ N is an encoding for every
element of the indexed family.

A∗ =
U
n∈N A
n
is the set of finite sequences on A. If A is empty, the only finite sequence
with elements from A is the empty sequence, so { () } is finite and countable. In the general
case, we know that N is enumerable, and An is the iterated binary Cartesian product of
enumerable sets and hence is an enumerable set for every n ∈ N (quick inline induction
proof: A0 = ; is countable; Ak+1 = Ak × A is the Cartesian product of countable Ak by IH,
and countable A by assumption). By the above proposition, the N-indexed disjoint union
of countable sets is countable.

Pfin (A) = { S ⊆ A | S is finite } is the set of finite subsets of A. If A is empty, Pfin (A) = { ; }
which is finite so countable. Otherwise, the set A has an encoding c : A ↣ N which imposes
an ordering on the elements on A based on the ordering of their code: for a, b ∈ A, a ⊑ b
if c(a) ≤ c(b). This ordering restricts to every subset of A, so in particular, finite subsets of
A can be mapped to finite sequences of elements of A according to the ordering ⊑. Then,
the set of finite subsets of A is isomorphic to the set of finite sequences on A, which is
countable for a countable A.

PFunfin (A, B) = S∈Pfin (A) S ⇒ B is the set of partial functions with a finite domain of
U

definition from A to B . If A or B are empty, the totally undefined function is the only
element of the set so it is countable. Otherwise, the disjoint union is indexed by Pfin (A)
which is enumerable by the result above. The function space S ⇒ B has a finite domain
S , so a single function f : S → B can be captured as a finite sequence of elements of B
as ( f (s1 ), f (s2 ), f (s3 ), . . . , f (sn )) where n = #S and si is the {i th } element of S in some
#S
ordering (which is always possible to define for a finite S ). Thus, S ⇒ B ∼ = B which is
countable for any countable B . By Proposition 154, the set PFunfin (A, B) is a countable
indexed disjoint union of countable sets and is therefore itself countable.