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

1

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.

  • 0
    But that isn't really a set of axioms in the same way that antisymmetry, transitivity, and totality is a set of axioms.2012-11-05
  • 1
    @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?2012-11-05
  • 0
    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.2012-11-06
  • 0
    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.2012-11-06
  • 0
    @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.2012-11-06
  • 0
    Let's call Cameron's axioms *irreflexive*, *transitive*, and *comparable*. If instead of Cameron's axioms you keep *irreflexive*, *transitive*, and replace *comparable* by the stronger *nonempty subsets have minimums*, you get the well-ordered sets. Dropping *minimums* then allows nonisomorphic structures of equal finite cardinality. But *minimums* can still be replaced by the simpler axiom *comparable*, and you get the finite ordering theorem back. But how do we know that we can't do something similar regarding Cameron's axioms?2012-11-06
  • 0
    Perhaps no one knows the answer to the question about Cameron's axioms. An answer to this question seems to require a precise definition of "simpler" when comparing axioms. There might be two axioms, say $A$ and $B$, and two sets of axioms, say $\Sigma$ and $\Pi$ that satisfy: (1) Every model of $\Sigma + A$ is also model of $\Sigma + B$ but not the other way around. (2) Every model of $\Pi + B$ is also a model of $\Pi + A$ but not the other way around. If such a situation occurs it will be difficult to decide which of $A$ and $B$ is simpler.2012-11-06
  • 0
    Yes, "simpler" is vague. It seems clear that such a notion has to apply to the axioms themselves. If we simply desire a type of relation that amounts to total orders for finite sets, but for infinite sets amounts to a relation that is transitive and total, then we can do that. You do it by replacing Cameron's axiom *irreflexive* by *if every nonempty subset of R has a minimum, then R is antisymmetric*. However this is rather ungainly and not at all simple, especially when you write it out in quantifiers. For one thing you have to mix quantifiers and connectives and quantify over subsets of R.2012-11-06
  • 0
    Perhaps we should require that each axiom be written out quantifier free (i.e. assume all variables are universally quantified), in its simplest form, using only logical connectives. Then you have (1): xRy implies ¬yRx, (2): (xRy and yRz) implies xRz. (3): xRy or yRx or x=y. Play around using different symbols in different places, you will soon exhaust all the different "simple" axiom systems of this sort. Then it will become clear that the most "stripped down" way to axiomatise total orders is the one we already use. Only worry about the definitions, not the actual objects.2012-11-06
0

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.

  • 0
    You should add to your remark that this can only be true when the axiom of choice is absent.2012-11-05
  • 0
    Good point, Asaf. I will.2012-11-05
  • 0
    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.2012-11-05
  • 0
    Glad to help, John. I didn't quite understand what you just said, though (apart from the first sentence, of course). Could you clarify?2012-11-05
  • 0
    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.2012-11-05
  • 0
    But then, how to state and prove this? That was the question.2012-11-05
  • 0
    Still not following. Maybe it would make more sense if you explained what you mean by "This is *not* the case for well-orders."2012-11-05
  • 0
    The structure *well-order* when restricted to finite sets, gives the finite well-orders, or equivalently the finite total orders. The structure *total order* also has this property. Any structure having this property, when you think about it generally (not only finite) seems to imply the axioms of a total order. It is not the case that any structure having this property implies the axioms of a well order. For example, total orders.2012-11-05
  • 0
    @Cameron: Your comparability axiom needs to state that at most one of the three cases holds. Suppose $X$ is a set with at least two elements. Consider the relation $xRy$ if and only if $x \ne y$. I only noticed this when I tried to complete the proof when transitivity is dropped.2012-11-06
  • 0
    Excellent point, @Jay! I forgot that I was relying both transitivity and irreflexivity to get that at most one of the comparability conditions holds. I'll have to think on that.2012-11-06
  • 0
    "To my mind, though, it's rather contrived." Yes it is, thanks for the reply in any case.2012-11-12
0

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.