0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ I have edited the Wikipedia article, so it reads "it partitions the class of all ordered sets into equivalence classes." $\endgroup$
    – TonyK
    Commented Feb 1, 2010 at 17:06

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TonyK
    Commented Feb 1, 2010 at 17:05
  • $\begingroup$ In the article's current form, yes. I was addressing the pre-edit version as quoted by the OP, which was still technically true. $\endgroup$
    – Jonah Ostroff
    Commented Feb 2, 2010 at 1:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .