[proofplan]
We split the assertion into two parts: infiniteness and countability. Infiniteness follows by exhibiting an injection $\mathbb{N} \to X^\star$ from the powers of a fixed letter. For countability, we use the hypothesis that $X$ is countable to obtain a surjection $\pi: \mathbb{N} \to X$, and we encode an arbitrary finite string over $X$ by a single natural number via prime factorisation: the exponent of $2$ records the length and the exponents of $3, 5, 7, \dots$ record the letter-preimages under $\pi$. Surjectivity of the resulting map $\mathbb{N} \to X^\star$ follows from surjectivity of $\pi$ and the Fundamental Theorem of Arithmetic.
[/proofplan]
[step:Fix a letter and exhibit an injection from $\mathbb{N}$ into $X^\star$]
Since $X \neq \varnothing$, pick $x_0 \in X$. For $n \in \mathbb{N}$ (with $\mathbb{N} = \{1, 2, 3, \dots\}$) let $x_0^n \in X^\star$ denote the string of length $n$ all of whose letters equal $x_0$. Define
\begin{align*}
\iota: \mathbb{N} &\to X^\star \\
n &\mapsto x_0^n.
\end{align*}
If $\iota(n) = \iota(m)$ then $x_0^n$ and $x_0^m$ are equal as strings, hence have equal length, so $n = m$. Therefore $\iota$ is injective. A set admitting an injection from $\mathbb{N}$ is infinite, so $X^\star$ is infinite.
[/step]
[step:Obtain a surjection $\pi: \mathbb{N} \to X$ from countability of $X$]
Since $X$ is a nonempty countable set, by definition of countability there exists a surjection
\begin{align*}
\pi: \mathbb{N} &\to X.
\end{align*}
Fix such a $\pi$ for the remainder of the proof.
[/step]
[step:Encode strings by natural numbers via prime factorisation]
Let $(p_i)_{i \geq 0}$ be the sequence of primes in increasing order, so $p_0 = 2$, $p_1 = 3$, $p_2 = 5$, and in general $p_i$ is the $(i+1)$-th prime. By the [Fundamental Theorem of Arithmetic](/theorems/???), every $k \in \mathbb{N}$ with $k \geq 2$ admits a unique factorisation
\begin{align*}
k &= \prod_{i \geq 0} p_i^{k_i},
\end{align*}
where $(k_i)_{i \geq 0}$ is a sequence of non-negative integers with only finitely many $k_i > 0$. For $k = 1$ the factorisation is the empty product, so $k_i = 0$ for all $i$.
Define
\begin{align*}
\Phi: \mathbb{N} &\to X^\star \\
k &\mapsto
\begin{cases}
(\pi(k_1), \pi(k_2), \dots, \pi(k_{k_0})) & \text{if } k_0 \geq 1, \\
\varepsilon & \text{if } k_0 = 0,
\end{cases}
\end{align*}
where $\varepsilon \in X^\star$ denotes the empty string and $k_i$ for $i \geq 1$ is interpreted as an element of $\mathbb{N}$ (with the convention $k_i = 0$ handled below).
For this definition to produce an element of $X^\star$, each entry $\pi(k_i)$ must be defined. If $k_i \geq 1$ then $k_i \in \mathbb{N}$ and $\pi(k_i) \in X$. If $k_i = 0$ we set $\pi(k_i) := x_0$ (the fixed letter from the first step); equivalently, we extend $\pi$ to $\{0\} \cup \mathbb{N}$ by $\pi(0) := x_0$. Either choice is immaterial for surjectivity; we fix this extension for definiteness.
The map $\Phi$ is well-defined because the factorisation $(k_i)_{i \geq 0}$ is unique (Fundamental Theorem of Arithmetic) and only finitely many $k_i$ are nonzero, so the tuple $(\pi(k_1), \dots, \pi(k_{k_0}))$ is a finite sequence.
[/step]
[step:Show that $\Phi$ is surjective onto $X^\star$]
Let $w \in X^\star$ be arbitrary. We must produce $k \in \mathbb{N}$ with $\Phi(k) = w$.
First, suppose $w = \varepsilon$ is the empty string. Take $k = 1$. Then $k_i = 0$ for all $i \geq 0$, in particular $k_0 = 0$, so $\Phi(1) = \varepsilon = w$.
Otherwise $w = (w_1, w_2, \dots, w_n)$ for some $n \geq 1$ and $w_j \in X$ for $1 \leq j \leq n$. Since $\pi: \mathbb{N} \to X$ is surjective, for each $j \in \{1, \dots, n\}$ we may choose $m_j \in \mathbb{N}$ with $\pi(m_j) = w_j$ (the axiom of countable choice suffices, or equivalently take $m_j := \min \pi^{-1}(\{w_j\})$ by the well-ordering of $\mathbb{N}$). Set
\begin{align*}
k &:= p_0^{n} \cdot \prod_{j=1}^{n} p_j^{m_j} = 2^n \cdot 3^{m_1} \cdot 5^{m_2} \cdots p_n^{m_n}.
\end{align*}
Then $k \in \mathbb{N}$ with $k \geq 2$, its prime factorisation has $k_0 = n$ and $k_j = m_j$ for $1 \leq j \leq n$, and $k_i = 0$ for $i > n$. By definition of $\Phi$,
\begin{align*}
\Phi(k) &= (\pi(k_1), \dots, \pi(k_{k_0})) = (\pi(m_1), \dots, \pi(m_n)) = (w_1, \dots, w_n) = w.
\end{align*}
Hence $\Phi$ is surjective.
[/step]
[step:Conclude that $X^\star$ is countable]
The existence of a surjection $\Phi: \mathbb{N} \to X^\star$ shows, by definition, that $X^\star$ is countable. Combined with infiniteness from the first step, $X^\star$ is infinite and countable.
[/step]
