Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) niech będzie relacją zwrotną w zbiorze \(\displaystyle{ X}\).
Wykażemy, że istnieje maksymalny, względem inkluzji, częściowy porządek \(\displaystyle{ S}\) na zbiorze \(\displaystyle{ X}\), taki, że: \(\displaystyle{ S \subset R}\).
DOWÓD TEGO FAKTU:
Dowód łatwo idzie z Lematu Zorna:
Niech:
\(\displaystyle{ \mathbb{B}= \left\{ S \subset X \times X\Bigl| \ \ S \hbox{ jest częściowym porządkiem na zbiorze } X\hbox{ i } S \subset R \right\}.}\)
Wtedy para \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) jest zbiorem uporządkowanym.
Zauważmy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest zawsze niepusta, bo dla identyczności \(\displaystyle{ I_X}\), mamy: \(\displaystyle{ I_X \subset X \times X}\), \(\displaystyle{ I_X}\) jest częściowym porządkiem na zbiorze \(\displaystyle{ X}\) i \(\displaystyle{ I_X \subset R}\), bo relacja \(\displaystyle{ R}\) jest zwrotna. Wobec czego \(\displaystyle{ I_X \in \mathbb{B}}\), i rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta.
Stosujemy do niej Lemat Kuratowskiego Zorna.
Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{D} \subset \mathbb{B}}\) będzie niepustym łańcuchem w \(\displaystyle{ \left( \mathbb{B}, \subset \right)}\) (dla \(\displaystyle{ \mathbb{D}= \left\{ \right\} }\) dowolny element \(\displaystyle{ S \in \mathbb{B} \neq \left\{ \right\}}\) jest ograniczeniem górnym pustego łańcucha). Dalej zakładamy, że łańcuch \(\displaystyle{ \mathbb{D}}\) jest niepusty.
Niech \(\displaystyle{ R \in \mathbb{D} \neq \left\{ \right\}}\). Wtedy, ponieważ \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\), więc \(\displaystyle{ R}\) jest częściowym porządkiem, w szczególności jest relacją zwrotną, wtedy ponieważ każda relacja w zbiorze \(\displaystyle{ X}\), będąca nadzbiorem relacji zwrotnej, jest relacją zwrotną, więc relacja \(\displaystyle{ \bigcup\mathbb{D}}\) jest zwrotna.
I podobnie, jeśli \(\displaystyle{ A \in \mathbb{D} \subset \mathbb{B}}\), to \(\displaystyle{ A}\) jest częściowym porządkiem, w szczególności jest relacją antysymetryczną, więc relacja \(\displaystyle{ \bigcup\mathbb{D}}\) będzie antysymetryczna ( jako suma łańcucha relacji antysymetrycznych).
I w podobny sposób otrzymamy, że relacja \(\displaystyle{ \bigcup\mathbb{D}}\) będzie relacją przechodnią (jako suma łańcucha relacji przechodnich).
W ukrytej treści poniżej przedstawiam dowód tego faktu:
Ukryta treść:
Mamy ponadto: \(\displaystyle{ \bigcup\mathbb{D} \subset X \times X}\) i \(\displaystyle{ \bigcup\mathbb{D} \subset R}\) (jako suma podzbiorów relacji \(\displaystyle{ R}\)). Wobec czego \(\displaystyle{ \bigcup\mathbb{D} \in \mathbb{B}}\), a zatem suma \(\displaystyle{ \bigcup\mathbb{D}}\) rodziny \(\displaystyle{ \mathbb{D}}\) jest jej supremum: \(\displaystyle{ \bigcup\mathbb{D}= \bigvee\mathbb{D}}\), a więc w szczególności ta suma \(\displaystyle{ \bigcup\mathbb{D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\)- tego łańcucha; i, z dowolności jego wyboru, otrzymujemy, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B}, \subset \right)}\) każdy łańcuch ma ograniczenie górne.
Korzystając z Lematu Zorna (czyli również korzystając z aksjomatu wyboru) otrzymujemy element maksymalny w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B}, \subset \right)}\). Jest to poszukiwany maksymalny, względem inkluzji, częściowy porządek zawarty w relacji \(\displaystyle{ R.\square}\)
Dodam tu jeszcze trzy proste fakty, które ostatnio udowodniłem.
Udowodniłem, że jeśli dla funkcji \(\displaystyle{ f:X \rightarrow Y}\) równość:
\(\displaystyle{ \stackrel{ \rightarrow}{f ^{-1} } \left( \stackrel{ \rightarrow }{f} \left( A\right) \right)=A;}\)
zachodzi dla każdego zbioru \(\displaystyle{ A \subset X}\), to funkcja \(\displaystyle{ f}\) jest różnowartościowa.
DOWÓD TEGO FAKTU:
Jeśli \(\displaystyle{ f\left( x_1\right) = f\left( x_2\right)}\), to oznaczmy tą wartość jako \(\displaystyle{ y}\). Wtedy, na mocy założenia:
\(\displaystyle{ \stackrel{ \rightarrow}{f ^{-1} } \left( \stackrel{ \rightarrow }{f} \left\{ x_1\right\} \right)= \left\{ x_1\right\} ;}\) i
\(\displaystyle{ \stackrel{ \rightarrow}{f ^{-1} } \left( \stackrel{ \rightarrow }{f} \left\{ x_2\right\} \right)= \left\{ x_2\right\} .}\)
A zatem:
\(\displaystyle{ \left\{ x_1\right\} = \stackrel{ \rightarrow}{f ^{-1} } \left( \stackrel{ \rightarrow }{f} \left\{ x_1\right\} \right)= \stackrel{ \rightarrow}{f ^{-1} } \left\{ f\left( x_1\right) \right\}= \stackrel{ \rightarrow}{f ^{-1} } \left\{ y\right\}}\), i podobnie:
\(\displaystyle{ \left\{ x_2\right\} = \stackrel{ \rightarrow}{f ^{-1} } \left( \stackrel{ \rightarrow }{f} \left\{ x_2\right\} \right)= \stackrel{ \rightarrow}{f ^{-1} } \left\{ f\left( x_2\right) \right\}= \stackrel{ \rightarrow}{f ^{-1} } \left\{ y\right\},}\)
skąd:
\(\displaystyle{ \left\{ x_1\right\}= \left\{ x_2\right\}, }\)
a zatem:
\(\displaystyle{ x_1=x_2}\),
i funkcja \(\displaystyle{ f}\) jest różnowartościowa.\(\displaystyle{ \square}\)
Również:
Jeśli dla funkcji \(\displaystyle{ f:X \rightarrow Y}\) równość:
\(\displaystyle{ \stackrel{ \rightarrow }{f}\left( \stackrel{ \rightarrow }{f ^{-1} } \left( B\right) \right) = B,}\)
zachodzi dla każdego zbioru \(\displaystyle{ B \subset Y}\), to funkcja \(\displaystyle{ f}\) jest 'na' zbiór \(\displaystyle{ Y}\).
PROSTY DOWÓD TEGO FAKTU:
Podstawiając \(\displaystyle{ B:=Y,}\) otrzymujemy:
\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( \stackrel{ \rightarrow }{f ^{-1} } \left( Y\right) \right)= Y.}\)
A zatem:
\(\displaystyle{ Y=\stackrel{ \rightarrow }{f} \left( \stackrel{ \rightarrow }{f ^{-1} } \left( Y\right) \right)\stackrel{f:X \rightarrow Y}{=} \stackrel{ \rightarrow }{f} \left( X\right) =f_P,}\)
a więc funkcja \(\displaystyle{ f}\) jest 'na' zbiór \(\displaystyle{ Y.\square}\)
Wpadłem też ostatnio na pomysł, aby dla funkcji identyczności wyznaczyć przeciwobrazy zbiorów, tzn.:
Wykażemy, że dla zbioru \(\displaystyle{ X}\), oraz dla identyczności \(\displaystyle{ I_X: X \rightarrow X}\), oraz dla zbioru \(\displaystyle{ B \subset X}\), mamy:
\(\displaystyle{ \stackrel { \rightarrow }{I _{X} ^{-1} } \left( B\right) =B.}\)
DOWÓD TEGO FAKTU:
Zauważmy najpierw, że identyczność jest funkcją różnowartościową.
Zauważmy, że \(\displaystyle{ \stackrel{ \rightarrow }{I_X} \left( B\right) = B}\).
A zatem, podstawiając za zbiór \(\displaystyle{ B,}\) ten obraz, otrzymujemy:
\(\displaystyle{ \stackrel { \rightarrow }{I _{X} ^{-1} } \left( B\right) = \stackrel { \rightarrow }{I _{X} ^{-1} } \left( \stackrel{ \rightarrow }{I_X} \left( B\right) \right) =}\)
i ponieważ funkcja identyczności jest różnowartościowa, więc to jest równe zbiorowi \(\displaystyle{ B.\square}\)
Dodam jeszcze, że istnieje niepusty zbiór \(\displaystyle{ X,}\) taki, że jedyną funkcją z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest identyczność;
Wystarczy wziąć:
\(\displaystyle{ X= \left\{ 0\right\},}\)
wtedy taka funkcja musi \(\displaystyle{ 0}\) przypisywać \(\displaystyle{ 0}\), a więc jest to identyczność na zbiorze \(\displaystyle{ \left\{ 0\right\}.}\)
Mamy tu kolejne zastosowanie \(\displaystyle{ \left\{ 0\right\}}\).
I mamy jeszcze jedno jego zastosowanie:
Jest to przykład niepustego zbioru \(\displaystyle{ X}\), takiego, że jedyną niepustą relacją z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest identyczność:
Bo biorąc:
\(\displaystyle{ X=\left\{ 0\right\}, }\)
to musi być:
\(\displaystyle{ R= \left\{ \left( 0,0\right) \right\}= I _{\left\{ 0\right\} }.}\)