Scribbles | Sandbox | Sandbox | gfrlog

(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 x3-4x2+.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: x2+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 ((x2+1),(x3+1),(x4+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...}
The last example is a little different from the others, because it's a set with an infinite number of elements.

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 countably infinite. Any infinite set that is larger than the positive integers is uncountable or uncountably infinite. I don't think it's possible for any infinite set to be smaller than the positive integers, so we can consider countable sets to belong to the smallest infinity. The reader may have noticed that I haven't given any examples of infinte sets that are different sizes, and this is because proving two infinite sets are different sizes is more difficult than the opposite, and I don't need it for an explanation of this Polynomials page. If you're interested, however, this article explains a relatively simple proof that the set of all real numbers is uncountable. So I'm actually only going to deal with countable sets.

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.