Niech zatem \(\displaystyle{ X}\) będzie zbiorem. Zadajmy ciekawe pytania:
1. Czym jest zbiór wszystkich relacji równoważności w X, które są równocześnie relacjami porządku na X ?
2. Czym jest zbiór wszystkich relacji równoważności w X, które są równocześnie funkcjami z X do X?
3. Czym jest zbiór wszystkich relacji porządku w X, które są równocześnie funkcjami z X do X?
Odpowiedź na każde z trzech pytań jest taka sama: jest to zbiór jednoelementowy złożony z relacji identyczności \(\displaystyle{ I _{X}.}\)
Relacja identyczności \(\displaystyle{ I _{X} }\) jest relacją równoważności. Jest też relacją porządku- aby to pokazać pokażemy antysymetrię: niech \(\displaystyle{ \left( x,y\right) \in I _{X },\left( y,x\right) \in I _{X }}\). Pokażemy, że \(\displaystyle{ x=y.}\). Ale założenie \(\displaystyle{ \left( x,y\right) \in I _{X } }\) oznacza, że x=y. W ten zabawnie prosty sposób sprawdziliśmy antysymetrię, a więc relacja identyczności jest relacją porządku. Jest też funkcją z X do X. Aby to wykazać, to przypuśćmy, że \(\displaystyle{ \left( x,x _{1} \right)\in I_X}\) i \(\displaystyle{ \left( x,x _{2} \right)\in I_X}\). Założenie \(\displaystyle{ \left( x,x _{1} \right)\in I_X}\) oznacza, że \(\displaystyle{ x=x_1}\), podobnie założenie \(\displaystyle{ \left( x,x _{2} \right)\in I_X}\) oznacza, że \(\displaystyle{ x=x_2}\); a zatem \(\displaystyle{ x_1=x_2}\). Łatwo się też przekonać, że zgodnie z intuicją \(\displaystyle{ \left( I_{X}\right) _{L}=X }\). Zatem \(\displaystyle{ I _{X} }\) jest funkcją z \(\displaystyle{ X}\) do \(\displaystyle{ X}\).
A więc identyczność spełnia wszystkie te trzy pytania. Pozostaje pokazać, że nie ma innych takich relacji- na każde z trzech pytań odpowiemy oddzielnie.
1. Przypuśćmy, że istnieje relacja równoważności \(\displaystyle{ R \neq I _{X } }\) w \(\displaystyle{ X}\) będąca relacją porządku. Ponieważ R nie jest relacją identyczności, to relacja R ma w sobie parę \(\displaystyle{ \left( x,y\right) }\) , gdzie \(\displaystyle{ x \neq y}\). Relacja ta jako relacja równoważności jest symetryczna, a więc \(\displaystyle{ \left( y,x\right) \in R. }\) Ponieważ jednak jest również relacją porządku, więc jest antysymetryczna, więc ponieważ \(\displaystyle{ \left(x,y \right) \in R }\) oraz \(\displaystyle{ \left( y,x\right) \in R,}\) więc x=y- sprzeczność.
2.Przypuśćmy, że istnieje relacja równoważności \(\displaystyle{ R \neq I _{X } }\) w X będąca funkcją z X do X. Ponieważ R nie jest relacją identyczności, to relacja R ma w sobie parę \(\displaystyle{ \left( x,y\right), }\) gdzie \(\displaystyle{ x \neq y.}\) Jako relacja równoważności jest zwrotna, więc \(\displaystyle{ \left( x,x\right) \in R. }\) Ponieważ jest to funkcja, a \(\displaystyle{ \left( x,y\right) \in R }\) oraz \(\displaystyle{ \left( x,x\right) \in R ,}\) więc y=x- sprzeczność.
3.Przypuśćmy, że istnieje relacja porządku \(\displaystyle{ R \neq I _{X } }\) na X będąca funkcją z X do X. Ponieważ R nie jest relacją identyczności, więc relacja ma w sobie parę \(\displaystyle{ \left( x,y\right) }\) gdzie \(\displaystyle{ x \neq y.}\) Jako relacja porządku jest zwrotna, więc \(\displaystyle{ \left( x,x\right) \in R. }\) A ponieważ jest to funkcja, a \(\displaystyle{ \left( x,y\right) \in R }\) oraz \(\displaystyle{ \left( x,x\right) \in R, }\) więc y=x- sprzeczność.
A zatem odpowiedzią na każde z trzech pytań jest: jest to \(\displaystyle{ \left\{ I _{X} \right\}. }\)
Niech teraz \(\displaystyle{ X,Y}\) będą zbiorami, niech \(\displaystyle{ f:X \rightarrow Y}\), funkcja ta wyznacza relację równoważności \(\displaystyle{ \sim _{f} }\) na zbiorze \(\displaystyle{ X}\) zdefiniowaną następująco:
\(\displaystyle{ x _{1} \sim _{f} x _{2} \Longleftrightarrow f\left( x _{1} \right)=f\left( x_{2} \right).}\)
W myśl tej definicji dwa elementy zbioru X są w relacji \(\displaystyle{ \sim _{f} }\), gdy funkcja \(\displaystyle{ f }\) na tych elementach przyjmuję te same wartości. Wykażemy, że ta relacja jest relacją równoważności
Można to udowodnić tradycyjnie- sprawdzić zwrotność, symetrczność, przechodniość, ale można też przeprowadzić
CIEKAWSZY DOWÓD :
Rozważmy rodzinę zbiorów \(\displaystyle{ \mathbb {B}}\)
\(\displaystyle{ \mathbb{B}=\left\{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y\right\}\Bigl| \ \ y \in f _{P}=\stackrel { \rightarrow }{f}\left( X\right) \right\}. }\) Pokażemy krótko, że ta rodzina zbiorów jest rozkładem zbioru X. Zbiory tej rodziny są rozłączne, gdyż przeciwobrazy różnych zbiorów jednoelementowych są rozłączne . \(\displaystyle{ \bigcup\mathbb {B}=X}\), gdyż ta suma jako suma rodziny podzbiorów X musi być podzbiorem zbioru X. W drugą stronę: jeśli \(\displaystyle{ x\in X}\), to \(\displaystyle{ x \in \stackrel { \rightarrow } {f ^{-1} }\left\{ f\left( x\right) \right\}, }\) a więc x należy do zbioru tej rodziny, a zatem \(\displaystyle{ x \in\bigcup\mathbb{B}.}\) Wobec czego rodzina \(\displaystyle{ \mathbb {B}}\) jest rozkładem zbioru X. W związku z czym relacja \(\displaystyle{ R _{\mathbb{B} } }\) na zbiorze X, taka, że dwa elementy zbioru X są w tej relacji, gdy należą do tego samego zbioru rozkładu \(\displaystyle{ \mathbb{B} }\), taka relacja jest relacją równoważności, (i zbiorem wszystkich klas równoważności jest właśnie ten rozkład \(\displaystyle{ \mathbb{B} }\)). Pokażemy teraz, że \(\displaystyle{ R _{\mathbb {B}} =\sim _{f} .}\)
Pokażemy najpierw, że dowolne dwa elementy \(\displaystyle{ x _{1},x _{2} \in X}\) są w relacji \(\displaystyle{ \sim}\), wtedy i tylko wtedy, gdy \(\displaystyle{ x _{1},x _{2} }\) należą do pewnego tego samego zbioru rodziny \(\displaystyle{ \mathbb {B}.}\)
Niech \(\displaystyle{ x _{1},x _{2} \in X.}\)
Przypuśćmy, że \(\displaystyle{ x _{1}\sim x _{2}. }\) Jest to równoważne równości \(\displaystyle{ f\left( x _{1} \right)= f\left( x _{2}\right). }\)
Pozostaje pokazać, że dla \(\displaystyle{ x _{1}, x _{2} \in X}\), mamy \(\displaystyle{ f\left( x _{1} \right) =f \left( x _{2} \right), }\) wtedy i tylko wtedy, gdy \(\displaystyle{ x _{1},x _{2} }\) należą do pewnego tego samego zbioru rodziny \(\displaystyle{ \mathbb {B}}\).
Aby to pokazać,to:
Niech \(\displaystyle{ x _{1},x _{2} \in X }\).
Jeśli \(\displaystyle{ f\left( x _{1} \right) =f\left( x _{2} \right) , }\) to oznaczmy tą wartość jako \(\displaystyle{ y}\), wtedy:
\(\displaystyle{ x _{1} \in \stackrel { \rightarrow }{f ^{-1} }\left\{ f\left( x _{1} \right) \right\} =\stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\} = \stackrel {\rightarrow }{f ^{-1} }\left\{ f\left( x _{2} \right) \right\}\ni x _{2}. }\) Otrzymujemy zatem, że elementy \(\displaystyle{ x _{1},x _{2} }\) należą do tego samego zbioru rodziny B.
Jeśli \(\displaystyle{ f\left( x _{1} \right) \neq f\left( x _{2} \right) }\), to zauważmy że \(\displaystyle{ x _{1} \in\stackrel { \rightarrow }{f ^{-1} }\left\{ f\left( x _{1} \right) \right\}}\) oraz \(\displaystyle{ x _{2} \in\stackrel { \rightarrow }{f ^{-1} }\left\{ f\left( x _{2} \right) \right\}. }\) Ponieważ \(\displaystyle{ f\left( x _{1} \right) \neq f\left( x _{2} \right),}\) to te przeciwobrazy są rozłączne, i są różne. Otrzymujemy zatem, że elementy \(\displaystyle{ x _{1},x _{2} \in X }\) należą do różnych zbiorów rodziny B(i ponieważ rodzina B jest rozkładem, i składa się ze zbiorów rozłącznych, więc te dwa elementy nie mogą należeć do tego samego zbioru tej rodziny B ).
Jeśli teraz to wszystko pozbieramy otrzymamy naszą wlasność relacji \(\displaystyle{ \sim,}\) a następnie (ponieważ rodzina B jest rozkładem), że \(\displaystyle{ \sim=R _{\mathbb {B}}.}\) Ponieważ relacja \(\displaystyle{ R _{\mathbb {B}} }\) jest relacją równoważności, więc to oznacza, że również \(\displaystyle{ \sim}\) jest relacją równoważności.\(\displaystyle{ \square}\)
