Large Numbers

First page . . . Back to page 9 . . . Forward to page 11

Transfinite and Infinite Numbers

Beyond all the finite numbers are transfinite numbers and infinities. Once we go beyond finite numbers, we enter an area where it is essential to define exactly what theory of numbers we're working in.

Most number theory follows the axiomatic method, a discipline established by Euclid in the study of geometry and later adapted to every other branch of mathematics. By the axiomatic method, results are found by starting with a set of axioms and strictly following a set of rules to derive new results. This technique seemed flawless until the development of non-Euclidean geometry in the 19th century, which showed that one could construct equally valid, useful, and consistent versions of a given type of mathematics (e.g. geometry) by starting with a different set of axioms. Mathematicians were even more surprised in the 1920's when Gödel showed that no (sufficiently powerful) axiomatic system of number theory can prove all statements which are true in that system. It is now agreed that this phenomenon of incompleteness is a property of all axiomatic systems.

Depending on what type of number theory you're looking at, there may or may not be transfinite numbers and there may or may not be a plurality of infinities. These differences result from the use of different axioms and rules for deriving results. Different axioms and rules lead to different results including different answers to the question what lies beyond all the integers?. Because different systems are useful for different things and none can generate all useful results (due to incompleteness as demonstrated by Gödel) we end up with several different 'right answers' to the question. None is the 'best' answer, but some are more popular than others. (The term transfinite itself is a result of this — it was Cantor's effort to avoid using the term infinite for certain quantities that were definitely not finite, but did not share all the properties of what he considered truly infinite, and now called "Absolute Infinite".)

In the discussion to follow, it is often difficult or even meaningless to compare the various definitions of infinities to each other, trying to determine which is larger. However, within any one number theory system the infinities can usually be put into a clear order.

Georg Cantor developed two different systems of infinities, called ordinal and cardinal, out of his work in set theory during the 1870's and 1880's. His work still suffices for most purposes (much as Newton's physics is sufficient for most engineers).

Ordinal Infinities

The transfinite numbers, also called ordinal infinities, arise out of a set of axioms from which one gets the nonintuitive result that "infinity" and "one plus infinity" are equal, but "infinity plus one" is bigger. Here, "infinity" can refer to any of a large number of different types of infinity. The smallest of them is called omega, which will usually be symbolised w.

The First Cardinal Infinity: ℵ₀

The cardinal systems are more familiar. In these systems, order is irrelevant in counting. Cardinal infinity systems are more common in set theory because most set theories have the property that sets are considered equivalent when reordered. Cardinal infinities also occur in topology, geometry and fractal studies because of the practice of treating geometrical objects as "sets" of points.

In cardinal systems, the first or "smallest" infinity is ℵ₀, pronounced "alef-null". This is the one that most people think of when they think of infinity — the number of integers, or where you'd get to if you counted "forever". Since we're talking about cardinal numbers, adding one does not change the value: ℵ₀ + 1 = 1 + ℵ₀ = ℵ₀. Also, it's the same infinity even if you counted the integers by taking all the evens first, and then the odds: infinity even numbers plus infinity odd numbers; the total is just infinity, not "two times infinity". All you did was reorder the numbers; that never changes how many there are.

This infinity is also the size of an infinite Euclidean geometrical object, like the length of a line, the area of a plane, etc. when measured in terms of another finite unit such as a line segment. Here we are referring to "size" in terms of measure, where specific distances are taken into account, not in terms of order, which is the number of elements in a set and therefore the number of points in a geometric object.

The Ordinal "Countable" Infinities

Now we switch back to the ordinal systems. As mentioned above, in the ordinal systems we have the strange result that infinity + 1 is a different quantity from infinity, but that 1 + infinity is equal to infinity. In the ordinal systems a lot of work is done to construct ever higher and higher infinities, developing rules for how addition (and later, multiplication, exponents, etc) work and inventing new symbols as you go along. I'll skip the details and just list some of the ordinal infinities. Each line gives an ordinal infinity (sometimes in more than one equal and equivalent form), and each line is a larger value than the lines before it. Also, in most cases we're leaving out an infinite number of lines between each line and the next:

"omega" = ω = 1 + ω = 2 × ω = ℵ₀
ω + 1
ω + 2
ω + ω = ω × 2
ω + ω + 1
ω × 3
ω × ω = ω²
ω² + 1
ω² + ω
ω³
ω³ + ω² × 3 + ω × 3 + 1
ω^ω = 1 + ω + ω² + ω³ + ω⁴ + ω⁵ + ...
ω^ω + 1
ω^ω + ω
ω^ω + ω²
ω^ω + ω³
ω^ω + ω^ω = ω^ω × 2
ω^ω × ω = ω^{ω + 1}
ω^{ω + 1} + ω
ω^{ω + 1} + ω^ω
ω^{ω + 2}
ω^{ω × 2}
ω^ω²
ω^ω³
ω^{ω^ω}
ω^{ω^{ω + 1}}
ω^{ω^{ω × 2}}
ω^{ω^{ω^ω}}
ω^{ω^{ω^{ω^ω}}}
ω^{ω^{ω^{ω^{ω^{.^.}}}}}
ε₀ = ω^{ω^{ω^{ω^{ω^{.^.}}}}}... (with ω omegas)

Epsilon-Null

Cantor defined ε₀, "epsilon-null", to be the first ordinal infinity that could not be expressed with a finite number of omegas and/or integers combined with addition, multiplication, and exponents. By definition ε₀ is the "fixed point" of exponentiation when applied on "the left" i.e. in the weaker sense:

ω^ε₀ ::= ε₀

As for addition and multiplication, exponentiation is not commutative, so we have several inequalities:

(ε₀)^ω > (ε₀)^2 = ε₀×ε₀ > ε₀×2 = ε₀+ε₀ > ε₀+1 > ε₀.

This adds to the existing pattern of equalities and inequalities in ordinal aritmetic:

left-associative operations	right-associative	fixed-point equivalences
1+ω = ω < ω+1	ω+ω = ω×2	1+ω+ω = 1+ω×2 = ω×2
2×ω = ω < ω×2	ω×ω = ω↑2	ω+ω×ω = ω+ω↑2 = ω↑2
2↑{ω} = ω < ω↑{2}	ω↑{ω} = ω↑↑2	ω×ω↑{ω} = ω×ω↑↑2 = ω↑↑2
2↑↑{ω} = ω < ω↑↑{2}	ω↑↑{ω} = ω↑↑↑2	ω↑ω↑↑{ω} = ω↑ω↑↑↑2 = ω↑↑↑2

In the table, the lower-right statement is equivalent to ω^ε₀ = ε₀, stated above, because ε₀ is ω↑↑{ω} = ω↑↑↑2.

Unfortunately, several problems happen when people try to use the exponential and/or tetration notation with ordinal numbers:

In the use of "exponentiation", the most common issue appears to be confusing the cardinal arithmetic of set theory with ordinal arithmetic (e.g. here. In set theory, given a set with ω elements, its power set has order 2^ω and this is recognised as being a larger infinity than ω itself. In ordinal arithmetic, 2^ω is the same as ω (provided a suitable ordering in which to count the 2^ω things).
Some discussions assume that α↑↑δ is equivalent to α↑²δ using some definiition of "↑²". In particular, the most popular definition of "↑²" implies that ω↑²(ω+1) is ω^{(ω↑²(ω))}, which ends up being useless because ω^ε₀ = ε₀. However, this discussion shows how to define a "↑²" that works properly. Similarly, this discussion by Mike Battaglia defines ↑, ↑↑, ↑↑↑ approriately for ordinal arithmetic and shows that the resulting operations reproduce the entire Veblan hierarchy using just the constants ω and 1 and the 2-argument functions (operators) +, ×, ↑, ↑↑, etc.

In light of the above there is no particular reason why Cantor had to switch to a new letter for ε₀, and then more letters like ζ and so on — except that he did not consider using a hyper4 operator or was perhaps limited by the thinking and notations of the time. Since we do have the hyper4 operator we'll go ahead and use it, and continue the series (repeating the last line and continuing from where we left off):

ε₀ = ω^{ω^{ω^{ω^{ω^{.^.}}}}}... (with ω omegas) = ω^④ω = ω↑↑ω
ω^④ω + 1
ω^④ω × 2
ω^④ω × ω
(ω^④ω)²
(ω^④ω)^ω
(ω^④ω)^④ω
ω^④(ω^④ω) = ω^⑤3
ω^⑤ω = ω↑↑↑ω
ω^⑥ω = ω↑↑↑↑ω
...

Within this sequence are the various higher "epsilons" ε₁, ε₂, ε_ω, ε_ε₀ and so on, and then a quantity Cantor calls alpha, which represents the first quantity that cannot be handled by the epsilon sequence.⁷,¹¹

All Ordinals Countable by Reordering

This process continues, of course, through higher hyper operators (which is as far as Cantor took it), then through the same procedures we used on the finite numbers: triadic operators, Ackerman functions, chained-arrow notation, and so on: All of these techniques will generate higher and higher, distinct ordinal infinities. The limit of finite algorithmic iteration on the ordinal infinities is given by a sort of transfinite ordinal busy beaver function. Beyond that are other non-algorithmically-reachable constructions of ordinal infinities.

All of this is possible because of the original axioms and rules of the ordinal system, which state that the order you count things in makes a difference. But what if you're allowed to reorder the items when counting them? That would amount to switching to a cardinal counting system. When this is done, all of these ordinal infinities turn out to be equal! They are all equivalent to the cardinal ℵ₀. For that reason, Cantor put all the ordinal infinites listed so far in a "class" and labeled that class ℵ₀.

All of these infinities are called countable because, if appropriately reordered, a set with ω + 1 or ω^ω or ω^⑤ω elements can be shown to have the same number of elements as the set of positive integers. (Such sets are called "countable" because you can "count" their elements with integers, and be sure that every one will get a number.)

Definition of ℵ₁

After showing how to construct all these countable ordinal infinities, Cantor then defined a new ordinal infinity omega-one or w₁ to be the number of countable ordinal infinities. This number, the number of countable ordinal infinities, is bigger than ℵ₀ even if treated as a cardinal number: there is no way to reorder the ordinal infinities in such a way that you can assign a different integer to each one. Any attempted ordering will leave at least one un-numbered.

In order to define w₁ Cantor had to use cardinal counting, where order doesn't matter and one-to-one mappings are used to show if two sets have the same number of members (more on this later).

In the ordinal system, ℵ₁ is called ω₁. It is the first non-countable infinity. The process of constructing ordinal infinities continues, and is even more tedious than the process that we used with the omegas. The resulting ordinal infinities all fall into a second "class" when counted in a cardinal system, and this class is called the ℵ₁ class, because when counted in the cardinal manner, any set with a number of elements constructed by this process has ℵ₁ elements.

The Order of the Continuum

In geometric set theory systems, which are cardinal systems, the ℵ-series is not used (although ℵ₀ may occasionally be used or implied by the use of the term "countable"). In these systems, the next infinity after the "countable" is c, called the *order of the continuum* or sometimes simply the continuum. One also sees reference to a continuum, in which case the reference is to a geometric/topological set that has c elements, that is to say, a geometric object containing c points. Examples of a continuum are a straight line, or the real numbers.

Since we are in a cardinal system, ℵ₀ × 2, 2 × ℵ₀ and ℵ₀ × ℵ₀ are all equal to ℵ₀, but 2^ℵ₀ is bigger, and in fact

c = 2^ℵ₀

c is the number of points in a line segment (canonically the open set consisting of all the points on the real line from 0 to 1 but not including 0 and 1 themselves). c is also sometimes called the line segment's measure.

Amazingly, this is also equal to the number of points on a line of infinite length.

Imagine a line segment of length 1 and an infinite line. The line segment has a midpoint Q₀ and the line has an arbitrary centre point P₀. Now, every point P on the line has a coordinate C_P corresponding to that point's distance from P₀, positive on one side and negative on the other. Every point Q on the line segment has a similar coordinate C_Q. To show that the two objects (the line and the line segment) have the same number of points, all we need to do is to supply a mapping function such as the following:

C_Q = arctan(C_P) / pi

Each point P has a unique coordinate C_P, and each value for C_P generates a unique value for C_Q by this formula, which corresponds to a unique point Q on the line segment.

The continuum is the number of real numbers. Real numbers include anything that has a decimal point and a finite (or infinite) number of digits, with a repeating or nonrepeating decimal pattern. Most real numbers have an infinite number of digits after the decimal point and no repeating pattern.

Real numbers can be used to show that the number of points on a plane is equal to the number of points on a line. For each point on a plane, there is a unique pair of coordinates, such as (2.21751..., 6.40861...) or (9.40589..., 3.25361...), etc. Take the digits of the two coordinates and form a single number by interleaving the digits: one digit from the first coordinate, then one digit from the second, then another digit from the first coordinate and another from the second, and so on. All the digits get used once, none get duplicated or thrown away. The result is a single real number that is different from the number you would get from any other pair of coordinates:

(2.21751..., 6.40861...) becomes 26.2410785611...
(9.40589..., 3.25361...) becomes 93.4205538691...
(1.01489..., 0.99749...) becomes 10.0919478499...
etc.

(This is another example of a one-to-one mapping, this time successful. It is a technique used often in set theory)

c is also the number of sets of integers, which is also the number of ascending integer sequences (just reorder each set of integers so their elements are in ascending order). An ascending integer sequence is something like:

-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, ...
-2, 1, 2, 4, 5, 7, 8, 10
0, 2, 4, 5, 7, 8, 10, 16, 17, 19, 22, ...
1, 2, 4, 8, 16, 32, 64, 128, 256, ...
1, 3, 4, 7, 10
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

where there are a finite or infinite number of integers and each one is bigger than the one before it. The number of possible sequences is infinite, and can be proven to be bigger than the number of integers. It can also be proven to be equal to the number of real numbers with another one-to-one mapping (here, we're skipping a detail that is necessary to avoid problems with integer sequences that have no definite start, as for example the set of negative even integers):

Starting with any real number *X, define its simple continued fraction* to be the expression of the form:

A + 1 / (B + 1 / (C + 1 / (D + ... ) ) )

where A is an integer, B, C, D, ... are positive integers, and the expression converges on the value of X (that is, the value of the expression, when all of its terms, perhaps infinite in number, are taken, is exactly equal to X.) For each real number there is exactly one such simple continued fraction and each real number gives a different simple continued fraction. If the real number is a rational number the continued fraction has a finite number of terms.

Now, replace the expression with the ordered integer sequence:

[ A, B, C, D, ... ]

For each simple continued fraction there is exactly one such sequence and each simple continued fraction gives a different sequence.

Now, replace each sequence with another sequence by taking sums to get an ascending sequence:

[ A, A+B, A+B+C, A+B+C+D, ... ]

Each ordered sequence gives exactly one ascending sequence and each ordered sequence gives a different ascending sequence.

To get the one-to-one mapping from ascending sequences back to real numbers, just reverse the process.

There are other ways to prove that c is the order of the power set of the integers; Cantor proved it in a manner similar to that discussed here.

The Continuum Hypothesis

After developing the ordinal and cardinal theories to this point, Cantor could not determine whether c was distinct from ℵ₁ or equal to it. Cantor tried for a long time to discover a set of points that had more than ℵ₀ points but less than c (if found, he could say that this set had ℵ₁ points, and c would be ℵ₂ or larger). He couldn't find such a set, and then proposed what is now called the continuum_hypothesis:

c is equal to ℵ₁ ? (continuum hypothesis)

Cantor then tried to prove or disprove this hypothesis but never succeeded. Today, with the benefit of Gödel's results, it is not surprising to see why he had so much trouble: Cantor was attempting to combine or assimilate results from two different formal systems: the ordinal and cardinal types of counting.

In an ordinal system, 1 + X is not always equal to X + 1, but X × 2 is always greater than X. In a cardinal system, 1 + X equals X + 1 but X × 2 is not always greater than X. Another more formal way of saying this is that ordinal systems retain the property of a unique multiplicative identity and cardinal systems retain the property of commutativity — but neither retains both.

Gödel showed in 1940 that Cantor could not have disproved the continuum hypothesis using his axioms (which are now called "Zermelo Fraenkel set theory with the Axiom of Choice", often abbreviated ZFC), Paul Cohen showed in 1963 that Cantor could not have proved it either. For this work, Gödel and Cohen both did major new work in the field of metamathematics, which involves "modeling" mathematical axiom-proof systems with "bigger" systems.

So, at least in standard ZFC set theory, the continuum hypothesis must be declared to be true or false using a new axiom, or left undecided (as Cantor did). You get a different system of infinities each way. By the 1990's, most mathematicians preferred to define the continuum hypothesis as being false (mostly because of the usefulness of the results that can be derived). The implication is that (if you follow the preference of the mathematicians) c is greater than ℵ₁.

The Power Sets of the Continuum

Returning permanently to cardinal set theory, we proceed to higher infinities beyond c. The set of integers, and all other countable sets, has ℵ₀ elements. A continuum (like a line) has c points, and if CH is assumed to be true, the set of integer sequences also has c elements. The set of integer sequences is an example of something called a power set: the set of all subsets of some other set. Cantor showed that power sets always have more elements than the set from which they were constructed, and so generate another higher infinity.

Let S1 be a set with ℵ₀ elements (like the set of integers)
Let S2 be the set of all countable ordinals
Let T be a set with c elements (like the set of points on a line)
Let T' be the set of all subsets of T (the power set of T).
Let T'' be the set of all subsets of T' (the power set of T').
etc.

It has been commonly held by experts on the subject (beginning with the likes of (Kurt Gödel and Paul Cohen) that the Continuum Hypothesis is false. If this turns out to be correct then all of the following can be said:

ℵ₀ is the order of S1. (The number of elements in S1).
ℵ₁ is the order of S2.
ℵ₂ is the next ordinal infinity after ℵ₁.
ℵ₃ is the next ordinal infinity after ℵ₂
etc.
c is the order of T.
2^c is the order of T'.
2^{2^c} is the order of T''.
etc.
AND there is no proven relation between the two series, other than that c is bigger than ℵ₁ (because as we just stated, in this section we're using the assumption that the Continuum Hypothesis is false).

In cardinal set theories it can be shown that that there are no infinities "in between" these. Any definition of an infinite quantity can be shown to be equivalent to a member of the power set sequence. When the Continuum Hypothesis is taken to be false, c cannot be equivalent to ℵ₁, but it could be ℵ₂ or one of the higher ones. All of the higher power sets would then coincide in the same way. For example, if c were ℵ₂, then 2^c would be ℵ₃ and so on.

Consider the order of the set T':

c^* = 2^c = order of set T'

This infinity is usually thought to be equal to the number of distinct sets of points in a Euclidean space. This is a little difficult to comprehend; an easier definition to comprehend is the number of distinct "wiggly lines" in two-dimensional space. A "wiggly line" in this case can be extremely convoluted, such that any level of magnification will show more and more wiggles (like a fractal, but not necessarily a self-similar fractal).

The next infinity after c^* or 2^c is c or 2^{2^c}. There appears to be no useful geometrical definition or application (outside set theory) for this or any of the higher infinites. Whereas the first three infinities can be thought of as counting the number of integers, points, and curves in 2-d space, 2^{2^c} doesn't appear to count anything geometrical. Anything we've found that can be counted is covered by one of the lower infinities.

Inaccessible Infinities

Finally consider the limit of these processes:

ℵ₀, ℵ₁, ℵ₂, ℵ₃, ... (ordinals)
ℵ₀, c, 2^c, 2^{2^c}, ... (cardinals)

In each of these processes, imagine the infinity you "get to" as you carry the process on "forever". This includes any algorithmic process in which the number of steps is finite, working up to such things as ℵ_BB(n) where BB(n) is the busy beaver function and N is some gratuitous huge integer.

Since the infinities all have an integer subscript, the "number of infinities" (or number of classes, if you are working within an ordinal system) is ℵ₀, and the "limit" of the process of defining higher infinities is the "ℵ_ℵ₀" class (ordinal system), or "2^④ℵ₀" (cardinal system).

Then you make another definition (still in a formal well-defined way) so you can talk about ℵ_ℵ₀ directly and thence move on to ℵ_ω+1 or ℵ_ℵ₁ (depending on whether your larger formal system uses ordinal rules or cardinal rules, respectively). This process can be continued, and eventually formalised through another level of abstraction to construct even higher infinities. One of these is so big that is is equal to its own ℵ-number: theta = ℵ_theta.

If you stay "within the system" while doing this process, by sticking to well-defined symbols, rules, axioms, etc. you can create more and more infinities, but you will always be working within a formal system of number theory or set theory.

However, all number theories and set theories are incomplete. It has been shown that by going outside the system you can demonstrate the existence of "inaccessible cardinals" or "inaccessible infinities", which are bigger than all of those producible through formal systems. This result is analogous to the computation-theory result of the uncomputable functions.

Note. I try to explain things at least a little bit, and to give suitable references. I definitely do not follow my own First Law of Mathematics. If you suggest an improvement for these pages, I'll probably be able to do something to make it better — just let me know (contact links at the bottom of the page).

First page . . . Back to page 9 . . . Forward to page 11

Japanese readers should see: 巨大数論 (from @kyodaisuu on Twitter)

If you like this you might also enjoy my numbers page.

s.30