3
$\begingroup$

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:

  1. If x, y ∈ S then one and only one of x < y, x = y, x > y is true.
  2. 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$
8
  • 1
    $\begingroup$ Consider the set $\{a,\psi\}$. If you don't define order on this set then this set is not ordered. $\endgroup$ Aug 3 at 6:53
  • 1
    $\begingroup$ Is 100+2i greater than 2-100i? $\endgroup$
    – David P
    Aug 3 at 6:54
  • $\begingroup$ @OğuzhanKılıç can you give me a simpler example, like a set with elements that are not ordered? I am relatively new to real analysis. $\endgroup$ Aug 3 at 6:55
  • 1
    $\begingroup$ assuming the axiom of choice, every set has a well ordering. what rudin describes is a total order structure. but, how do you place a total order structure on say, the power set of the reals? $\endgroup$
    – C Squared
    Aug 3 at 6:56
  • 1
    $\begingroup$ @ZarifMuhtasim one last point if it wasn’t clear, David P’s example was trying to say that the complex numbers that we are all familiar with is an example of an unordered field. $\endgroup$
    – C Squared
    Aug 3 at 7:01
8
$\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
  • 2
    $\begingroup$ So to be preice, an ordered set is a pair $(X,\leq)$, where $X$ is a set and $\leq$ is an ordering on $X$. It should not be confused with $X$. $\endgroup$ Aug 3 at 7:23
  • 1
    $\begingroup$ @MartinBrandenburg Yes, that is the conventional rigorous way of supplying an ordering. I didn't want to go down that route, because a pair is usually just another set under the hood, which means that a set on its own can be an ordered set, if it has the exact right form. So my first paragraph is actually a lie, but I don't think it's a bad one to tell beginners. $\endgroup$
    – Arthur
    Aug 3 at 7:28
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$
0
$\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
  • 3
    $\begingroup$ The set of complex numbers can be ordered lexicographically very easily. $\endgroup$ Aug 3 at 7:13
  • $\begingroup$ @MartinBrandenburg how about alphabetically? $\endgroup$
    – Graviton
    Aug 3 at 7:15
  • $\begingroup$ Yes. This is another name for the lexicographic order. $\endgroup$ Aug 3 at 7:23
  • 1
    $\begingroup$ @MartinBrandenburg well, yes, sort of, however I was making a joke. Lexicographic order includes ordering of alpha-numeric symbols. But by alphabetically I meant by ordering each complex number alphabetically from its corresponding English representation such as twenty-seven-and-three-point-two-i. $\endgroup$
    – Graviton
    Aug 3 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.