\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\QQ{\mathbb{Q}}
\def\r{\,r\,}
\def\R{\cal R}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\fczesc{\mathrel{{-}\mskip-2.7mu{\circ}\mskip-2.7mu{\rightarrow}}}
\def\poz{\vphantom{f}}\)
Podaj 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.
W zbiorze \(\{2,3,4,5,6,8,9,12,24\}\), uporządkowanym częściowo przez relację podzielności (\(m \preceq n\) wtedy i tylko wtedy gdy \(n = m\cdot k\), dla pewnego \(k \in \NN\)) wskaż wszystkie elementy minimalne, maksymalne, największe i najmniejsze. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy?
Niech \(r \subseteq \NN^\NN\times \NN^\NN\) będzie relacją określoną następująco: \(f\r g \Leftrightarrow \forall_{n \in \NN} \; f(n) \leq g(n)\). Udowodnij, że \(\la\NN^\NN, r\ra\) to częściowy porządek. Wskaż elementy minimalne, najmniejsze, maksymalne, największe, nieskończony łańcuch, nieskończony antyłańcuch. Czy jest to porządek liniowy? Czy jest gęsty?
Rozpatrzmy zbiór \(\{0,1\}^*\) z porządkiem leksykograficznym \(\preceq_{lex}\). Znajdź kres górny i dolny (jeśli istnieją) dla następujących zbiorów:
Jak zmienią sie odpowiedzi gdy kresy powyższych zbiorów będą szukane w częściowym porządku \(\la\{0,1\}^\NN \cup \{0,1\}^*, \preceq_{lex}\ra\), gdzie \(\{0,1\}^\NN \cup \{0,1\}^*\) jest zbiorem słów skończonych lub nieskończonych nad alfabetem \(\{0,1\}\), a \(w \preceq_{lex} v\) zachodzi wtedy i tylko wtedy gdy \(w\) jest prefiksem \(v\) lub gdy istnieje pozycja \(i\) taka, że \(w_i=0\) i \(v_i=1\)?
Które z następujacych stwierdzeń są prawdziwe dla dowolnego porządku \(\la X,\leq\ra\) i dowolnych \(A,B\subseteq X\):
Niech \(A\) i \(B\) będą zbiorami częściowo uporządkowanymi i niech funkcje \(f:A\to B\) oraz \(g:B\to A\) będą monotoniczne. Udowodnić, że następujące warunki są równoważne:
Niech \(A\) będzie dowolnym zbiorem i niech \(B \subseteq A \times A\). Udowodnij, że istnieje maksymalny zbiór \(C \subseteq A\) taki, że \(C\times C \subseteq B\).
Udowodnij, że każdy częściowy porządek można rozszerzyć do liniowego.
Niech \(A\) będzie dowolnym zbiorem do którego należą \(0\) i \(1\) i niech \(f: \pot{A^*} \to \pot{A^*}\) będzie określona następująco
Udowodnij, że \(f\) jest monotoniczna, zbadaj jakie są jej punkty stałe i udowodnij, że \(\{0,1\}^*\) jest jej najmniejszym punktem stałym.
Rozważmy częściowy porządek \(\la A \fczesc B, \subseteq\ra\), gdzie \(A \fczesc B)\) to zbiór funkcji częściowych z \(A\) do \(B\) i \(f \, \subseteq\, g\) wtedy i tylko wtedy gdy dla każdego \(a \in A\) albo \(f(a)\) jest nieokreślone, albo obie funkcje \(f\) i \(g\) są określone w \(a\) i \(f(a)=g(a)\). Czy \(\la A \fczesc B, \subseteq\ra\) jest kratą zupełną?
Udowodnij, że porządek \(\la A \fczesc B, \subseteq\ra\) zdefiniowany powyżej jest zupełny.
Niech \(A = \{3 - {1\over 2n} \;|\; n \in \NN - \{0\}\}\), \(B = \{\pi - {2\over n} \;|\; n \in \NN - \{0\}\}\cup \{4\}\), \(C = \{0\} \cup \{{1\over n} \;|\; n \in \NN - \{0\}\}\cup \{2 - {1\over n} \;|\; n \in \NN - \{0\}\}\). Rozpatrzmy zbiory \(A\), \(B\), \(A \cup B\), \(C\), \(\NN\), \(\ZZ\), \(\QQ\), \(\QQ - \{0\}\), \(\RR\), \(\RR - \{0\}\) uporządkowane liniowo przez zwykłą relację ,,\(\leq\)''. Które z nich są izomorficzne?