The definition of an ordered set according to W. Rudin in his book, Principles of Mathematical Analysis is:
An ordered set is a set S in which an order is defined
He also defined order in his book:
Let S be a set. An order on S is a relation, denoted by <, with the following two properties:
- If x, y ∈ S then one and only one of x < y, x = y, x > y is true.
- If x, y, z ∈ S and x < y and y < z then x < z.
I can't think of any set that doesn't have an order. Is there any set that is not ordered? A counterexample would be very helpful.
$\endgroup$ 93 Answers
$\begingroup$A set isn't ordered unless you supply an ordering. A set on its own is not an ordered set.
So the natural numbers is not an ordered set. The natural numbers with the standard $<$ is an ordered set. Usually, when in the context of ordered sets, just saying "the natural numbers" will implicitly imply "with the standard ordering". But if we're being pedantic and strict about it, then it needs to be said explicitly; if it isn't we don't have an ordered set.
And, of course, there are plenty of sets without a standard total ordering. Like the complex numbers. Or the points on a sphere. Or the integers modulo $10$. Many of these sets can be given a total order, and in many cases it is even pretty easy to do so. But it won't play nicely with the standard structures those sets do have, so that's of limited use. And there is no canonical way of doing it, so if you want others to know which order you're talking about you have to say exactly what your order is.
And then there is the possibility of sets which can't be given a total order at all. It's impossible to mention concrete examples here, because no set can be proven un-orderable, at least in ZF.
$\endgroup$ 2 $\begingroup$This is usally called a total order. For example, every well-order is a total order. It can be shown that the existence of well orders for every set is equivalent to the axiom of choice (Well-ordering theorem). The existence of total orders for every set is weaker than the axiom of choice, but it cannot be proven from $\mathbf{ZF}$ (the standard axiom system for set theory but without the axiom of choice) alone. See MO/37272.
$\endgroup$ $\begingroup$"I can't think of any set that doesn't have an order"
This attests to how fundamental order seems to be, and why it's one of the foundational axioms of modern set theory. The well-ordering theorem (equivalent to the Axiom of Choice), apart of ZFC, is simply that; an axiom. An assertion that for any set there exists a relation (which could be more of an abstract relation than your typical $>$ or $<$) that well-orders that set. There's nothing stopping you from using a set theory without such axiom, as many set theorists do.
The answers to this question goes over the difference between total order, which is what Rudin is referring to, and well order.
The set of complex numbers is a good example of set with undefined order. However, you can order them given a more abstract relation.
It's important to note that no set naturally comes equipped with an ordering relation. The relation is something that is usually defined after a set is defined. For example, how do you order the set $\{a,7,\uparrow\}$? There's no "right" way, but you can create a well-defined relation that orders such set, just as was done for the real numbers and etc.
$\endgroup$ 4
