# Linear Orders

• May 3rd 2009, 04:19 AM
kurac
Linear Orders
Im doing some self study and I would like to ask question about linear orders.

Listing all linear orders (total orders) of the set {a,b,c}:

Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.

Also, how many ways can one linear order a set with n elements?
I was thinking it would n x n different ways, because in above example with 3 elements i ordered it 9 times? I dont know how to prove this (im very bad at proofs!!!)
Does anyone know how to explain this with a small simple proof or explanation?

Much appreciated, Kurac.
• May 4th 2009, 01:05 PM
aleph1
Quote:

Originally Posted by kurac
Im doing some self study and I would like to ask question about linear orders.

Listing all linear orders (total orders) of the set {a,b,c}:

Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.

Also, how many ways can one linear order a set with n elements?
I was thinking it would n x n different ways, because in above example with 3 elements i ordered it 9 times? I dont know how to prove this (im very bad at proofs!!!)
Does anyone know how to explain this with a small simple proof or explanation?

Much appreciated, Kurac.

I am not sure what your notation means. Is (p,g) an open interval, a 2 space coordinate pair or possibly a set {p,q}? In wikipedia a linear order or total order is explained as a binary relation with operator ≤ .

Using that definition with the following relationship abc (1)

Then

aa since a = a (reflexivity)
ab by (1)
ac by (1) (transivity)
ba if and only if b = a which also satisfies (1) (antisymmetry)
b ≤ b since b = b (reflexivity)
bc by (1)
ca if and only if c = a which also satisfies (1) (antisymmetry)(transivity)
c ≤ b if and only if c = b which also satisfies (1) (antisymmetry)
c ≤ c since c = c (reflexivity)

All these 2-tuple relations are true for binary relationship ≤, with assumed ordering relation (1).

• May 4th 2009, 01:55 PM
Plato
Quote:

Originally Posted by kurac
Listing all linear orders (total orders) of the set {a,b,c}:

Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.

Self-study is often a very dangerous activity.
The above notation is an example: it is completely wrong.
A linear order (most often called a total order) on a set is a partial order in which any two terms in the set are comparable.
Now it is true that any relation is a set of ordered pairs.

This is for the sake of notation because any linear order is reflexive.
$\Delta = \left\{ {(a,a),(b,b),(c,c)} \right\}$, the diagonal of the set.

Consider the set $\{a,b,c\}$. Here is a linear order on the set $:\;\;b - c - a$.
Here is the set of pairs in that l.o. : $\Delta \cup \left\{ {(b,c),(b,a),(c,a)} \right\}$.
Note that there are six pairs.

Here is another example.
$\;\;c - b - a$, pairs $\Delta \cup \left\{ {(c,b),(c,a),(b,a)} \right\}$

In all the are $3!=6$ such linear orderings.

Let’s bump it up a couple of notches.
$\Delta = \left\{ {(a,a),(b,b),(c,c),(d,d),(e,e)} \right\}$, the diagonal of the set.

Consider the set $\{a,b,c,d,e\}$. Here is a linear order on the set $:\;\;e-b- c - a -d$.
Here is the set of pairs in that l.o. : $\Delta \cup \left\{ {(e,b),(e,c),(e,a),(e,d),(b,c),(b,a),(b,d),(c,a),( c,d),(a,d)} \right\}$.
Notice that there are 15 pairs in the linear ordering.
There are 5! such each with 15 pairs.

In general, on a set of n elements there are n! linear orderings with $n+\frac{n(n-1)}{2}$ pairs.
• May 4th 2009, 01:57 PM
HallsofIvy
As aleph1 says, your use of pairs like (a,a) or (a,b) is confusing. I think you mean that you have a set of three objects, {a, b, c}, and want orders like a< b< c, a< c< b, b< a< c, b< c< a, c< a< b, and c< b< a. Those are, in fact, the only linear orders on the set {a, b, c}. Notice that we could write those orders with the "<" understood: abc, acb, bac, bca, cab, cba. That is, linear orders are just permutations on the set. For a set with 3 members, there are 3!= 6 permutations and so 6 linear orders. For a set with n members, there are n! permutations and so n! linear orders.