2
$\begingroup$

Perhaps this is a strange question. But it made me think and I have no idea how to answer it. Or if it actually makes sense.

I've come across "Well-Ordered Sets" a few times now, and it's well known that there are different (nonisomorphic) ways of Well-Ordering Infinite Sets of any cardinality. On the other hand, there is only one (up to isomorphism...) way to well-order a finite set of size n. Also well known.

Furthermore, there is only one way to totally order a finite set of size n. Obviously this is not true for infinite sets either, as totally ordered sets are simpler than well-ordered sets (and so they are a superset of them).

The thought occurred to me, is there some kind of rigorous theorem, whereby the second statement, that there is only one way to totally order a finite set of size n, is the "simplest" of it's kind?

It seems hard to make the statement any simpler, as we did when moving from well-orders to total orders. Does/can this make rigorous sense?

Any help/quibbles appreciated!

  • 0
    It's not true that there's only one way to well-order a set of size $n$; rather there are $n!$ ways. But there's only one isomorphism class of linear orderings.2012-11-05
  • 0
    Yeah that's what I meant.2012-11-05
  • 0
    For finite sets, every total order is a well-ordering: Startingfrom any element you will reach a smallest element in a finit number of steps as long as smaller elements exist.2012-11-05
  • 0
    Yes I know that, but is it clear what I am asking?2012-11-05
  • 1
    Are you asking: Is a set finite if and only if all well-ordering of the set are isomorphic? If the axiom of choice fails there are sets that can not be well-ordered. If $X$ is such a set then all well-orderings are isomorphic. If the set $X$ can be well-ordered in a way that is isomorphic to some infinite ordinal $\alpha$ then $X$ can also be well-ordered so that it is isomorphic to $\alpha + 1$.2012-11-05
  • 0
    No that's not what I'm asking. I'm asking is the *total order* the structurally "simplest" kind of relation such that when restricted to finite sets, gives the total orders, and of course the usual theorem that any two of these relations of equal cardinality are isomorphic.2012-11-05
  • 0
    Your philosophical approach seems strange to me. "Total orders are simpler because it's a larger class" makes no sense. The class of all sets is ineffably complicated whereas hereditarily finite sets are rather simple. Well-orders are *very* well-behaved because there is a Cantor-Bernstein property for well-ordered sets, namely if two sets embed into one another then they are isomorphic (furthermore, this isomorphism is unique). This is a very simple class of sets, whereas even scattered orders, become much more complicated.2012-11-05
  • 0
    Put more rigorously, Jay, the OP's question is this: "If $\mathcal{T}$ is the class of total order relations, is there a class of relations $\mathcal{R}$ of which $\mathcal{T}$ is a strict subclass, such that for any finite set $X$ and any two $\mathcal{R}$-relations $R,S$ on $X$ we have that the structures $\langle X,R\rangle$ and $\langle X,S\rangle$ are isomorphic?"2012-11-05
  • 0
    Asaf: Perhaps he simply means simpler to qualify, as total orders have fewer requirements to satisfy than well-orders do.2012-11-05
  • 0
    @Cameron, you should really remember to use `@` symbol in front of nicknames... :-)2012-11-05
  • 0
    @Asaf, did it not ping you? Strange. That usually works for me. I'll start using the `@` again, then.2012-11-05
  • 0
    @Jay: See my comment above, which hopefully clarifies things for you. (Of course, it's possible that I misinterpreted.)2012-11-05
  • 0
    @Cameron: If you are chatting with one person; one of you is the poster of the answer/question on which you are discussing; and no one else commented yet -- then it works without `@`, but *none* of these conditions hold in this case.2012-11-05
  • 0
    Take a look at my updated answer, and let me know if you've any uncertainties about it.2012-11-07

3 Answers 3