Exercise 1

\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]

1 Injections and Surjections

1.1

Prove the following lemma about injective functions.

Lemma. Let \(f : A \to B\) and \(g : B \to C\) be injective functions. Then the composition \(g \circ f\) is injective.

Solution

Let \(a,a' \in A\) be such that \((g\circ f)(a) = (g\circ f)(a')\). By the injectivity of \(g\), we have \(f(a)=f(a')\). The injectivity of \(f\) then gives \(a=a'\), as required.

1.2

Show that \(A\) is countable if and only if there exist a countable set \(B\) and an injective function \(f : A \to B\).

Solution

Forward direction. Suppose \(A\) is countable. By definition, there is an injective function \(f : A \to \N\), so take \(B=\N\).

Backward direction. Let \(B\) be countable, and let \(f : A \to B\) be injective. Since \(B\) is countable, there is an injective function \(g : B \to \N\). By the previous lemma, \(g \circ f : A \to \N\) is injective. Therefore, \(A\) is countable.

---

In the lecture slides, we claimed that, for nonempty sets \(A\) and \(B\), there exists an injection from \(A\) to \(B\) if and only if there exists a surjection from \(B\) to \(A\). It turns out that the backward direction is a little controversial.

1.3

Show the forward direction. That is, show that if there exists an injection from \(A\) to \(B\), then there exists a surjection from \(B\) to \(A\).

Solution

Suppose \(f : A \to B\) is injective. Because \(A\) is nonempty, fix some \(a_0 \in A\). Define \(g : B \to A\) by

\[ g(b) = \begin{cases} a & \text{if } b = f(a) \text{ for some } a \in A, \\ a_0 & \text{if } b \notin \text{range}(f). \end{cases} \]

This function is well-defined because the injectivity of \(f\) ensures that there is at most one \(a\) such that \(b = f(a)\). For every \(a \in A\), we have \(g(f(a)) = a\). Therefore, every element of \(A\) is in the range of \(g\), so \(g\) is surjective.

---

Suppose \(g: B \to A\) is a function. Recall that the preimage of \(a\) under \(g\), denoted by \(g^{-1}(a) = \{b : g(b) = a\}\), is the set of elements that \(g\) maps to \(a\).

Consider the following proof for the backward direction.

Proof. Suppose \(g: B \to A\) is a surjection. Define \(f: A \to B\) as follows. For each \(a \in A\), let \(f(a)\) be some element of \(g^{-1}(a)\). For any \(a \in A\), the set \(g^{-1}(a)\) is nonempty because \(g\) is surjective. Therefore, \(f(a)\) is always well-defined. We now show that \(f\) is injective. Suppose \(a \neq a'\). Then \(g^{-1}(a)\) and \(g^{-1}(a')\) are disjoint. Because \(f(a)\) and \(f(a')\) are chosen from disjoint sets, they cannot be equal. \(\blacksquare\)

It turns out that the line in orange is a little controversial because we did not specify exactly how to pick an element from \(g^{-1}(a)\). The claim that we can make such a selection for every \(a \in A\) is logically equivalent to the Axiom of Choice. The Axiom of Choice is controversial because it allows us to prove some counterintuitive results, such as the Banach–Tarski paradox.

We’ll return to the Axiom of Choice later in the course, but for now, I want to ask your opinion: should we be able to use the line in orange in our proof? Do you think it is reasonable to say that we can pick some element of \(g^{-1}(a)\), knowing that \(g^{-1}(a)\) is nonempty?

1.4

There is no problem, however, if \(B = \N\). In that case, we can replace “\(f(a)\) is some element of \(g^{-1}(a)\)” with “\(f(a) = \min(g^{-1}(a))\)”. The key difference is that we are now giving an explicit, deterministic way to select an element: pick the smallest one.

Thus, without assuming the Axiom of Choice, we can safely use the following equivalent characterization: \(A\) is countable if and only if there exists a surjection from \(\N\) to \(A\).

2 Countability

We saw that \(\Sigma^*\) is countable for any alphabet \(\Sigma\) that is finite.

For any set \(A\), an encoding of the elements of \(A\) is a function from \(A\) to \(\Sigma^*\), for some alphabet \(\Sigma\), such that no two elements of \(A\) have the same encoding. In other words, an encoding is an injective function from \(A\) to \(\Sigma^*\).

2.1

Prove the following lemma.

Lemma. A nonempty set \(A\) is countable if and only if there exists an encoding of \(A\) into \(\Sigma^*\) for some finite alphabet \(\Sigma\).

Solution

Forward direction. Suppose \(A\) is countable. Then there exists an injective function \(f : A \to \N\). Take \(\Sigma=\{1\}\). The function \(g : A \to \Sigma^*\) defined by \(g(a)=1^{f(a)}\) is an encoding of \(A\) into \(\{1\}^*\).

Backward direction. Suppose there is an encoding \(f : A \to \Sigma^*\), where \(\Sigma\) is a finite alphabet. We showed that \(\Sigma^*\) is countable, so \(A\) is countable by Problem 1.2.

2.2

Are the following sets countable? Prove your answer. Note that for uncountable sets, diagonalization might be useful.

• \(\mathbb{Z}\)
• \(\mathbb{R}\)
• \(\mathbb{N}^\mathbb{N} = \{f \mid f : \mathbb{N} \rightarrow \mathbb{N}\}\)
• The set of all graphs with finitely many vertices.
• The set of finite lists of natural numbers.

Solution

• \(\mathbb{Z}\) is countable. Encode each integer over the alphabet \(\{0,1,2,3,4,5,6,7,8,9,-\}\) in the usual way. For example, \(-438 \mapsto \texttt{-438}\).

• \(\mathbb{R}\) is uncountable. It is enough to show that \([0,1]\) is uncountable. Suppose, for the sake of contradiction, that its elements can be listed as \(r_0,r_1,r_2,\ldots\). For each \(r_n\), use its decimal expansion that does not end in repeating nines. Construct \(x \in [0,1]\) so that its \((n+1)\)st digit after the decimal point is \(1\) if the corresponding digit of \(r_n\) is not \(1\), and is \(2\) otherwise. Then \(x\) differs from \(r_n\) in its \((n+1)\)st digit for every \(n\), so \(x\) is not in the list. This is a contradiction.

• \(\mathbb{N}^{\mathbb{N}}\) is uncountable. Suppose its elements can be listed as \(f_0,f_1,f_2,\ldots\). Define \(g : \N \to \N\) by

  \[ g(n) = f_n(n)+1. \]

  For every \(n\), the functions \(g\) and \(f_n\) differ on input \(n\). Thus, \(g\) does not appear in the list, which is a contradiction.

• The set of all finite graphs is countable. We can encode a graph on \(n\) vertices by its adjacency matrix, which is a string over the alphabet \(\{0,1,\texttt{,},\texttt{[},\texttt{]}\}\).

• The set of finite lists of natural numbers is countable. We can encode each list in the usual way using the alphabet \(\{0,1,2,3,4,5,6,7,8,9,\texttt{,},\texttt{[},\texttt{]}\}\).

3 How Many Unsolvable Problems Are There?

In the lecture, we identified the set of programs with \(\Sigma^*\) and the set of problems with \(\powerset(\Sigma^*)\). We then applied Cantor’s theorem to show that the function \(\text{Solves} : \text{Programs} \to \text{DecisionProblems}\) is not surjective; that is, there is some problem that cannot be solved by a program. The proof of Cantor’s theorem identifies a specific subset \(D \subset \Sigma^*\) that is not in the range of \(\text{Solves}\): the set obtained by flipping the diagonal.

Could it be that \(D\) is the only unsolvable problem?

3.1

The answer is no. In fact, there are uncountably many unsolvable problems.

Formally, show the following. Let \(B\) be the set of all unsolvable problems. That is, \(B = \text{DecisionProblems} \setminus \text{range}(\text{Solves})\).

Show that \(B\) is uncountable.

Solution

For the sake of contradiction, suppose \(B\) is countable. Then

\[ \text{DecisionProblems} = B \cup \text{range}(\text{Solves}). \]

The set \(\text{range}(\text{Solves})\) is countable because it is the image of the countable set \(\text{Programs}\). Thus, \(\text{DecisionProblems}\) would be countable as the union of two countable sets. However, \(\text{DecisionProblems} = \powerset(\Sigma^*)\) is uncountable by Cantor’s theorem. This is a contradiction, so \(B\) is uncountable.