Infinity: Countable Sets

Before reading this post, read Infinity: The First Transfinite Cardinal.
At the end of the previous post, it was stated that any infinite set or subset of a number system defined by integral ordered n-tuplets, where n is a natural number, has a cardinality of aleph-zero. This statement is more easily understood with examples.

We have already seen that natural numbers can be put in one-to-one correspondence with any set of n-tuplets that contains only integers. When n=1, the resulting number system is simply the integers themselves: {...-3,-2,-1,0,1,2,3...} Furthermore, the above guarantees that any infinite subset of integers will have equivalent cardinality. The even numbers {2,4,6...}, multiples of 10, {10,20,30...}, and even the powers of 2 {1,2,4,8,16...} all can be accessed from the natural numbers through a simple bijection (in this case the functions y=2x, y=10x, and y=2^x, respectively) and therefore have the same cardinality, aleph-zero.
However, the above theorem states that a number system defined by integral ordered n-tuplets for any finite n are also allowed. First, consider the ordered pairs. How does one define a number system with the general integral pair (a,b)? One way, is to view these numbers as the solutions to polynomial equations with coefficients a and b, namely
ax+b=0

Solving for x, one obtains x=-b/a. The general solutions of these equations are the rational numbers, any numbers that can be formed by the ratio of two integers. Admittedly, using the spiral method to pair each natural number with an ordered pair does not hold up well when converted into rational numbers. For instance, the ordered pairs (-2,1) and (-4,2) both produce the same solution, namely 1/2, and pairs such as (0,1) are not defined at all! Therefore, the function from natural numbers to rational numbers through the spiral method is not a bijection.
These problems can be resolved, however. One way is to simply discard duplicates and undefined ordered pairs. The natural numbers corresponding to unique rational numbers will henceforth be known as unique ordered pair numbers, or UOPN's for short. The first few are

2 -> (1,0) -> 0
3 -> (1,1) -> -1
5 -> (-1,1) -> 1
10 -> (2,-1) -> 1/2
12 -> (2,1) -> -1/2
14 -> (1,2) -> -2

In the above expression, the first number of each row is a natural number, followed by the corresponding ordered pair defined by the spiral rule, and the final number is the rational number that results using the polynomial method on the ordered pair. Since it is clear that there are an infinite number of rational numbers accessed by the above series, one can set up a bijection pairing each natural number n to the nth UOPN. This would change the set {1,2,3,4...} into {2,3,5,10...}. The UOPN's then have the same cardinality as the natural numbers, and therefore the rational numbers do as well.
The result just established is remarkable. Despite there being infinite rational numbers between the natural numbers 0 and 1 alone, the cardinality of both of these sets are identical. But this still isn't the end of it. The theorem also deals with numbers defined by ordered n-tuplets. Continuing the theme of using ordered n-tuplets to define integral polynomial equations, the solutions of the resulting equation give the value of the ordered n-tuplet. For example, the ordered quadruplet (1,0,0,-2) corresponds to
x^3+0x^2+0x-2=x^3-2=0,

the real solution of which is the cube root of two. However, with higher degree polynomials, there may be multiple solutions. Consider the polynomial graph below.


This is the graph of x^3-2x^2-x+1, the ordered quadruplet for which would be (1,-2,-1,1). In this case, there are three solutions to the polynomial equation x^3-2x^2-x+1=0 on the real number line, i.e. the three intersections of the graph with the x-axis. How then does one avoid ambiguity? Which of the three solutions does (1,-2,-1,1) represent? The solution lies in specifying an interval on which the solution is found. For example, the first solution, to the left of the origin, lies on the interval [-1,0], and with this constraint, the unique solution can be specified.
Generally, given a ordered n-tuplet of the form (A1,A2,A3...,An-4,B1,B2,C1,C2), one specifies the corresponding number to be a zero of the polynomial

(A1)x^(n-4)+(A2)x^(n-3)+...(An-3)x+An-4
on the interval whose endpoints are the rational numbers defined by the ordered pairs (B1,B2) and (C1,C2).
It is now clear that any solution of any polynomial equation of integral coefficients has an accompanying natural number. Since these solutions can be set up in a one-to-one correspondence with some subset of the natural numbers, one can be set up with the natural numbers themselves. As before, this implies an identical cardinality, i.e. the set of the solutions to integral polynomial equations has a cardinality of aleph-zero.
Just what are these numbers? We know that they are the general solutions of integral polynomial equations, but what form do they take? This specific set of numbers are called the algebraic numbers, and they include square roots, cube roots, and for that matter any nth root. They also include more complicated sets of nested roots, such as numbers of the form



for integer a, b, and c. Any number with nested roots such as this is algebraic. Specifically, algebraic numbers encompass all rational numbers along with many irrational numbers, but not all real numbers are algebraic. For example, π and e are not algebraic, and cannot be expressed as the solutions of polynomials of any finite degree.
All of the above sets have a cardinality the same as that of the natural numbers, and they are therefore denoted countable sets, named after the ability to count natural numbers. All of the rational numbers, and even some irrational numbers are countable, but one hurdle remains: the real numbers. All of the surprising discoveries above suggest that the idea of real numbers being countable is not an implausible notion. The answer is revealed in the next post.
Sources: http://en.wikipedia.org/wiki/Cardinal_number