2
$\begingroup$

What is the cardinality of $\mathbb{Z}[x]$, the set of all polynomials with integer coefficients? It seems like it is countably infinite:

Define the height of a polynomial to be the sum of the absolute value of its coefficients and its degree $-1$. There are only finitely many polynomials of each height. We can list each polynomial, starting with height $-1$, $0$, and then $1$, etcetera, ordering the polynomials of each height by their constant term, and moving to the linear term if they are equal. It seems as though this is an ordering of the polynomials with integer coefficients, so the set is countably infinite.

However, each polynomial can be expressed as an infini-tuple. Then a diagonal argument shows that there is a polynomial that is not in the list. How can this be?

$\endgroup$
8
$\begingroup$

Your initial argument is correct: $\mathbb{Z}[x]$ is countable.

You can indeed represent polynomials as "$\infty$-tuples", and the diagonal argument does construct an $\infty$-tuple not on the list. But why should such a thing be a polynomial?

To wit, the polynomials are characterized as the $\infty$-tuples that only have a finite number of nonzero terms.

Note the same "paradox" would come up if you apply the diagonal argument to the natural numbers: after all, every natural number is a sequence of digits, so you can apply the diagonal argument to create an infinite sequence of digits not on the list. But is such a thing a natural number?

In regards to cardinality, there is a major qualitative difference between the set of all infinite sequence, and the set of all finite sequences. Relatedly, given a set $S$, there is a similar difference between the set of all subsets of $S$ and the set of all finite subsets of $S$. e.g. the set of all finite subsets of $\mathbb{N}$ is, in fact, countable.

$\endgroup$
2
$\begingroup$

Every polynomial is defined by a $finite$ tuple, that is a sequence of whole numbers that equals $0$ from some point on. There, the diagonal argument fails. It generates an "infinite" polynomial which is not an element of $\mathbb Z[x]$.

Your ordering of all polynomials looks fine to me.

$\endgroup$
2
  • $\begingroup$ Well, it is an infinite order pair, it is just identically 0 for sufficiently large terms. $\endgroup$ – vukov Feb 10 '14 at 14:37
  • $\begingroup$ What does that have to do with my argument? If you apply the diagonal argument to your sequence of polynomials, the inifini-tuple it will produce will contain an infinite amount of non-zero values and will thus not be a polynomial. $\endgroup$ – 5xum Feb 10 '14 at 14:39
0
$\begingroup$

Let $D_n=\{P\in\Bbb Z[X]:\deg P=n\}$. Then each $D_n$ is countable -- it is easy to see it is equipotent with $\Bbb Z^{n-1}\times (\Bbb Z-\{0\})$ by sending $a_0+a_1X+\cdots+a_nX^n\to (a_0,\ldots,a_n)$ -- and $$\Bbb Z[X]=\bigcup_{n\geqslant 0}D_n\cup\{0\}$$

Your argument breaks down the same way the argument $\Bbb N$ is uncountable breaks down by identifying a natural number by it's binary expansion: the expansion terminates, but a diagonal argument might produce nonterminating strings of $0$s and $1$s.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.