Witam
Mam do rozwiązania następującą listę dotyczącą relacji porządku i relacji. Niestety nie potrafię sobie z nią poradzić. Jeśli ktoś potrafiłby rozwiązać którekolwiek z zadań i podać jakieś wytłumaczenie byłbym wdzięczny.
Zadania:
1. Rozważmy zbiór liczb rzeczywistych R wraz ze zwykłym porządkiem \(\displaystyle{ \leqslant}\) .
a) czy R jest kratą ? Jeśli tak, to jak wyglądają a \(\displaystyle{ \vee}\) b , a \(\displaystyle{ \wedge}\) b ?
b) znajdź sup \(\displaystyle{ \lbrace}\)x \(\displaystyle{ \in}\) R : x< 73\(\displaystyle{ \rbrace}\)
c) inf \(\displaystyle{ \lbrace}\)x \(\displaystyle{ \in}\) R : \(\displaystyle{ x^{2}}\)< 73\(\displaystyle{ \rbrace}\)
2. Niech \(\displaystyle{ \sum}\) będzie pewnym alfabetem. Dla \(\displaystyle{ w^{1}}\), \(\displaystyle{ w^{2}}\) \(\displaystyle{ \in}\)\(\displaystyle{ (\sum)^{*}}\) powiemy, że \(\displaystyle{ w^{1}}\)\(\displaystyle{ \leqslant}\)\(\displaystyle{ w^{2}}\) jeżeli w \(\displaystyle{ (\sum)^{*}}\) istnieją słowa w i w’ takie, że \(\displaystyle{ w^{2}}\)=\(\displaystyle{ w*w^{1}*w'}\). Czy \(\displaystyle{ \leqslant}\) jest częściowym porządkiem w \(\displaystyle{ (\sum)^{*}}\) ?
3. Poniższa częściowo wypełniona tabelka zawiera wartości działań x \(\displaystyle{ \vee}\) y dla pewnej kraty (L, \(\displaystyle{ \leqslant}\))
a) uzupełnij tabelkę
b) wskaż element największy i element najmniejszy w L
c) wykaż, że f \(\displaystyle{ \leqslant}\) c \(\displaystyle{ \leqslant}\) d \(\displaystyle{ \leqslant}\) e
d) narysuj diagram Hassego dla L.
\(\displaystyle{ \begin{tabular}{ccccccc}
\vee & a & b & c & d & e & f \\
a & & e & a & e & e & a \\
b & & & d & d & e & b \\
c & & & & d & e & c \\
d & & & & & e & d\\
e & & & & & & e\\
f & & & & & & \\
\end{tabular}}\)
4. Niżej podano definicje relacji < , \(\displaystyle{ \leqslant}\) oraz \(\displaystyle{ \subseteq}\) w R x R (płaszczyzna)
(x,y) < (z,w) \(\displaystyle{ \iff}\) \(\displaystyle{ x^{2}+y^{2}< z^{2}+w^{2}}\).
(x,y) \(\displaystyle{ \leqslant}\) (z,w) \(\displaystyle{ \iff}\) (x,y) < (z,w) \(\displaystyle{ \vee}\) (x,y) = (z,w)
(x,y) \(\displaystyle{ \subseteq}\)(z,w) \(\displaystyle{ \iff}\) \(\displaystyle{ x^{2}+y^{2}\leqslant z^{2}+w^{2}}\)
a) które z tych relacji są częściowymi porządkami? quasi-porządkami?
b) wyznacz zbiór \(\displaystyle{ \lbrace}\)(x,y): (x,y) \(\displaystyle{ \leqslant}\) (3,4)\(\displaystyle{ \rbrace}\)
c) wyznacz zbiór \(\displaystyle{ \lbrace}\)(x,y): (x,y) \(\displaystyle{ \subseteq}\) (3,4)\(\displaystyle{ \rbrace}\)
5. Czy każdy podzbiór kraty jest kratą?
6. Niech (S, |) będzie zbiorem \(\displaystyle{ \lbrace}\)2,3,4,...,999,1000\(\displaystyle{ \rbrace}\) z częściowym porządkiem „jest dzielnikiem”.
a) w (S, |) jest dokładnie 500 elementów maksymalnych. Wskaż je.
b) podaj dwa przykłady łańcuchów maksymalnych w (S, |).
c) czy do każdego łańcucha maksymalnego należy jakiś element minimalny?
7. Czy każdy zbiór liniowo uporządkowany jest kratą?
8. Niech ( \(\displaystyle{ \sum}\), \(\displaystyle{ \leqslant}\) ) będzie niepustym zbiorem liniowo uporządkowanym
a) czy zbiór ( \(\displaystyle{ (\sum)^{*}}\), \(\displaystyle{ \leqslant^{*}}\)) ma element maksymalny?
b) czy zbiór ( \(\displaystyle{ (\sum)^{*}}\), \(\displaystyle{ \leqslant_{L}}\) ) ma element maksymalny?
9. Jakie warunki musi spełniać zbiór \(\displaystyle{ \sum}\), by porządki: standardowy i leksykograficzny w zbiorze \(\displaystyle{ (\sum)^{*}}\) były identyczne?