13.pdf

8. UPORZĄDKOWANIE ZBIORÓW

8.1. ZBIORY UPORZĄDKOWANE

Zbiory,zktórymimamydoczynieniawpraktycenaukowejroz-

ważającjakąśdziedzinętonietylkoprostenagromadzenieobiektów.

Zwyklemiędzytymiobiektamizachodząróżnegorodzajustosunki,w

szczególnościobiektytesąjakośuporządkowane,np.międzyliczbami

zachodzistosunekwiększości.Takjestzresztąnietylkowdziedzinach

matematycznych, np. w zbiorze ludzi określony jest stosunek bycia

potomkiem.Rolaiznaczenieuporządkowaniastałysięźródłemteo-

riiporządków.Cantor,którybyłnietylkotwórcąogólnejteoriimno-

gości, lecz także teorii zbiorów uporządkowanych, pojmował jąjako

teorięabstrahującąodjakościprzedmiotówtworzącychzbiory,alenie

od ich porządku. Ideę tę wyrażała pojedyńcza kreska w oznaczeniu

typuporządkowego.

(DEF. relacji porządkujących) Relacja R jest relacją porządkującą

zbiór X wtedyitylkowtedy,gdyjestzwrotna,przechodniaiantysy-

metryczna,czyliwtedyitylkowtedy,gdy

1 . ∀ x ∈ X. ( xRx ) ,

zwrotność,

2 . ∀ x,y,z ∈ X. [( xRy ∧ yRz )

⇒ xRz ] ,

przechodniość,

3 . ∀ x,y ∈ X. [( xRy )

∧

( yRx )

⇒

( x = y )] , antysymetryczność,

czyli

R ∈ REF ∩ TRANS ∩ ANTYSYM 155 .

155 Przezniektórychautorówrelacjespełniającewarunki1–3określanesąjako

relacje częściowoporządkujące .

8.1. ZBIORYUPORZĄDKOWANE

393

Warunki,októrychmowawdeﬁnicjimożemyrównoważniezapi-

saćnastępująco,odpowiednio:

1. I X ⊆ R ,

2. R ◦ R ⊆ R ,

3. R ∩ R − 1 ⊆ I X .

Zamiast xRy ,gdy R jest relacją porządkującą, piszemy: x ≤ y i

czytamy: x jestzawarte w y lubteż: y zawiera x .

Należytuzauważyć,żerelacjeporządkującetopewnaklasarela-

cji.Relacja,któranależydotejklasy,czylijestrelacjąporządkującą,

możemiećjeszczeinnewłasnościniżwskazanewdeﬁnicjirelacjipo-

rządkującej.

(DEF.zbioruuporządkowanego)Gdy R ( ⊆ X × X ) jestrelacjąporząd-

kującą,tomówimy,że R porządkuje zbiór X ,aparauporządkowana

( X,R ) to zbióruporządkowany .

Należypamiętać,żeuporządkowanieniejestwłasnościąsamego

tylko zbioru; jeden i ten sam zbiór może być uporządkowany przez

różnerelacje.

PRZYKŁADY

1.Niech R będzieniepustąrodzinąpodzbiorówzbioru X .Relacja

inkluzji ⊆ porządkujezbiór R .

Dladowolnychpodzbiorów A,B,C zbioru X mamybowiem: A ⊆

A (zwrotność), A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C (przechodniość), A ⊆ B ∧ B ⊆

A ⇒ A = B (antysymetryczność).

2.Zbiór N wszystkichliczbnaturalnychuporządkowanyjestprzez

relacjępodzielności | ( ∀ n,m ∈ N . [ n | m ⇔∃ k ∈ N . ( k · n = m )] ;czyli n | m

wtedyitylkowtedy,gdy n jestdzielnikiem m ).

Dla dowolnych liczb naturalnych n,m,k prawdą jest, że: n | n

(zwrotność), ( n | m ∧ m | k ) ⇒ n | k (przechodniość), ( n | m ∧ m | n ) ⇒ n = m

(antysymetryczność).

3. Relacja ≤ niewiększości porządkuje dowolny niepusty zbiór

liczbrzeczywistych.

394

8. UPORZĄDKOWANIEZBIORÓW

Dla dowolnych liczb rzeczywistych x,y,z prawdą jest, że: x ≤ x

(zwrotność), x ≤ y ∧ y ≤ z ⇒ x ≤ z (przechodniość), x ≤ y ∧ y ≤ x ⇒

x = y (antysymetryczność).

4.Relacjaporządkupreﬁksowegoporządkujezbiórsłów.

Niech A będzie dowolnym zbiorem a A ∗ niech będzie zbiorem

wszystkichitylkoskończonychciągówelementów A ( słowemnad A ).

Ciągpusty, słowopuste ,to ε . Złożeniemsłów w 1 [= ( a 1 ,...,a n ) ]i w 2

[= ( b 1 ,...,b m ) ]jestsłowo w 1 w 2 [= ( a 1 ,...,a n ,b 1 ,...,b m ) ].Słowo w jest

preﬁksem słowa u , w ≤ u ,wtedyitylkowtedy,gdyistniejesłowo w 1

takie,że u = ww 1 .

Zauważmy,żerelacja ≤ ( ⊂ A ∗ × A ∗ ) ( porządek preﬁksowy )jest:

(a) zwrotna–każdesłowojestswoimpreﬁksem,

(b) antysymetryczna – jeśli w jest preﬁksem u ,a u jest preﬁksem

w , to zgodnie z deﬁnicją mamy: u = ww 1 oraz w = uu 1 .Ztego

u =( uu 1 ) w 1 . Ponieważ składanie jest łączne, więc u 1 w 1 = ε ,az

tego u 1 = ε oraz w 1 = ε .Ostateczniemamy: u = w .

5.Relacjaporządkuleksykograﬁcznegonad ( A, ≤ ) porządkuje A .

Niech ≤ ( ⊆ A × A ) będzieporządkiem.Niechdla w =( a 1 ,...,a i ,

...,a n ) , w ( i )= a i .

Relację ( ⊆ A ∗ × A ∗ ) deﬁnujemynastępująco.

Dlakażdego w,u ( ∈ A ∗ ) : w jestpreﬁksem u lubistnieje i takie,że

w ( i ) <u ( i ) idlakażdego j<i ,zachodzi w ( j )= u ( j ) .

Relacja torelacja porządkuleksykograﬁcznegonad ( A, ≤ ) indu-

kowanaprzez ≤ .

Relacjaporządkuleksykograﬁcznegojestzwrotna,bokażdesłowo

jestswoimpreﬁksem,

Dlapokazaniaantysymetrycznościzałóżmy,że w u i u w .

Jeżeli w jest preﬁksem u , to nie istnieje i takie, że u ( i ) <w ( i ) ,

zatem u jestpreﬁksem w .Awięc w = u .

Jeżeli u jestpreﬁksem w ,tosytuacjajestanalogicznadopoprzed-

niej.

8.1. ZBIORYUPORZĄDKOWANE

395

Pozostaje do rozważenia wypadek, gdy zarówno w nie jest pre-

ﬁksem u ,ani u nie jest preﬁksem w . Niech więc istnieje i takie, że

w ( i ) <u ( i ) oraz dla każdego j , jeżeli j<i ,to w ( j )= u ( j ) . Ponadto

niechistnieje i 1 takie,że u ( i 1 ) <w ( i 1 ) orazdlakażdego j ,jeżeli j<i 1 ,

to u ( j )= w ( j ) .Ztegomamy,że i = i 1 .Niejestjednakmożliwe,aby

w ( i ) <u ( i ) i u ( i ) <w ( i ) .Wykluczonejestwięc,że w niejestpreﬁksem

u i u niejestpreﬁksem w .

Ostateczniemamywięc,żejeżeli w u i u w ,to w = u .

Pozostaje jeszcze do udowodnienia przechodniość relacji po-

rządku leksykograﬁcznego, .Niech w u i u v .Rozważymy

wszystkiemożliwości,wynikającezdeﬁnicji .

(a)Niech w będziepreﬁksem u a u preﬁksem v .Zzałożeniawy-

nika,że w jestpreﬁksem v ,azatem w v .

(b) Niech w będzie preﬁksem u adla u i v istnieje takie i ,że

u ( i ) <v ( i ) oraz dla każdego j<i , u ( j )= v ( j ) . W opisanej sytuacji

możebyćtak,że w jestpreﬁksem v ,awówczas w v .Jeżeli w niejest

preﬁksem v ,to w ( i ) <v ( i ) idlakażdego j<i , w ( j )= v ( j ) ,awówczas

ww v .

j<i , w ( j )= u ( j ) .Niech u będziepreﬁksem v .Wtymwypadkumamy,

że w ( i ) <v ( i ) idlakażdego j<i , w ( j )= v ( j ) .Zatem w v .

(d)Ostatniamożliwośćtowypadek,gdydla w i u istnieje i takie,

że w ( i ) <u ( i ) i dla każdego j<i , w ( j )= u ( j ) oraz dla u i v istnieje

takie i 1 ,że u ( i 1 ) <v ( i 1 ) orazdlakażdego j<i 1 , u ( j )= v ( j ) .Niech i 2

będzieniemniejszą zliczb i oraz i 1 .Mamy,że w ( i 2 ) <v ( i 2 ) oraz dla

każdego j<i 2 , w ( j )= v ( j ) .Zatem w v .

Napodstawiea–brelacja jestprzechodnia.

(DEF. ≺ , poprzedzania) x ≺ y , x poprzedza y ( x,y ∈ X )wzbiorze

uporządkowanym ( X, ≤ ) wtedyitylkowtedy,gdy x ≤ y ∧ x = y ,czyli

∀ x,y ∈ X. [( x ≺ y )

⇔

( x ≤ y )

( x = y )] .

Jesttopoprawnadeﬁnicjaliterypredykatowej„ ≺ ”.

TWIERDZENIE1

∧¬

396

8. UPORZĄDKOWANIEZBIORÓW

Jeżelirelacja ≤ porządkuje zbiór X ,torelacja ≺ jestprzeciwzw-

rotna i przechodnia w X ,czyli

≤∈ REF ∩ TRANS ∩ ANTYSYM ⇒≺∈ IRREF ∩ TRANS.

DOWÓD

Wpierw wykażmy przeciwzwrotność ≺ .Niech ≤ będzie relacją

porządkującąwzbiorze X .

Zdeﬁnicjirelacjiporządkującej:

1. ( x ≤ x ) .

Zdeﬁnicji ≺ mamy:

2. ( x ≺ x ) ⇔ [( x ≤ x ) ∧¬ ( x = x )] .

Z1i2dostajemy

3. ¬ ( x = x ) ⇒ ( x ≺ x ) .

Ponieważ

4. x = x ,

więcz3i4mamy

5. ¬ ( x ≺ x ) .

Terazwykażemyprzechodniość ≺ .Załóżmy,że

1. x ≺ y ∧ y ≺ z .

Z1ideﬁnicji ≺ mamy

2. x ≤ y ∧ y ≤ z .

Zprzechodniości ≤ i2dostajemy

3. x ≤ z .

Zprzeciwzwrotności ≺ i1mamy

4. ¬ ( x = y ) ,

oraz

5. ¬ ( y = z ) .

Z2dostajemy

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: