« poprzedni punkt  następny punkt »


5. Porządek liniowy i dobry porządek

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.

Definicja 5.7

Relację binarną á w zbiorze X nazywamy porządkiem liniowym wtedy i tylko wtedy, gdy

  1. á jest relacją porządku częściowego,
  2. á jest relacją spójną, tzn. dla dowolnych x, y Î X, albo x á y albo y á x albo x = y.

Przykład 5.6

  1. Zbiór liczb rzeczywistych z relacją £ jest liniowo uporządkowany.
  2. Relacja przedstawiona na rysunku 5.1d 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 x1 á x2 wttw litera x1 poprzedza w alfabecie literę x2 albo x1=x2, jest relacją liniowego porządku.
  4. Każda lista obiektów a1, a2, a3..., wyznacza w zbiorze tych obiektów relację liniowego porządku wynikającą z kolejności obiektów na liście: ai á aj wttw i £ j.

Pytanie 9: 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.

Lemat 5.1

Niech < X, á > będzie zbiorem liniowo uporządkowanym, wtedy

  1. jeśli w X istnieje element maksymalny, to jest on elementem największym,
  2. jeśli w X istnieje element minimalny, to jest on elementem 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 10 : 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?

Zobacz odpowiedź

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 5.3. 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}, {3n : n Î N} , czy {2 n : 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.

Definicja 5.8

Relacją binarną w X nazywamy dobrym porządkiem wtedy i tylko wtedy, gdy jest to porządek liniowy i dobrze ufundowany.

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.


« poprzedni punkt  następny punkt »