Relacje porządku
Potocznie mówimy, \e zbiór skończony jest w uporządkowany, gdy jego elementy mo\emy uło\yć w
szereg od ``najmniejszego'' do ``największego''. Dla określenia takiego porządku istotna jest relacja ``
poprzedza '', którą często symbolicznie zapisujemy w postaci . Taka relacja porządku jest
określona na zbiorze liczb rzeczywistych . Analizując jej własności formułujemy ogólną definicję.
Definicja 8..1 Załó\my, \e jest relacją na zbiorze oraz .
(1) Relacja na zbiorze jest relacją liniowego porządku (lub krócej: liniowym porządkiem), gdy jest
zwrotna, przechodnia, antysymetryczna i spójna.
(2) Jeśli relacja ma trzy pierwsze własności, nazywamy ją relacją częściowego porządku (lub krócej:
częściowym porządkiem).
Załó\my, \e jest częściowym porządkiem na zbiorze .
(3) Gdy i , mówimy, \e jest mniejszy od (poprzedza ) i jest większy od (w sensie
częściowego porządku ). Dodatkowo, jeśli nie istnieje element taki, \e , to
mówimy, \e jest następnikiem , zaś poprzednikiem .
(4) Mówimy, \e elementy są porównywalne w tym częściowym porządku, gdy lub .
Widzimy więc, \e w częściowym porządku nie zawsze wszystkie elementy są porównywalne, w
przeciwieństwie do liniowego porządku, gdzie spójność gwarantuje porównywalność ka\dych dwóch
elementów.
Przykład liniowego porządku to relacja na . Ka\dy liniowy porządek jest w szczególności częściowy.
Przykład częściowego porządku, który nie jest liniowy, to relacja podzielności na zbiorze czy te\
relacja inkluzji na zbiorze .
Relacje porządku często oznacza się symbolem lub symbolami podobnymi.
Uwaga 8..2 Jeśli jest relacją częściowego [odpowiednio: liniowego] porządku na zbiorze , to dla
relacja ograniczona równie\ jest porządkiem częściowym [odpowiednio: liniowym].
Relacje porządku na zbiorze skończonym wygodnie jest przedstawiać w formie graficznej, w postaci
diagramów Hassego. Diagram Hassego składa się z pewnej liczby punktów odpowiadających elementom
naszego zbioru. Pary punktów odpowiadające parom (poprzednik, następnik) są połączone niepoziomymi
odcinkami. Element jest mniejszy od elementu dokładnie wtedy, gdy na rysunku mo\na dojść od
punktu odpowiadającego elementowi do punktu odpowiadającego elementowi wzdłu\ odcinków idąc
cały czas w górę.
Przykład 1. Niech . Na rysunku
przedstawiona jest relacja
Oznaczając relację symbolem mamy więc:
Relacja ta jest częściowym porządkiem, nie jest jednak liniowym porządkiem, gdy\ nie jest spójna (np.
nie są porównywalne).
Przykład 2. Rysunek
określa liniowy porządek na zbiorze taki, \e i ogólniej
liczba napisana ni\ej jest mniejsza od liczby napisanej wy\ej. Oczywiście ró\ni się od zwykłego
porządku na zbiorze .
Przykład 3. Niech . Rysunek
przedstawia relację podzielności , która jest częściowym porządkiem na zbiorze (jako
ograniczenie relacji na zbiorze do zbioru ).
Definicja 8..3 Niech będzie relacją częściowego porządku na . Niech .
1. jest największy (względem )
(tzn. `` jest większy w sensie od wszystkich innych elementów '').
2. jest najmniejszy (względem )
(tzn. `` jest mniejszy w sensie od wszystkich innych elementów '').
3. jest maksymalny (względem )
(tzn. ``w nie ma elementu większego od w sensie '').
4. jest minimalny (względem )
(tzn. ``w nie ma elementu mniejszego od w sensie '').
W przykładzie 1. elementy i są maksymalne, elementy są minimalne, nie ma ani elementów
największych ani najmniejszych.
W przykładzie 2. jest elementem najmniejszym i jedynym elementem minimalnym, jest elementem
największym i jedynym elementem maksymalnym.
W przykładzie 3. jest elementem największym i jedynym maksymalnym, zaś elementem
najmniejszym i jedynym minimalnym.
Uwaga 8..4 (1) Jeśli jest największy, to jest maksymalny.
(2) Jeśli jest najmniejszy, to jest minimalny.
(3) Jeśli w istnieje element największy, to jest on jedyny, ponadto w tym przypadku jest on równie\
jedynym elementem maksymalnym.
(4) Jeśli w istnieje element najmniejszy, to jest on jedyny, ponadto w tym przypadku jest on równie\
jedynym elementem minimalnym.
Dowód. (1) Załó\my, \e jest największy. Jest więc większy w sensie od wszystkich innych
elementów . Dlatego nie ma w elementu większego od w sensie . To potoczne rozumowanie
mo\e być jednak mylące, gdy\ mo\e być odczytywane w oparciu o nieadekwatne w tym przypadku
intuicje na temat liniowego porządku liczb rzeczywistych (tzn. czytelnik mo\e być nieświadom, gdzie w
dowodzie u\ywa się własności częściowego porządku). Dlatego przeprowadzimy dowód bardziej
formalnie.
Załó\my więc jeszcze raz, \e jest największy, tzn.
(a)
dla ka\dego mamy .
By pokazać, \e jest maksymalny, musimy udowodnić, \e
czyli \e
(b)
dla ka\dego , je\eli , to .
W tym celu rozwa\amy dowolne . Zakładając, \e , chcemy pokazać, \e (tzn. chcemy
pokazać prawdziwość implikacji ). Przypuśćmy więc, \e . Z punktu (a) dostajemy te\,
\e . Warunek antysymetryczności daje nam, \e i implikuje . Dlatego mamy ,
co kończy dowód (b) i (1).
Dowody pozostałych punktów pozostawiamy jako ćwiczenie.
Załó\my teraz, \e jest liniowym porządkiem na zbiorze skończonym . Rozumując podobnie jak w
dowodzie uwagi 8.4 mo\na udowodnić, \e wtedy istnieją w elementy największe i najmniejsze (na
mocy uwagi 8.4 są one jedyne). Wybieramy więc kolejno jako element najmniejszy w , jako
element najmniejszy w zbiorze (względem relacji ), jako element najmniejszy w
zbiorze (względem relacji ), i tak dalej. W ten sposób po skończeniu wielu
krokach wyczerpiemy zbiór układając jego elementy w uporządkowany (w sensie ) szereg
, od najmniejszego do największego. W szeregu tym elementy wcześniejsze będą mniejsze w sensie od
elementów pózniejszych (na mocy przechodniości). Odpowiada to dobrze intuicji związanej ze zwykłym
liniowym uporządkowaniem liczb rzeczywistych. Uzasadnia to poprawność naszej definicji liniowego
porządku.
Definicja 8..5 Załó\my, \e jest częściowym porządkiem na zbiorze , i .
1. jest łańcuchem
(Jest to warunek spójności, jedyny brakujący do tego, by była liniowym porządkiem, dlatego te\
w tym przypadku warunek ten jest równowa\ny temu, \e jest liniowym porządkiem.)
2. jest ograniczeniem górnym zbioru
(tzn. jest równe lub większe (w sensie ) od wszystkich elementów ).
3. jest ograniczeniem dolnym zbioru
(tzn. jest równe lub mniejsze (w sensie ) od wszystkich elementów ).
4. jest kresem górnym zbioru jest najmniejszym ograniczeniem górnym zbioru .
Symbolicznie warunek ten mo\na zapisać następująco:
Mówi on po pierwsze, \e jest ograniczeniem górnym zbioru , a następnie, \e dla dowolnego ,
jeśli jest ograniczeniem górnym , to jest mniejsze lub równe (w sensie ) .
5. jest kresem dolnym zbioru jest największym ograniczeniem dolnym zbioru (względem
) .
Badanie istnienia ograniczeń i kresów zbioru wymaga często nieco wysiłku.
Przykład 4. Rozwa\my znów relację podzielności na zbiorze . Zbiór
zło\ony z i kolejnych potęg dwójki jest łańcuchem w tym częściowym porządku. Istotnie, jest on
liniowo uporządkowany przez relację podzielności. Zbadamy istnienie ograniczeń i kresów górnych i
dolnych.
Ograniczenia dolne. Liczba naturalna jest ograniczeniem dolnym zbioru (w sensie relacji
podzielności) dokładnie wtedy, gdy dla wszystkich mamy , tzn. gdy dzieli wszystkie
liczby ze zbioru . Widzimy, \e jedyna taka liczba to . Zatem jest jedynym ograniczeniem dolnym
zbioru , jest w związku z tym największym (w sensie relacji podzielności) takim ograniczeniem czyli jest
kresem dolnym zbioru .
Ograniczenia górne. Liczba naturalna jest ograniczeniem górnym zbioru ( w sensie relacji
podzielności) dokładnie wtedy, gdy dzieli się przez wszystkie liczby ze zbioru . Widzimy, \e jedyną taką
liczbą jest . Jest więc ona tak\e kresem górnym zbioru .
Przykład 5. Rozwa\my zwykły porządek na zbiorze liczb rzeczywistych . Jest to liniowy porządek,
więc zarówno zbiór , jak i jego ka\dy podzbiór, jest tu łańcuchem. Niech
Znajdziemy kresy dolny i górny zbioru .
Ograniczenia dolne. Niech . Dowodzimy, \e jest ograniczeniem dolnym zbioru .
. Załó\my, \e . Wtedy oczywiście dla wszystkich , gdy\ wszystkie liczby ze zbioru
są . Zatem jest ograniczeniem dolnym zbioru .
Nie wprost. Przypuśćmy, \e jest ograniczeniem dolnym zbioru oraz nieprawda, \e , to
znaczy mamy . Korzystając z własności liczb rzeczywistych8.3znajdujemy liczbę naturalną taką,
\e . Ale , więc skoro ogranicza z dołu zbiór , to . Uzyskana
sprzeczność kończy dowód .
Widzimy, \e w zbiorze ograniczeń dolnych zbioru istnieje liczba największa: jest to . Dlatego jest
kresem dolnym zbioru .
Podobnie pokazujemy, \e jest kresem górnym zbioru . Szczegóły pozostawiamy jako ćwiczenie.
Nasza definicja relacji liniowego porządku odzwierciedla własności relacji na . Definiuje się równie\
tak zwane relacje ścisłego porządku liniowego (i częściowego), odpowiadające własnościom relacji na
. Mianowicie, mówimy, \e relacja na zbiorze jest relacją ścisłego porządku liniowego, gdy ma
następujące własności:
Relacje porządku http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skry...
1. (przeciwzwrotność)
2. (ścisła antysymetryczność)
3. (przechodniość)
4. (ścisła spójność).
Gdy relacja spełnia warunki 1-3, nazywamy ją ścisłym częściowym porządkiem.
Następująca uwaga pokazuje związek między porządkami i ścisłymi porządkami. Jej dowód opiera sie na
spostrze\eniu, \e w przypadku liczb rzeczywistych mamy
Uwaga 8..6 jest relacją ścisłego częściowego [odpowiednio: liniowego] porządku na jest
przeciwzwrotna i jest relacją częściowego [odpowiednio: liniowego]
porządku na .
Wyszukiwarka
Podobne podstrony:
7 Funkcje,relacje i porządki08 Nowy Porządek Świata08 Porządki w Shire08 1 Kwiecień 1996 Zdjąć Czeczenię z porządku dniaTI 99 08 19 B M pl(1)ei 05 08 s029Wyklad 2 PNOP 08 9 zaoczneEgzamin 08 zbior zadan i pytan4 Relacja człowiek środowiskoniezbednik wychowawcy, pedagoga i psychologa 08 4 (1)Kallysten Po wyjęciu z pudełka 08więcej podobnych podstron