Ways Of Ordering A Set

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

It seems that modifying the axioms for a total order indeed allows almost anything you want for infinite sets, and for finite sets you still get a total order. This can be done in various ways that have been written down.

So if one regards "simpler" in terms of mathematical objects alone, without regard to the definitions/concepts behind them, you don't end up being able to say much of anything.

So "simpler" can only be about the axioms. All the "modifications" that make the finite structures the same, but the infinite ones more relaxed, make the axioms considerably more complicated. They are longer, and you have to mix quantifiers and logical connectives. I have never actually seen an algebraic structure defined in such a way (i.e. not in prenex normal form).

If one considers axioms where all variables are elements of the structure and are implicitly universally quantified, and all you have are logical sentences concerning states of affairs for the relation concerning those variables, then you can see that the number of axioms, variables, or length of sentences cannot be cut down, so in this sense the "total order" is indeed the simplest concept. It is the most stripped down and abstract order theory concept that does what it does.

But that's all you can do, I think.