Countability of a set of polynomial functions I was trying some questions on countability of a set. Got stuck in an intermediate step.
Given $X$ = {$f$|$f$: $\Bbb{N} \rightarrow \Bbb{N}$ s.t $f$ is a polynomial function}.
I was supposed to check whether the set is countable or not.
If $f \in X$ then $f(x) = a_{0}+a_{1}x+a_{2}x^2+..a_kx^k$
My teacher said since $f(x) \in \Bbb{N}$ for all $x \in \Bbb{N}$ implies that all coefficients of $f(x)$ will belong to $\Bbb{Q}$.
I didn't get it. Please throw light on this.
 A: if $f\colon \Bbb N\to\Bbb N$ is a polynomial function of degree $d$, then it completely determined by the values $f(1),f(2),\ldots,f(d+1)$. There are countably many such $(d+1)$-tuples, hence the number of degree $d$ polynomial functions in $X$ is countable. Summing over the countably many possible $d$, we are still countable.
Going by the values is perhaps easier than going by the coefficients. The best you can say about those is that they are rational. For example, the function given by $f(n)=\frac16n^3+\frac12n^2+\frac13n$ is $\in X$ in spite of its non-integer coefficients.
A: First of all, for the case cardinality of $X$ , it doesn't matter whether we take $a_i$ in $\mathbb{Z} $ or in $\mathbb{N} $, the result will be same.
For simplicity, we choose $a_i$ randomly in $\mathbb{N}$.
Each $a_i$ is randomly choosen in $\mathbb{N} $,
So, for each $a_i$, there is countably infinite choice in natural numbers.
And there are finitely many $a_i$ ,$1 \le i \le n$, as $f$ is polynomial.
So, cardinality of $X$= cardinality of $\mathbb{N} × \mathbb{N} × \mathbb{N} × ..... × \mathbb{N} $ (finitely many times).
So, actually, cardinality of $X$ = $\aleph $
Edit : By the way,  your statement "$f(x) \in \mathbb{N} $ as $x \in \mathbb{N} $ $\implies$ $f$ is a polynomial in $\mathbb{N}$ " is not true always, as all others' comments.
You can create even such polynomial which contradicts your statement. For example, $f(x)=(x-1)^3 + 4 $
