Problem Sheet 1¶

Problem Hints

Question 1¶

Find an explicit bijection \(f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}\).

Solution (Diagonals of a 2D Grid)

From lectures we've seen we can define this bijection by considering diagonals of a 2D grid consisting of all pairs \((m, n) \in \mathbb{N} \times \mathbb{N}\). Each diagonal corresponds to a fixed value of \(s = m + n\). For example diagonal \(s = 2\) contains elements \((2, 0), (1, 1), (0, 2)\).

Each diagonal \(s\) contains \(s + 1\) elements. The total number of pairs before diagonal \(s\) is the triangular number:

\[ T_s = \sum_{i = 0}^{s - 1} (i + 1) = \frac{s(s + 1)}{2}. \]

Alternative Solution (Cantor Pairing)

The Cantor pairing function gives an explicit bijection from \(\mathbb{N} \times \mathbb{N}\) to \(\mathbb{N}\).

\[ \pi(m, n) = \frac{(m + n)(m + n + 1)}{2} + n. \]

Question 2¶

Prove carefully from the definition that if \(|A| \leq |B|\) and \(|B| \leq |C|\), then \(|A| \leq |C|\). (This says that this relation is transitive on any set of sets).

Proof

Given that \(|A| \leq |B|\) and \(|B| \leq |C|\) this means there exists injective functions \(f: A \to B\) and \(g: B \to C\). Now consider the composition of these function \(g \circ f: A \to C\).

It now suffices to show that \(g \circ f\) is injective. Let \(x, y \in A\) and suppose that \((g \circ f)(x) = (g \circ f)(y)\). Now since \(f\) is injective, this implies that \(f(x) = f(y)\). Similarly, since \(g\) is also injective we have that \(g(f(x)) = g(f(y))\). Thus there exists an injective function from \(A\) to \(C\), hence \(|A| \leq |C|\).

Question 3¶

Prove that if \(A\) is a nonempty set, then \(|A| \leq |B|\) if and only if there exists a surjective map \(g: B \to A\) (assuming the Axiom of Choice).

Proof

\((\implies)\) Suppose there exists an injective function \(f: A \to B\). Then each element of \(A\) corresponds to a distinct element in \(f(A) \subseteq B\). Consider a fixed element \(a_0 \in A\) then define \(g: B \to A\) by

\[ g(b) = \begin{cases} f^{-1}(b) & \text{if } b \in f(A), \\ a_0 & \text{if } b \notin f(A). \end{cases} \]

For every \(a \in A\), there exists \(b = f(a) \in f(A)\) such that \(g(b) = f^{-1}(f(a)) = a\), so \(g\) is surjective onto \(A\).

\((\impliedby)\) Suppose there exists a surjection \(g: B \to A\). For each \(a \in A\), since \(g\) is surjective, there eixsts at least one \(b_a \in B\) such that \(g(b_a) = a\). Now define \(f: A \to B\) by choosing such an element \(b_a\) for each \(a: f(a) = b_a\). This is injective because if \(f(a_1) = f(a_2) = b\), then applying \(g\) gives \(a_1 = g(b) = a_2\). Hence, \(f\) is an injection from \(A\) into \(B\).

Question 4¶

Let \(A\) be any infinite set and \(B\) any countable set. Prove that \(|A| = |A \cup B|\).

Proof

We first prove \(|A| \leq |A \cup B|\). Consider the identity map \(f: A \to A \cup B, f(a) = a\). This is obviously injective hence \(|A| \leq |A \cup B|\).

We now prove \(|A \cup B| \leq |A|\). Fix an enumeration of \(B\), say \(B = \{b_0, b_1, b_2, \dots\}\). Since \(A\) is infinite, it has a countable infinite subset \(A' = \{a_0, a_1, a_2, \dots\}\). Then we define \(g : A \cup B \to A\) by

\[ g(a) = \begin{cases} a & \text{if } a \in A \setminus (A' \cup B), \\ a_{2n} & \text{if } a = a_n \in A' \setminus B, \\ a_{2n + 1} & \text{if } a = b_n \in B. \end{cases} \]

which is clearly injective. Hence we have \(|A \cup B| \leq |A|\).

Thus by Schroeder-Bernstein's Theorem \(|A| = |A \cup B|\).

Alternative Proof

Let \(A' \subset A\) where \(A'\) is countably infinite. Let \(B' = B \setminus A\). Then \(B'\) is countable and \(A \cup B = A \cup B'\) and \(A \cap B' = \emptyset\).

Now since \(A'\) and \(A' \cup B'\) are countably infinite, there is a bijection \(f: A' \cup B' \to A'\). We can then extend \(A \cup B' = A \cup B\) by letting \(f(x) = x\) for \(x \in A \setminus A'\). Then \(f: A \cup B \to A\) is a bijection which proves the statement.

Question 5¶

Suppose that \(|A_n| = |\mathbb{R}|\), for \(n = 1, 2, 3, \dots\). Prove that \(|\bigcup_{n = 1}^\infty A_n| = |\mathbb{R}|\).

Proof

Let \(|A_i| = |[i - 1, i)|\) which we know has cardinality \(|\mathbb{R}|\) since \(|[0, 1)| = |\mathbb{R}|\) from lectures. Then \(|\bigcup_{n = 1}^\infty| = |[0, n)]\) which again has cardinality \(|\mathbb{R}|\).

Question 6¶

Prove that \(|\mathbb{R}| = |[0, 1)| = |\mathbb{R} \setminus \mathbb{Q}|\).

Proof

To prove that \(|\mathbb{R}| = |[0, 1)|\) we construct the following map \(f: [0, 1) \to (0, 1); f\left(\frac{1}{n}\right) = \frac{1}{n + 1}, f(x \neq \frac{1}{n}) = x\). This is a bijection which proves that \(|(0, 1)| = |(0, 1]|\). Now construct \(g: (0, 1) \to \mathbb{R}, g(x) = \tan(x - \frac{\pi}{2})\) which is also a bijection. Since the compositions of bijections is bijective, the map \((g \circ f)\) provides a bijection from \([0, 1) \to \mathbb{R}\).

To prove \(|\mathbb{R}| = |\mathbb{R} \setminus \mathbb{Q}|\). We prove the following

\(|\mathbb{R}| \leq |\mathbb{R} \setminus \mathbb{Q}|\). Let \(f: \mathbb{R} \to (\mathbb{R} \setminus \mathbb{Q}), f(x) = e^x + \pi\). This is clearly injective since \(e^x\) is.
\(|\mathbb{R} \setminus \mathbb{Q}| \leq |\mathbb{R}|\). Let \(f: (\mathbb{R} \setminus \mathbb{Q}) \to \mathbb{R}, f(x) = x\). This is also injective.

Hence by Schroeder-Bernstein's Theorem we have \(|\mathbb{R}| = |\mathbb{R} \setminus \mathbb{Q}|\).

Question 7¶

Decide whether the following sets are countable or uncountable. Be clear about whether you are using the definition or a theorem.

\(\mathbb{R} \times \mathbb{Q}\)
The set \(B\) of all open intervals of \(\mathbb{R}\) with rational endpoints.
\(\mathbb{N}^\mathbb{N}\), the set of all sequences of natural numbers.
The set \(\mathcal{M}\) of all matrices of any (finite) size which have integer entries.
The set \(C\) of all \(x \in [0, 1]\) whose decimal expansion contains no 7s.
The set of all polynomials with rational coefficients.
The set of convergent sequences of rational numbers.

Proof Sketch

Uncountable since \(\mathbb{R}\) is uncountable.
\(B = \{(p, q) \mid p, q \in \mathbb{Q} \}. |B| = \mathbb{Q} \times \mathbb{Q}\) which is a finite product of countable sets and thus is countable.
From lectures this is uncountable. Also \(\mathbb{N}^\mathbb{N} \geq 2^\mathbb{N}\) and \(2^\mathbb{N}\) is uncountable.
This is equivalent to a finite product of \(\mathbb{Z}\) where you just convert the matrix into a tuple. This is countable.
The possible digits for each decimal are \(\{0, 1, 2, 3, 4, 5, 6, 8, 9\}\). There are at most \(\mathbb{N}\) decimal points. We can write the possible decimal expansions as a list where each entry in the tuple is a decimal place: \(\{(0, 0, \dots), (1, 0, \dots), \dots, (0, 1, 0, \dots), (0, 2, 0, \dots), \dots \},\) which by definition is countable. Note that this has cardinality equivalent to \(|9^\mathbb{N}|\).
This is equivalent to \(\mathbb{Q}^\mathbb{N}\) which has cardinality equivalent to \(|\mathbb{N}^\mathbb{N}|\) which from 2. is uncountable.
Consider a subset starting with \(\{\{1, 1/2, 1/4, \dots\}, \{1, 1/3, 1/9, \dots\}, \dots\}\). There are \(\mathbb{N}\) such sequences each with \(\mathbb{Q}\) elements. Meaning this structure is similar to \(\mathbb{Q}^\mathbb{N}\) which is uncountable.

Question 8¶

Suppose that \(\{x_n \}_{n = 1}^\infty\) is a sequence of positive numbers such that \(\sum_{n = 1}^\infty x_n\) converges. Prove that for every \(\epsilon > 0\), the set \(\{n : x_n \geq \epsilon \}\) is finite.
Let \(f: [0, 1] \to (0, \infty)\). Prove that there exists some \(\epsilon > 0\) such that \(\{ x \in [0, 1]: f(x) \geq \epsilon \}\) is uncountable.
Explain why this means that you can only make some sense of \(\sum_{x \in [0, 1]} f(x)\) if \(f(x) = 0\) except on a countable set.

Solution

Since the series \(\sum x_n\) converges and all \(x_n > 0\), for every \(\epsilon > 0\), there exists \(N \in \mathbb{N}\) such that \(\sum_{n > N} x_n < \epsilon\). In particular, for \(n > N\), each \(x_n < \epsilon\); otherwise if \(x_n \geq \epsilon\) for some \(n > N\), then \(\sum_{n > N} x_n \geq x_n \geq \epsilon\), which contradicts the tail bound. Hence, all \(x_n > \epsilon\) must occur for \(n \leq N\). So \(A_\epsilon\) is finite.
Let \(f: [0, 1] \to (0, \infty)\). Define \(E_n = \{x \in [0, 1] \mid f(x) \geq \frac{1}{n}\}\) for \(n \in \mathbb{N}\). Since \(f(x) > 0\), we have \([0, 1] = \bigcup_{n = 1}^\infty E_n\). As \([0, 1]\) is uncountable, if all \(E_n\) where countable, then their countable union would be countable, a contradiction. Thus some \(E_n\) is uncountable. Set \(\epsilon = \frac{1}{n}\) for such an \(n\). Then \(\{x \in [0, 1] \mid f(x) \geq \epsilon\} = E_n\) is uncountable.
On a countable set, the sum converges. This does not apply to uncountable sets, and hence we can't exactly find the sum. If \(f(x) = 0\) when trivially the sum will just be 0.

Question 9¶

Let \(S\) be a countable subset of \([0, 1]\). Define an increasing function \(f: [0, 1] \to [0, 1]\) whose set of discontinuities is \(S\).

Solution

Let \(S = \{s_1, s_2, s_3, \dots\} \subseteq [0, 1]\) be a countable susbet, enumerate without repetition. Choose a sequence of positive numbers \((a_n)_{n=1}^\infty\) such that

\[ a_n > 0, \quad \text{ and } \quad \sum_{n = 1}^\infty a_n = 1. \]

Define the function \(f:[0,1] \to [0,1]\) by

\[ f(x) = \sum_{\substack{n = 1 \\ s_n < x}}^\infty a_n. \]

Check that \(f\) is increasing, bounded between \([0, 1]\), continuous for every \(x \notin S\) and at each point \(s_n \in S\), \(f\) has a jump discontinuity of size \(a_n\):

\[ \lim_{x \to s_n^-} f(x) = \sum_{\substack{k = 1 \\ s_k < s_n}}^\infty a_k, \quad \lim_{x \to s_n^+} f(x) = \sum_{\substack{k = 1 \\ s_k \leq s_n}}^\infty a_k, \]

so the jump is \(f(s_n^+) - f(s_n^-) = a_n\).