# Axiom of Choice and Order Types

A beginner's question:

We know: "Since order-equivalence is an equivalence relation, it partitions the class of all sets into equivalence classes." (from Wikipedia)

This holds since every set can be (well-)ordered by the Axiom of Choice.

But there can be many (well-)orderings of a given set. Especially, the Axiom of Choice doesn't tell us, what the choice function is and thus, what the well-ordering is: there can be many.

Thus, a set can belong to many order types and order-equivalence isn't an equivalence relation anymore.

What's wrong with this (presumably dummy) line of thoughts?

• I have edited the Wikipedia article, so it reads "it partitions the class of all ordered sets into equivalence classes." – TonyK Feb 1 '10 at 17:06

## 2 Answers

Order equivalence is an equivalence relations on ordered sets, not on sets. It is just the isomorphism relation on ordered structures. An ordered structure is a set, together with an order.

The Axiom of Choice says that every set has a well-order. Since the order-types of well-orders are well-ordered (given any two, one of them is uniquely isomorphic to a unique initial segment of the other), it follows under AC that for every set, we can associate to it the smallest order-type of a well-order on that set. This is called the cardinality of the set.

There is another more general concept of cardinality, which does not rely on AC or on orderings at all, and it is just the equinumerosity class of the set.

The equivalence classes referred to by Wikipedia don't correspond to order types; different orderings belong to the same equivalence class so long as the underlying sets have the same cardinality.

To elaborate: you can define an equivalence relation on unordered sets by saying that A~B if A and B can be ordered equivalently. This is, of course, an equivalence relation on sets, so it partitions the class of unordered sets. It just doesn't do it in the nice way you assumed it did, where different order types end up in different classes.

• Are you looking at the same article as the rest of us? The equivalence classes in OP's Wikipedia article are precisely the order types. – TonyK Feb 1 '10 at 17:05
• In the article's current form, yes. I was addressing the pre-edit version as quoted by the OP, which was still technically true. – Jonah Ostroff Feb 2 '10 at 1:16