Can I use Gödel numbering to prove a set is countable? We're studying the basics of set theory (introducing ZFC, defining countability, etc.) and in one of my homework questions I am asked to prove that given a finite set of symbols $a_1, a_2, \cdots, a_n$, the set of all finite strings of these symbols is countable (the next question makes there be countably many symbols).
My first thought was showing that every such string can be assigned a unique natural number using the standard Gödel numbering as follows:
$$(a_{i_1}, a_{i_2}, \cdots, a_{i_n}) \mapsto p_1^{i_1} p_2^{i_2} \cdots p_n^{i_n}$$
And arguing that due to the fundamental theorem of arithmetic, this numbering must be unique, since the numbering differs if the two strings differ in at least one position (including if they have distinct lengths), so there is an injection from the set of finite strings of symbols to $\mathbb{N}$ hence this set is countable (and of course there are infinitely many primes so this works for any finite string of symbols)
(I think this works even if the number of different symbols is countable as long as the strings are finite)

But then it occurred to me that because this is a logic course which I am told makes up the foundation of mathematics, I might not "have access" to things like the FTA because that might be circular reasoning or something, and would need a solution that uses more basic tools of set theory without making use of high level statements that basically seem to already use what I am trying to prove on some level (speaking generally here, not specifically about the above problem).
So my question is: does this make any sense? Can I use facts about integers like prime numbers to prove these kinds of "low-level" statements? Do I need to particularly worry about things like circular reasoning here, or is it just about making sure any fact I invoke doesn't depend on an axiom (of ZFC) that I haven't assumed? Thanks for any help!
 A: Your worries are justified. One would have to check carefully if the prrof of FTA does not rely on this fact (well, actually it doesn't).
Show that for given $L$ the set of strings oflength $L$ is finite. Then use the (known?) fact that the countable union of finite sets is countable.
A: Yes, you can use that.
First of all, just prove the fundamental theorem of arithmetic. You don't need to appeal to Gödel numbering there. It's a fact that you prove about the natural numbers via induction.
A: It's easier when the indices start at $0$, and so for all $n$ let $b_n = a_{n + 1}$.
Establish a bijection from $\mathbb{N}$ by letting each natural number $n$ correspond to the finite string of symbols whose length is equal to the number of $1$'s in the binary representation of $n$, and whose $i$th symbol is $b_{f(i)}$, where $f(i)$ is the number of $0$'s immediately following the $i$th $1$. The procedure works whenever there are countably many (or finitely many) symbols to choose from. Notice that $0$ corresponds to the empty string.
