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:

X={1,2,3,4...}
Y=X-1={0,1,2,3...}

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
Y=X-1={0,1,2...,n-1}

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,a3...an) 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.

Sources: http://en.wikipedia.org/wiki/Cardinal_number

3 comments:

Blog Heard said...

Listen to this blog on youTube here:

http://www.youtube.com/watch?v=hMPTw5GVdfo

Unknown said...

Really nice clear examples, thankyou for this! I only found 3 people prepared to seriously debate these ideas in the last 20 years :)

Louis said...

Thank you for your comments!