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...