Axiom of Choice and Order Types - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:47:29Z http://mathoverflow.net/feeds/question/13705 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13705/axiom-of-choice-and-order-types Axiom of Choice and Order Types Hans Stricker 2010-02-01T16:30:34Z 2010-02-10T11:23:35Z <p>A beginner's question:</p> <p>We know: "Since order-equivalence is an equivalence relation, it partitions the class of all sets into equivalence classes." (from <a href="http://en.wikipedia.org/wiki/Order%5Ftype" rel="nofollow">Wikipedia</a>)</p> <p>This holds since every set can be (well-)ordered by the Axiom of Choice.</p> <p>But there can be many (well-)orderings of a given set. Especially, the Axiom of Choice doesn't tell us, <em>what</em> the choice function is and thus, what the well-ordering is: there can be many.</p> <p>Thus, a set can belong to many order types and order-equivalence isn't an equivalence relation anymore.</p> <blockquote> <p>What's wrong with this (presumably dummy) line of thoughts?</p> </blockquote> http://mathoverflow.net/questions/13705/axiom-of-choice-and-order-types/13706#13706 Answer by Joel David Hamkins for Axiom of Choice and Order Types Joel David Hamkins 2010-02-01T16:36:54Z 2010-02-01T16:36:54Z <p>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.</p> <p>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 <em>cardinality</em> of the set. </p> <p>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. </p> http://mathoverflow.net/questions/13705/axiom-of-choice-and-order-types/13707#13707 Answer by Jonah Ostroff for Axiom of Choice and Order Types Jonah Ostroff 2010-02-01T16:42:28Z 2010-02-01T16:47:32Z <p>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.</p> <p>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.</p>