Tree decomposition in Budapest

I am spending this week in Budapest in order to participate in the 6th European Set Theory Conference, and I want to take the occasion to present a nice little result of Paul Erdős, one of the great mathematicians of the twentieth century, who was born and spent the first decades of his life in Budapest before spending most of his adult life traveling the world, living and working with a vast network of mathematical collaborators.

Erdős contributed to a huge array of mathematical disciplines, including set theory, my own primary field of specialization and the field from which today’s result is drawn. Like most other Hungarians working in set theory, Erdős’s results in the field have a distinctly combinatorial flavor.

In order to state and prove the result, we need to review a bit of terminology. Recall first that the Continuum Hypothesis is the assertion that the size of the set of all real numbers is \aleph_1, i.e., that there are no sizes of infinity strictly between the sizes of the set of natural numbers and the set of real numbers. As we have discussed, the Continuum Hypothesis is independent of the axioms of set theory.

The Continuum Hypothesis can be shown to be equivalent to a surprisingly diverse collection of other mathematical statements. We will be concerned with one of these statements today, coming from the field of graph theory. If you need a brief review of terminology regarding graphs, visit this previous post.

If Z is a set, then we say that the complete graph on Z is the graph whose vertex set is Z and which contains all possible edges between distinct elements of Z.

The complete graph on 7 vertices.

If G = (V, E) is a graph and k \geq 3 is a natural number, then a k-cycle in G is a sequence of k distinct elements of V, (v_1, v_2, \ldots, v_k), such that \{v_1, v_2\}, \{v_2, v_3\}, \ldots, \{v_{k-1}, v_k\}, \{v_k, v_1\} are all in E.

In this graph, both (A,B,C,D,E,F) and (G,H,I,J,K,L) form 6-cycles. (Image by Blacklemon67)

A graph without any cycles is called a tree. (Note that many sources require a tree to be connected as well as cycle-free and call a cycle-free graph a forest. This leads to the pleasing definition, “A tree is a connected forest.” We will ignore this distinction here, though.)

A complete graph is very far from being a tree: every possible cycle is there. We will be interested in the question: `How many trees does it take to make a complete graph?’

Let us be more precise. An edge-decomposition of a graph G = (V,E) is a disjoint partition of E, i.e., a collection of sets \{E_i \mid i \in I\}, indexed by a set I, such that E_i \cap E_j = \emptyset for distinct elements i,j \in I and \bigcup_{i \in I} E_i = E. An edge-decomposition thus decomposes the graph G = (V,E) into graphs G_i = (V, E_i) for i \in I.

An edge-decomposition of the complete graph on 8 vertices into 4 pieces, indicated by black, blue, green, and red edges, respectively.

We will be interested in the number of pieces required for an edge-decomposition of a complete graph into trees. In the above image, we provide an edge-decomposition of the complete graph on 8 vertices into 4 trees (in fact, into 4 Hamiltonian paths). For an infinite complete graph, though, no finite number of pieces will ever suffice. The question we will be interested in today is the number of pieces necessary to provide an edge-decomposition of the complete graph on the real numbers, \mathbb{R}, into trees.

Theorem. (Erdős-Kakutani and Erdős-Hajnal) The following statements are equivalent:

  1. The Continuum Hypothesis
  2. There is an edge-decomposition of the complete graph on \mathbb{R} into countably many trees.

Proof. Suppose first that the Continuum Hypothesis holds. Then \mathbb{R} can be enumerated as \langle r_\alpha \mid \alpha < \omega_1 \rangle. For all \beta < \omega_1, we know that \beta is countable, so we can fix a function e_\beta:\beta \rightarrow \mathbb{N} that is one-to-one, i.e., if \alpha_0 and \alpha_1 are distinct ordinals less than \beta, then e_\beta(\alpha_0) \neq e_\beta(\alpha_1).

We now specify an edge-decomposition of the complete graph on \mathbb{R} into countably many graphs. The edge-sets of these graphs will be denoted by E_n for n \in \mathbb{N}. To specify this decomposition, it suffices to specify, for each pair \alpha < \beta of countable ordinals, a natural number n_{\alpha, \beta} such that \{r_\alpha, r_\beta\} \in E_{n_{\alpha, \beta}}. And we have a natural way of doing this: simply let n_{\alpha, \beta} = e_\beta(\alpha).

We claim that each E_n is cycle-free. To prove this, suppose for sake of contradiction that k,n \in \mathbb{N} and E_n has a k-cycle. This means there are distinct ordinals \alpha_1, \alpha_2, \ldots, \alpha_k such that \{r_{\alpha_1}, r_{\alpha_2}\}, \{r_{\alpha_2}, r_{\alpha_3}\}, \ldots, \{r_{\alpha_{k-1}}, r_{\alpha_k}\}, \{r_{\alpha_k}, r_{\alpha_1}\} are all in E_n.

Now fix \ell \leq k such that \alpha_\ell is the maximum of the set \{\alpha_1, \ldots, \alpha_k\}. Without loss of generality, let us suppose that 1 < \ell < k (if this is not the case, simply shift the numbering of the cycle). Then we have \{r_{\alpha_{\ell - 1}}, r_{\alpha_\ell}\}, \{r_{\alpha_\ell}, r_{\alpha_{\ell + 1}}\} \in E_n. Since \alpha_\ell > \alpha_{\ell - 1}, \alpha_{\ell + 1}, our definition of E_n implies that e_{\alpha_\ell}(\alpha_{\ell - 1}) = n = e_{\alpha_\ell}(\alpha_{\ell + 1}), contradicting the assumption that e_{\alpha_\ell} is one-to-one and finishing the proof of the implication  1. \Rightarrow 2.

To prove that 2. implies 1., we will actually prove that the negation of 1. implies the negation of 2.. So, suppose that the Continuum Hypothesis fails, i.e., |\mathbb{R}| \geq \aleph_2. Let \langle r_\alpha \mid \alpha < |\mathbb{R}|\rangle be an enumeration of \mathbb{R}, and suppose \langle E_n \mid n \in \mathbb{N} \rangle is an edge-decomposition of the complete graph on \mathbb{R}. This means that, for all pairs of ordinals \alpha < \beta smaller than |\mathbb{R}|, there is a unique natural number n_{\alpha, \beta} such that \{r_\alpha, r_\beta\} \in E_{n_{\alpha, \beta}}. We will prove that there is a natural number n such that E_n contains a 4-cycle.

Let X be the set of ordinals that are bigger than \omega_1 but less than |\mathbb{R}|. Clearly, |X| = |\mathbb{R}| \geq \aleph_2. For each \beta \in X and each n < \omega, let A_{\beta, n} be the set of ordinals \alpha less than \omega_1 such that n_{\alpha, \beta} = n. Then \bigcup_{n \in \mathbb{N}} A_{\beta, n} = \omega_1, so, since \mathbb{N} is countable and \omega_1 is uncountable, there must be some natural number n such that A_{\beta, n} is uncountable. Let n_\beta be such an n.

For n \in \mathbb{N}, let X_n = \{\beta \in X \mid n_\beta = n\}. Then \bigcup_{n \in \mathbb{N}}X_n = X. Since |X| \geq \aleph_2, this means that there must be some natural number n^* such that |X_{n^*}| \geq \aleph_2.

Now, for each \beta \in X_{n^*}, let \alpha_{\beta, 0} and \alpha_{\beta, 1} be the least two elements of A_{\beta, n^*}. Since there are only \aleph_1 different choices for \alpha_{\beta, 0} and \alpha_{\beta, 1}, and since |X_{n^*}| \geq \aleph_2, it follows that we can find \beta_0 < \beta_1 in X_{n^*} and \alpha_0 < \alpha_1 < \omega_1 such that \alpha_{\beta_0, 0} = \alpha_0 = \alpha_{\beta_1, 0} and \alpha_{\beta_0, 1} = \alpha_1 = \alpha_{\beta_1, 1}. It follows that \{r_{\alpha_0}, r_{\beta_0}\}, \{r_{\beta_0}, r_{\alpha_1}\}, \{r_{\alpha_1}, r_{\beta_1}\}, \{r_{\beta_1}, r_{\alpha_0}\} \in E_{n^*}. In other words, (r_{\alpha_0}, r_{\beta_1}, r_{\alpha_1}, r_{\beta_1}) forms a 4-cycle in E_{n^*}. This completes the proof of the Theorem.

Notes: The proofs given here do not exactly match those given by Erdős and collaborators; rather, they are simplifications made possible by the increased sophistication in dealing with ordinals and cardinals that has been developed by set theorists over the previous decades. The implication from 1. to 2. is due to Erdős and Kakutani and can be found in this paper from 1943. The implication from 2. to 1. was stated as an unsolved problem in the Erdős-Kakutani paper. It was proven (in a much more general context) in a landmark paper by Erdős and Hajnal from 1966.


Trying to make sense of it doesn’t make sense.

-Last Year at Marienbad

A spa town in the Czech Republic, Marienbad was a favored vacation spot of European royalty and celebrities during the 19th and early 20th centuries. Some mathematicians came, too: Karl Weierstrass, Gösta Mittag-Leffler, and Sofia Kovalevskaya were all drawn by the combination of the restful atmosphere and sparkling social life that could be found at the spa.

Though its golden era ended in the early 20th century, Marienbad remained popular between the world wars. Among the visitors during that time was a young Kurt Gödel. According to some accounts, Gödel’s interest in the sciences was kindled by a teenage visit to Marienbad, during which he and his brother studied Goethe’s philosophical theory of color and found it lacking in comparison to Newton’s more strictly scientific account.

After the war we were in Marienbad quite often with my brother, and I remember that we once read Chamberlain’s biography of Goethe together. At several points, he took a special interest in Goethe’s theory of color, which also served as a source of his interest in the natural sciences. In any case, he preferred Newton’s analysis of the color spectrum to Goethe’s.

-Rudolf Gödel

Goethe himself was a frequent visitor to Marienbad. During an 1823 trip, the 73-year-old Goethe became infatuated with the 18-year-old Baroness Ulrike von Levetzow. The pain caused by her rejection of his marriage proposal led him to write the famous Marienbad Elegy (updated in 1999 by the great W.G. Sebald).

…who dance, stroll up and down, and swim in the pool, as if this were a summer resort like Los Teques or Marienbad.

-Adolfo Bioy Casares, The Invention of Morel

In 1961, Last Year at Marienbad was released. Directed by Alain Resnais and written by Alain Robbe-Grillet, the film is as beautiful as it is inexplicable. On its face, the film is set at a resort hotel; an unnamed man (‘X’) becomes infatuated with an unnamed woman (‘A’) and attempts to convince her that they had an affair the previous year. The film unfolds in combinatorial play, with narration and scenes repeated in ever-evolving and bewildering variation.

A popular theory is that Last Year at Marienbad is actually an adaptation of Adolfo Bioy Casares’ The Invention of Morel, a novel of which our friend Jorge Luis Borges wrote, “To classify it as perfect is neither an imprecision nor a hyperbole.” I will not say much about this, so as not to spoil the book (you should go read it right now), but will only mention that Morel was, in a way, an homage to Louise Brooks, a Hollywood actress with whom Casares was somewhat obsessed and whose performance in Pandora’s Box provided a model for Delphine Seyrig’s performance as ‘A’ in Marienbad. The idea that there is a direct line from Casares and Brooks to the main characters in Morel to ‘X’ and ‘A’ in Marienbad, and that the obscurities of both novel and film are at heart simply odes to the power of cinema is an appealing one.

This theory about the connection between Marienbad and Morel was never acknowledged by the filmmakers (some say that the source text for the film is not Casares’ novel, but rather Wittgenstein’s Philosophical Investigations). Perhaps its fullest explication is given by this article in Senses of Cinema, in which the only sources given by the author are the dust jacket of a different Casares work and an Encyclopedia Britannica article which has since been removed from the online archives. Regardless of the theory’s truth, though, when one views the film through the lens of Morel, it comes tantalizingly close to making sense; the characters of the film lose their agency, consigned to repeating their roles ad infinitum.

At first sight, it seemed impossible to lose your way. At first sight…

Last Year at Marienbad

The third main character in Marienbad is ‘M’, a man who may or may not be the husband of ‘A’. Throughout the film, we see ‘M’ playing a version of the mathematical game of Nim with ‘X’.

This version of Nim became known by the name “Marienbad” and was a brief craze in certain circles. It even got written about in Time:

Last week the Marienbad game was popping up at cocktail parties (with colored toothpicks), on commuter trains (with paper matches), in offices (paper clips) and in bars (with swizzle sticks). Only two can play, but any number can kibitz — and everyone, it seems, has a system for duplicating “X’s” talent for winning.

-“Games: Two on a Match,” Time, Mar. 23, 1962

The game is a theoretical win for the second player, although, as it is unlikely that a player will stumble upon the winning strategy by accident, ‘X’ is able to win even as the first player. We will return to general winning strategies for Nim and other games in later posts.

-The one who starts, wins.

-You must take an even number.

-You must take the smallest odd number.

-It’s a logarithmic series.

-You must switch rows as you go.

-And divide by three.

-Seven times seven is forty-nine.

-kibitzers in Last Year at Marienbad

I leave you now with Nick Cave’s exquisite “Girl in Amber.” Another secret adaptation of The Invention of Morel? Possible…

Cantor and the Absolute (Universal Structures IV)

As long-time readers of this blog will know, the mathematical discipline of set theory, and with it the modern mathematical investigation of infinity, was almost single-handedly initiated by Georg Cantor, a mathematical giant of the late 19th century. Among the factors contributing to Cantor’s revolutionary achievements was his willingness to work with actual infinities, to consider infinite sets as completed entities that can be manipulated as mathematical objects in their own right. Two of the foundational ideas made possible by Cantor’s acceptance of actual infinity are:

  • the existence of multiple infinite cardinalities;
  • the concept of transfinite ordinal numbers.

It was realized quite early in the development of set theory, though, that a naïve conception of infinity and sets would lead to paradoxes. (Indeed, the existence of these paradoxes is one of the reasons for the reluctance of mathematicians to accept actual infinities and provided fodder for Cantor’s mathematical enemies.) Two of the most consequential of these paradoxes are Russell’s Paradox and the Burali-Forti Paradox.

Russell’s Paradox: Essentially, Russell’s Paradox asserts that there can be no set of all sets. For suppose that such a set exists (call it S). Then, by any reasonable formulation of set theory, we could form the set of all sets that do not contain themselves. Formally, this set, which we will call R, would be \{x \in S \mid x \not\in x\}. Now comes the crucial question: can R be a member of itself? Either answer leads to contradiction: if R \in R, then  R \not\in R, and if R \not\in R, then R \in R. Thus, there can be no set of all sets.

Burali-Forti Paradox: The Burali-Forti Paradox goes even further than Russell’s Paradox: not only can the set of all sets not exist, but the set of all ordinal numbers cannot exist either. For suppose that T is the set of all ordinal numbers. Recall that an ordinal number is, essentially, the order type of a well-ordered set. Recall also that the class of ordinal numbers is well-ordered: any set of ordinals has a least element. But this implies that T itself is a well-ordered set, but, since T contains all of the ordinals, its order type must be larger than all the ordinals numbers. This is a contradiction.

The collection of all sets and the collection of all ordinal numbers are therefore not sets. But it seems that we are nonetheless able to conceive of them, to reason about them. They seem to have some form of reality. So what are they?

The standard response in modern set theory is simply to say that these collections are what is known as proper classes. They are collections that are “too large” to be sets, that are “too large” to be manipulated in ways that sets are manipulated. This has served us well, to this point banishing paradox from the subject. Cantor’s response was similar but was imbued with something more. Consider this excerpt from a letter sent by Cantor to the English mathematician Grace Chisholm Young:

I have never assumed a “Genus Supremum” of the actual infinite. Quite on the contrary I have proved that there can be no such “Genus Supremum” of the actual infinite. What lies beyond all that is finite and transfinite is not a “Genus”; it is the unique, completely individual unity, in which everything is, which comprises everything, the ‘Absolute’, for human intelligence unfathomable, also that not subject to mathematics, unmeasurable, the “ens simplicissimum”, the “Actus purissimus”, which is by many called “God”.

For Cantor, infinity comes in not two but three varieties: the potential infinity of limits, sequences, and series; the transfinite infinity of the infinite cardinal and ordinal numbers; and the absolute infinity, which transcends mathematics and human comprehension, and which is identified with God.

Much has been made of the possibility that Georg Cantor’s family had Jewish roots and that Cantor’s conceptions of infinity and mathematical philosophy were influenced by Jewish mysticism and Kabbalah. On the former issue we will just say that there is evidence, from correspondence and genealogical records, pointing in both directions. On the latter, we will simply note that Cantor’s choice to denote infinite cardinals was ‘aleph’ (ℵ), the first letter of the Hebrew alphabet and a letter of importance in Kabbalah as the opening of the words Ein Sof (infinity, roughly) and Elohim (a name for God).

Also, here’s a little-known fact: the symbol that Cantor used to denote the class of all cardinal numbers (too big to be a set, of course) is ‘tav’ (ת), the last letter in the Hebrew alphabet and the representative, in Kabbalah, of perfection, of the synthesis of all that exists.

Another fascinating intersection between Cantor’s set theory and theology involves the Catholic Church. Long-time readers may recall that, the last time the Church appeared in our story, the mathematician involved was Galileo, and the relationship between the two could be described, at the risk of understatement, as antagonistic.

250 years later, the relationship between the Catholic Church and the day’s leading provocateur of the infinite would turn out decidedly differently. This was due in large part to Pope Leo XIII, who assumed the position in 1878 and, the following year, issued the encyclical Aeterni Patris. The encyclical called for the revival of the Scholastic philosophy of Thomas Aquinas. It sought to modernize the Church and to increase its interest and participation in scientific inquiry.

For, the investigation of facts and the contemplation of nature is not alone sufficient for their profitable exercise and advance; but, when facts have been established, it is necessary to rise and apply ourselves to the study of the nature of corporeal things, to inquire into the laws which govern them and the principles whence their order and varied unity and mutual attraction in diversity arise. To such investigations it is wonderful what force and light and aid the Scholastic philosophy, if judiciously taught, would bring.

-Leo XIII, Aeterni Patris

Neo-Scholastic scholars thus gained prominence in the Church, and the Church began engaging more with the cutting-edge scientific work of the day. Cantor’s brand new ideas about infinity were naturally of interest. Cantor, with religious tendencies of his own and upset by the skeptical or hostile reactions of most of his fellow mathematicians to his work, was himself eager to explain his ideas to the Church and ensure that they were properly understood. And thus began the remarkable correspondence between Cantor and the leading Catholic scholars and clergy of the day.

In any case it is necessary to undertake a serious examination of the latter question concerning the truth of the Transfinitum, for were I correct in asserting its truth in terms of the possibility of the Transfinitum, then there would be (without doubt) a certain danger of religious error for those of the opposite opinion, since: error circa creaturas redundat in falsam de Deo scientiam.

-letter from Cantor to Jeiler von Pfingsten, 1888

One of the issues that arose in Cantor’s correspondence with the Church involved the fundamental existence of Cantor’s transfinite numbers. (Note that I am in no way a theological scholar, so this account is probably grossly oversimplified.) A number of Catholic intellectuals were hesitant to accept the objective existence of Cantor’s transfinite numbers on the grounds that, as God is often theologically identified with the infinite, the acceptance of the existence of transfinite numbers would lead inevitably to Pantheism, a doctrine which was not only implicity but explicitly (by Pius IX in 1861) condemned by the Church. Cantor responded by emphasizing his distinction between the absolute infinity and the transfinite infinity, between an “Infinitum aeternum increatum sive Absolutum” and an “Infinitum creatum sive Transfinitum.” The former is reserved for God; the latter manifests itself in mathematics and in the universe.

The neo-Scholastic thinkers were largely convinced by Cantor’s distinction and came to accept many of his ideas about infinity. Cantor himself took great pride in this achievement, even going so far as, in a moment of mathematical self-doubt engendered by his inability to solve the Continuum Problem, to express the following remarkable sentiment in an 1894 letter to the French mathematician Charles Hermite:

Now I only thank God, the all-wise and all-good, that he always denied me the fulfillment of this wish [for a position at University in either Göttingen or Berlin], for He thereby constrained me, through a deeper penetration into theology, to serve Him and His Holy Roman Catholic Church better than I would have been able to with my probably weak mathematical powers through an exclusive occupation with mathematics.

P.S.: Cantorian set theory recently made a surprise appearance in the New York Times crossword puzzle:


Rex Parker was not happy!

Acknowledgement: The material about Cantor’s correspondence with the Catholic Church came largely from Joseph W. Dauben’s excellent paper, “Georg Cantor and Pope Leo XIII: Mathematics, Theology, and the Infinite.”

Cover Image: Harald Sohlberg, “Winter Night in the Mountains,” 1901. Nasjonalgalleriet, Oslo.

Surreal Numbers (Universal Structures III)

“You get surreal numbers by playing games. I used to feel guilty in Cambridge that I spent all day playing games, while I was supposed to be doing mathematics. Then, when I discovered surreal numbers, I realized that playing games IS mathematics.”

-John Horton Conway

First issue of VVV, published by David Hare in collaboration with Marcel Duchamp, André Breton, and Max Ernst
“Julius Caesar,” by Man Ray
“Untitled,” by Joseph Cornell
“Las Meninas,” by Salvador Dali, after Diego Velasquez
“The Evil Genius of a King,” by Giorgio de Chirico
“Imaginary Numbers,” by Yves Tanguy
“Untitled,” by Joan Miró
“Möbius Strip II,” by M.C. Escher
“The Surrealist,” by Victor Brauner
“The Pleasure Principle (Portrait of Edward James),” by René Magritte

The Random Graph (Universal Structures II)

In our previous post, we provided a literary prologue to the study of universal structures, objects that, in a sense, “contain” all other objects of the same type. Today, we return to the world of mathematics to look at a fascinating concrete example of such a universal structure.

The mathematical objects we will be working with are graphs, which we briefly introduced in our Ultrafilters series. Recall that a graph is a set of vertices and a set of edges, where each edge connects two distinct vertices. For example:


A graph G is often represented as a pair (V,E), where V is the set of vertices and E is the set of edges. An edge is represented by a set containing the two vertices it connects. If G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are two graphs, then we say that G_1 embeds into G_2 if there is a function f:V_1 \rightarrow V_2 such that:

  • for all u,v \in V_1, if u \neq v, then f(u) \neq f(v);
  • for all u,v \in V_1, if \{u,v\} \in E_1, then \{f(u), f(v)\} \in E_2;
  • for all u,v \in V_1, if \{f(u), f(v)\} \in E_2, then \{u,v\} \in E_1;

One can think of the statement “G_1 embeds into G_2” as saying that “G_2 contains a copy of G_1.” To really understand this idea, try the following exercise.

Exercise: Every graph with three vertices embeds into the graph pictured above.

In light of this exercise, we might be tempted to say that the graph we have drawn above is universal for graphs with three vertices. However, we are cheating a little bit, since our graph has more than three vertices itself. We would really like for a universal object to itself be a member of the class for which it is universal; otherwise, finding universal objects is too easy! A bit of thought should convince you that, with this more stringent definition of “universal,” no graph that is universal for a meaningful class of graphs can be finite (the word “meaningful” here is just meant to rule out whatever trivial examples you can think of).

We therefore will waste no time trying to find finite universal graphs and will instead move on to the next step: graphs with a countable infinity of vertices. And here we will succeed: we will find a graph G with countably many vertices such that, for every graph H with countably many vertices, H embeds into G. What’s more, we will succeed with a wonderfully interesting graph: the random graph.

One commonly cited criterion for an idea or an object to possess mathematical beauty is that it arise independently in a variety of different contexts, in a variety of guises that are only revealed to be identical upon close inspection. By this accounting, I would say that the random graph is quite beautiful indeed. Let us give just a few descriptions of this graph.

1: Hereditarily finite setsFor a set x, the transitive closure of x is, roughly, the set consisting of all elements of x, all elements of elements of x, all elements of elements of elements of x, and so on. It is quite possible that a set x is finite but its transitive closure is infinite (consider, for example, the set whose one element is the set of all natural numbers). A set is called hereditarily finite if its transitive closure is finite. Assuming that all sets are built up from the empty set, one can prove that there are only countably many hereditarily finite sets. Moreover, if n is a natural numbers and x_1, x_2, \ldots, x_n are hereditarily finite sets, then \{x_1, x_2, \ldots, x_n\} is a hereditarily finite set. Now form a graph G = (V,E) by letting V be the set of all hereditarily finite sets and, for all x,y \in V, letting \{x,y\} \in E if and only if either x \in y or y \in x.

2: Binary expansion. We typically write natural numbers in base 10, or decimal, notation, but one could just as well write them in base 2, or binary, notation, using only 0s and 1s. I will assume the reader is at least passingly familiar with this. As a brief refresher, recall that, in binary notation, 1 is 1, 2 is 10, 3 is 11, 4 is 100, 5 is 101, and so on. We define a graph G = (V,E) such that V is the set of natural numbers. If m < n are natural numbers, then we put an edge between m and n if and only if the m^{\mathrm{th}} digit (from the right, starting with 0) in the binary expansion of n is 1. For example, the number 10 in binary is 1010. Therefore, there is no edge between 0 and 10 or 2 and 10 but there is an edge between 1 and 10 and between 3 and 10. If 4 \leq m < 10, then there is no edge between m and 10 because the binary expansion of 10 only has 4 digits.

The first nine vertices of the binary expansion graph. Illustration by David Eppstein.

3: Coin flipping. We will define a graph G = (V,E) probabilistically, where V is the set of natural numbers. For each pair of natural numbers m < n, we will flip a fair coin. If the coin lands heads, we put an edge between m and n. If it lands tails, we do not put an edge between m and n.

4: Quadratic residues. If p and q are natural numbers, we say that p is a quadratic residue modulo q if there is a natural number x such that x^2 - p is divisible by q. We define a graph G = (V,E) such that V is the set of all prime numbers that leave a remainder of 1 when divided by 4. It is an elementary fact of number theory that there are infinitely many such prime numbers. If p < q are two elements of V, then we put an edge between p and q if and only if p is a quadratic residue modulo q or q is a quadratic residue modulo p.

5: Fraïssé limit. Let G be the Fraïssé limit of the class of finite graphs. I am not going to explain this further; I just wanted to use the phrase “Fraïssé limit.”

One of the almost miraculous aspects of our story is that all five of these graphs are the same, and we shall refer to all of them as “the random graph.” Before we go any further, though, I should explain what I mean by “the same,” since these graphs are not literally “the same” (some of them don’t even have the same sets of vertices). By “the same” we mean isomorphic, or “structurally the same,” in the way in which we would say that any two graphs with three vertices and edges between all three vertices are “the same.” More precisely, if G_1 = (V_1, E_1) and G_2 = (V_2, E_2) we say that G_1 and G_2 are “the same” (or isomorphic) if there is a one-to-one correspondence (i.e., a bijection) f:V_1 \rightarrow V_2 such that, for all x,y \in V_1, we have \{x,y\} \in E_1 if and only if \{f(x), f(y)\} \in E_2. The point is that the way in which we label the vertices of a graph is immaterial to the actual structural properties of the graph, which are what we care about.

Now, how can we show that all of these graphs are the same? We show that all of the graphs have a very special property, and that all countable graphs with this property are isomorphic. This property is called the extension property.

Definition: A graph G = (V,E) satisfies the extension property if, for all finite subsets U_1, U_2 \subseteq V with U_1 \cap U_2 = \emptyset, there is a vertex v \in V such that:

  • v \not\in U_1 \cup U_2;
  • for all u \in U_1, we have \{u,v\} \in E;
  • for all u \in U_2, we have \{u,v\} \not\in E.

I will leave the verification that all five of our graphs have the extension property as an exercise. For graphs 1 and 2, this is pretty easy. For graph 3, since the definition of the graph is probabilistic, it is conceivable (just ask Rosencrantz and Guildenstern) that every coin flip somehow comes up heads, in which case the graph would obviously not satisfy the extension property. However, the graph will satisfy the extension property with probability 1, so we can be almost sure. The fact that graph 4 satisfies the extension property follows from the Chinese Remainder Theorem and Dirichlet’s theorem about primes in arithmetic progressions, two somewhat non-trivial theorems from number theory.

Theorem: Suppose G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are two countably infinite graphs with the extension property. Then G_1 and G_2 are isomorphic.

Proof sketch: Since G_1 and G_2 are countable, we can enumerate V_1 as \{u_0, u_1, u_2, \ldots \} and V_2 as \{v_0, v_1, v_2, \ldots \}. We will construct an isomorphism f:V_1 \rightarrow V_2 in infinitely many steps by defining f on more and more elements of V_1.

Suppose n is a natural number. We now describe Step n of the construction. Assume that we have already defined f on finitely many elements of V_1 in such a way that f is thus far an isomorphism, i.e., for all pairs u \neq v on which f is thus far defined, we have f(u) \neq f(v) and \{u,v\} \in E_1 if and only if \{f(u), f(v)\} \in E_2. Suppose moreover that, for all m < n, f is defined on u_m and there is u \in V_1 such that f is defined on u and f(u) = v_m.

We now extend f so that it is defined on u_n. If it happens to be the case that it is already defined on u_n, then we have nothing to do. Otherwise, let U be the set of vertices on which f is thus far defined. Let U_1 be the set of vertices in U to which u_n is connected by an edge, and let U_2 be the set of vertices in U to which u_n is not connected. Let W_1 = \{f(u) \mid u \in U_1\} and W_2 = \{f(u) \mid u \in U_2\}. Since G_2 satisfies the extension property, we can find v \in V_2 such that:

  • v \not\in W_1 \cup W_2;
  • for all w \in W_1, we have \{w,v\} \in E_2;
  • for all w \in W_2, we have \{w,v\} \not\in E_2.

Let f(u_n) = v. Next, we extend f so that v_n is in its image. If there is already u \in V_1 such that f(u) = v_n, then there is nothing to do. Otherwise, let W be the set of w \in V_2 such that, for some u \in V_1, we have f(u) = w. Let W_1 = \{w \in W \mid \{v_n, w\} \in E\} and W_2 = \{w \in W \mid \{v_n, w\} \not\in E\}. Let U_1 = \{u \in V_1 \mid f(u) \in W_1\} and U_2 = \{u \in V_1 \mid f(u) \in W_2\}. Since G_1 satisfies the extension property, we can find u \in V_1 such that:

  • u \not\in U_1 \cup U_2;
  • for all v \in U_1, we have \{u,v\} \in E_1;
  • for all v \in U_2, we have \{u,v\} \not\in E_1.

Let f(u) = v_n. This completes Step n of the construction. Continuing through all of the steps, one for each natural number, we find that we have constructed a full isomorphism from G_1 to G_2, thus completing the proof of the theorem.

The theorem shows that we are justified in referring to the random graph rather than random graph. Up to isomorphism (and with probability 1), all of the graphs we have called “the random graph” are the same! Essentially the same proof as that given above shows that every countable graph embeds into the random graph (Exercise: Do it!). Thus, the random graph can truly be said to be universal for the class of countable graphs.

P.S. To what extent do these ideas generalize to higher infinities? Assuming some assumptions about cardinal arithmetic, they generalize quite straightforwardly. If \kappa is an infinite cardinal and \kappa^{<\kappa} = \kappa, then it is meaningful to talk about the “random graph of size \kappa,” and this graph will be universal for graphs of size \kappa. However, the assumption \kappa^{<\kappa} = \kappa is not necessarily true for uncountable cardinals. In fact, it is consistent with the axioms of set theory that there are no universal graphs of size \aleph_1. The question of the existence of universal graphs becomes especially interesting at cardinals of the form \mu^+, where \mu is a singular cardinal; much work has been done even in the last few years on this topic.

The Simurgh (Universal Structures I)

To see a World in a Grain of Sand
And a Heaven in a Wild Flower
Hold Infinity in the palm of your hand
And Eternity in an hour

-William Blake, “Auguries of Innocence”

In Persian mythology, the Simurgh is a bird that lives in the mountains of Alborz. Sometimes she has the head or body of a dog, sometimes of a human. She has witnessed the destruction of the world three times. The wind of her beating wings is responsible for scattering seeds from the Tree of Life, creating all plants in the world.

The Simurgh is, in some tellings, the archetype of all birds. Her name resembles the Persian phrase si murg, meaning “thirty birds.”

In The Conference of the Birds, Farid ud-Din Attar’s 12th-century masterpiece, the birds of the world undertake a journey to find the Simurgh. And they succeed.

Their life came from that close, insistent sun
And in its vivid rays they shone as one.
There in the Simorgh’s radiant face they saw
Themselves, the Simorgh of the world – with awe
They gazed, and dared at last to comprehend
They were the Simorgh and the journey’s end.
They see the Simorgh – at themselves they stare,
And see a second Simorgh standing there;
They look at both and see the two are one,
That this is that, that this, the goal is won.

-Farid ud-Din Attar, The Conference of the Birds

The Simurgh is a bird that contains all birds. She is a universal bird.

Unsurprisingly, the Simurgh shows up a number of times in the works of Jorge Luis Borges, in both his short stories and his essays. One reference appears in the masterful story, “The Aleph,” a particularly rich and dense work which you should certainly read for yourself.

“The Aleph” is partly about how we create our own worlds, how we approximate the unknowable universe within our lives and our art. The narrator of the story, also named Borges, grieving the loss of his beloved Beatriz, pays repeated visits to the home of her father and her cousin, the poet Carlos Argentino Daneri. On one of these visits, Carlos Argentino takes Borges to his basement to show him the source of his poetry, the titular Aleph, a single point that contains the universe.

On the back part of the step, toward the right, I saw a small iridescent sphere of almost unbearable brilliance. At first I thought it was revolving; then I realised that this movement was an illusion created by the dizzying world it bounded. The Aleph’s diameter was probably little more than an inch, but all space was there, actual and undiminished. Each thing (a mirror’s face, let us say) was infinite things, since I distinctly saw it from every angle of the universe. I saw the teeming sea; I saw daybreak and nightfall; I saw the multitudes of America; I saw a silvery cobweb in the center of a black pyramid; I saw a splintered labyrinth (it was London); I saw, close up, unending eyes watching themselves in me as in a mirror; I saw all the mirrors on earth and none of them reflected me; I saw in a backyard of Soler Street the same tiles that thirty years before I’d seen in the entrance of a house in Fray Bentos; I saw bunches of grapes, snow, tobacco, lodes of metal, steam; I saw convex equatorial deserts and each one of their grains of sand; I saw a woman in Inverness whom I shall never forget; I saw her tangled hair, her tall figure, I saw the cancer in her breast; I saw a ring of baked mud in a sidewalk, where before there had been a tree; I saw a summer house in Adrogué and a copy of the first English translation of Pliny — Philemon Holland’s — and all at the same time saw each letter on each page (as a boy, I used to marvel that the letters in a closed book did not get scrambled and lost overnight); I saw a sunset in Querétaro that seemed to reflect the colour of a rose in Bengal; I saw my empty bedroom; I saw in a closet in Alkmaar a terrestrial globe between two mirrors that multiplied it endlessly; I saw horses with flowing manes on a shore of the Caspian Sea at dawn; I saw the delicate bone structure of a hand; I saw the survivors of a battle sending out picture postcards; I saw in a showcase in Mirzapur a pack of Spanish playing cards; I saw the slanting shadows of ferns on a greenhouse floor; I saw tigers, pistons, bison, tides, and armies; I saw all the ants on the planet; I saw a Persian astrolabe; I saw in the drawer of a writing table (and the handwriting made me tremble) unbelievable, obscene, detailed letters, which Beatriz had written to Carlos Argentino; I saw a monument I worshipped in the Chacarita cemetery; I saw the rotted dust and bones that had once deliciously been Beatriz Viterbo; I saw the circulation of my own dark blood; I saw the coupling of love and the modification of death; I saw the Aleph from every point and angle, and in the Aleph I saw the earth and in the earth the Aleph and in the Aleph the earth; I saw my own face and my own bowels; I saw your face; and I felt dizzy and wept, for my eyes had seen that secret and conjectured object whose name is common to all men but which no man has looked upon — the unimaginable universe.

-Jorge Luis Borges, “The Aleph”

Aleph (\aleph) is of course the letter chosen by Georg Cantor to represent transfinite cardinals and the first letter of the Hebrew alphabet. It plays a special role in Kabbalah as the first letter in “Ein Sof,” roughly translated as “infinity,” and in “Elohim,” one of the names of the Hebrew god. We will surely return to these matters.

This is the first installment in a mini-series on what we will call “universal structures,” objects that contain all other objects of their type. We will continue to look at examples from literature and religion, and will delve into the existence of universal structures in mathematics, a topic which continues to drive cutting-edge research to this day. Next week, we will look at a particular universal structure in mathematics, the wonderfully named “random graph.” I hope you will join us.

An Infinitude of Proofs, Part 1

In our previous post, we gave three elementary number-theoretic proofs of the infinitude of the prime numbers. Today, in an unforgivably delayed second installment, we provide two proofs using machinery from more distant fields of mathematics: analysis and topology.

A small word of warning: today’s proofs, though not difficult, require a bit more mathematical sophistication than those of the previous post. The first proof will involve some manipulation of infinite sums, and the second proof uses rudiments of topology, which we introduced here.

Without further ado, let us begin. Our first proof today dates to the 18th century and is due to the prolific Leonhard Euler, of whom Pierre-Simon Laplace, an exceptional mathematician in his own right, once said, “Read Euler, read Euler, he is the master of us all.”

Proof Four (Euler): Suppose there are only finitely many prime numbers, \{p_1, p_2, \ldots, p_n\}. For each prime number p, consider the infinite series \sum_{i = 0}^\infty \frac{1}{p^i} = 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots . As you probably learned in a precalculus class, the value of this infinite sum is precisely \frac{1}{1-\frac{1}{p}}.

Now recall that every natural number greater than 1 can be written in a unique way as a product of prime numbers. Since \{p_1, \ldots, p_n\} are all of the primes, this means that, for each natural number m \geq 1, we can express \frac{1}{m} as \frac{1}{p_1^{s_1}} \cdot \frac{1}{p_2^{s_2}} \cdot \ldots \cdot \frac{1}{p_n^{s_n}} for some natural numbers s_1, s_2, \ldots, s_n. Moreover, it is clear that this gives a one-to-one correspondence between natural numbers m \geq 1 and the corresponding n-tuples of natural numbers, \langle s_1, s_2, \ldots, s_n \rangle. Putting this all together, we obtain the following remarkable formula:

\sum_{m=1}^\infty \frac{1}{m} = \prod_{k=1}^n \frac{1}{1-\frac{1}{p_k}}.

The sum on the left hand of this equation is the famous harmonic series, and it is well-known and easily verified that this sum diverges to infinity. On the other hand, the product on the right hand is a finite product of finite numbers and is therefore finite! This gives a contradiction and concludes the proof.

Our next proof was published in 1955 by a young Hillel Furstenburg, who is still active at the Einstein Institute of Mathematics here in Jerusalem.

Proof Five (Furstenberg): For all integers a and b, let U_{a,b} be the set \{a + bk \mid k \in \mathbb{Z} \}, i.e., U_{a,b} contains a and all integers that differ from a by a multiple of b.

Claim: For all pairs of integers (a_0, b_0) and (a_1, b_1), either U_{a_0,b_0} \cap U_{a_1, b_1} = \emptyset or there are a_2, b_2 such that U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}.

Proof of Claim: If U_{a_0, b_0} \cap U_{a_1, b_1} \neq \emptyset, then let a_2 be any element of the intersection, and let b_2 be the least common multiple of b_0 and b_1. It is easily verified that U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}, thus finishing the proof of the claim.

It now follows that we can define a topology on \mathbb{Z} by declaring that a set U \subseteq \mathbb{Z} is open if and only if U = \emptyset or U is a union of sets of the form U_{a,b}. In particular, for each prime number p, the set U_{0,p}, which is the set of all multiples of p, is open. However, U_{0,p} is also closed, since it is the complement of the set \bigcup_{0 < a < p} U_{a,p}, which is an open set.

Now suppose that there are only finitely many prime numbers, \{p_1, \ldots, p_n\}. Since each set U_{0,p_k} is closed and a finite union of closed sets is closed, we have that \bigcup_{k = 1}^n U_{0,p_k} is a closed set. Notice that every integer that is not 1 or -1 is a multiple of some prime number, so \bigcup_{k = 1}^n U_{0,p_k} is precisely the set of all integers except 1 and -1. Since it is closed, its complement, which is \{-1,1\}, is open. But every non-empty open set is a union of sets of the form U_{a,b}, each of which is clearly infinite, so there can be no finite non-empty open sets. This is a contradiction and concludes the proof.

Cover Image: Passio Musicae by Eila Hiltunen, a monument to Jean Sibelius in Helsinki, Finland. Photograph by the author.