Porządek częściowy, o którym była do tej pory mowa nie gwarantował, by można było porównywać dowolne elementy zbioru uporządkowanego. Ten punkt poświęcimy porządkom liniowym. Pozwalają one porównywać dowolne elementy zbioru, w którym są określone, tzn. dla dowolnych dwóch różnych elementów pozwolą ustalić, który z nich jest większy, a który mniejszy.

Przykład 6.5.1

1. Zbiór liczb rzeczywistych z relacją ≤ jest liniowo uporządkowany.
2. Relacja przedstawiona na rysunku 6.1.1 (d) jest relacją liniowego porządku: dowolne dwa elementy x, y są albo połączone strzałką od x do y albo strzałką od y do x. Jest to więc relacja spójna. Diagram Hassego dla tej relacji ma charakterystyczny, dla wszystkich relacji liniowego porządku, kształt - jest to linia pionowa z zaznaczonymi na niej wierzchołkami.
3. Relacja określona w zbiorze liter {a,...,z} w taki sposób, że x₁ ≤ x₂ wttw litera x₁ poprzedza w alfabecie literę x₂ albo x₁=x₂, jest relacją liniowego porządku.
4. Każda lista obiektów a₁, a₂, a₃..., wyznacza w zbiorze tych obiektów relację liniowego porządku wynikającą z kolejności obiektów na liście: a_i ≤ a_j wttw i ≤ j.

Pytanie 6.5.1: Przy okrągłym stole zasiadło n osobistości. Czy porządek osób wyznaczony przez zajmowane miejsce następująco " a ≤ b wttw a siedzi na lewo od b" jest porządkiem liniowym?

Następujący lemat pokazuje na istotną różnicę między zbiorami uporządkowanymi częściowo i uporządkowanymi liniowo. Zacierają się różnice między elementami maksymalnym i największym oraz minimalnym i najmniejszym.

Do dowodu tego lematu wrócimy w wykładzie siódmym.

Element największy zbioru liniowo uporządkowanego nazywamy ostatnim. Element najmniejszy zbioru liniowo uporządkowanego nazywamy pierwszym.

W zbiorze liczb rzeczywistych liniowo uporządkowanym przez relację ≤ nie ma ani elementu pierwszego ani ostatniego. Zbiór liczb naturalnych, jako podzbiór zbioru liczb rzeczywistych, jest liniowo uporządkowany przez relację ≤ . W tym zbiorze mamy element pierwszy ale nie mamy elementu ostatniego. Natomiast w zbiorze {1,2,3,4...9} uporządkowanym liniowo przez relację ≤ jest element pierwszy, a mianowicie 1 i jest element ostatni, a mianowicie 9.

Pytanie 6.5.2 : Czy istnieje taki niepusty i skończony zbiór liniowo uporządkowany, w którym nie ma elementu pierwszego lub ostatniego? Czy słowo "skończony" jest istotne w tym pytaniu?

Niech <X, ≤ > będzie zbiorem częściowo uporządkowanym. Nawet jeśli X nie jest liniowo uporządkowany, to istnieją w nim podzbiory, które są liniowo uporządkowane. Takie niepuste podzbiory nazywamy łańcuchami.

Jako przykład weźmy graf na rysunku 6.3.1. Każdy ze zbiorów {a,c,e}, {b,c,d} {a,c,d} jest łańcuchem, chociaż relacja przedstawiona na tym rysunku nie jest relacją liniowego porządku.

Chociaż zbiór <N,| > nie jest liniowo uporządkowany, to jego podzbiory {5,15,30, 60}, {3ⁿ : n ∈ N} , czy {2 ⁿ : n ∈ N} są łańcuchami. Dwa ostatnie z wymienionych są maksymalne w tym sensie, że nie da się ich już rozszerzyć.

Uwaga.   Każdy podzbiór zbioru liniowo uporządkowanego jest sam liniowo uporządkowany.

Rzeczywiście, jeśli ≤ jest liniowym porządkiem w X, a A jest podzbiorem X, to przyjmując jako ≤ ' relację ≤ ∩ (A × A), czyli obcięcie relacji ≤ do produktu A × A, otrzymujemy relację porządku liniowego w A.

Wynika stąd, że zbiory <N, ≤ >, <Q, ≤ >, jako podzbiory R, są liniowo uporządkowane. Jest jednak olbrzymia różnica między relacjami porządku w tych zbiorach. Otóż porządek ≤ w zbiorze liczb wymiernych Q ma własność gęstości (podobnie jak R), tzn. między dowolnymi dwoma różnymi elementami zawsze znajdzie się trzeci od nich różny. Nie jest to prawda w zbiorze liczb naturalnych, gdzie każda liczba ma swojego bezpośredniego następnika w sensie relacji ≤ . Porządek ≤ w N ma za to inną ważną własność dobrego ufundowania:

(*) każdy niepusty podzbiór ma element pierwszy.

Nie można tego powiedzieć ani o R ani o zbiorze liczb wymiernych Q.

Zbiory częściowo uporządkowane, które mają własność (*) nazywamy dobrze ufundowanymi. W zbiorze uporządkowanym dobrze ufundowanym nie można znaleźć nieskończonego ciągu malejącego.

Przykładem zbioru dobrze uporządkowanego jest zbiór liczb naturalnych z relacją ≤ . Innym przykładem zbioru dobrze uporządkowanego może być dowolny liniowo uporządkowany, skończony zbiór.