8344044630

strona 18

29 września 2008, godzina 17:13

Porządki częściowe

200.    Podać przykład zbioru częściowo uporządkowanego, z dwoma elementami maksymalnymi i jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry ale nie ma kresu górnego.

201.    Niech X będzie zbiorem częściowo uporządkowanym i niech A C X nie ma elementu największego. Niech B = {b G X : Va € A(b > a)}. Pokazać, że jeśli istnieje inf(5) to istnieje sup(A) oraz sup(A) = inf(B) € B.

202.    W zbiorze {2,3,4,5,6,8,9,12,24}, uporządkowanym częściowo przez relację podzielności (m -< n wtedy i tylko wtedy gdy n — m ■ k, dla pewnego k € N — {0}) wskazać wszystkie elementy minimalne, maksymalne, największe i najmniejsze. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy?

203.    Wskazać elementy minimalne, maksymalne, największe i najmniejsze w zbiorze

{{1,2,3,4,6}, {3}, {1,2,3,4,5}, {2,3,3,5,2}, {3,4,2,4,1}, {2,1,2,2,1}, {2,1,2,1}}, uporządkowanym przez inkluzję.

204.    Zbiór częściowo uporządkowany nazywamy kratą, gdy każdy jego dwuelementowy podzbiór ma kres górny i kres dolny. Czy zbiór z poprzedniego zadania jest kratą?

205.    Niech (X, r) i (Y, s) będą niepustymi zbiorami częściowo uporządkowanymi. Pokazać, że

(a)    (X © Y, r © s) jest zbiorem częściowo uporządkowanym i nie ma elementu największego;

(b)    Dla dowolnego a € X © Y, element a jest minimalny w (X © Y, r © s) wtedy i tylko wtedy gdy jest elementem minimalnym w (X,r) lub w (Y,s);

206.    Jeśli < jest częściowym porządkiem w zbiorze A to relację < nazywamy ostrym uporządkowaniem wyznaczonym przez <. Pokazać, że ostre uporządkowania wyznaczone przez porządki częściowe to dokładnie te relacje, które są przechodnie i przeciwzwrotne.

207.    Niech A i B będą zbiorami częściowo uporządkowanymi i niech funkcje / : A —* B oraz g : B —> A będą monotoniczne. Udowodnić, że następujące warunki są równoważne:

(a)    \/aę.AVbEB(a < g(b) f(a) < 6);

(b)    VaeA(a < g(f(a))) oraz VbeB(f(g(b)) < b).

208.    Niech (D, <) będzie skończonym zbiorem częściowo uporządkowanym z elementem największym i najmniejszym. Dla a,b G D stosujemy oznaczenia:

(a, b) = {d € D : a < d < 6};    [a,b\ = {d E D : a < d < b}.

Załóżmy, że dla dowolnych a,b G D, jeśli (a, b) ± 0 to (a, b) = [c,d], dla pewnych c, d (tj. że każdy przedział otwarty jest też przedziałem domkniętym). Udowodnić, że wtedy (D, <) jest liniowo uporządkowany.

209.    Czy zbiór tych słów nad alfabetem {0,1}, które mają tyle samo zer co jedynek, ma kres górny (dolny) w porządku leksykograficznym?