[problem:Countability Of N Cubed | 1] Show that the set $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ is countable. [/problem]

[solution] **Step 1 (Reduce to a product of two countable sets).** Since $\mathbb{N} \times \mathbb{N}$ is countable (proved in the article), there exists a bijection $\varphi: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$. **Step 2 (Use associativity of the Cartesian product).** Define \begin{align*} \psi: \mathbb{N} \times \mathbb{N} \times \mathbb{N} &\to (\mathbb{N} \times \mathbb{N}) \times \mathbb{N} \\ (a, b, c) &\mapsto ((a, b), c), \end{align*} which is a bijection (since Cartesian products are associative up to canonical bijection). **Step 3 (Conclude).** The set $(\mathbb{N} \times \mathbb{N}) \times \mathbb{N}$ is the product of two countable sets ($\mathbb{N} \times \mathbb{N}$ and $\mathbb{N}$), hence countable by the product closure theorem. Therefore $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ is countable. [/solution]

[problem:Finite Subsets Of N Are Countable | 2] Let $S$ denote the set of all finite subsets of $\mathbb{N}$. Prove that $S$ is countable. [/problem]

[solution] **Step 1 (Decompose by cardinality).** For each $k \in \mathbb{N}$, let $S_k$ denote the set of subsets of $\mathbb{N}$ with exactly $k$ elements. Then $S = \{\varnothing\} \cup \bigcup_{k=1}^{\infty} S_k$. It suffices to show that each $S_k$ is countable, since $S$ is then a countable union of countable sets (together with the finite set $\{\varnothing\}$). **Step 2 (Inject $S_k$ into $\mathbb{N}^k$).** For each $k$, define the map \begin{align*} \iota_k : S_k &\to \mathbb{N}^k \\ \{n_1, n_2, \ldots, n_k\} &\mapsto (n_1, n_2, \ldots, n_k), \end{align*} where $n_1 < n_2 < \cdots < n_k$ is the unique increasing enumeration. This map is well-defined because every finite subset of $\mathbb{N}$ has a unique listing in increasing order, and it is injective because distinct subsets produce distinct tuples. **Step 3 (Conclude).** Since $\mathbb{N}^k$ is countable (by induction on the countability of $\mathbb{N} \times \mathbb{N}$), $S_k$ is countable. Therefore $S = \{\varnothing\} \cup \bigcup_{k=1}^{\infty} S_k$ is a countable union of countable sets, hence countable. [/solution]

[problem:Finite Strings Over A Countable Alphabet | 2] Prove that the set of all finite strings over a countable alphabet $\Sigma$ is countable. [/problem]

[solution] **Step 1 (Decompose by string length).** Let $\Sigma$ be a countable alphabet. For each $n \in \mathbb{N} \cup \{0\}$, let $\Sigma^n$ denote the set of strings of length exactly $n$. Then $\Sigma^0 = \{\varepsilon\}$ (containing only the empty string), which is finite. **Step 2 (Each $\Sigma^n$ is countable).** For $n \geq 1$, since $\Sigma$ is countable and the finite product of countable sets is countable, the set $\Sigma^n$ is countable. **Step 3 (Apply the countable union theorem).** The set of all finite strings is $\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n$, a countable union of countable sets. By the countable union theorem, $\Sigma^*$ is countable. [/solution]

[problem:Infinite Subsets Of N Are Uncountable | 3] Prove that the set of all infinite subsets of $\mathbb{N}$ is uncountable. *Hint:* Use the fact that $\mathcal{P}(\mathbb{N})$ is uncountable (by Cantor's theorem) and the result that finite subsets of $\mathbb{N}$ are countable. [/problem]

[solution] **Step 1 (Partition the power set).** Let $\mathcal{F}$ denote the set of finite subsets of $\mathbb{N}$, and let $\mathcal{I}$ denote the set of infinite subsets of $\mathbb{N}$. Then $\mathcal{P}(\mathbb{N}) = \mathcal{F} \cup \mathcal{I}$, and this union is disjoint. **Step 2 (Apply Cantor's theorem).** By Cantor's theorem, $\mathcal{P}(\mathbb{N})$ is uncountable (there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, so $|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|$). **Step 3 (Use countability of $\mathcal{F}$).** By the preceding problem, $\mathcal{F}$ is countable. **Step 4 (Conclude by contradiction).** If $\mathcal{I}$ were countable, then $\mathcal{P}(\mathbb{N}) = \mathcal{F} \cup \mathcal{I}$ would be a union of two countable sets, hence countable by the countable union theorem. This contradicts Step 2. Therefore $\mathcal{I}$ is uncountable. [/solution]

[problem:Discontinuities Of A Monotone Function | 3] Let $f: \mathbb{R} \to \mathbb{R}$ be a monotonically increasing function. Prove that the set of discontinuities of $f$ is countable. *Hint:* At each discontinuity $x$, the left and right [limits](/page/Limit) $f(x^-)$ and $f(x^+)$ exist, and the "jump" $(f(x^-), f(x^+))$ is a non-empty open interval. Use this to inject the set of discontinuities into $\mathbb{Q}$. [/problem]

[solution] **Step 1 (Identify the jump intervals).** Since $f$ is monotonically increasing, at every point $x \in \mathbb{R}$ the left-hand [limit](/page/Limit) $f(x^-) = \lim_{t \to x^-} f(t)$ and right-hand limit $f(x^+) = \lim_{t \to x^+} f(t)$ exist and are finite, with $f(x^-) \leq f(x^+)$. The function $f$ is [continuous](/page/Continuity) at $x$ if and only if $f(x^-) = f(x) = f(x^+)$. At a discontinuity $x$, we have $f(x^-) < f(x^+)$, so the interval $J_x = (f(x^-), f(x^+))$ is a non-empty open interval. **Step 2 (The jump intervals are pairwise disjoint).** If $x < y$ are both discontinuities, then $f(x^+) \leq f(y^-)$ (since $f$ is increasing and there are points between $x$ and $y$). Therefore $J_x = (f(x^-), f(x^+))$ and $J_y = (f(y^-), f(y^+))$ are disjoint. **Step 3 (Inject into $\mathbb{Q}$).** Since the intervals $\{J_x\}$ are pairwise disjoint and non-empty, and since $\mathbb{Q}$ is dense in $\mathbb{R}$, each interval $J_x$ contains at least one rational number. Choose one such rational $q_x \in J_x \cap \mathbb{Q}$. The map $x \mapsto q_x$ is an injection from the set of discontinuities into $\mathbb{Q}$: if $x \neq y$, then $J_x$ and $J_y$ are disjoint, so $q_x \neq q_y$. **Step 4 (Conclude).** Since $\mathbb{Q}$ is countable and we have an injection from the set of discontinuities into $\mathbb{Q}$, the set of discontinuities is countable. [/solution]