The random graph and anti-foundation

Last year, Bea Adam-Day, one of my undergraduate project students, settled a question that had been bugging me for years.

According to the downward Löwenheim–Skolem Theorem of first-order logic (a consequence of the proof of Gödel’s Completeness Theorem), if a first-order theory in a countable language is consistent, then it has a countable model. This means, for example, that if I am interested in permutation groups of infinite degree which have specified numbers of orbits on n-tuples from the domain, or on n-element subsets of the domain, for some or all natural numbers n, then I can restrict my attention to countable groups acting on countable sets, and I don’t have to perplex myself with the mysteries of uncountable sets. (This is because the group axioms, the axioms for a group action, and the statement that in a given action a group has a given finite number of orbits can all be expressed as first-order sentences.)

However, there is a well-known puzzle arising from this theorem, the Skolem paradox. If, as mathematicians hope and most of us believe, the Zermelo–Fraenkel axioms for set theory are consistent (since they form the most common foundation for mathematics), then they have a countable model. How can this be reconciled with Cantor’s theorem (a consequence of ZF) stating that there exist uncountable sets?

This paradox makes one think more carefully about what a model of set theory is, and what uncountability means. A set is uncountable if there is no bijection between it and the set of natural numbers (or any of its initial subsets). A bijection is a special type of function, and a function is a set of ordered pairs with certain properties; an ordered pair is a particular kind of set. (Most usually, the ordered pair (x,y) is defined to be the set {{x},{x,y}}; the precise construction is not important provided it has the property that (x,y) = (u,v) if and only if x = u and y = v.) Moreover, the natural numbers comprise a particular set in the model, constructed in a certain way. Thus, Cantor’s theorem states the existence of a set U for which there does not exist a set of ordered pairs, with first elements in U and second elements in the set of natural numbers, satisfying the conditions to be a bijection.

Informally, we say that an observer outside the model, looking in, will see that U has countably many members, even though there is no set in the model to witness this countability. The resolution of the paradoxes I described here is similar; the collections defined do not constitute sets in the model.

Anyway, this post is not about the Skolem paradox. I went through this to get across the point that the ZF axioms are stated in terms of the membership relation on sets. In other words, a model of ZF is a directed graph, whose vertices are things called “sets”, with a directed edge from x to y if and only if xy. Thus, a countable model is just a countable directed graph, and can be considered from the point of view of graph theory.

One of the most remarkable facts about this is this. For any directed graph, we can form an undirected graph by simply forgetting the directions, replacing an arc xy by an edge {x,y}. If we do this for a countable model of ZF, we obtain the countable random graph! [In other words, Zermelo–Fraenkel set theory is the first-order theory of certain orientations of the random graph.]

I will sketch the argument. How do we recognise the random graph? As I have described in other posts, R is characterised by the Alice’s Restaurant property: given any two finite disjoint sets of vertices U and V, there is a vertex z joined to everything in U and to nothing in V. How do we check this for a countable model of ZF? Try taking the set U as z; it is certainly joined to all the vertices in U, since they are its members. Moreover, it does not contain any vertex in V. But there is a small problem: U itself might be contained in some member of V, in which case it would be joined to this vertex. To avoid this, we simply add to z the set V. Now if some element v of V were joined to z, then either vz, in which case necessarily z = V, so that vv; or zv, which would give a loop vVzv.

Here the gathering of finitely many elements into a set is justified by the Empty Set, Pairing and Union axioms of ZF, while the existence of a set containing itself, or a cycle of length 3 in the membership relation, are both forbidden by the Axiom of Foundation (which, more or less, forbids infinite descending chains in the membership relation). Note that the Axiom of Foundation also ensures that the undirected version of the membership digraph is a simple graph, that is, has no loops or multiple edges (it forbids both xx and xyx).

The Axiom of Foundation was initially seen as an important part of avoiding the paradoxes of set theory such as Russell’s Paradox concerning the set of all sets which are not members of themselves. (Russell’s Paradox can be expressed, more positively, as saying that there does not exist a set A which consists precisely of those sets which are not members of themselves. Now if there were a “universal” set S containing all sets, then Russell’s set would be {xS:xx}, whose existence would follow from the Axiom of Selection; so no such universal set can exist. In the motivation for ZF, we imagine the sets being constructed in stages, each stage containing sets built out of those which have already been constructed; the universal set would have to appear at the very last stage, but there is no last stage! This construction by stages has as a consequence that no infinite descending chain of sets can occur (there would have to be a first stage at which such a set arose …), and indeed has a consequence the standard formulation of the Axiom of Foundation.)

Incidentally, this approach shows why a model of ZF set theory has no symmetry. If there were an automorphism which didn’t fix everything, there would be a set moved by the automorphism appearing at the earliest possible stage; but this set is uniquely determined by its members (by the Axiom of Extension), all of which are fixed. This perhaps makes it even more remarkable that, by undirecting the adjacency relation in such an asymmetric graph, we obtain a graph with the huge amount of symmetry that the random graph possesses.

[This is not right, see comment below.]

However, there have been calls to examine alternative axiom systems not using this axiom, with a view to modelling recursive processes in computer science (among other possible applications). An “anti-foundation axiom” was introduced by Peter Aczel, and anti-foundational set theory is discussed in detail in the book Vicious Circles by Barwise and Moss. They denote by ZFA the Zermelo–Fraenkel system in which the axiom of foundation is replaced by the anti-foundation axiom. There is a relative consistency result stating that, if ZF is consistent, so is ZFA: the proof starts from a model of ZF and constructs a model of ZFA by adjoining solutions to certain sets of equations.

My question was: What do we get if we take a countable model of ZFA (as a directed graph) and symmetrise the membership relation?

Bea studying AFA

(The picture above is a self-portrait of Bea Adam-Day studying the Anti-Foundation Axiom; it is homage to the picture La reproduction interdite by René Magritte, used on the cover of the book by Barwise and Moss.)

Since a model of AFA can (and indeed does) contain loops and double edges, there are several ways we could interpret this question.

  • We could keep loops, or ignore them.
  • We could keep double edges, or ignore them.
  • We could even keep loops and double edges and ignore single edges.

It is not at all clear, in any case, whether we obtain a unique and highly symmetric graph like the random graph, or we just get a mess!

After quite a struggle, Bea managed to figure out what we get if we undirect the membership relation keeping loops but not double edges (in other words, putting a single undirected edge {x,y} when xy, whether or not yx). The graph we get is the random graph with loops, the graph we obtain with probability 1 if we toss a coin repeatedly to decide, not only which pairs of vertices are joined by edges, but which single vertices carry loops. There is a unique countable graph, defined by a similar “Alice’s restaurant property” (requiring that, given U and V, there is a witnessing vertex without a loop and another one with a loop). It is homogeneous, and universal for finite or countable graphs with loops but no multiple edges. Like the random graph, it is highly symmetric.

The proof follows the outline suggested earlier; but this time we have no Axiom of Foundation to invoke. Instead, the Anti-Foundation Axiom is consructive in nature, asserting that sets with certain properties exist; and in the other direction we use the failure of Russell’s Paradox. Pushing our earlier argument one step further, given a positive integer k, there is no set which consists precisely of all k-element sets (if there were, its union would be the “universal set”, since every set is a member of a k-element set); so, given any set whatsoever, there is a k-element set which it does not contain.

Inspired by this, I looked at one further case. What happens if we keep loops and double edges but throw away single edges? In other words, we put an edge {x,y} if both xy and yx hold. This time, no homogeneity result holds (indeed, the graph is not countably categorical), but it is not without structure. It has infinitely many finite connected components; indeed, any finite connected graph with loops occurs infinitely often as a connected component of our double-edge graph. The graph has at least one infinite component as well.

A preprint containing these results has just appeared on the arXiv.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition and tagged , , , . Bookmark the permalink.

3 Responses to The random graph and anti-foundation

  1. I forgot to say that Bea is my 200th co-author (including people with whom I have a paper published, accepted, or on the arXiv).

  2. Thanks to Imre Leader for pointing out to me that the “proof” that the membership digraph has no non-trivial automorphisms is rubbish. The argument shows that no function in the model can be a non-trivial automorphism. But there is no reason why an arbitrary digraph automorphism should preserve the levels of the Zermelo hierarchy.

    • Asvin G. says:

      Can’t you prove that an arbitrary digraph automorphism should preserve the levels in the following way:

      You can identify the empty set as the unique source. So any di-graph automorphism has to preserve the empty set. Second, you can identify the sets built at the first level as those with at least one arrow from the 0-th level (= empty set) and not part of the 0-th level. This is a purely di-graph property and will also be preserved by automorphisms.

      Similarly, characterize the n-th level as having an arrow from the n-1 th level and not being part of it which shows that each level is preserved by the automorphisms.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s