« poprzedni punkt | następny punkt » |
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
Przykład 5.6
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
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 » |