Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Activities 13.4 Activities
A4US

Activity 13.1.

In each of the following, prove that the given set is countable by exhibiting an explicitly defined bijective correspondence between it and \(\N\text{.}\)

(a)

The set of natural numbers excluding 0.

(b)

The set of natural numbers that are greater than \(9,999,999\text{.}\)

(c)

The set of odd natural numbers.

(d)

The set of integer powers of \(2\) (including both positive and negative exponents).

Activity 13.2.

Without cheating and looking at the proofs in this chapter, prove each of the following statements. You may wish to make use of the characterization of countability in Fact 13.1.2 instead of the technical definition of countable set.
Note: Each statement except the first two can be proved directly from the preceding statements.

(a)

Every subset of \(\N\) is countable.

(b)

If two sets have the same size and one of them is countable, then so is the other.

(c)

Every set that is the same size as a subset of \(\N\) is countable.

(d)

Every subset of a countable set is countable.

(e)

Every set that is the same size as a subset of a countable set is countable.

(f)

A set that contains an uncountable subset is uncountable.

Activity 13.3.

(a)

Prove that \(\N \times \N\) is countable.
Hint.
Use a zig-zag-through-a-grid method similar to the proof of the countability of the rational numbers. (See Theorem 13.1.4 and its proof.)

(b)

Prove that if \(A\) and \(B\) are both countable, then so is \(A \times B\text{.}\)
Hint.
You could do more zig-zagging, or you could use the statement of Task a.

(c)

Prove that if \(X\text{,}\) \(Y\text{,}\) and \(Z\) are each countable, then so is \(X \times Y \times Z\text{.}\)
Hint.
Use the statement of Task b twice.

(d)

What proof method do you think you would use to prove the following statement?
If \(A_1, A_2, \dotsc, A_n\) are all countable, then so is
\begin{equation*} A_1\times A_2 \times \dotsb \times A_n \text{.} \end{equation*}

Activity 13.4. The Infinite Orchard Problem.

You own a magical apple orchard that contains an infinite number of trees, each of which bears an infinite number of apples. Describe a method to pick all of the apples in the orchard, one apple at a time. (No shaking the trees, please! However, you may assume an infinite amount of time.)

Activity 13.5.

Prove that if \(A_0,A_1,A_2,\dotsc\) is an infinite collection of sets, each of which is countably infinite, then the union
\begin{equation*} \bigcup_{n=0}^\infty A_n = A_0 \cup A_1 \cup A_2 \cup \dotsb \end{equation*}
is also countably infinite.
Hint.
What if each set was an apple tree?

Activity 13.6.

Let \(\mathscr{F}\) represent the set of all functions with domain \(\{0,1\}\) and codomain \(\N\text{.}\)

(a)

Determine a bijective correspondence between \(\mathscr{F}\) and \(\N \times \N\text{.}\)

Activity 13.7.

Let \(\mathscr{F}'\) represent the set of all functions with domain \(\N\) and codomain \(\{0,1\}\text{.}\)
Note that each element of \(\mathscr{F}'\) defines an infinite sequence of \(0\)s and \(1\)s.

(a)

Suppose \(A\) is a countable subset of \(\mathscr{F}'\text{.}\) (So \(A\) is an infinite list of infinite sequences of \(0\)s and \(1\)s.)
Describe how to construct an element of \(\mathscr{F}'\) that is definitely not in \(A\text{.}\) That is, build an infinite sequence of \(0\)s and \(1\)s that is definitely not the same as any of the infinite sequences in the infinite list of \(A\text{.}\)
Hint.
Use Cantor’s diagonal argument from the proof of Lemma 13.1.7.

(b)

Explain why Task a proves that \(\mathscr{F}'\) is uncountable.
Hint.
\(\mathscr{F}' \subseteq \mathscr{F}'\text{.}\)
<Prev^TopNext>