April 13, 2018 at 14:56The Innumerable: Finding a Finite Number
The ancient Greeks - adherents of concepts that have a strict logical meaning - in every possible way avoided the concept of infinity. Indeed, what do we care about an infinite series of numbers, if we can neither write down nor imagine it.
In the Middle Ages, logical rigor was discarded for the sake of mathematical results and developed extremely efficient algorithmic methods that operate in infinity computing.
In the XX century. another problem began to emerge distinctly. We can deal with infinity with a single character (∞), but what about numbers that are less than infinity, but are unimaginably huge?
We came close to the numbers, barely inferior to the "Ouroboros", but at the same time still having theoretical and practical significance. You probably could hear about Graham's number, which is the upper bound for solving a particular problem in Ramsey's theory. 88 years after the advent of Ramsey's theorem, mathematicians are ready to drop old methods and go even further.
Welcome to the rabbit hole without a bottom.
Intro to remember the past
In the XVII century. the mathematician and philosopher Blaise Pascal wrote about his fear of infinity, about his own insignificance at the thought of the vast expanses of space. I wonder what Pascal would say about Graham's number, consisting of a tower of numbers tall from the Earth to the most distant star, each number of which has its own tower of numbers? Each bend of a number in a tower of numbers, which consists of a tower of numbers, accommodates a tower of other numbers - but even with this formulation, we did not come close to the discovery made by Graham.
The origins of the Graham number should be sought in 1928, when the young mathematician Frank Ramsay, while working on an article on logic, noticed an amazing thing: complete disorder is impossible. Each sufficiently large set of numbers, points or objects necessarily contains a highly ordered structure.
The conjecture, which was only a small part of the work on logic, laid the foundation for a completely new field of mathematics called the Ramsey theory. It is often explained by the example of a party: suppose you want to find the perfect balance between those who know each other and strangers. You draw a map of the relationships of all your friends, connecting two people if they are friends, a blue line, and a red one if they are not familiar with each other. Then you can get a similar illustration: The
beauty of Ramsay’s theory is that problems in this area are always very easy to formulate . Considering the example of a party, it is very interesting to understand how many people are enough to form a group in which there will always be four people either familiar or not familiar with each other.
In a group of 17 points shown in the figure above, it is impossible to find four points for which the network of edges connecting them would be completely red or blue. Therefore, more than 17 people are required, so that among them there must be four people who are familiar or not familiar with each other. In fact, in a group of 18 people there will always be either four acquaintances or four not familiar with each other.
Take any star cluster. In it you can always find a group that with very high accuracy forms any given configuration - a straight line, a rectangle, a bucket.
Mathematicians try to calculate how large the set of stars, numbers, or any objects should be so that it is possible to guarantee the existence of a certain desired substructure. Decisions of such problems often take decades.
Ramsey's theory is also of great practical importance - from organizing a good party to building more advanced communication networks and transmission and information retrieval systems. In fact, it is very difficult to imagine for what purpose many methods developed for solving problems in Ramsey theory can serve - this is the most advanced field of mathematics.
How and why Graham came to his number
American mathematician Ronald Lewis Graham (born 1935) made a significant contribution to discrete mathematics. Graham is a versatile personality. At one time, he was even the president of the international association of jugglers, but became famous solely due to the large positive integer, which serves as the upper limit of a specific problem in Ramsey's theory.
An N-dimensional cube always contains 2n vertices. Despite their dimension, n-dimensional cubes are simply graphs whose vertices are connected by edges
We can turn any n-dimensional cube into a complete graph by simply connecting all the vertices. The remaining edges thus formed are located inside or on one of the faces. Imagine that these edges have two colors - red and blue. Thus, Graham formulated an interesting question lying in the plane of the classical Ramsey theory: at what minimum value N of a two-color k-dimensional cube does each such coloring necessarily contain a single-color full subgraph with four vertices, each of which lies in one plane?
A full graph on a three-dimensional cube with two-color rib coloring
In 1971, Ronald Graham and Bruce Lee Rothschild provedthat this problem has a solution, and it is a number that is greater than 6 (lower bound), and less than some N. The lower bound was subsequently raised to 13, and the upper bound was called the small Graham number. A small number of Graham is less than the number that fell into the Guinness Book of Records, but it is still an unimaginably huge number.
In general, Graham’s task does not sound like something supernatural - a fifth grader can also understand it. But simple questions are sometimes very difficult to get answers. If the solution is less than the Graham number we know, then what is the answer? The Graham number, like some other large numbers, just tells us that a problem in principle has a solution, and this solution can be found. By optimizing the solution to the problem, we can move the Graham number closer to 1, and move it until we find a real solution.
How the number has become a legend
So, Ronald Graham wrote a professional mathematical work on Ramsey theory, which attracted the attention of journalist Martin Gardner. It was Gardner who contributed to the inclusion of the Graham number in the Guinness Book of Records, after which the number attracted the attention of the general public.
The problem Graham was trying to solve was actually just one concrete example of the application of Ramsey theory. Further research in this theory gave mathematicians larger numbers than even the Graham number. These numbers are not an exact solution to problems, but are the upper bound.
Perhaps the best theorems in Ramsey's theory can drastically reduce the upper bounds, which will lead to the disappearance of a huge number of super-large numbers. This, for example, happened to the number of squash: in 1987 it was defined as 8.185 · 10 370 , and after 30 years it turned out that it lies between 10 19 and 1.3971672 · 10 316 .
What graham charmed people? Beauty and visibility.
To operate with gigantic numbers, Graham used fast-growing functions. Many of these functions are familiar to everyone - addition, multiplication, and exponentiation. Mathematicians have created new functions that scale much faster.
Graham used Knut's arrow notation to record the number. - expansion of exponentiation. In the same way that exponentiation is repeated multiplication and is indicated by a single arrow pointing up, two up arrows indicate iterative exponentiation, three arrows indicate repeated iterative exponentiation, etc.
Or so:
3 ↑↑ 5 = 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 = three to the power of three to the power of 7 625 597 484 987.
Mathematicians realized that when dealing with large numbers, it was necessary to use a new operator each time, which should be more powerful than the previous one. ↑↑ is the next operator from ↑, just as ↑ is the next operator from multiplication, and just like multiplication is one operator from addition. Thus, increasing the number of consecutive arrows increases the ability to work with large numbers.
If you add another arrow, then the speed of formation of new numbers will increase significantly:
3 ↑↑↑ 3 gives us a tower of degrees of triples with a height of 7 trillion numbers.
Four arrows will give a number, which will be very difficult to write down. Let's look at an example from the wonderful article “ Graham Number on the Fingers ”:
And here is the original illustration that Gardner used to explain Graham's number:
The highest level is 3 ↑↑↑↑ 3. The formula you saw above. Below it is a layer in which the number of arrows is 3 ↑↑↑↑ 3. Next is a layer in which the number of arrows is equal to the number of arrows in the previous layer. And so on until the 64th layer.
The beauty of this expression is that if you want to exceed the Graham number and write “super large number = Graham number + 1”, then nothing will change on a mathematical scale. It's like climbing to the top of Everest and jumping on it - Everest will still remain the highest mountain, on top of which you can climb.
But somewhere in the solar system, there is Olympus , right?
Bowers notation: the beginning of the rabbit hole
Further work with the Ramsey theory of mathematicians Joseph Kraskal and Harvey Friedman led to the number TREE (3), in which even the lower boundary of the solution is super-huge, not to mention the upper one.
If we can at least write down the Graham number, then the TREE number (3) cannot be placed in the framework of Knut's notation. Judge for yourself:
TREE (3) = ...> A A (187196) (4), where even A 2 (4) is greater than the number of atoms in the Universe, because A is the Ackerman function , which is determined recursively for non-negative integers m and n as follows:
Using the Ackerman function, one can very easily write the Graham number ≈ A64 (4).
Mathematicians have calculated that TREE (3) has a theoretical boundary that can be written withmassive notation proposed in 2002 by Jonathan Bowers. In massive notation, there are five rules:
- {a} = a and {a, b} = a b
- {a, b, c, ..., n, 1} = {a, b, c, ..., n}
- {a, 1, b, c, ..., n} = a
- {a, b, 1, ..., 1, c, d ..., n} = {a, a, a, ..., {a, b - 1,1 ..., 1, c, d ..., n}, c - 1, d ..., n}
- If rules 1-4 are not applied, then {a, b, c, d ..., n} = {a, {a, b - 1, c, d ..., n}, c - 1, d ..., n}
In the simplest case, a massive notation with an array of two elements looks like this: {10,100} = 10 100 or 10 ↑ 100.
The function grows incredibly fast. An array of three elements {10,100,2} in Knuth arrow notation will have the following form: 10 ↑ 2 100.
Bowers triple arrays are completely identical to Conway’s triple chains (another method of writing - numbers connected by horizontal arrows (chains), grow faster than Knuth notations ):
{3,3,3} = 3 → 3 → 3 = 3 ^ (3 ^ (3 ^ (3 ^ ... 7 625 597 484 987 times ... ^ 3) ^ 3) ^ 3)
An array of four elements (for example {10,100,1,2}) is already larger than the Graham number itself - thanks to a trick invented by Bowers: on the fourth element, he "optimizes" the formula, as we optimized multiplication and exponentiation, only now the mathematician is engaged in doubling brackets:
{3,3,1,2} = 3 {{1}} 3 = 3 {3 {3} 3} 3 = {3, 3, {3, 3, 3}}.
You can find a more detailed discussion of this operation in the article “ Bird's Linear Array Notation ”.
Moreover, "the largest number used in serious mathematical proof" is limited between {3,65,1,2} and {3,66,1,2}. We are now talking only about linear arrays, and in fact they can be hyper-dimensional. In principle, a four-element Bowers array is able to accommodate all of Conway’s notation, and hyper-dimensional arrays (in the illustration above) are already becoming a mathematical hyper-game.
The beauty of mathematics is that we can work with data that is impossible to even imagine. Any difficult task can be facilitated to incredibly simple values. Perhaps we will never find answers to some questions, but the methods used to solve them may be useful in other areas of knowledge. The elaboration of these methods of constructing hierarchies by the rate of growth of functions improves many sections of mathematics.
Bowers made a successful attempt to answer the question of how to use the hierarchy of techniques to expand the capabilities of the formal system. In fact, we write down not the number itself in an allegorical way, but the way to someday come to this number, even in theory.
Bowers notations are a great way to get an understanding of the TREE function. Of course, we cannot determine the value of TREE (3), but using the iterative “improvement” of the notation carried out by the English mathematician Chris Byrd, it was possible to find out that TREE (3)> {3,6,3 [1 [1¬1,2 ] 2] 2}.
TREE (3)
TREE is a fast-growing function in graph theory developed by mathematician Harvey Friedman.
Suppose we have a sequence of k-numbered trees T1, T2, ... with the following properties:
- each tree T i has at most i vertices;
- no tree is embeddable homeomorphically into any tree following it in sequence.
T i <T j , that is, T i is not embeddable in T j
Such a sequence cannot be infinite. Joseph Kruskal was the first to put forward this theory in 1960. Harvey Friedman extended the theory by asking the question: Given k, what is the maximum length of such a sequence of trees?
This maximum length is a function of k called TREE (k).
TREE (1) = 1. The first tree is a unique tree with one vertex labeled 1. This tree is obviously embeddable in any other tree, so we ended up with 1:
TREE (2) = 3. The first tree can only be a single one-vertex tree, labeled 1 or 2. Denote it 1 (red). Then no other trees can use label 1 - all vertices must be labeled 2 (blue). The second tree can be either a single one-vertex tree, or a unique two-vertex tree:
So we come to the most interesting: TREE (3) = ... - this is an incomprehensibly great number. Probably, a way to determine its scope will never be invented, since it is an order of magnitude higher than human capabilities. Let's see what the beginning of the number looks like:
TREE (3) starts this way and lasts VERY long time.
Abyss: SCG (n)
Mathematicians could not stop at TREE (3) and went further. No, not to TREE (4). The TREE (n) function is weaker than Buchholz hydra and Subcubic Graph Numbers . Subcubic Graph Function - SCG (n) - gives the greatest result.
Here we need to make a small digression: from 1983 to 2004, mathematicians Neil Robertson and Paul D. Seymour in a 500-page study developed the theory that any inherited property of graphs is characterized by a finite number of forbidden subgraphs . The Robertson-Seymour theorem extends these results to arbitrary families of graphs closed by minors. The theorem indicates that the set of toroidal graphshas a finite obstructive set, but does not give any such set. The complete set of forbidden minors for toroidal graphs remains unknown and contains at least 16 thousand graphs.
A simple subcubic graph is a finite simple graph in which each vertex has degree no more than three. Suppose we have a sequence of simple subcubic graphs G1, G2, ... such that every graph G i has at most i + k vertices (for some integer k) and is homeomorphically embeddable in G j .
The Robertson-Seymour theorem proves that subcubic graphs (simple or not) are completely justified by homeomorphic embeddability, implying that such a sequence cannot be infinite. Thus, for each value of k there is a sequence with a maximum length. The SSCG (k) function denotes this length for simple subcubic graphs. The function SCG (k) denotes this length for (common) subcubic graphs.
The SSCG sequence starts with SSCG (0) = 2, SSCG (1) = 5, but then grows rapidly. SSCG (2) = 3 × 23 × 295 - 8 ≈ 103.5775 × 1028.
SSCG (3) is not only larger than TREE (3), it is much larger than TREE (TREE (... TREE (3) ...)), where the total nesting depth of the formula is the TREE (3) level of the TREE function. There is no qualitative difference between the asymptotic growth rates of SSCG and SCG. It is clear that SCG (n) ≥ SSCG (n), but it can also be said that SSCG (4n + 3) ≥ SCG (n).
To infinity and beyond: BIG FOOT and other numbers
Mathematicians are now developing theories that can be used to create the “very-most" number. The "king" of the digital series often changes, but I want to finish today's review with the excellent BIG FOOT. Let it be larger than TREE (3) and SSCG (3) combined, but it is no longer considered the BIGGEST. However, the mechanics of its creation did not lose relevance and is used to study the new greatest numbers.
Before moving on to the legendary Bigfoot, let's get acquainted with Rayo's number theory. The Rayo number is a large number named after the mathematician Agustin Rayo who won the “Big Number Duel” in 2007 with the following definition: “The smallest number greater than any finite number that can be defined by a first-order language expression set theory using less than googol ( 10,100 ) characters. ”
BIG FOOT is an analogue of the Rayo number - its definition is almost identical. BIG FOOT extends first-order set theory using a unique discourse area called oodleverse, using a language called first-orderoodletheory (FOOT), and generalizing n-order set theory to an arbitrarily large n.
Let FOOT (n) denote the largest positive integer uniquely determined in the FOOT language in no more than n characters. BIG FOOT is defined as FOOT 10 (10 100 ), where FOOT a (n) is FOOT (n) (recursion).
BIG FOOT thus equals
FOOT (FOOT (FOOT (FOOT (FOOT (FOOT (FOOT (FOOT (FOOT (FOOT (10 100 )))))))))))
Searches for a finite number continue. Will it ever be found?
Blaise Pascal described the existential horror that grips him at the thought of the infinity of the world: "The eternal silence of this infinite space scares me." Numbers give us the opportunity to establish the framework of understanding and the boundaries of what is permitted, to take control of the fear of uroboros. They are our relict radiation, the ability to approach the metaphorical edge of the world. But just as in space it is impossible to fly to such a place where the sign “the end of the Universe” will hang, so in mathematics it is impossible to reach the last frontier. However, we have yet to verify this.
PS The author is not a professional mathematician and hopes that he did not make gross errors in the article. If you notice an inaccuracy - please report. Comments that extend the material presented are also welcome.
Sources: