A partial order relation does not guarantee that any two elements are comparable by this order. The present section is devoted to linear orders. A linear order allows to compare any pair of elements of an ordered set and to establish which of them is greater.

 If  X is a set in which a linear order is defined, then we say that X is a linearly ordered set.

Example 5.5.1

1. The set R of real numbers with relation  ≤ is linearly ordered.
2. The relation shown on Figure  5.1.1(d) is a linear order: note that for two elements  x, y either an arrow leads from x to y or from y to x. Hence, the relation satisfies the connectivity condition. The Hasse diagram of this relation has a shape typical for all linear orderings - it is a perpendicular line with elements on it.
3. The relation defined in the set of letters {a,...,z} in such a way that x₁ ≤ x₂ iff the letter x₁ precedes in the alphabet the letter x₂ or x₁ = x₂, is the   linear order.
4. Every sequence of objects a₁, a₂, a₃..., determines in the set of these objects a realation of linear order: we put a_i ≤ a_j iff i ≤ j .
   

Question 5.5.1 At a round table there sit n persons. An ordering relation is defined by the following formula " a ≤ b iff a sits on the left of b". Is this relation a linear order?. 

The following lemma illustrates the difference between partial orders and linear orders. In a set which is linearly ordered the notions of maximal element and of greatest element coincide. The same applies to the notions of the least element and the minimal element.

A proof of this lemma will be given later.

The least element of a linearly ordered set is also called the first element of the set. The greatest element of a linearly ordered set is also called the last element of the set.

Example 5.5.2

1. The set R of real numbers linearly ordered by the relation ≤  has neither the first element nor the last one.
2. The set N of natural numbers ordered by the same relation ≤ has the first element but there is no last element.
3. The set  {1,2,3,4...9} ordered by the relation ≤ has the first element, namely 1 and the last element, namely 9.

Question 5.5.2  Does there exist a non-empty and finite, linearly ordered set which has neither the first nor the last element?
Consider the same question without the word "finite".

Let <X, ≤ > be a partially ordered set. A non-empty linearly order subset of the set X is called a chain. 

Example 5.5.3

1. Consider the graph from the Figure  5.3.1. Each of the subsets {a,c,e}, {b,c,d}, {a,c,d} is a chain, but the whole set is not a linearly ordered set.
2. The set  <N,| > is not a linearly ordered set, the following subsets  {5,15,30, 60}, {3ⁿ : n ∈ N}, {2 ⁿ : n ∈ N} are chains. The last and last but one subsets are maximal, i.e. there exists not a proper superset of  the set {3ⁿ : n ∈ N} which is a chain.

Remark.

Each subset of a linearly ordered set is a linearly ordered set.

Indeed, if a relation  ≤ is a linear order relation in the set X and A is a subset of X then the relation  ≤ ' defined as ≤ ∩ (A × A),  is a linear ordering relation in A.

As a consequence, both sets <N, ≤ >, <Q, ≤ >, are linearly ordered sets since both of them are subsets of the linearly ordered set R of real numbers. They differ essentially, however: namely the relation ≤ in Q is dense, i.e. for any two elements x and y of the set there exists a third one that differs from them. It is not true for the set of natural numbers where each element has a direct successor.

The set of natural numbers has another important property: it is a well founded set because:

(*) every non-empty subset of it has the first element.

The sets R and Q do not have this property.

Every set which is partially ordered and has the property  (*) is called a well founded set. If an ordered set X is well founded it does not contain an infinite descending subset of X.

The set N of natural numbers with the relation  ≤ is an example of a well ordered set.
Any finite, linearly ordered set is also a well founded set.

« previous section

next section »