The Curious Dependence of Set Theory on Order Theory
Posted by Tom Leinster
(Note: the Café went down for a few days in early November 2012, and when Jacques got it back up again, some of the comments had been lost. I’ve tried to recreate them manually from my records, but I might have got some of the threading wrong.)
This is the first of a series of posts on set theory, order theory, and how they are intertwined.
I won’t assume you know any more set theory than the average pure mathematician: in other words, no axiomatic set theory, just the ordinary “naive” principles that mathematicians use every day. (And I’ll steer clear of the debate about which system of axioms is “best”. Important as that is, it tends to suck the oxygen out of a room.) As far as order theory is concerned, I’ll assume just the very basic definitions, such as “partially ordered set”.
In this first installment, I’ll ask: why is it that some of the fundamental theorems of set theory do not mention order in their statements, but apparently need substantial order theory in their proofs?
Although I’m steering clear of axiomatics, I should probably clarify one assumption: the “sets” I’ll talk about are taken to satisfy the axiom of choice. Any of the standard elementary formulations will do: every surjection has a right inverse, or every equivalence relation has a system of representatives, or the product of any family of nonempty sets is nonempty.
Here are three of the most basic nontrivial theorems about sets. For sets $X$ and $Y$, I’ll write $X \cong Y$ to mean that there exists a bijection between $X$ and $Y$.
- (Cantor–Bernstein theorem) Let $X$ and $Y$ be sets. If there exist injections $X \to Y$ and $Y \to X$ then $X \cong Y$.
- (Cardinal comparability) Let $X$ and $Y$ be sets. Then either there exists an injection $X \to Y$ or there exists an injection $Y \to X$.
- (Squares of infinite sets) Let $X$ be an infinite set. Then $X \times X \cong X$.
The Cantor–Bernstein theorem is often called the Schröder–Bernstein theorem, but people who know the history seem to prefer the first name. Here’s a passage from R. M. Dudley’s book Real Analysis and Probability (page 22):
The equivalence theorem came up as an open problem in Cantor’s seminar in 1897. It was solved by Felix Bernstein, then a 19-year-old student. Bernstein’s proof was given in the book of Borel (1898). Meanwhile, E. Schröder published another proof. The equivalence theorem has often been called the Schröder–Bernstein theorem. Korselt (1911), however, pointed out an error in Schröder’s argument. In a letter quoted in Korselt’s paper, Schröder gives full credit for the theorem to Bernstein. […] Bernstein also worked in statistics […] and in genetics; he showed that human blood groups A, B, and O are inherited through three alleles at one locus.
I couldn’t resist including the Cantor–Bernstein theorem in this list, since it really is one of the basic nontrivial results about sets. But in a way it doesn’t belong, because it doesn’t require any order theory to prove it.
I know two proofs. The first (which I’m guessing was Bernstein’s) is dynamical. It takes injections $f\colon X \to Y$ and $g\colon Y \to X$, and traces each element of $X$ or $Y$ along its backwards trajectory for as long as possible. The second is order-theoretic. It uses the result in order theory known as Tarski’s fixed point theorem or the Knaster–Tarski fixed point theorem. (Incidentally, the two proofs construct the same bijection between $X$ and $Y$, starting from an initial choice of injections $f\colon X \to Y$ and $g\colon Y \to X$.)
So while the Cantor–Bernstein theorem can be proved using order theory, it doesn’t have to be.
However, I don’t know a proof of cardinal comparability that doesn’t use substantial order theory. Here’s one classic proof. It uses a certain class of partially ordered sets called the well-ordered sets. A well-ordered set is a set equipped with a well-order, which is an order relation satisfying certain further conditions that don’t matter for the present purposes. We’ll need two facts:
- every set can be equipped with a well-order
- if $X$ and $Y$ are well-ordered sets then either $X$ is isomorphic (as an ordered set) to a subset of $Y$ or $Y$ is isomorphic to a subset of $X$.
Cardinal comparability follows immediately.
I’m claiming that cardinal comparability is a general theorem about sets whose statement doesn’t mention order, but whose proof uses order in an essential way. You might object that it’s not a very good example. Sure, the statement doesn’t mention order explicitly, but it’s there all right, in thin disguise. After all, there’s a (pre)order $\leq$ on the class of all sets defined by
$X \leq Y \iff \text{there exists an injection } X \to Y,$
and cardinal comparability simply states that it’s a total order.
I concede: it’s not a great example. But what about the third theorem, on squares of infinite sets? The statement here really isn’t order-theoretic at all. (Well, not except in a trival sense: any theorem asserting that two sets have the same cardinality could be called order-theoretic, since by Cantor–Bernstein, $A \cong B$ if and only if $A \leq B \leq A$.) So here’s a question for you all:
Does anyone know a proof that $X \times X \cong X$ for infinite sets $X$ that neither uses substantial order theory nor involves elaborate convolutions to avoid doing so?
I should make clear that I have no objection to order theory. In fact, I probably like it more than most people (and, for example, I find the order-theoretic proof of the Cantor–Bernstein theorem more appealing than the dynamical proof). But I’d like to understand better why it is that basic results about sets seem to depend so heavily on the concept of order.
I’ll finish by posing and attempting to answer a question:
Is it strange that results about sets should depend on results about order?
On the one hand, yes.
Think again of the proof of cardinal comparability sketched above. We took two abstract sets $X$ and $Y$, and we equipped them with well-orders in a quite arbitrary way. (Even if you don’t know what a well-order is, it should be clear that the choice is arbitrary: given one well-order on $X$, you can transport it along any bijection $X \to X$ to obtain another.) Then we used some order theory to show that either $X$ is order-isomorphic to a subset of $Y$ or vice versa, then we threw away the orders, to conclude that either $X$ is set-theoretically isomorphic to a subset of $Y$ or vice versa.
If you’re already familiar with that kind of argument, maybe it doesn’t seem so strange. In that case, consider the following. It’s a fact that every nonempty set can be equipped with a group structure. (For finite sets, use the cyclic groups; then observe that taking the free group on an infinite set doesn’t change its cardinality.) Wouldn’t it be strange if we proved a result about abstract sets by (1) equipping them arbitrarily with group structures, (2) using some result from group theory, then (3) forgetting the group structures to draw some conclusion about the sets themselves?
Or — leaving set theory behind — consider the fact that every finite abelian group can be given a multiplicative structure making it into a ring. (Proof: every finite abelian group is a product of cyclic groups, and every cyclic group can be given a ring structure.) There’s no canonical way to do this: for example, in the group of order three, there’s no canonical choice for the multiplicative identity. Wouldn’t it be strange to prove a theorem about finite abelian groups by (1) equipping the groups arbitrarily with multiplicative structures, (2) using some theorem about rings, then (3) forgetting the multiplicative structures?
On the other hand, no, it’s not strange.
Consider elementary enumerative arguments about finite sets. For example, suppose someone asks you: why are there exactly $n!$ permutations of an $n$-element set? You’d probably reply with something like: there are $n$ places for the first element to go, then $(n - 1)$ places for the second element, and so on. Almost without thinking, you’ve chosen an ordering on the set concerned. Indeed, it’s hardly surprising that choosing an ordering is involved: for a set $X$ to have $n$ elements means that there exists a bijection between $X$ and $\{1, \ldots, n\}$, so to exploit the fact that $X$ has $n$ elements, we’re probably going to have to choose such a bijection.
Still, perhaps it’s a surprise that when we progress from finite to infinite sets, the question of ordering moves to centre stage. In the world of finite sets, putting an order on the set is something we do almost without noticing — it feels like a trivial part of the argument. But in the world of infinite sets, the order theory becomes really substantial. Indeed, for the three theorems above, it makes up the weightiest part of the proofs.
I’d like to understand better what’s going on here, and I hope your comments will help me to do so. It seems that set theory, which is about maximally unstructured objects, depends on order theory, which is about more structured objects. Is that really true? If so, what are some comparable situations elsewhere in mathematics? (I’m thinking of maybe geometric structures on topological manifolds, but I’m not sure how similar that really is.) And can someone paint a philosophical picture that makes this seem natural?
Re: The Curious Dependence of Set Theory on Order Theory
Since the axiom of choice is equivalent to the well-ordering principle, one might say that when doing “set theory” with the axiom of choice, one is assuming explicitly that one’s “maximally unstructured” objects are simultaneously “maximally structurable”. I think it’s not surprising, then, that results which depend on that assumption will proceed by choosing such a structure. Suppose you wanted to prove some theorem about “all sets which admit a group structure” — it wouldn’t be at all strange to begin your theorem by putting a group structure on your set, since you expect to have to use your hypothesis! So I would say that any uncomfortableness one feels with the idea that “results about sets depend on results about order” should actually be regarded as an uncomfortableness with the axiom of choice. (-: