What is the difference between a contradiction and a paradox?
A contradiction is a dead end, a sign that the road leads nowhere and you should turn back and take the other road. A paradox, however, is an invitation to think creatively about the situation; you stand to gain a lot.
So here are a couple of paradoxes. The first I only realised recently, but it will be relevant to my story later. Here are two views of Aristotle, both of which have been very influential in Western thought.
- We observe that in the world, every effect has a cause. Aristotle thought that this created a backward chain of causes, which could not go on for ever, and therefore there must be a First Cause or Prime Mover somewhere outside our universe to set the whole thing into motion.
- Though Aristotle denied the existence of actual infinity, he was happy with potential infinity (such as the passage from one natural number to the next in induction); also, he believed that human souls have an immortal part.
I have always regarded the first argument as unworthy of a philosopher. I see no problem with infinite backward chains of causation in principle; even if we deny them, it by no means follows that there can be only one First Cause. Why not many?
But there is an asymmetry between the two parts. If there is a Prime Mover to start everything off, why not a Prime Eater at the end, like the eagle in Carlos Castaneda’s philosophy? Doron Zeilberger claims that there is a largest natural number, and it is impossible to refute that.
But there is a place where mathematicians have embraced that asymmetry (look away now, Doron); that is in set theory, where everything is built from the empty set but there is no end to how far the sets go.
But before following that, it is time for the second paradox. One of the “portals” of first-order model theory is the Löwenheim–Skolem theorem, which says that if a first-order theory in a countable language has an infinite model, then it has a countable model. Now, the Zermelo–Fraenkel axioms for set theory are first-order in a countable language (with a single binary relation symbol ∈ for membership). So, if they are consistent (as most mathematicians would assume, although Gödel showed us that they cannot prove their own consistency), then there is a countable model of ZF.
The paradox, the famous Skolem paradox, arises because there is a theorem of ZF asserting the existence of uncountable sets.
I discussed the resolution of the paradox in my book Sets, Logic and Categories, and am not intending to repeat that here. Rather, this is to discuss the properties of countable models.
The membership relation is not symmetric, so it defines a directed graph structure on the universe of the model. But it has the remarkable property that if we ignore the directions, and consider the undirected graph, it is isomorphic to the Erdős–Rényi random graph (also known as the Rado graph). I have discussed this graph in a series of posts beginning here. I have known this for so long that I cannot remember when I first learned it.
The proof is very simple. Clearly it relies on the axioms of ZF, but not many of them are actually used. Apart from the Empty Set, Union and Pairing axioms (which are needed to guarantee that there is something), only one axiom is used, the Axiom of Foundation. So, for example, the Axiom of Choice is not used; the Axiom of Infinity is not used. This has historical significance. There is a standard model of hereditarily finite set theory (in which every set is finite, as are all its subsets, and so on): the sets are natural numbers, and x is in y if and only if 2x occurs in the base 2 expansion of y. If we undirect this relation, we obtain precisely Rado’s original definition of his graph.
The Axiom of Foundation is the one I alluded to above, which destroys the symmetry of up and down in set theory. Its statement is somewhat technical, but it has the effect of forbidding infinite descending chains under the membership relation (although this is not a theorem of first-order ZF, but rather a metatheorem). It can be proved in ZF (using the Axiom of Foundation) that there are no finite cycles under the membership relation; in particular, no set can be a member of itself; and there do not exist two sets, each a member of the other.
So I wondered what sort of graphs would arise if we negate the Axiom of Foundation, for example by replacing it by some version of the Anti-Foundation Axiom proposed by Peter Aczel. The resulting theory is known as ZFA. This is discussed in detail in the book Vicious Circles by John Barwise and Lawrence Moss, who give a number of applications of the theory.
Some fairly large number of years ago, I tried to interest a PhD student in this problem, but the student did not take it up. Then, much more recently, Bea Adam-Day, a St Andrews student doing the undergraduate Masters degree, got interested in the question. I hope I am doing justice to Bea when I say that a combination of the beauty of the ideas around the random graph and the excitement of proving new mathematical results together seduced her into continuing her studies; she is now a PhD student at the University of Leeds.
We proved several results. One is the fact that, if you keep loops and double edges but delete single edges from the digraph, you get the “random loopy graph” (the random graph with loops at a random set of vertices); whereas other reducts are more complicated and do not have countably categorical theories. I discussed the results here.
After a long and complicated story, the paper was finally published on-line yesterday; you can read it here (it is open access).
But happily the story goes on. There were several questions we were unable to answer. At Leeds, Bea has got her fellow students John Howe, Rosario Mennuni interested in the question, and they have a paper on the arXiv.