# Ways Of Ordering A Set

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!

-
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. –  Michael Hardy Nov 5 '12 at 17:47
Yeah that's what I meant. –  John Smith Nov 5 '12 at 17:50
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. –  Hagen von Eitzen Nov 5 '12 at 17:56
Yes I know that, but is it clear what I am asking? –  John Smith Nov 5 '12 at 18:00
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$. –  Jay Nov 5 '12 at 18:13

Consider the following infinite axiom set. We suppose that $R$ is a binary relation symbol and we have an equality symbol. For each natural number $n$ one axiom is:

If there are no more than $n$ elements then $R$ is a total order.

We can say "there are no more than $n$ elements" as follows:

For all $x_{0}, x_{1}, \cdots, x_{n}$ we have $x_{0} = x_{1}$ or $x_{0} = x_{2}$ or $\cdots$ or $x_{0} = x_{n}$ or $\cdots$ or $x_{n - 1} = x_{n}$.

Any binary relation on a finite set that satisfies this set of axioms is a total order. This set of axioms does not restrict binary relations on infinite sets.

There might be some quibbles about situations where the axiom of choice fails to hold. I am not competent to comment on those situations.

-
But that isn't really a set of axioms in the same way that antisymmetry, transitivity, and totality is a set of axioms. –  John Smith Nov 5 '12 at 20:03
@JohnSmith It is clearly a set and clearly its elements are axioms. And it is even recursively enumerable. Can you elaborate on what "the same way" might mean? –  Hagen von Eitzen Nov 5 '12 at 20:51
Well that was kind of my question. The axioms for a total order appear to be the "simplest" we can get away with and still have the theorem that any finite total orders of cardinality n are isomorphic. The axioms for a well-order, and the infinitely many axioms you gave, are not the simplest that do that job. They take longer to write down. I want to say this rigorously/mathematically but I am not sure how. –  John Smith Nov 6 '12 at 14:32
Sorry Hagen I mean the axioms Jay gave. They do define a superset of the total orders, and for the finite case they give exactly the total orders, but as axioms they are definitely not simpler - they contain infinitely many axioms and variables, and infinitely many copies of the total order axioms. My trouble is how to articulate this. –  John Smith Nov 6 '12 at 14:41
@JohnSmith: Recalling Cameron's answer we can not simply drop irreflexivity or comparability. I suspect the same is true for transitivity. If not, someone who was writing a book on order would have proven transitivity could be derived from the other axioms. This means the axioms you are looking for would imply these three properties hold sometimes but not always. The axioms you looking for would have to describe how all of this worked together to get a total order on finite sets. My guess is that no finite set of axioms can do this. My conjecture may merely reflect my lack of imagination. –  Jay Nov 6 '12 at 16:58

Remark: Some infinite sets may not be well-orderable at all, or even orderable. The statement "Every set is well-orderable." is one of the forms of the Axiom of Choice. The statement "Every set is orderable." is called the Ordering Principle, and is a weakened form of the Axiom of Choice. That said, you're quite correct that any infinite set that is (well-)orderable can be (well-)ordered in non-isomorphic ways.

So that we're on the same page, I'll be using the following

Definition: A (strict) total order is a structure $\langle X,R\rangle$--with $X$ a set and $R$ a relation--satisfying the following:

(i) $\forall x\in X$, we have $\neg(x\: R\: x)$. (irreflexivity)

(ii) $\forall x,y,z\in X$, we have $(x\: R\: y\wedge y\:R\: z)\Rightarrow(x\: R\: z)$. (transitivity)

(iii) $\forall x,y\in X$, we have $(x=y)\vee(x\:R\:y)\vee(y\:R\:x)$. (comparability)

UPDATE: I have replace the old claim (and its proof) with the following, more comprehensive, result.

Proposition: Let $\mathcal{A}$ be a set of axioms about structures $\langle X,R\rangle$--where $X$ is a set and $R$ is a relation--and let $\mathcal{A}'$ be the restriction of $\mathcal A$ to structures on finite sets (effectively, we're just adding an axiom of finiteness to $\mathcal A$ to get $\mathcal A'$). Suppose that every total order $\langle X,R\rangle$ satisfies the axioms of $\mathcal A$. Further suppose that there is some structure $\langle Y,S\rangle$ that is not a total order and which satisfies the axioms of $\mathcal A'$ (and so satisfies the axioms of $\mathcal A$). Then there is some finite $n$ such that $\mathcal A'$-structures on sets of cardinality $n$ need not be isomorphic.

Proof: Let $\langle Y,S\rangle$ be any $\mathcal A'$-structure that is not a total order, and put $n=|Y|$. Let $R$ be any total order relation on $Y$, so that $\langle Y,R\rangle$ is also a $\mathcal A'$-structure (being an $\mathcal A$-structure on a finite set). It suffices to show that $\langle Y,S\rangle$ is not isomorphic to $\langle Y,R\rangle$. By way of contradiction, suppose that they are isomorphic, and let $f$ be an isomorphism from $\langle Y,S\rangle$ to $\langle Y,R\rangle$. Since $\langle Y,S\rangle$ isn't a total order, then irreflexivity, transitivity, or comparability must fail.

If irreflexivity fails on $\langle Y,S\rangle$, then $\exists x\in Y$ such that $x\:S\:x$, but since $R$ is irreflexive on $Y$, then $\neg\bigl(f(x)\:R\:f(x)\bigr)$, which is impossible, since $f$ is an isomorphism. Thus, irreflexivity holds on $\langle Y,S\rangle.$

If transitivity fails on $\langle Y,S\rangle$, then $\exists x,y,z\in Y$ such that $(x\:S\:y)\wedge(y\:S\:z)\wedge\neg(x\:S\:z)$. Since $x\:S\:y$ and $f$ is an isomorphism, then $f(x)\:R\:f(y)$, and similarly, $f(y)\:R\:f(z)$, so by transitivity of $R$, we have $f(x)\:R\:f(z)$. But this is impossible, since $\neg(x\:S\:z)$ and $f$ is an isomorphism. Thus, transitivity holds on $\langle Y,S\rangle$.

Since irreflexivity and transitivity hold on $\langle Y,S\rangle$, then comparability fails--that is, there exist $x,y\in Y$ such that $(x\neq y)\wedge\neg(x\:S\:y)\wedge\neg(y\:S\:x)$. Since $f$ is an isomorphism, then $\bigl(f(x)\neq f(y)\bigr)\wedge\neg\bigl(f(x)\:R\:f(y)\bigr)\wedge\neg\bigl(f(y)\:R\:f(x)\bigr)$, so comparability fails on $\langle Y,R\rangle$. But $\langle Y,R\rangle$ is a total order, so this is impossible. Thus, we have our contradiction. $\Box$

Conclusion: It looks like the Proposition shows that your statement about total orders is the "simplest" of its kind, but it actually doesn't.

Consider the following axioms about structures $\langle X,R\rangle$:

(i$'$) If $X$ is finite, then $\forall x\in X$, we have $\neg(x\:R\:x)$.

(ii$'$) If $X$ is finite, then $\forall x,y,z\in X$, we have $(x\: R\: y\wedge y\:R\: z)\Rightarrow(x\: R\: z)$.

(iii$'$) If $X$ is finite, then $\forall x,y\in X$, we have $(x=y)\vee(x\:R\:y)\vee(y\:R\:x)$.

Clearly, every total order satisfies these axioms, and any structure on a finite set satisfying these axioms will be a total order. However, there are structures on infinite sets satisfying these axioms, but which aren't total orders--for example, given an infinite set $X$, define $R$ on $X$ by $x\:R\:y$ if and only if $x=y$. The result then crucially relies on the existence of a structure $\langle Y,S\rangle$ on a finite set $Y$ that satisfies the axioms of $\mathcal A$ and isn't a total order.

The axioms (i$'$), (ii$'$), (iii$'$) give us the "simplest" sort of structure that is uniquely determined on finite sets up to isomorphism. To my mind, though, it's rather contrived.

-
You should add to your remark that this can only be true when the axiom of choice is absent. –  Asaf Karagila Nov 5 '12 at 18:31
Good point, Asaf. I will. –  Cameron Buie Nov 5 '12 at 18:32
Thanks for the reply! Perhaps it is the case that "any reasonable system of axioms for a relation" that in the finite case, axiomatises total orders, contains/implies the axioms for a total order. This is not the case for well-orders. –  John Smith Nov 5 '12 at 18:39
Glad to help, John. I didn't quite understand what you just said, though (apart from the first sentence, of course). Could you clarify? –  Cameron Buie Nov 5 '12 at 18:45
I think I made a typo. Starting again, the well-orders, when restricting to finite sets, give you the finite total orders (or whatever you want to call them). But the total orders also do this job, and are implied, for any sort of set, by the axioms for a total order. So the well-orders "give way" to total orders. It seems that the same thing will not happen to total orders, under any reasonable notion of a set of axioms for a relation. –  John Smith Nov 5 '12 at 18:54