Countability of Polynomials

(This is an explanation of the polynomials web applet)

I'll have to explain a couple background concepts first, so bear with me.

Alright, remember what polynomials are? If we limit ourselves to one variable (like x,
for example), a polynomial is something like x^{3}-4x^{2}+.87. It's
basically a string of any number of terms involving x to some power, all added together.
High school algebra featured a lot of time spent factoring 3-term polynomials into
a pair to 2-term polynomials: x^{2}+3x-18=(x+6)(x-3). So anyways, if I asked
how many different polynomials there are, any sane person ought to reply that there
are an infinite number of them, which makes sense. At the very least, there's an infinite
number of polynomials like (x+1),(x+2),(x+3),(x+4)..., not to mention (x+1),(2x+1),(3x+1),(4x+1)...
and with those two lists we haven't even gotten into powers of x larger than 1
((x^{2}+1),(x^{3}+1),(x^{4}+1)...), negative numbers, fractions/decimals, or the
possibility of polynomials with more than 2 terms! So clearly there are many ways in which
the set of polynomials is infinite, both lots of simple ways (like the few I just demonstrated), as well as
countless ways of mixing them all together.

Also, we need some basic set theory (which is quite simple, at least the parts that we'll be using). A "set" is just a collection of things. We show sets with a pair of curly braces and some commas. For example, The set of things I had for breakfast this morning = {Peanut butter cinnamon oatmeal, black coffee, pulpy orange juice}. Mathematicians are most often interested in sets of mathematic things, like numbers:

- The set of integers between five and twelve: {6,7,8,9,10,11}
- The set of two-digit integers divisible by ten: {10,20,30,40,50,60,70,80,90}
- The set of one-digit integers between five and six: {}
- The set of integers larger than sixty-two: {63, 64, 65, 66, 67...}

That brings us to the specific part of set theory we'll be talking about - the part that deals with
the size of a set. The official term for this is cardinality, but we'll just use the word size. When
we're dealing with finite sets, like the set of things I had for breakfast and the set of integers
between five and twelve, size is a pretty easy thing to work with. If I asked you to compare the sizes
of those two sets and tell me which is bigger, you'd say the second one is bigger, because it has six
elements, while the set of things I had for breakfast only has three. And that's true. But when we
start talking about infinite sets, that method isn't so helpful anymore. For example, which of these
two sets is bigger: the set of all even integers, {2,4,6,8...} or the set of integers larger than
sixty-two, {63,64,65,66,67...}? To answer these questions, we have to have a different method for
comparing sizes. The way we do it is, instead of counting the elements in each set, we make pairs of
elements, one from each set. If we pair up as many elements as we can, but one set still has some left
over, then the set with elements left over must be larger, right? Probably. With finite sets, this is
certainly true. With infinite sets, two sets are different only if there is *no possible
way* to pair their elements up. Here's why this distinction is important. Let's consider
the two sets I mentioned earlier - even integers, and integers larger than sixty-two. Somebody who is
convinced that the set of integers larger than sixty-two has more elements may arrange the pairs like this:
(2,65),(4,66),(6,67),(8,68)... On the left side of the pairs, we count up all the even integers. On
the right side, we count up all the integers larger than sixty-two, but we start with sixty-five. This
means that 64 and 63 are left out, which could (supposedly) prove that the set of integers larger than
sixty-two is the larger set, since some of its elements were left over. (If this is seeming rather
trivial so far, just hold on a bit) But, of course, somebody could just as easily arrange the pairs
so to leave out elements from the other set: (6,63),(8,64),(10,65),(12,66)... Here we've included all
of the integers above 62, but left out the first two even integers. So that should prove the exact
opposite - that the set of even integers is larger. That's why we have the distinction that for the
sets to be different sizes, there must be *no possible way* of pairing up all of each of their
elements. In this case, the two sets are the same size, because we can obviously pair both sets up
without leaving anybody out: (2,63),(4,64),(6,65),(8,66)...

Ok, let's make this more interesting. When we're measuring the sizes of infinite sets, it's helpful
to have some sort of standard. In this case, the simplest standard is the size of a set we're all
quite familiar with - the positive integers {1,2,3,4,5,6...}. Since the positive integers are what
we use for counting, we're going to say that any set that is *the same size as* the positive
integers is ** countable** or

One handy shortcut is to notice that, to prove a set is countable, we don't have to worry about actually
pairing its elements with the positive integers, as long as we can simply arrange the elements in a list.
Once the elements are listed with a definite starting point, the pairing is obvious: pair the first
element in the list with the number 1, the second with the number 2, etc. For example, the set of positive
*and* negative integers: {...-3,-2,-1,0,1,2,3...}. This set is countable, because we can list its
elements by rearranging them like this: {0,1,-1,2,-2,3,-3...}. Now the obvious pairing with the positive
integers is (0,1),(1,2),(-1,3),(2,4),(-2,5),(3,6)... So to prove a set is countable, we simply need to
make a list.

We can use simple methods to prove some counterintuitive things, like that the set of even numbers is the same size as the set of positive and negative numbers, or that the set of numbers larger than five is the same size as the set of numbers larger than four.

One last step we'll take is to prove that the set of rational numbers (this includes all integers, fractions, and normal and repeating decimal numbers (but excludes non-repeating decimals like pi and many square roots)) is countable. This is harder to believe than the previous concepts, because there are an infinite number of rational numbers merely between 0 and 1. In fact, between any two rational numbers, there are an infinite number more of them. However, they are countable. To prove this, we need to note that all rational numbers can be expressed in fraction form, with one integer divided by another. The integers are simply themselves divided by 1: 8=8/1, -17=-17/1, etc. Fractions are already in fraction form, and finite decimals can easily be put into fractions by using powers of ten: .6=6/10, .7429=7429/10000, etc. Showing how a repeating decimal can be turned into a fraction is a little more complicated, but there are explanations all over the internet if necessary. Once we have all our rational numbers in fraction form, simply think of the fractions are coordinates from geometry. 3/5 is like the point (3,5). 1/12 is the point (1,12). Each fraction has its own point on the coordinate plane somewhere. Now we can list all of these points by starting at (1,1), moving to the right one to (2,1), going diagonally up-left to (1,2), then back down-right up (3,1), up-left through (2,2) to (1,3), and keep zig-zagging up-left and down-right out to infinity. If we do this forever, we'll go through all the positive rational numbers. To add the negatives, we can simply insert them after their positive counterparts in an alternating manner.

So how does all that relate to this page? Well, remember at first we talked about how the set of polynomials is quite infinite. It also so happens that they're countable. When I first learned this, I thought it was the most counterintuitive example of countability that I could think of, so that I wanted to actually see them listed to see what it would look like. So I made my own method of listing them and wrote it into a computer program. This page has links to some smaller sub-lists of the whole infinite list. The first 10000 polynomials is probably the best place to start. My favorite part is how relatively simple polynomials won't appear on the list until beyond the 100-digit numbers (look at the Fibonacci polynomials to see what I mean).

Well, that's about all the explaining I'm in the mood for.