Wednesday, January 25, 2012

Infinity: The Cardinality of the Continuum

Before reading this post, make sure you have read Infinity: The First Transfinite Cardinal, and Infinity: Countable Sets.

In the previous posts of this series, it was established that the sets of natural numbers, integers, rational numbers, and even algebraic numbers have an equivalent cardinality: aleph-zero. However, not all real numbers fall under the umbrella of algebraic numbers. All of the numbers that are real but non-algebraic are irrational, and are specifically known as transcendental. Numbers such as e and π are transcendental.

To determine the cardinality of the real numbers, this problem can be again simplified to a problem involving ordered n-tuplets. This is done by considering the construction of an arbitrary real number. The general real number has a finite whole number part, followed by an infinite decimal expansion. For example, the real number π has a whole number part of 3, and a decimal expansion of .14159265... It is simpler to just ignore the whole number part, and focus on the real numbers on the interval (0,1). All of these are defined uniquely (almost, as we will see below) by their infinite decimal expansion. Therefore, each of these numbers is defined by an ordered n-tuplet, with n being infinite, and of the form


Since all values in this sequence are place values, each must be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. However, no clarity is lost if these real numbers are converted to binary, and each number still as a unique infinite decimal expansion, this time only incorporating 1's and 0's. We have the just simplified the problem to determining whether the set of all infinite sequences consisting of 1's and 0's is countable, i.e. whether it has a cardinality of aleph-zero.

Georg Cantor was the first to devise this method, and through infinite binary sequences found a very elegant way to find the cardinality of the real numbers, through proof by contradiction. It is called the diagonal argument. To understand this argument, consider all possible infinite binary sequences as making up a set, called S. Each element Sn is then an infinite binary sequence. If the cardinality of the real numbers is aleph-zero, then each element in the set can be numbered Sn, with n being a natural number. The first few elements of the set are shown below:

The actual ordering of this set is arbitrary, since if the cardinality of S is aleph-zero, all sequences with be covered eventually. For the next part of the proof, consider a sequence Sx, which is constructed by taking the nth element of each Sn and reversing it, i.e. 0 becomes 1, and 1 becomes 0. This is illustrated below:

The nth element of every nth sequence is bolded, and for each bolded element, the opposite one is placed in the sequence Sx. The resulting sequence is clearly an infinite binary sequence, and therefore is a member of the set S. However, by definition, it is different from any sequence in the set (S1,S2,S3...) because for any sequence Sn, with n a natural number, the nth element of the sequence is different from that of Sx. Therefore, assigning a natural number to each infinite binary sequence does not cover all such sequences, and the function from the natural numbers to S is not a bijection. Therefore, the set S has a cardinality greater then aleph-zero. Sets with cardinalities greater than aleph-zero are also known as uncountable.

When extending this back to our real number problem, there are a few slight glitches in this system, one of which being that an infinite binary decimal expansion such as .001111... with infinite 1's is actually equal to another, namely .010000... Therefore, each real number does not quite have a unique decimal expansion. However, this problem can be resolved.

Only numbers with terminating decimal expansions can be expressed in the two ways shown above, and in binary, the only such numbers are those whose denominators involve only a power of 2. For example, 1/2=.1000...=.0111..., and 5/8=.101000...=.100111... These numbers can be collected into a set of their own, called A, the first few members of which are {1/2, 1/4, 3/4, 1/8, 3/8,...}.

This is a subset of the rational numbers, and therefore has cardinality aleph-zero. The set of infinite binary sequences with infinite 0's or infinite 1's (which starts {.1000...,.0111...,.01000...,.00111...,...}) merely has two elements for each element of set A, and still has a cardinality of aleph-zero. (just as the sets {1,2,3...} and {1,-1,2,-2...} have the same cardinality, even though there are two elements in the latter whose absolute values correspond to the former) Because of this, a bijection can be set up between them, corresponding .1000... to 1/2, .0111... to 1/4, and so on. Adding this to the original set S, one finds that each real number on (0,1) now corresponds to a single unique infinite binary sequence.

Clearly, the cardinality of the entire set of real numbers must be greater than or equal to that of the real numbers on (0,1), and so we have now proved that

The cardinality of the real numbers, known as the cardinality of the continuum and denoted by , is strictly greater then the cardinality of the natural numbers, aleph-zero. In other words

> 0

More number systems still remain, including the complex numbers. However, it is fairly easy to see that the complex numbers still have the cardinality of the continuum, as any complex number can be defined uniquely as an ordered pair of two real numbers (a,b). Also, through a similar method that was used for integral ordered n-tuplets that is not detailed here, it can be proved that sets of ordered n-tuplets of real numbers or of complex numbers both have the cardinality of the continuum. This result also seems intuitively correct from previous examinations of ordered n-tuplets.

Using Cantor's diagonal argument, it was established that the cardinality of the set of real numbers was greater than that of natural numbers, in other words that there is no bijection between them. However, it has not been found exactly what this cardinality of the continuum actually is, or how to relate these quantities to each other in any way.

In order to accomplish this, one must first understand the concept of a power set. A power set is denoted P(S), where S is any ordinary set. Every set has a corresponding power set, and the above statement says that the power set of S is called P(S).

To construct the power set for any set S, take each unique combination of the elements in S, and put it into its own set. Then compile all of these sets and place them within another set. This is the power set, P(S). For example, the set {1,2,3} includes eight unique combinations of the elements contained within it, namely: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}. (the first of these is included as a choice of zero elements from the set) All of these are then included in a larger set, yielding {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. In conclusion:

P({1,2,3})={{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

If one compares the cardinality of these two sets, where each subset of the latter is a single element, it is easy to see that they are 3 and 8, respectively. One also notices that 2^3=8. This is no coincidence. The total number of combinations of n elements is (2^n)-1, and when one adds the empty set to this total, 2^n. Expressed in formula form, with the cardinality of a set S written as |S|:

Applying this knowledge to what we know about the set of natural numbers, it is easy to identify the set of all real numbers as the set of combinations of natural numbers, using the technique of binary sequences that was used previously. Combinations of natural numbers can be interpreted at the decimal expansion of real numbers through binary sets. For example, one can draw the combination {1,4,7} from the set of natural numbers {1,2,3...} and take it to mean .1100111000... which is a decimal sequence in which the binary expansions of 1 4, and 7 are joined, and then followed by zeros. There are also infinite subsets of the natural numbers, such as the even numbers {2,4,6...}, which will provide an infinite decimal expansion. This is not a precise mathematical way of doing this, but it serves as an intuitive glimpse into the cardinality of the continuum.

One can also choose the first element of the subset to represent the whole number part, which is always a finite natural number for all positive reals. Using this method, every real number can be generated from a subset (finite or infinite) of the natural numbers, and the real set is the power set of the natural numbers. This proves that

In other words, the cardinality of the continuum is two to the power of aleph-zero. But how can one even comprehend arithmetic operations with cardinal numbers, and infinite ones at that? What other properties does aleph-zero have? The answers can be defined through sets, and are discussed in the next post.


Tuesday, January 17, 2012

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

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

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

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.

Monday, January 9, 2012

Infinity: The First Transfinite Cardinal

In mathematics, infinity, often denoted ∞, is defined as exceeding all natural numbers, or, conversely, as the limiting value as a variable n increases without bound. ∞ has always been regarded as a sort of mystical quantity, ever out of reach from most mathematical concepts and calculations. However, through set theory, insights into infinity, in fact multiple infinities, can be gained.

A set is a series of elements, such as {1,2,3} or {12,58,-1,4}. The number of elements in a set is known as its cardinality. For example, {1,2,3} has a cardinality of 3, and {12,58,-1,4} has a cardinality of 4. Any number that can represent the cardinality of a set is known as a cardinal number. 3 and 4, as demonstrated above, are examples of cardinal numbers.

In fact, every natural number 1, 2, 3... is a cardinal number, and even 0 is a cardinal number, as it measures the number of elements in the empty set {}, also written Ø.

Now, it is useful to define functions on sets, namely rules for changing one set into another. The most important of these are known as bijections, and they are defined as functions of sets that preserve the cardinality of a set.

The above diagram is a pictorial representation of a bijection, defined as a function that maps each point in set X to exact one point in set Y, in other words a one-to-one correspondence. It is clear that such a function, when applied to a set, will preserve its cardinality. For example, the function y=x-1 maps the set {2,3,4} to the set {1,2,3}, each of the sets having a cardinality of exactly 3. Since this function preserves the cardinality of all sets in the same matter, it is a bijection.

It is also possible to define an infinite set, or a set with an infinite number of elements. The simplest of these is the set of all natural numbers, namely {1,2,3,4...}. This set has infinite cardinality, and the cardinal number representing this set is the first so-called transfinite cardinal. It is denoted aleph-zero, or ℵ0.

Aleph-zero is not contained within the normal number system that we think of, but rather describes the size of the set containing all natural numbers. One could then wonder whether adding another element, for example 0, to the set would result in a cardinality of ℵ0+1. This intuitively seems reasonable, but it is not the case. It was earlier shown that the function y=x-1 is a bijection, so that, when applied to the above set X, will preserve its cardinality of aleph-zero. The result is as follows:


Therefore, the set containing all whole numbers, which include both the natural numbers and 0, also has a cardinality of aleph-zero.

At first glance, the above result appears paradoxical. It seems that by subtracting all the terms by 1, an element is added to the beginning of the set, but taken off the end. This is certainly true for finite sets of natural numbers. For any finite natural number n, if

X={1,2,3...,n-1,n}, then

However, as n increases without bound towards ∞, n-1 is ultimately indistinguishable from n, as ∞-1 is still ∞. In addition to this, when one considers any natural number in the infinite set {1,2,3,4...}, it is decreased by 1 when the function is applied, but there is always another number to take its place. When one takes these points into consideration, the result begins to make sense.

One can easily use the functions y=x-2, y=x-3... etc. to incorporate the elements -1, -2, etc. with the same logic as before, generalizing the above statement to include any finite number of negative integers.

This is only the beginning. Next, consider the function defined below.

If x is odd, then y=(x-1)/2
If x is even, then y=-x/2

The above is not a usual function that can be defined in simple operators of x. However, it is still a bijection when applied to the set of natural numbers, as each element of the set {1,2,3,4...} is transferred to a unique number in a second set. This set is {0,-1,1,-2,2-3,3...}. Remarkably, the output of this function covers all integers! Again, it is easy to see that for any integer one could choose, there is always a natural number that produces it with the above function. Therefore, the total set of integers still has the same cardinality, namely aleph-zero, as the natural numbers.

Nor does the fun stop there! Next consider the mapping of a set to a set of ordered pairs, namely assigning a set of two integers to each natural number. This can be done in the following way:

1 -> (0,0), 2 -> (1,0), 3 -> (1,1), 4 -> (0,1), 5 -> (-1,1), 6 -> (-1,0), 7 -> (-1,-1), 8 -> (0,-1), 9 -> (1,-1), 10 -> (2, -1)...

The exact pattern of these ordered pairs can take several different forms, the above being one of these. Initially, the above sequence seems to have no clear pattern, but it does have a clear geometric significance.

The above pattern lists all the integral ordered pairs (white circles) reached as one follows a rectangular counterclockwise spiral beginning at the origin (the black path). Clearly, by following this path for a sufficient distance, we will visit any ordered pair of integers (a,b) that we could choose!

Before exploring the implications of the above statement, we must make one more logical step. Consider an ordered triplet of the form (a,b,c), again with a, b, and c integers. One can use a similar system to the one above to set up a one-to-one correspondence between the natural numbers and these triplets. The first few terms are listed below:

1 -> (0,0,0), 2 -> (0,0,1), 3 -> (0,1,1), 4 -> (1,1,1), 5 -> (1,0,1), 6 -> (1,-1,1), 7 -> (0,-1,1), 8 -> (-1,-1,1), 9 -> (-1,0,1), 10 -> (-1,1,1)...

Just as before, this can be visualized as a rectangular spiral in the three dimensional coordinate system, where each point is given coordinates (x,y,z). In fact, this pattern, and its geometric interpretation, continue for any order n-tuplets, each consisting of elements (a1,a2, and representing a spiral in the n-dimensional Cartesian system.

But what does this mean in terms of the number systems? Clearly, the set of all integral n-tuplets, for any finite n, has a cardinality of aleph-zero. From this, we draw the similar result that

Any infinite set or subset of a number system whose members can be represented by integral ordered n-tuplets, with n a natural number, has the same cardinality as the set of natural numbers, namely aleph-zero.

The implications of the above statement are explored in the next post.


Sunday, January 1, 2012


Juno is a NASA spacecraft whose mission is to orbit Jupiter and gain further insight to its composition and formation. It is named for the goddess Juno, wife of Jupiter in Roman mythology.

The spacecraft launched on August 5, 2011 to start its six year mission, culminating in a Jupiter arrival in 2016. The probe's trajectory included a flyby of Earth designed to conserve fuel. Unlike previous missions to the outer Solar System, Juno's energy will come only from solar panels, despite the relative dimness of the Sun at Jupiter's orbit.

Juno's trajectory from launch in 2011 to arrival at Jupiter in 2016.

In 2012, Juno executed several deep-space-maneuvers that prepared the probe for its flyby of Earth. Next, in October 2013, Juno completed its Earth flyby, assuming a trajectory directly toward Jupiter.

On July 4, 2016, the spacecraft executed an engine burn that inserted it into orbit around Jupiter. The probe assumed a highly elliptical orbit that took it past the north and south poles of Jupiter with every revolution.

The image above shows Juno's orbits around Jupiter over time, beginning with the orbital insertion on July 4.

This image, Juno's first acquired from orbit, shows the gas giant as well as three of the four Galilean moons, Io, Europa, and Ganymede (from left to right).

After its initial insertion burn, the Juno spacecraft spent over two months completing an elongated orbit that took it far away from the Solar System's largest planet. The first of 37 science flyby took place on August 27 and brought Juno over the north pole of Jupiter, capturing the first ever image of this polar region (see below).

The polar region is very different in appearance than the midlatitudes and equatorial region of Jupiter. The latter regions have characteristic colored bands of red, white, and orange, as well as prominent storm features. The poles are bluer, and lack these storm features.

Juno's path will take it just over 3,000 miles from the cloud tops near the poles, and will allow extensive observations of aurorae and other magnetic field phenomena. However, such an orbit also leaves Juno exposed to high concentrations of radiation, which will slowly degrade the functionality of the spacecraft. Juno is therefore planned to spend just over a year at Jupiter, making 33 orbits, before intentionally crashing into Jupiter late in 2017.

Juno will hopefully provide further information concerning the formation and evolution of Jupiter, specifically about its interior, about which little is known.