Ćwiczenia 7 13 listopada 2001

Zbiory uporządkowane

1. Niech r będzie relacją binarną w P(X) dla pewnego zbioru niepustego X taką, że
A r B wttw A È B = B

· Udowodnić, że r jest relacją częściowego porządku.

· Wskazać elementy (o ile istnieją) minimalne, maksymalne, największy i najmniejszy.

· Rozważyć, relację r w zbiorze ( P(X)/{Æ})/{X} i wskazać jej elementy wyróżnione.

2. Pokazać, że jeśli <X,r> jest zbiorem uporządkowanym, to r ^-1 też jest zbiorem uporządkowanym. Czy to samo można powiedzieć

· o zbiorach liniowo uporządkowanych?

· o zbiorach dobrze uporządkowanych?

3. Podać przykład zbioru częściowo uporządkowanego, który ma

· kilka elementów minimalnych

· tylko jeden element minimalny.

· dokładnie jeden element minimalny ale nie ma elementu najmniejszego.

W każdym z podanych przykładów, narysować diagram Hassego.

4. Udowodnić, że relacja r (porządek produktowy) określona w produkcie X´Y dwóch zbiorów częściowo uporządkowanych <X, £₁>, <Y, £₂ > następująco
(x,y) r(x',y') wttw x £₁x' i y £₂ y' jest porządkiem częściowym.

· Czy to jest porządek liniowy?

· Czy to jest dobry porządek?

· Niech X=Y={1,2,3}. Narysować diagram Hasse porządku produktowego w X´Y i wskazać elementy wyróżnione.

5. Udowodnić, że porządek leksykograficzny w N³ jest porządkiem liniowym.

6. Rozważmy zbiór R w relacją £ .

· Czy R jest kratą?

· Podać przykład niepustego podzbioru R, który nie ma ograniczenia górnego w R.

· Znaleźć sup{xÎR : x<23}

· sup{xÎ R : x² < 23}, sup{ xÎ N : x² < 23}

· inf {x ÎR : x²< 23}, inf {x ÎN : x²< 23}

7. Niech E(N) będzie zbirem tych wszystkich podzbiorów zbioru N, które mają parzystą liczbę elementów. Rozważmy E(N) z częściowym porządkiem Í.

· Niech A={1,2}, B={1,3}. Wskazać 2 różne ograniczenia górne zbioru {A,B} w E(N).

· Czy zbiór {A,B} ma kres dolny w E(N)? Kres górny?

· Czy E(N) jest kratą?