We saw in the previous post that almost all countable graphs, in either the sense of probability or that of Baire category, are isomorphic to R. But what. exactly, does R look like?
Before we begin, how are we going to recognise R? Recall from the last post that it is the unique countable graph satisfying the following condition (there called (*)):
If U and V are finite disjoint sets of vertices, then there is a vertex joined to everything in U and to nothing in V.
So, if we construct a countable graph and verify that it has this property, then we have built a copy of R.
Put on your number theory hat for the first description. (I am not sure who came up with this description, but it is my favourite.) In a sense, it relies on the “randomness” of the primes.
According to the Law of Quadratic Reciprocity, proved by Gauss, if p and q are prime numbers congruent to 1 (mod 4), then p is congruent to a square mod q if and only if q is congruent to a square mod p. We take the vertex set P to be the set of all primes congruent to 1 (mod 4), and join two primes if each is congruent to a square modulo the other.
Let U and V be finite disjoint sets of vertices. Choose fixed squares modulo the primes in U, and fixed non-squares modulo the primes in V. We seek z congruent to 1 (mod 4) and satisfying the congruences modulo primes in U and V that we have just specified. Now the Chinese Remainder Theorem guarantees that the simultaneous congruences have a solution, and Dirichlet’s Theorem on primes in arithmetic progression guarantees that there is a prime number satisfying them. So (*) holds.
What do we learn from this construction? In a sense, it makes things more mysterious. We have seen that R has a lot of symmetry (it is homogeneous); but the primes have no obvious symmetry.
Exercise: What happens if we consider instead primes congruent to 3 (mod 4)?
Another construction is set-theoretic in nature. First we note that, by the downward Löwenheim–Skolem theorem, a consistent first-order theory in a countable language has a countable model. (See my second post on mathematics and logic.) In particular, if the Zermelo–Fraenkel axioms (ZFC) for set theory are consistent, then they have a countable model. This gives rise to the Skolem paradox: from ZFC, one can prove the existence of uncountable sets!
We have to be prepared to think of a model of ZFC combinatorially. Such a model consists of a set of elements with a binary relation (which we write as ∈ and call the membership relation) satisfying the axioms. In other words, it is a directed graph! Now the claim is that there is a countable directed graph satifying the translations of ZFC into graph-theoretic terms; but any such directed graph contains a vertex with the property that no vertex “represents” a bijection between this vertex and the vertex representing a standard countable set in the model. (A bijection is a set of ordered pairs; an ordered pair (x,y) is a set {{x},{x,y}}, as explained in any set theory book; all this can be translated into graph-theoretic terms.)
There are many different countable models of ZFC. (On one hand, we know this because there are various additional axioms which are known to be independent. Another way to see this is using the theorem of Engeler, Ryll-Nardzewski and Svenonius discussed in the post on “Mathematics and Logic”. The natural numbers can be defined in a model of set theory; we see that each natural number is fixed by all automorphisms, so the automorphism group has infinitely many orbits and is not oligomorphic.)
From each model we obtain a graph by “symmetrising the membership relation”: that is, join x and y by an edge if either x∈y or y∈x. Now, remarkably, it holds that
the resulting graph is isomorphic to R,
no matter which model we choose.
It is interesting to see why. Given disjoint finite sets U and V, we want a vertex joined to all members of U and none of V. The set U itself almost works. It contains all members of U and none of V; but it might happen that U may be contained in some member of V. To get round this, add V to U. Now, if U were joined to some v∈V, then either
- U∈v∈V∈U; or
- v=V, whence V∈V.
In either case the Axiom of Foundation is contradicted.
The Axiom of Foundation is the axiom that forbids infinite descending chains under the membership relation. One of its functions is to save us from Russell’s Paradox. Of course, it forbids cycles in the membership relation, as in the two bullet points above. In particular, no set can be a member of itself, so “all sets which are not members of themselves” cannot be collected into a set.
From the proof, we see that we need very few of the ZFC axioms: only the very simplest set-building axioms, the Empty Set, Pairing, and Union axioms, and in the final part of the argument the Axiom of Foundation. In particular, the Axiom of Choice is not needed, so symmetrised membership gives the random graph whether or not AC holds in the model.
Authors such as Barwise and Moss, in their book Vicious Circles, have considered set theories in which the Axiom of Foundation fails. Since Foundation is essential for the above proof, I have wondered on occasion what the symmetrised membership relation can look like in anti-foundation models. (In particular, it can have loops, since a set is permitted to be a member of itself.)
Even the Axiom of Infinity is not needed in the proof. So “hereditarily finite set theory”, in which this axiom is denied, also gives R. (This is the theory in which every set is finite, its members are finite, and so on.) Now there is a particularly simple construction of a model for hereditarily finite set theory:
- the “sets” are the natural numbers (including zero);
- a finite set {a,b,…,k} of natural numbers is represented by the number 2^{a}+2^{b}+…+2^{k}.
In other words, x∈y if and only if, when y is written in base 2, the x-th digit is 1.
This gives us perhaps the simplest description of R: take the digraph just defined and symmetrise it. In other words, x is joined to y if and only if, when y is written in base 2, the x-th digit is 1, or vice versa. This was Rado’s description of the graph in 1964.
This gives us a slightly better idea about symmetry. Consider the problem of finding an automorphism of R (in this representation) which interchanges the vertices 0 and 1. Now 2 is joined to 1 but not 0, so we’d like to interchange it with a vertex joined to 0 but not 1; the first such vertex is 1, which is unavailable, so we interchange 2 with the next such vertex 5. Now 3 is joined to both 0 and 1 but neither 2 nor 5, so we can leave it where it is. Then 4=2^{2} can be interchanged with 32=2^{5}, and so on. We see that the automorphism can be constructed recursively, but there seems little hope of finding a formula for it!
That is enough for this lesson, I think. I will leave you with a problem:
Does R admit a cyclic automorphism (permuting all the vertices in a single cycle)?
In the next posting, I will answer this question, and discuss some of the remarkable properties of R.
Sam Tarzi just suggested a nice question about constructions of the random graph.
The constructions given here have the property that, given U and V, the witness z is a recursive function of U and V.
Does there exist a construction of R in which the size of the witness is not bounded by any provably recursive function?
This would presumably give a graph whose isomorphism to R cannot be proved in Peano arithmetic.
Perhaps I’m being overly hasty, but it seems clear to me that we can construct a graph isomorphic to R with a cyclic automorphism:
Basically, we have a graph whose vertices are the integers Z, and whose edge relation E(x, y) must depend only on |x – y|. So let the predicate F be defined by F(x) = E(x,0), it suffices to determine when F(x) is true.
We can define F(x) inductively in stages. At stage 1, let’s arbitrarily say that F(1) is true. Now suppose that F(1), …, F(x_n) have been determined by stage n. Then for all finite disjoint U, V subset {-x_n,…,x_n}, we can ensure that there exists a vertex adjacent to everything in U and nothing in V simply by setting some more values of F(x) for sufficiently large x. E.g. if U = {2, 6} and V = {3, 11} then set F(K – 2) = true, F(K – 6) = true, F(K – 3) = false and F(K – 11) = false, where K is sufficiently large so that the new values don’t conflict with the existing ones.
Now there are only finitely many such pairs (U, V). Having dealt with all of them, we simply ‘fill in the gaps’ in F arbitrarily, and let x_{n+1} be the supremum of values of F(x) that we’ve set so far.
The sequence x_n will be growing very rapidly, but it won’t matter. Every iteration provides all of the ‘witnesses’ necessary for the previous one, and at the end our graph is well-defined on all of Z.
(This trick, in which we close under operations with finitely many arguments simply by repeating those operations omega times, is found frequently in mathematical logic, e.g. in the usual proof of the Löwenheim-Skolem theorem.)
Yes, that works. In fact (see the third post in this series) it is maybe easier just to observe that a function F which is universal (i.e. every finite sequence of zeros and ones occurs as consecutive values of F) gives the random graph. Moreover, since almost all functions are universal (in either the sense of measure or of Baire category), in a suitable sense almost all cyclic graphs are isomorphic to R.
Pingback: The random graph, 1 « Peter Cameron's Blog
Fascinating! Quibble: There’s a typo in the statement of the quadratic reciprocity theorem; “p” and “q” need to be swapped after the “mod”s.
Thanks. now fixed.