First page . . . Back to page 5 . . . Forward to page 7
Attempts to go beyond the Busy Beaver function, by necessity, have to go beyond functions, algorithms and formal systems. Imagine any sufficiently general definition of formalism (such as the Turing machine) and then define a function f(N) giving the maximum value of the results of its computation in terms of N, a suitably formalized specification of the amount of information used to define the formal system and the algorithm. f(N) will have a finite value for any finite N and can be said to grow at a certain rate. Because all f(N) are finite for all finite N, there exists a g() such that g(N) is greater than f(N) for all N.
By necessity, it is impossible to define g(N) in any specific way because the entire realm of formal systems and algorithmic definition is already a part of the definition of f(N). By necessity, g(N) cannot have a clear definition: if it did that definition is formalizable and capable of being computed by the Turing machine, and is therefore already part of f(N).
At this point in the discussion (or usually sooner) it becomes apparent that there is additional knowledge and assumptions "outside the system". An effort is made to identify these, define them precisely and add them into the quantity N. After doing this, it is soon discovered that the resulting formal system itself depends on things outside itself, and so on. I have encountered many expositions, discussion threads, etc. over the years, that begin with an optimistic determination to formalize the problem and quantify exactly how large numbers can be derived from first principles; they all have ended up somewhere in this jungle of abstraction. Here is a relevent quote:
I have this vision of hoards of shadowy numbers lurking out there in the dark, beyond the small sphere of light cast by the candle of reason. They are whsipering to each other; plotting who knows what. Perhaps they don't like us very much for capturing their smaller brethren with our minds. Or perhaps they just live uniquely numberish lifestyles, out there beyond our ken.12
As of this writing (last checked in 2007), this seems to be the frontier of development for the expression of large finite numbers. Of course, many people try, but everything seen so far appears to duplicate or fall short of the results of computation theory.
If you're interested in defining larger functions, go right ahead, but please note that you'll want to check your new function to see if it really pushes the limits a significant amount. If you use any of the methods described above, then your new function will not push the limits a significant amount.
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. In most axiomatic systems, there is no difference.)
One of the consequences is that, 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).
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 symbolized w.
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 ℵ0, 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: ℵ0 + 1 = 1 + ℵ0 = ℵ0. 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.
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" = w = 1 + w = 2 × w = ℵ0
w + 1
w + 2
w + w = w × 2
w + w + 1
w × 3
w × w = w2
w2 + 1
w2 + w
w3
w3 + w2 × 3 + w × 3 + 1
ww = 1 + w + w2 + w3 + w4 + w5 + ...
ww + 1
ww + w
ww + w2
ww + w3
ww + ww = ww × 2
ww × w = ww + 1
ww + 1 + w
ww + 1 + ww
ww + 2
ww × 2
ww2
ww3
www
www + 1
www × 2
wwww
wwwww
wwwww..
e0 = wwwww..... (with w omegas)
Cantor defined e0, "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. I see no particular reason why Cantor had to do this, except that he did not consider using a hyper4 operator. Since we do have the hyper4 operator we'll go ahead and use it, and continue the series (repeating the last line and continuing):
e0 = wwwww..... (with w omegas) = w④w
w④w + 1
w④w × 2
w④w × w
(w④w)2
(w④w)w
(w④w)④w
w④(w④w)
w⑤w
w⑥w
...
Somewhere along this sequence or perhaps after it (it is unclear from the sources I have access to) are various higher "epsilons" e1, e2, ew, ee0 and so on, and then a quantity Cantor calls alpha, which represents the first quantity that cannot be handled by the epsilon sequence.10,11
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 ℵ0. For that reason, Cantor put all the ordinal infinites listed so far in a "class" and labeled that class ℵ0.
All of these infinities are called countable because, if appropriately reordered, a set with w + 1 or ww or w⑤w 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.)
After showing how to construct all these countable ordinal infinities, Cantor then defined a new ordinal infinity omega-one or w1 to be the number of countable ordinal infinities. This number, the number of countable ordinal infinities, is bigger than ℵ0 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 w1 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, ℵ1 is called w1. 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 ℵ1 class, because when counted in the cardinal manner, any set with a number of elements constructed by this process has ℵ1 elements.
In geometric set theory systems, which are cardinal systems, the ℵ-series is not used (although ℵ0 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, ℵ0 × 2, 2 × ℵ0 and ℵ0 × ℵ0 are all equal to ℵ0, but 2ℵ0 is bigger, and in fact
c = 2ℵ0
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 Q0 and the line has an arbitrary center point P0. Now, every point P on the line has a coordinate CP corresponding to that point's distance from P0, positive on one side and negative on the other. Every point Q on the line segment has a similar coordinate CQ. 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:
CQ = arctan(CP) / pi
Each point P has a unique coordinate CP, and each value for CP generates a unique value for CQ 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):
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.
[ A, B, C, D, ... ]
For each simple continued fraction there is exactly one such sequence and each simple continued fraction gives a different 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.
First page . . . Back to page 5 . . . Forward to page 7
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13