Zbioru uporządkowane, kraty Birkhoffa, oraz podzbiory iporządkowane i podkraty
Wlodzimierz Holsztynski
zbiór częściowo uporządkowany, czyli
parę (X \<), złożoną ze zbioru X oraz
relacji 2-argumentowej (czyli binarnej \<
w zbiorze X, spełniającej 3 aksjomaty:
(0) x \< x
(1) (x \< y) & (y \< z) ==> x \< z
(2) (x \< y) & (y \< x) ==> x=y
dla dowolnych x y z \in X.
Gdy (X \>) jest zbiorem uporządkownym,
to także jest nim (X >/), gdzie relacja >/
jest odwróceniem relacji \<, mianowicie:
(*) x >/ y <==> y \< x
dla dowolnych x y \in X. (Dwukrotne
odwrócenie relacji daje relację wyjściową).
***
Zbiór całkowitych liczb nieujemnych
Z^+ := {0 1 2...} jest uprządkowany
(i to liniowo) ze względu na zwykłą
relację porządku \<.
Niech P := {2 3 5 7 11 13 17 19 23 ...}
będzie zbiorem wszytkich liczb pierwszych.
Niech LN będzie zbiorem wszystkich
funkcji:
n : P --> Z^+
o skończonym nośniku (t.zn. n(p) = 0
dla wszystkich p \in P poza skończoną
liczbbą elementów p). Wtedy LZ jest
zbiorem uporządkowanym względem
relacji \<, działającej po argumentach,
t.zn.:
m \< n <==> _A_ p \in P (m(p) \< n(p))
(gdzie symbol _A_ oznacza "dla każdego").
***
Po angielsku już od dawna zbiór (częściowo)
uporządkowany nazywany jest "poset" (od
Partially Ordered SET). Po polsku możemy
je nazywać po prostu uzbiorami.
***
Niech (X \<) będzie uzbiorem. Niech
x y z \in X. Mówimy, że z jest kresem
górnym elementów x y, gdy zachodzą 2 warunki:
(i) x \< z oraz y \< z;
(ii) jezeli z' \in X, x \< z' oraz y \< z',
to z \< z'.
Taki element z, o ile istnieje, jest jedyny.
Oznaczmy go z angielska z = lub(x y),
co harmonizuje z polskim słowem "lub"
(po angielsku chodzi o "Least Upper Bound").
Podobnie mówimy, że z jest kresem dolnym
elementów x y, symbolicznie z = glb(x y),
gdy z jest kresem górnym elementów x y
w uzbiorze (X >/).
***
W przypadku (Z^+ \<) oba kresy istnieją
dla dowolnych x y \in Z^+:
lub(x y) = max(x y)
glb(x y) = min(x y)
Podobnie dla LN oba kresy też zawsze
istnieją; są to maksimum i minimum dwóch
funkcji (gdzie operacje max i m in dla funkcji
liczy się dla wartości każdego argumentu p \in P
osobno).
***
Wolę skończyć teraz i kontynuować potem,
pozdrawiam,
Włodek
Wlodzimierz Holsztynski
kratą Birkhoffa, gdy kres górny i kres dolny
istnieje w nim dla dowolnych dwóch elementów.
Wtedy lub oraz glb są operacjami 2-argumentowymi
(binarnymi) w zbiorze X. Mają one następujące
własności:
(L1) przemienność:
lub(x y) = lub(y x) oraz glb(x y) = glb(y x)
(L2) łączność:
lub (lub(x y) z) = lub (x lub(y z))
glb( glb(x y) z) = glb (x glb(y z))
(L3) pochłanianie:
lub (x glb(x y)) = x = glb(x lub(x y)
Chociaż te wzory ćmią się w oczach z powodu
oznaczeń, to są one oczywiste. Może używać
jednak znaczków v oraz ^ na lub oraz glb:
(L1) x v y = y v x oraz x ^ y = y ^ x
(L2) ((x v y) v z) = (x v (y v z))
((x ^ y) ^ z) = (x ^ (y ^ z))
(L3) x v (x ^ y) = x = x ^ (x v y)
Zauważmy, że następujące własności
są równoważne:
(i) x \< y
(ii) x v y = y
(iii) x ^ y = x
***
Można przejście od uzbiorów do algebry odwrócić:
dla dowolnego zbioru X, z dwoma operacjami v oraz ^,
spełniającymi (L1) (L2) (L3), definiujemy uporządkowanie:
x \< y <==> lub(x y) = y
Wtedy nowe operacje kresu górnego i dolnego zawsze
w X istnieją i pokrywają się z wyjściowymi lub oraz glb.
***
Ćwiczenie: Niech (X v ^) spełnia (L1) (L2) (L3).
========= Wyprowadzić wzór:
(L0) x v x = x = x ^ x
***
Pozdrawiam,
Włodek
PS. Palę się, żeby nawiązać do baroku, a tu
tyle pisaniny. Przedtem ociągałem się chyba
ze względu na niepewny status ładnych
oznaczeń dla \cup i \cap. Skandal, że po pół
wieku komputerów wciąż nie można liczyć
na standartdowe matematyczne symbole.
Wlodzimierz Holsztynski
<=:=> X jest podzbiorem zbioru Y, oraz
(<) u \<' w <==> u \< w
dla dowolnych u w \in X.
Gdy (Y \<) jest uzbiorem, oraz X jest podzbiorem Y,
to w zbiorze X mamy dokładnie jeden porządek \<',
zwany indukowanym, który z (X \<') czyni poduzbiór
uzbioru (Y \<) -- mianowicie \<' definiujemy za pomocą
równoważnościpowyższej (<).
***
Dla wygody, o poduzbiorze (X \<') uzbioru (Y \<)
będziemy mówić po prostu jako o X, zam iast (X \<').
***
Poduzbiór X kraty Birkhoffa (Y \<) na ogół
nie jest kratą Birhoffa, gdyż na ogół w X nie
istnieją kresy górne i dolne par elementów u w \in X
(istnieją one w ramach Y, ale na ogól mogą nie należeć
do X). Co więcej:
UWAGA! Kres górny lub_X(u w) (odpowiednio dolny:
glb_X(u w)) w poduzbiorze X na ogół jesr różny od
kreu górnego (odpowiednio: dolnego) w całym uzbiorze
(Y \<); zachodzą jednynie nierówności:
lub_X(u w) >/ lub(u w)
glb_X(u w) \< glb(u w)
dla dowolnych u w \in X.
***
Popatrzmy na kwestię podobiektu od strony'
algebraicznej. Niech (Y v ^) będzie kratą Birkhoffa,
czyli spełnione są aksjomaty (L1) (L2) (L3).
Niech X bdzie podzbiorem zbioru Y. Wtedy X
albo jest, albo nie jest zamknięte ze względu na
operacje v ^. Jeżeli jest, i tylko wtedy, to X
nazywamy podkratą Birkhoffa kraty (Y v ^).
Wtedy X ze względu na indukowane operacje
v' oraz ^', czyli (X v' ^') samo jest kratą Birkhoffa.
Podkrata spełnia wszystkie równościowe identyczności,
spełnione przez kratę. Na przykład krata X := LN jest
rozdzielcza, t.zn. spełnia oba warunki:
(LD^v) x ^ (y v z) = (x^y) v (x^z)
(LDv^) x v (y ^ z) = (xvy) ^ (xvz)
dla dowolnych x y z \in X.
Wynika stąd, że powyższe dwa warunki spełnia także
każda podkrata kraty LN.
UWAGA!! Poduzbiór X uzbioru (Y \<), będacego
======= kratą Birkhoffa, może sam być kratą Birkhoffa
(względem indukowanego porządku), ale mimo to NIE
musi być podkratą kraty Y. W szczególności, podkrata
kraty rozdzielczej nie musi być rozdzielcza.
ĆWICZENIE Z aksjomatów (L1) (L2) (L3) oraz
========= z jednego z aksjomatów rozdzielczości
(LD^v) (LDv^) wyprowadzić pozostały.
***
Pozdrawiam,
Włodek