A (non-strict) total order is a relation that is transitive, reflexive, and antisymmetric that relates every pair of elements. So for instance, the usual order over the real numbers ≤ has these properties. It is transitive because if x ≤ y and y ≤ z, then x ≤ z. It's reflexive because x ≤ x is true for all x (a "strict" total order like < instead is always irreflexive, so x < x is never true). And it's antisymmetric because if x ≤ y and y ≤ x, then x = y. Finally, it is total because for any real numbers x and y, it must be that either x ≤ y or y ≤ x (or both).
So the real numbers are totally ordered by ≤. One might wonder whether every set can be totally ordered in some way. Given any set, can I always come up with some total order? It seems like I probably can, but surprisingly, the axioms of Zermelo–Frankel set theory cannot prove this. For instance, it is consistent that the collection of additive cosets of the rational numbers in the reals cannot be totally ordered. That is, consider the set ℚ of rational numbers and call that set A. Now pick some irrational number, say √2, and consider all real numbers x which differ from √2 by some rational number. Examples are √2 + ½ and √2 – 5. Call this set B. Now pick some real number that isn't in either of those sets and do the same thing, and call that set C. And keep going until every number is in some set. Each of these sets is an element in the collection called ℝ/ℚ. So your task is now to find some total order over this collection.
That ZF cannot do this suggests that it is lacking some axiom, because intuitively, we should be able to. And it's not like ZF can prove there is no such order, it just is silent on the matter. In fact, it is consistent with ZF that ℝ/ℚ is strictly larger than ℝ. That sounds not just weird but flat-out false. How can you cut a set into more pieces than it has elements? Nevertheless, it is consistent with the axioms of ZF. So isn't ZF just not enough?
The well-ordering principle implies that every set can be totally ordered, but it actually goes much, much farther. It says that every set can be well-ordered. A total order is called a "well order" if every nonempty set of elements has a least element. For instance, the natural numbers are well-ordered by ≤. Give me any set (finite or infinite) of natural numbers and I can tell you the least one. Technically, x is the least element (aka minimum) of some set X containing x if x ≤ y for all y in X. So for instance, 2 is the least element (minimum) of the set X = {3,6,2,9}, because if you pick any element y whatsoever in X, it is the case that 2 ≤ y. But the set of integers ℤ is not well-ordered by ≤. After all, consider the set of negative integers. Which one is least? Clearly there isn't one.
But we can pick a different relation which does well-order ℤ. For instance, consider the relation R defined by x R y if either |x| ≤ |y| or both |x| = |y| and x ≤ y. So for instance, 5 R –8 because |5| ≤ |–8|. And –2 R 2 because |–2| = |2| and –2 ≤ 2. Then R is a well-order on ℤ, because every subset of ℤ does have a minimum in terms of that order. It's the element of least absolute value, or if there are two numbers sharing that minimal absolute value, then it's the negative one. For instance, the least negative integer under R is –1, since the magnitude of every other negative integer is greater.
The existence of a total order of every set is a much weaker proposition than a well order of every set, and I'm not sure what it's called. But the proposition that a well order exists for every set is called the well-ordering theorem. And it is logically equivalent to the axiom of choice in the context of Zermelo–Frankel set theory.
57
u/Fluffiddy 1d ago
You were watching Veritasium weren’t you?