[proofplan] We prove the equivalence by showing that condition (i) gives both an injection into $\mathbb{N}$ and, when $X$ is non-empty, a surjection from $\mathbb{N}$. Conversely, an injection $X \to \mathbb{N}$ identifies $X$ bijectively with a subset of $\mathbb{N}$, which is [countable](/page/Countable%20Set). Finally, a surjection $\mathbb{N} \to X$ lets us choose the first natural number mapping to each element of $X$, producing an injection $X \to \mathbb{N}$ and reducing to the injection case. [/proofplan] [step:Construct an injection into $\mathbb{N}$ from a countable set] Assume $X$ is countable. If $X=\varnothing$, define the empty map \begin{align*} f_0: \varnothing &\to \mathbb{N}. \end{align*} There are no elements $a,b \in \varnothing$ with $f_0(a)=f_0(b)$ and $a \neq b$, so $f_0$ is injective. If $X$ is finite and non-empty, choose $n \in \mathbb{N}$ and elements $x_1,\dots,x_n \in X$ such that $X = \{x_1,\dots,x_n\}$ with the $x_i$ distinct. Define \begin{align*} f: X &\to \mathbb{N} \\ x_i &\mapsto i . \end{align*} If $f(x_i)=f(x_j)$, then $i=j$, hence $x_i=x_j$, so $f$ is injective. If $X$ is countably infinite, then by definition there exists a bijection \begin{align*} g: X &\to \mathbb{N}. \end{align*} Every bijection is injective, so $g$ is the required injection. Thus (i) implies (ii). [/step] [step:Identify $X$ with a countable subset of $\mathbb{N}$] Assume there exists an injection \begin{align*} f: X &\to \mathbb{N}. \end{align*} Let $Y := f(X) \subseteq \mathbb{N}$ denote the image of $f$. By [Subsets of Natural Numbers are Countable](/theorems/752), the set $Y$ is countable. The corestriction \begin{align*} \tilde f: X &\to Y \\ x &\mapsto f(x) \end{align*} is surjective by the definition of $Y$ and injective because $f$ is injective; hence $\tilde f$ is a bijection. If $Y$ is finite, then $X$ is finite because it is in bijection with $Y$. If $Y$ is countably infinite, choose a bijection \begin{align*} b: Y &\to \mathbb{N}. \end{align*} Then the composition \begin{align*} b \circ \tilde f: X &\to \mathbb{N} \end{align*} is a bijection. Hence $X$ is finite or admits a bijection to $\mathbb{N}$, so $X$ is countable. [guided] Assume there exists an injection \begin{align*} f: X &\to \mathbb{N}. \end{align*} The idea is to replace $X$ by the subset of $\mathbb{N}$ that it actually hits. Define \begin{align*} Y := f(X) = \{f(x) \in \mathbb{N} : x \in X\}. \end{align*} Then $Y \subseteq \mathbb{N}$, so [Subsets of Natural Numbers are Countable](/theorems/752) applies directly and gives that $Y$ is countable. Now we relate $X$ and $Y$ without losing information. Define the corestriction \begin{align*} \tilde f: X &\to Y \\ x &\mapsto f(x). \end{align*} This map is well-defined because $f(x) \in f(X)=Y$ for every $x \in X$. It is surjective because every element of $Y$ has the form $f(x)$ for some $x \in X$. It is injective because $f$ is injective: if $\tilde f(x)=\tilde f(x')$, then $f(x)=f(x')$, hence $x=x'$. Therefore $\tilde f$ is a bijection. Since $Y$ is countable, there are two cases. If $Y$ is finite, then the bijection $\tilde f: X \to Y$ transfers finiteness from $Y$ to $X$, so $X$ is finite. If $Y$ is countably infinite, choose a bijection \begin{align*} b: Y &\to \mathbb{N}. \end{align*} Then \begin{align*} b \circ \tilde f: X &\to \mathbb{N} \end{align*} is a composition of bijections, hence is a bijection. In either case, $X$ is finite or admits a bijection to $\mathbb{N}$, which is precisely the definition of countability. [/guided] [/step] [step:Construct a surjection from $\mathbb{N}$ onto a non-empty countable set] Assume $X$ is countable. If $X=\varnothing$, then condition (iii) holds by its first alternative. Now suppose $X \neq \varnothing$. If $X$ is finite, choose $k \in \mathbb{N}$ and distinct elements $x_1,\dots,x_k \in X$ such that $X=\{x_1,\dots,x_k\}$. Since Androma's convention is $\mathbb{N}=\{1,2,3,\dots\}$, define \begin{align*} h: \mathbb{N} &\to X \\ i &\mapsto \begin{cases} x_i, & 1 \leq i \leq k, \\ x_1, & i > k . \end{cases} \end{align*} For each $x_j \in X$ with $1 \leq j \leq k$, we have $h(j)=x_j$, so $h$ is surjective. If $X$ is countably infinite, then by definition there exists a bijection \begin{align*} u: X &\to \mathbb{N}. \end{align*} Its inverse \begin{align*} u^{-1}: \mathbb{N} &\to X \end{align*} is a bijection, hence is surjective. Thus (i) implies (iii). [/step] [step:Choose the first preimage under a surjection to build an injection] Assume condition (iii). If $X=\varnothing$, then $X$ is finite and therefore countable. Suppose $X \neq \varnothing$ and let \begin{align*} h: \mathbb{N} &\to X \end{align*} be a surjection. For each $a \in X$, define the fibre \begin{align*} A_a := \{n \in \mathbb{N} : h(n)=a\}. \end{align*} Since $h$ is surjective, $A_a$ is non-empty for every $a \in X$. By the [Well-Ordering Principle](/theorems/721), each $A_a$ has a least element. Define \begin{align*} g: X &\to \mathbb{N} \\ a &\mapsto \min A_a . \end{align*} This map is well-defined by the preceding paragraph. We prove that $g$ is injective. If $a,b \in X$ and $g(a)=g(b)=n$, then $n \in A_a$ and $n \in A_b$, so $h(n)=a$ and $h(n)=b$. Hence $a=b$. Therefore $g:X \to \mathbb{N}$ is injective. By the previous step proving (ii) implies (i), $X$ is countable. [guided] Assume condition (iii). If $X=\varnothing$, then $X$ is finite, so $X$ is countable. Now suppose $X \neq \varnothing$ and let \begin{align*} h: \mathbb{N} &\to X \end{align*} be a surjection. We want to reduce to the injection characterisation already proved. A surjection may hit the same element of $X$ many times, so we choose one natural number for each element of $X$ in a canonical way: the first time it appears in the list determined by $h$. For each $a \in X$, define the fibre \begin{align*} A_a := \{n \in \mathbb{N} : h(n)=a\}. \end{align*} Because $h$ is surjective, every $a \in X$ is hit by at least one natural number; equivalently, $A_a \neq \varnothing$ for every $a \in X$. Since $A_a$ is a non-empty subset of $\mathbb{N}$, the Well-Ordering Principle gives a least element of $A_a$. Therefore the assignment \begin{align*} g: X &\to \mathbb{N} \\ a &\mapsto \min A_a \end{align*} is well-defined. We now verify that $g$ is injective. Let $a,b \in X$ and suppose $g(a)=g(b)=n$. Since $g(a)=\min A_a$, we have $n \in A_a$, so $h(n)=a$. Since $g(b)=\min A_b$, we also have $n \in A_b$, so $h(n)=b$. Hence $a=h(n)=b$. Thus $g(a)=g(b)$ implies $a=b$, and $g$ is injective. We have produced an injection $g:X \to \mathbb{N}$. The earlier implication from (ii) to (i) applies to this injection, so $X$ is countable. [/guided] [/step] [step:Conclude the equivalence of the three conditions] We have proved (i) implies (ii), (ii) implies (i), (i) implies (iii), and (iii) implies (i). Therefore each of (i), (ii), and (iii) holds exactly when the others hold. This proves the claimed equivalence. [/step]