Thread: 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.

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 a ≤ b ≤ c (1)

Then

a ≤ a since a = a (reflexivity)
a ≤ b by (1)
a ≤ c by (1) (transivity)
b ≤ a if and only if b = a which also satisfies (1) (antisymmetry)
b ≤ b since b = b (reflexivity)
b ≤ c by (1)
c ≤ a 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).

If you intend something else, please explain your notation.

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.
, the diagonal of the set.

Consider the set . Here is a linear order on the set .
Here is the set of pairs in that l.o. : .
Note that there are six pairs.

Here is another example.
, pairs

In all the are such linear orderings.


Let’s bump it up a couple of notches.
, the diagonal of the set.

Consider the set . Here is a linear order on the set .
Here is the set of pairs in that l.o. : .
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 pairs.

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.