Total order relations on a finite set

[Fernando Revilla]

I quote a question from Yahoo! Answers

How many elements are there in a total order?
So, let's suppose a given set containing n elements . How many elements, in terms of n, are there in a total order on this set?

I have given a link to the topic there so the OP can see my complete response.

 

[Fernando Revilla]

If $S=\{a_1,a_2,\ldots,a_n\}$, and $\le$ is a total order relation on $S$, for all $x,y\in S$ we have $x\le y$ or $y\le x$. This means that every total order relation has the form: $$a_{n_1}< a_{n_2}<\ldots <a_{n_n}$$ or equivalently, is a permutation on $S$. So, there are $n$ elements in a total order relation and there are $P_n=n!$ total order relations induced over $S$.

 

[Evgeny.Makarov]

This means that every total order relation has the form: $$a_{n_1}< a_{n_2}<\ldots <a_{n_n}$$ or equivalently, is a permutation on $S$. So, there are $n$ elements in a total order relation and there are $P_n=n!$ total order relations induced over $S$.

A couple of remarks. First, it's not good to write $n_n$: then $n$ denotes both a function $\mathbb{N}\to\mathbb{N}$ and an element of $\mathbb{N}$ (an index). We could denote the function by $k_i$; then the ordering would look $a_{k_1}< a_{k_2}<\dots <a_{k_n}$.

Second, the question is,

How many elements, in terms of n, are there in a total order on this set?

And what is a total order? It is a binary relation, i.e., a set of pairs of indices. If this is indeed what the question is asking and if the total order in question is non-strict (i.e., reflexive), then the answer is $n(n-1)/2$.

 

[Fernando Revilla]

Also, a couple of remarks

A couple of remarks. First, it's not good to write $n_n$: then $n$ denotes both a function $\mathbb{N}\to\mathbb{N}$ and an element of $\mathbb{N}$ (an index). We could denote the function by $k_i$; then the ordering would look $a_{k_1}< a_{k_2}<\dots <a_{k_n}$.

Yes, it is good. Easily understood, if $\sigma$ is a permutation on $\{1,2,\ldots,n\}$, $a_{n_k}$ is a notation for $a_{\sigma (k)}$

Second, the question is,And what is a total order? It is a binary relation, i.e., a set of pairs of indices. If this is indeed what the question is asking and if the total order in question is non-strict (i.e., reflexive), then the answer is $n(n-1)/2$.

My interpretation was: how many order relations in terms of $n$ are there on a set with $n$ elements? Also when I wrote there are $n$ elements in a total order relation I meant the number $n$ of elements in each permutation (which univoquely determine each total order relation).

 

[Evgeny.Makarov]

Easily understood, if $\sigma$ is a permutation on $\{1,2,\ldots,n\}$, $a_{n_k}$ is a notation for $a_{\sigma (k)}$.

Yes, $a_{n_k}$ is fine, but $a_{n_n}$ results in using $n$ to denote two different things, which is a name clash.

My interpretation was: how many order relations in terms of $n$ are there on a set with $n$ elements?

Yes, we provided several interpretations of what the question may mean. If the OP wants further clarification, he/she should say which interpretation is correct.

 

[Fernando Revilla]

Yes, $a_{n_k}$ is fine, but $a_{n_n}$ results in using $n$ to denote two different things, which is a name clash.

The third stage of knowledege (notations in this case) usually is similar to the first one. If you use the perspective of the second stage, then you have the risk of confusing the former with the latter.

 

[Daniela1]

Thanks so much Fernando for introduce me to this place. Also thanks both Fernando and Evgeny for answering my question. Now, this is my problem:

1) Actually the original question is: Let $$A$$ be a set containing $$n$$ elements. Prove that a total order on $$A$$ contains exactly $$\dfrac{1}{2} n(n-1)$$ order pairs.

2) My answer is exactly the same as Fernando. My first thought was then that I was missing something about understanding the definition of "total order". Then I decided to ask the question to compare answers.

3) These are my definitions just the way I understand them to be (please tell me if something is wrong):

- A total order on a set is a binary relation that is antisimetric, comparable, reflexive and transitive.
- A binary relation $$R$$ is antisimetric on $$X$$ if an only if $$\forall Y\forall Z(Y\in X\wedge Z\in X \wedge Y\neq Z \longrightarrow (Y,Z)\notin R \vee (Z,Y) \notin R)$$.
- A binary relation $$R$$ is comparable on $$X$$ if and only if $$\forall Y\forall Z (Y\in X \wedge Z\in X \wedge Y\neq Z\longrightarrow (Y,Z)\in R \vee (Z,Y)\in R)$$
- A binary relation $$R$$ is reflexive on $$X$$ if and only if $$\forall Y(Y\in X \longrightarrow (Y,Y)\in R)$$
- A binary relation is transitive on $$X$$ if and only if $$\forall Y, Z,K\in X((Y,Z)\in R \wedge (Z,K)\in R \longrightarrow (Y,K)\in R)$$

4.- Evgeny, could you please explain your answer. It would be great if you could compare both answers by using a set with few elements, let say $$\{X,Y,Z \}$$.

 

[Fernando Revilla]

1) Actually the original question is: Let $$A$$ be a set containing $$n$$ elements. Prove that a total order on $$A$$ contains exactly $$\dfrac{1}{2} n(n-1)$$ order pairs.

Hello Daniela, welcome to MHB!

That formula is not true. For example, the sequences $X<Y<Z$, $X<Z<Y,\ldots,Z<Y<X$ determine all the total order relations on $\{X,Y,Z \}$. That is $3!=6$. The elements of the order relation defined by $X<Y<Z$ (i.e. the pairs $(S,T)$ such that $S\le T$) are: $$(X,X),(Y,Y),(Z,Z), (X,Y),(X,Z),(Y,Z)$$ That is, $3+ \binom{3}{2}=3+\frac{3\cdot 2}{3}=3+3=6$ which is different from $\frac{1}{2}3(3-1)$. In general, the elements of a total order relation defined on a set with $n$ elements is $$n+\binom{n}{2}=n+\frac{n(n-1)}{2}=\frac{n(n+1)}{2}=\binom{n+1}{2}$$

P.S. The only way that the formula $\frac{1}{2} n(n-1)$ works is if we don't consider the elements of the diagonal, but in such a case, the reflexive property is not fulfilled.