[proofplan] Let $S \subset \mathbb{N}$ be arbitrary. If $S$ is finite, then it is countable by the definition of countability. If $S$ is infinite, we enumerate its elements in increasing order by repeatedly taking the least unused element, and then prove that the resulting map $g: \mathbb{N} \to S$ is injective and surjective. [/proofplan] [step:Dispose of the finite case by the definition of countability] Let $S \subset \mathbb{N}$. If $S$ is finite, then $S$ is countable by the definition of a [countable set](/pages/1215). Hence it remains to consider the case where $S$ is infinite. [/step] [step:Enumerate the infinite subset by repeatedly taking the least unused element] Assume that $S$ is infinite. By the [Well-Ordering Principle](/theorems/721), the nonempty subset $S \subset \mathbb{N}$ has a least element. Define $s_1 \in S$ to be this least element. Suppose $n \in \mathbb{N}$ with $n \geq 2$, and suppose $s_1,\dots,s_{n-1}$ have been defined as distinct elements of $S$. Define \begin{align*} A_n := S \setminus \{s_1,\dots,s_{n-1}\}. \end{align*} The set $\{s_1,\dots,s_{n-1}\}$ is finite, while $S$ is infinite, so $A_n$ is nonempty. By the Well-Ordering Principle, $A_n$ has a least element; define $s_n \in A_n$ to be that least element. This recursively defines a [sequence](/pages/1149) \begin{align*} s: \mathbb{N} &\to S \\ n &\mapsto s_n. \end{align*} The sequence is strictly increasing. Indeed, for each $n \in \mathbb{N}$, the element $s_{n+1}$ lies in $A_{n+1}=A_n\setminus\{s_n\}$. Since $s_n$ is the least element of $A_n$ and $s_{n+1}\in A_n$ with $s_{n+1}\neq s_n$, we have $s_n<s_{n+1}$. [guided] We now build the enumeration of $S$ without skipping any smaller available element. Since $S$ is an infinite subset of $\mathbb{N}$, it is nonempty. The Well-Ordering Principle applies to every nonempty subset of $\mathbb{N}$, so $S$ has a least element. Define $s_1 \in S$ to be that least element. Assume that $n \in \mathbb{N}$ with $n \geq 2$, and that distinct elements $s_1,\dots,s_{n-1}$ of $S$ have already been chosen. We remove the elements already chosen and define \begin{align*} A_n := S \setminus \{s_1,\dots,s_{n-1}\}. \end{align*} The removed set $\{s_1,\dots,s_{n-1}\}$ is finite. Since $S$ is infinite, removing finitely many elements cannot exhaust $S$, so $A_n$ is nonempty. Therefore the Well-Ordering Principle applies again, and $A_n$ has a least element. Define $s_n \in A_n$ to be that least element. This gives a [function](/pages/1214) \begin{align*} s: \mathbb{N} &\to S \\ n &\mapsto s_n. \end{align*} The reason this construction lists the elements in increasing order is that at stage $n+1$ we choose from \begin{align*} A_{n+1}=A_n\setminus\{s_n\}. \end{align*} Every element of $A_{n+1}$ is still an element of $A_n$, and $s_n$ was the least element of $A_n$. Since $s_{n+1}\in A_{n+1}$ and $s_{n+1}\neq s_n$, the inequality $s_n \leq s_{n+1}$ improves to \begin{align*} s_n < s_{n+1}. \end{align*} Thus the constructed sequence is strictly increasing. [/guided] [/step] [step:Define the enumeration map and prove it is injective] Define \begin{align*} g: \mathbb{N} &\to S \\ n &\mapsto s_n. \end{align*} If $m,n \in \mathbb{N}$ and $m<n$, then repeated use of the strict inequalities gives $s_m<s_n$. Hence $g(m)\neq g(n)$. Therefore $g$ is injective. [/step] [step:Show every element of $S$ appears in the increasing enumeration] Let $k \in S$. We prove that $k=s_j$ for some $j \in \mathbb{N}$ with $j\leq k$. Suppose, toward a contradiction, that $k\neq s_j$ for every $j\in\{1,\dots,k\}$. Then, at each stage $j\leq k$, the element $k$ still belongs to the unused set from which $s_j$ is chosen. Since $s_j$ is the least element of that unused set and $s_j\neq k$, we have \begin{align*} s_j < k \end{align*} for every $j\in\{1,\dots,k\}$. Thus $s_1,\dots,s_k$ are $k$ distinct elements of the finite set \begin{align*} \{1,\dots,k-1\}, \end{align*} which has exactly $k-1$ elements. This is impossible. Hence $k=s_j$ for some $j\leq k$, so $k$ lies in the image of $g$. [guided] Fix an arbitrary element $k\in S$. We want to prove that the enumeration eventually reaches $k$. The key point is that if $k$ has not yet been chosen, then the construction always chooses an unused element no larger than $k$, because $k$ itself is still available. Assume for contradiction that $k$ is not among the first $k$ chosen elements: \begin{align*} k\neq s_j \quad \text{for every } j\in\{1,\dots,k\}. \end{align*} At stage $j\leq k$, the element $k$ has not yet been removed, so $k$ belongs to the unused set from which $s_j$ is chosen. Since $s_j$ is the least element of that unused set, we get $s_j\leq k$. Because our contradiction assumption says $s_j\neq k$, this gives \begin{align*} s_j < k \end{align*} for every $j\in\{1,\dots,k\}$. Therefore $s_1,\dots,s_k$ are $k$ distinct natural numbers all lying in \begin{align*} \{1,\dots,k-1\}. \end{align*} But this finite set has exactly $k-1$ elements, so it cannot contain $k$ distinct elements. This contradiction proves that $k=s_j$ for some $j\leq k$. Since $k\in S$ was arbitrary, every element of $S$ lies in the image of $g$. [/guided] [/step] [step:Conclude that the subset is countable] The map $g:\mathbb{N}\to S$ is injective and surjective, hence bijective. Therefore the infinite set $S$ is countably infinite. Combining this with the finite case, every subset $S\subset\mathbb{N}$ is countable. [/step]