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
.
jest największy (względem
)
(tzn. `` jest większy w sensie
od wszystkich innych elementów
'').
1.
jest najmniejszy (względem
)
(tzn. `` jest mniejszy w sensie
od wszystkich innych elementów
'').
2.
jest maksymalny (względem
)
(tzn. ``w
nie ma elementu większego od w sensie
'').
3.
jest minimalny (względem
)
(tzn. ``w
nie ma elementu mniejszego od w sensie
'').
4.
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óźniejszych (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
.
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.)
1.
jest ograniczeniem górnym zbioru
(tzn. jest równe lub większe (w sensie
) od wszystkich elementów
).
2.
jest ograniczeniem dolnym zbioru
(tzn. jest równe lub mniejsze (w sensie
) od wszystkich elementów
).
3.
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
)
.
4.
jest kresem dolnym zbioru
jest największym ograniczeniem dolnym zbioru
(względem
)
.
5.
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 rzeczywistych
8.3
znajdujemy 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:
(przeciwzwrotność)
1.
(ścisła antysymetryczność)
2.
(przechodniość)
3.
(ścisła spójność).
4.
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
.
Relacje porządku
http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skry...