Informatyka MIMUW

Pokażemy, że \( \displaystyle \sqsubseteq \) spełnia warunki bycia porządkiem.
1. Dla dowolnego zbioru \( \displaystyle x \) mamy \( \displaystyle x\subset x \), więc w szczególności dla elementów \( \displaystyle a\in A \) również \( \displaystyle a\subset a \), czyli \( \displaystyle a \sqsubseteq a \). Relacja \( \displaystyle \sqsubseteq \) jest więc zwrotna.

2. Dla dowolnych zbiorów \( \displaystyle x,y,z \) mamy \( \displaystyle (x\subset y \wedge y\subset z) \Rightarrow x \subset z \). Weźmy dowolne elementy \( \displaystyle a,b,c\in A \), dla których mamy \( \displaystyle a\sqsubseteq b \) oraz \( \displaystyle b\sqsubseteq c \). Z definicji \( \displaystyle \sqsubseteq \) wynika, że wtedy \( \displaystyle a\subset b \) oraz \( \displaystyle b\subset c \). Otrzymujemy więc \( \displaystyle a\subset c \), co oznacza dokładnie, że \( \displaystyle a\sqsubseteq c \). Relacja \( \displaystyle \sqsubseteq \) jest więc przechodnia.

3. Dla dowolnych zbiorów \( \displaystyle x,y \) z wiemy, że \( \displaystyle (x \subset y \wedge y\subset x) \Rightarrow x=y \). Weźmy dowolne elementy \( \displaystyle a,b\in A \), dla których \( \displaystyle a\sqsubseteq b \) oraz \( \displaystyle b\sqsubseteq a \). Wtedy \( \displaystyle a\subset b \) oraz \( \displaystyle b\subset a \), skąd otrzymujemy \( \displaystyle a=b \). Relacja \( \displaystyle \sqsubseteq \) jest więc symetryczna.

Sprawdź, czym jest \( \displaystyle \bigcup r \) i \( \displaystyle \bigcap r \).

Pokażemy, że dla dowolnej rodziny \( \displaystyle r\subset \mathcal{P}(A) \) mamy \( \displaystyle \bigcup r= \bigvee r \) oraz \( \displaystyle \bigcap r= \bigwedge r \). Ze względu na symetrię udowodnimy tylko pierwszą równość (uwaga! sytuacja przestaje być symetryczna, jeśli dopuścimy puste rodziny). Pokażemy, że \( \displaystyle \bigcup r \) spełnia warunki bycia supremum.

1. Z własności sumy wynika, że \( \displaystyle x\in r \Rightarrow x \subset \bigcup r \).
2. Weźmy dowolny element \( \displaystyle b \in A \), dla którego prawdą jest, że \( \displaystyle \forall_{a\in r} a \subset b \). Weźmy dowolny element \( \displaystyle z\in \bigcup r \), musi on należeć do pewnego zbioru \( \displaystyle a_z\in r \). Ponieważ \( \displaystyle a_z\subset b \), więc \( \displaystyle z\in b \). Wynika stąd, że \( \displaystyle \bigcup r \subset b \).

Zaczniemy od pokazania, że \( \displaystyle | \) jest porządkiem.

1. Dla każdej liczby \( \displaystyle n\in \mathbb{N} \) wystarczy dobrać \( \displaystyle c=1 \), aby otrzymać \( \displaystyle 1 \cdot a = a \). Więc relacja \( \displaystyle | \) jest zwrotna.

2. Weźmy dowolne liczby \( \displaystyle x,y,z\in \mathbb{N} \), dla których \( \displaystyle x|y \) oraz \( \displaystyle y|z \). Oznacza to, że istnieją liczby \( \displaystyle c_1, c_2 \in \mathbb{N} \) takie, że \( \displaystyle x \cdot c_1=y \) oraz \( \displaystyle y \cdot c_2= z \). Z tych dwóch równości otrzymujemy \( \displaystyle x \cdot (c_1 \cdot c_2)=z \). Wobec tego możemy do \( \displaystyle x \) dobrać \( \displaystyle c_3= c_1 \cdot c_2 \) tak, aby \( \displaystyle x \cdot c_3= z \), a to oznacza, że \( \displaystyle x|z \). Relacja \( \displaystyle | \) jest więc przechodnia.

3. Weźmy dowolne liczby \( \displaystyle n,m \), dla których \( \displaystyle n|m \) oraz \( \displaystyle m|n \). Oznacza to, że istnieją liczby \( \displaystyle c_1,c_2\in \mathbb{N} \), dla których \( \displaystyle n \cdot c_1= m \) oraz \( \displaystyle m \cdot c_2 = n \). Z tych dwóch równości otrzymujemy \( \displaystyle n\cdot (c_1\cdot c_2) = n \). Rozważymy teraz dwa przypadki:

1. Jeśli \( \displaystyle n\neq 0 \) to \( \displaystyle c_1 \cdot c_2 =1 \) i ponieważ są to liczby naturalne, to \( \displaystyle c_1=c_2=1 \). Oznacza to, że \( \displaystyle n=1 \cdot m= m \).

Jeśli \( \displaystyle n=0 \), to wtedy \( \displaystyle m=0\cdot c_1= 0 = n \).

Udowodniliśmy więc, że relacja \( \displaystyle | \) jest antysymetryczna.

W porządku \( \displaystyle (\mathbb{N},|) \) elementem najmniejszym jest 1, a największym 0. Dla każdej liczby \( \displaystyle x\in \mathbb{N} \) możemy dobrać \( \displaystyle c=0 \) i wtedy \( \displaystyle x \cdot c=0 \), a więc \( \displaystyle x|0 \). Dla każdej \( \displaystyle x\in \mathbb{N} \) liczby możemy dobrać \( \displaystyle c=x \) i wtedy \( \displaystyle 1 \cdot c =x \), co oznacza \( \displaystyle 1|x \).

1. Jest zwrotna i przechodnia. Nie jest antysymetryczna.
2. Aby pokazać, że nie jest antysymetryczna, rozważ funkcję stałą i identyczność.

1. Dla każdej funkcji \( \displaystyle f\in \mathbb{N}^\mathbb{N} \) możemy dobrać funkcję \( \displaystyle 1_\mathbb{N} \) i wtedy \( \displaystyle 1_\mathbb{N} \circ f= f \circ 1_\mathbb{N} \). Relacja \( \displaystyle R \) jest więc zwrotna.

2. Weźmy dowolne funkcje \( \displaystyle e,f,g\in \mathbb{N}^\mathbb{N} \), takie że \( \displaystyle e R f \) oraz \( \displaystyle f R g \). Oznacza to, że istnieją funkcje \( \displaystyle h_1,h_2 \in \mathbb{N}^\mathbb{N} \), takie że:
\( \displaystyle h_1 \circ e = f \circ h_1 \)

oraz:

\( \displaystyle h_2 \circ f = g \circ h_2. \)

Składając funkcję z pierwszej równości z funkcją \( \displaystyle h_2 \), otrzymujemy:

\( \displaystyle h_2 \circ h_1 \circ e = h_2 \circ f \circ h_1. \) Z powyższej oraz z drugiej równości otrzymujemy:

\( \displaystyle (h_2 \circ h_1) \circ e = g \circ (h_2 \circ h_1). \)

Wobec tego do \( \displaystyle e \) wystarczy dobrać funkcję \( \displaystyle h_3=h_2 \circ h_1 \), aby otrzymać \( \displaystyle h_3 \circ e = g \circ h_3 \). Udowodniliśmy więc, że relacja \( \displaystyle R \) jest przechodnia.

3. Relacja \( \displaystyle R \) nie jest symetryczna. Rozważmy funkcję \( \displaystyle 1_\mathbb{N} \) oraz funkcję \( \displaystyle f \) stale równą 0. Wtedy dobierając \( \displaystyle h= f \), mamy \( \displaystyle h \circ 1_\mathbb{N}= f \circ h \), co oznacza \( \displaystyle 1_\mathbb{N} R f \) oraz \( \displaystyle h \circ f = 1_\mathbb{N} \circ h \), co oznacza \( \displaystyle f R 1_\mathbb{N} \). Ponieważ funkcje \( \displaystyle 1_\mathbb{N} \) i \( \displaystyle f \) są różne, to relacja \( \displaystyle R \) nie jest antysymetryczna.

Jest zwrotna, nie jest przechodnia ani antysymetryczna.

1. Dla dowolnej funkcji \( \displaystyle f\in I^I \) mamy \( \displaystyle f(0)\leq f(0) \), więc relacja \( \displaystyle R \) jest zwrotna.

2. Pokażemy, że relacja \( \displaystyle R \) nie jest przechodnia. Weźmy funkcję \( \displaystyle f_0 \), która jest stale równa 0, \( \displaystyle f_1 \), która jest stale równa 1 oraz funkcję \( \displaystyle 1_I \), czyli identyczność. Wtedy \( \displaystyle f_1 R 1_I \) (bo \( \displaystyle f_1(1)=1 \leq 1_I(1)=1 \)) oraz \( \displaystyle 1_I R f_0 \) (bo \( \displaystyle 1_I(0)=0 \leq f_0(0)=0 \), podczas gdy nie jest prawdą, że \( \displaystyle f_1 R f_0 \), bo dla każdego \( \displaystyle x\in I \) mamy \( \displaystyle f_1(x)=1 > 0=f_0(0) \).

3. Relacja nie jest antysymetryczna. Weźmy funkcję \( \displaystyle f_1 \) stale równą 1 oraz funkcję \( \displaystyle 1_I \). Wtedy biorąc \( \displaystyle x=1 \), otrzymamy \( \displaystyle f_1(x)=1 =1_I(x) \), czyli \( \displaystyle f_1(x) \leq 1_I(x) \), skąd wynika, że \( \displaystyle f_1 R 1_I \) oraz \( \displaystyle 1_I(x) \leq f_1(x) \), skąd wynika, że \( \displaystyle 1_I R f_1 \). Ponieważ \( \displaystyle 1_I \neq f_1 \), to relacja \( \displaystyle R \) nie jest antysymetryczna.

Pokażemy, że \( \displaystyle R \) porządkuje zbiór \( \displaystyle I \).

1. Dla każdej funkcji \( \displaystyle f\in I^I \) mamy \( \displaystyle \forall_{x\in I} f(x)=f(x) \), a więc w szczególności \( \displaystyle \forall_{x\in I} f(x)\leq f(x) \), co oznacza, że \( \displaystyle f R f \). Relacja \( \displaystyle R \) jest więc zwrotna.
2. Weźmy dowolne funkcje \( \displaystyle f,g,h \in I^I \), takie że \( \displaystyle f R g \) oraz \( \displaystyle g R h \). Pokażemy, że \( \displaystyle f R h \). Weźmy dowolny element \( \displaystyle x\in I \) wtedy \( \displaystyle f(x) \leq g(x) \) oraz \( \displaystyle g(x) \leq h(x) \). Z przechodniości porządku \( \displaystyle \leq \) otrzymujemy \( \displaystyle f(x) \leq h(x) \). Wobec dowolności wyboru \( \displaystyle x \) otrzymujemy \( \displaystyle f R h \).
3. Weźmy funkcje \( \displaystyle f,g \) dla których \( \displaystyle f R g \) oraz \( \displaystyle g R f \). Oznacza to, że:

\( \displaystyle [\forall_{x\in I} f(x) \leq g(x)] \wedge [\forall_{x\in I} g(x) \leq f(x)]. \)

Jest to równoważne następującej formule:

\( \displaystyle \forall_{x\in I} [f(x) \leq g(x) \wedge g(x) \leq f(x)]. \)

Z antysymetryczności porządku \( \displaystyle \leq \) otrzymujemy \( \displaystyle \forall_{x\in I} f(x) =g(x) \). Oznacza to dokładnie, że \( \displaystyle f=g \). Wobec tego relacja \( \displaystyle R \) jest antysymetryczna.

Najmniejszym elementem jest funkcja \( \displaystyle f_0 \) stale równa zero, a największym elementem jest funkcja \( \displaystyle f_1 \) stale równa 1. Dla dowolnej funkcji \( \displaystyle f\in I^I \) i dowolnego elementu \( \displaystyle x\in X \) mamy \( \displaystyle f(x)\in I \), a więc \( \displaystyle 0\leq f(x) \leq 1 \), skąd otrzymujemy \( \displaystyle f_0 R f \) oraz \( \displaystyle f R f_1 \).

Wystarczy wziąć zbiór \( \displaystyle X=[0,1] \cap \mathbb{Q} \) uporządkowany naturalną relacją mniejszości na liczbach wymiernych. \( \displaystyle 0 \in \mathbb{Q} \) jest więc elementem najmniejszym, \( \displaystyle 1\in \mathbb{Q} \) jest więc elementem największym. Zbiór \( \displaystyle X \) jest nieskończonym podzbiorem zbioru przeliczalnego, więc jest przeliczalny.

Rozważmy zbiór \( \displaystyle \{0,1\} \) uporządkowany relacją identycznościową. Wtedy każdy jego element jest maksymalny, a żaden nie jest największy, bo są nieporównywalne.

Istnieje też porządek, w którym istnieje dokładnie jeden element maksymalny, który nie jest elementem największym. Niech \( \displaystyle \flat \) będzie zbiorem takim, że \( \displaystyle \flat \notin \mathbb{N} \) (w roli \( \displaystyle \flat \) może wystąpić na przykład zbiór \( \displaystyle \mathbb R \) albo \( \displaystyle \mathbb{N} \)). Niech \( \displaystyle M=\mathbb{N} \cup \{\flat\} \). Zbiór \( \displaystyle M \) uporządkujemy relacją \( \displaystyle R=\leq_\mathbb{N} \cup \{(\flat,\flat)\} \), gdzie \( \displaystyle \leq_\mathbb{N} \) jest naturalną relacją porządku w \( \displaystyle \mathbb{N} \). Łatwo sprawdzić, że \( \displaystyle R \) jest porządkiem. Wtedy \( \displaystyle \flat \) jest elementem maksymalnym (bo jedyny element, który jest z nim porównywalny to on sam, a więc nie może istnieć żaden większy). W dodatku \( \displaystyle \flat \) nie jest elementem największym, bo na przykład nie jest większy od 0. Nie ma drugiego elementu maksymalnego, gdyż musiałby być liczbą naturalną. Dla każdej liczby naturalnej natomiast istnieje liczba od niej większa.

Przypuśćmy, że w \( \displaystyle (X,\leq) \) istnieje \( \displaystyle \bigvee \emptyset \), oznaczmy ten element przez \( \displaystyle a_0 \). Wtedy z definicji supremum otrzymujemy:

\( \displaystyle \forall_{a\in \emptyset} a \leq a_0 \) oraz dla każdego \( \displaystyle b\in X \):

\( \displaystyle (\forall_{a\in \emptyset} a\leq b) \Rightarrow a_0 \leq b. \)

Pierwsza formuła niewiele mówi, gdyż jest zawsze prawdziwa (rozpisz kwantyfikator ograniczony). Z tego samego powodu zawsze jest prawdziwa przesłanka drugiej z formuł. Wobec tego dla każdego \( \displaystyle b\in X \) mamy \( \displaystyle a_0 \leq b \), co oznacza dokładnie, że \( \displaystyle a_0 \) jest elementem najmniejszym w \( \displaystyle X \).

Dla implikacji w drugą stronę, jeśli \( \displaystyle a_0 \) jest elementem najmniejszym, to prawa strona implikacji w drugiej formule jest zawsze prawdziwa, więc cała implikacja również. Pierwsza formuła jest zawsze spełniona. Wobec tego element \( \displaystyle a_0 \) spełnia warunki bycia \( \displaystyle \bigvee \emptyset \), a więc takie supremum istnieje.

Przypuśćmy, że \( \displaystyle (X,\leq) \) jest zbiorem uporządkowanym, w którym każdy podzbiór ma supremum. Weźmy dowolny zbiór \( \displaystyle A \subset X \) pokażemy, że ma infimum. Niech \( \displaystyle B=\{x \in X : \forall_{a\in A} x \leq a\} \), czyli zbiór \( \displaystyle B \) jest zbiorem minorant zbioru \( \displaystyle A \). Zbiór \( \displaystyle B \) jako podzbiór \( \displaystyle X \) ma supremum, oznaczmy je przez \( \displaystyle s \). Pokażemy, że \( \displaystyle s \) jest infimum zbioru \( \displaystyle A \). Ponieważ każdy element zbioru \( \displaystyle A \) jest majorantą zbioru \( \displaystyle B \), to \( \displaystyle s \) musi być mniejszy od każdego elementu z \( \displaystyle A \), gdyż jest najmniejszą majorantą \( \displaystyle B \). Wobec tego, \( \displaystyle s \) jest minorantą \( \displaystyle A \) i ponieważ jest supremum minorant, to jest największą minorantą, a więc infimum zbioru \( \displaystyle A \).

(Przyjrzyj się, jak powyższe rozumowanie działa w przypadkach, gdy \( \displaystyle A=X \) oraz gdy \( \displaystyle A=\emptyset \).)

Rozważmy zbiór \( \displaystyle \{0,1\} \) uporządkowany relacją \( \displaystyle \{(0,0),(0,1),(1,1)\} \). Wtedy zbiory \( \displaystyle \{0\} \) oraz \( \displaystyle \{1\} \) są antyłańcuchami, podczas gdy ich suma nie jest.

Rozważmy zbiór \( \displaystyle \{0,1\} \) uporządkowany relacją \( \displaystyle \{(0,0),(1,1)\} \). Wtedy zbiory \( \displaystyle \{0\} \) oraz \( \displaystyle \{1\} \) są łańcuchami, podczas gdy ich suma nie jest.

Każdy antyłańcuch jednoelementowy lub pusty jest łańcuchem.

Dla każdego porządku \( \displaystyle (X,\leq) \), zarówno zbiór jego łańcuchów jak i zbiór jego antyłańcuchów jest uporządkowany przez inkluzję. Możemy więc mówić o największym (maksymalnym) ze względu na inkluzję łańcuchu (antyłańcuchu). Łatwo można pokazać, że zawsze istnieje najmniejszy łańcuch i antyłańcuch. Istnienie w każdym posecie maksymalnego łańcucha jest równoważne aksjomatowi wyboru. Tym zagadnieniem zajmujemy się w Wykładzie 11: "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady".

Rozważmy zbiór \( \displaystyle \mathcal{P}(2) \) uporządkowany relacją inkluzji. Wtedy zbiory \( \displaystyle \{\emptyset\} \) oraz \( \displaystyle \{\{1\}, \{0\}\} \) są różnymi antyłańcuchami maksymalnymi, a więc nie istnieje największy antyłańcuch. Podobnie zbiory \( \displaystyle \{\emptyset,\{0\},\{0,1\}\} \) oraz \( \displaystyle \{\emptyset,\{1\},\{0,1\}\} \) są różnymi maksymalnymi łańcuchami, więc łańcuch największy również nie istnieje.

W porządku \( \displaystyle (X,\leq) \) istnieje największy w sensie inkluzji łańcuch wtedy i tylko wtedy, gdy porządek ten jest liniowy.

Implikacja w lewą stronę jest oczywista, gdyż porządek liniowy jest w całości łańcuchem, a więc łańcuch ten jest największy.

Przypuśćmy teraz, że porządek \( \displaystyle (X,\leq) \) nie jest liniowy. Oznacza to, że istnieją przynajmniej dwa nieporównywalne elementy, oznaczmy je przez \( \displaystyle x,y \). Ponieważ zbiory \( \displaystyle \{x\} \) oraz \( \displaystyle \{y\} \) są łańcuchami, to musiałyby być podzbiorami największego antyłańcucha, gdyby taki istniał. Oznaczałoby to jednak, że w tym łańcuchu znajdują się elementy nieporównywalne, wobec tego taki łańcuch nie istnieje.

W porządku \( \displaystyle (X,\leq) \) istnieje największy w sensie inkluzji łańcuch wtedy i tylko wtedy, gdy żadne dwa różne elementy \( \displaystyle X \) nie są porównywalne.

Implikacja w lewą stronę jest oczywista. Jeśli \( \displaystyle \leq = 1_X \), to cały \( \displaystyle X \) jest antyłańcuchem. Ponieważ jest nadzbiorem każdego antyłańcucha, to jest największy.

Przypuśćmy teraz, że \( \displaystyle \leq \neq 1_X \). Wtedy istnieją elementy porównywalne \( \displaystyle x,y \). Przypuśćmy, że istnieje największy antyłańcuch. Wtedy antyłańcuchy \( \displaystyle \{x\} \) oraz \( \displaystyle \{y\} \) są jego podzbiorami, co oznacza, że w największym antyłańcuchu znajdują się elementy porównywalne. Wobec tego największy antyłańcuch nie istnieje.

W zbiorze \( \displaystyle \mathbb{N} \) uporządkowanym relacją identyczności, każdy niepusty łańcuch jest singletonem, a więc jest skończony, podczas gdy cały zbiór jest nieskończony.

W zbiorze \( \displaystyle \mathbb{N} ^2 \) rozważmy porządek zdefiniowany następująco:

\( \displaystyle (x_1,y_1) \sqsubseteq (x_2,y_2) \Leftrightarrow (x_1+y_1=x_2+y_2 \wedge x_1 \leq x_2). \)

W tym porządku z każdy element \( \displaystyle (a,b) \) jest porównywalny dokładnie z \( \displaystyle a+b+1 \) elementami, wobec czego nie może istnieć nieskończony łańcuch. Z drugiej strony dla dowolnej liczby \( \displaystyle n\in \mathbb{N} \) możemy skonstruować łańcuch \( \displaystyle \{(a,b)\in \mathbb{N}^2: a+b=n\} \), który ma dokładnie \( \displaystyle n+1 \) elementów.

Łańcuchy maksymalne:

1. \( \displaystyle \{1,2,4,6,0\} \),
2. \( \displaystyle \{1,3,6,0\} \),
3. \( \displaystyle \{1,5,0\} \).

Antyłańcuchy maksymalne:

1. \( \displaystyle \{1\} \),
2. \( \displaystyle \{0\} \),
3. \( \displaystyle \{5,6\} \),
4. \( \displaystyle \{2,3,5\} \),
5. \( \displaystyle \{4,3,5\} \).