”Wst¸ep do Teorii Mnogości”, rok akademicki 2009/2010

12. Relacje porz¸adkuj¸ace

Zadanie 12.1 Relacja R jest określona w zbiorze Z nast¸epuj¸aco:

xRy ⇔ |x| ≤ |y| dla x, y ∈ Z .

Czy (Z , R) jest cz¸eściowym (liniowym) porz¸adkiem?

Zadanie 12.2 Czy relacja podzielności w zbiorze Z jest relacj¸a cz¸eściowego porz¸adku?

Zadanie 12.3 Relacja R jest określona w zbiorze R nast¸epuj¸aco:

(a) xRy ⇔ x 2 < y 2;

(b) xRy ⇔ x 2 ≤ y 2;

(c) xRy ⇔ x 3 < y 3;

(d) xRy ⇔ x 3 ≤ y 3,

dla x, y ∈ R. Czy R jest relacj¸a cz¸eściowego (liniowego) porz¸adku w zbiorze R?

Zadanie 12.4 W zbiorze X = { 2 , 3 , . . . , 15 } rozważamy relacj¸e podzielności.

(a) Narysować diagram tej relacji.

(b) Wskazać elementy wyróżnione.

(c) Wskazać wszystkie Ãlańcuchy dÃlugości 3.

Zadanie 12.5 Zbadać, czy jeżeli ( X, R) jest zbiorem cz¸eściowo (liniowo) uporz¸adkowanym, to zbiór dualny1 jest zbiorem cz¸eściowo (liniowo) uporz¸adkowanym.

Zadanie 12.6 Niech R i S b¸ed¸a relacjami cz¸eściowo porz¸adkuj¸acymi zbiór X. Czy relacjami cz¸eściowo porz¸adkuj¸acymi zbiór X s¸a relacje:

(a) R ∪ S;

(b) R ∩ S;

(c) R \ S;

(d) S ◦ R.

Zadanie 12.7 W zbiorze RN1, gdzie N1 = N \ { 0 }, określamy relacj¸e

{an}R{bn} ⇔ ∃ k ∈ N1 , ∀ n ∈ N1 ( n ≥ k ⇒ an ≤ bn)

dla {an}, {bn} ⊂ RN1. Czy relacja R cz¸eściowo porz¸adkuje zbiór RN1?

Zadanie 12.8 W zbiorze NN określamy relacj¸e R cz¸eściowego porz¸adku

f Rg ⇔ ∀ n ∈ N f ( n) ≤ g( n)

dla f , g ∈ NN.

(a) Wskazać elementy wyróżnione w zbiorze (NN , R).

(b) Wskazać w tym zbiorze nieskończony Ãlańcuch.

(c) Czy zbiór (NN , R) jest liniowo uporz¸adkowany?

Zadanie 12.9 Niech ( X, R) i ( Y, S) b¸ed¸a zbiorami cz¸eściowo uporz¸adkowanymi. Niech f : X → Y b¸edzie surjekcj¸a speÃlniaj¸ac¸a warunek

∀ x 1 , x 2 ∈ X ( x 1 R x 2 ⇐⇒ f( x 1) S f( x 2)) .

Udowodnić, że f jest bijekcj¸a.

1Dla zbioru ( X, R), zbiór ( X, R− 1) nazywamy dualnym do ( X, R)