In the 1st incompleteness theorem proof, how do we assume that everything in arithmetic language can be mapped to naturals?

Question

Consider the following set of arithmetic functions,

$a_0,a_1,a_2.....a_m(n)=a_0+a_1n+a_2n^2+...a_mn^m$

$a_0,a_1,a_2.....a_n$ can be any subset of naturals. So clearly, the number of these arithmetic functions is uncountable and can't be mapped to the naturals. What am I missing?

EDIT-$f(n)=\sum_{k=0}^{\infty} \frac{n^k}{a_kk!}$. What if we use this function? Now we can allow infinite subsets.

Answer 1

But the set of finite sequences of numbers $a_0, a_1, a_2, \ldots, a_n$ is not uncountable! So the set of polynomials of the form $f(n) = a_0+a_1n+a_2n^2+...a_mn^m$ isn't uncountable either.

Take the mapping that sends the finite sequence $a_0, a_1, a_2, \ldots, a_n$ to $\pi_0^{a_0}\pi_1^{a_1}\pi_2^{a_2}\cdot\cdot\cdot\pi_n^{a_n}$ where $\pi_n$ is the $n+1$th prime. That's an injective map into the naturals, establishing countability! (And of course this is an example of the sort of mapping we use in Gödel codings ...)

Answer 2

Addressing your new comment:

Yes, we can assign to each $A\subseteq\mathbb{N}$ a function $f_A:\mathbb{N}\rightarrow\mathbb{N}$ in an injective way - that is, such that $f_A=f_B$ iff $A=B$. (I'm ignoring the question of whether your specific construction works, that's beside the point.) More snappily, $\vert 2^\mathbb{N}\vert=\vert\mathbb{N}^\mathbb{N}\vert$.

However, this has nothing to do with Godel's incompleteness theorem! In the incompleteness theorem we're not saying that we have a way to represent every $g:\mathbb{N}\rightarrow\mathbb{N}$ by a natural number; all we're saying is that we have a way to represent every "simple" $g:\mathbb{N}\rightarrow\mathbb{N}$ by a natural number. And the set of "simple" functions is indeed countable, so there's no contradiction.

Specifically, "simple" for Godel means "computable" (or "recursive"). That said, it turns out that's overkill: for example, it's enough to just look at the primitive recursive functions (and indeed this is what Godel originally did).

---

Now a bit of an editorial comment:

Before tackling the incompleteness theorem you really need to be familiar with the basics of computable functions. Fully understanding the following facts is a good starting point:

• The set of computable functions is countable.

• Every computable function is definable in the structure $\mathfrak{N}=(\mathbb{N};+,\times)$, but not conversely.

  • The former is basically Kleene's $T$ predicate; for the latter, note that the set of $\mathfrak{N}$-definable functions is also countable so a cardinality argument won't help.

• However, a broad class of functions are computable - for example, the characteristic function of the set of powers of $10$, or of the set of Godel numbers of well-formed formulas.

The proof of Godel's theorem then really kicks off properly with the result that all computable functions are representable in the theory in question (usually PA or similar).