Porządek na funkcjach

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Porządek na funkcjach

Post autor: Jakub Gurak »

Wczoraj udowodniłem, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ (Y, \le)}\) niepustym zbiorem liniowo uporządkowanym, to w zbiorze \(\displaystyle{ Y^X,}\) czyli w zbiorze wszystkich funkcji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to relacja, że jedna funkcja jest mniejsza od drugiej funkcji, gdy w każdym puncie dziedzin tych funkcji wykres funkcji mniejszej leży poniżej (lub na równi) od wykresu funkcji większej, taka relacja jest istotnie relacją porządku. Jednak łatwo można pokazać, że ten porządek nie musi być liniowy, gdyż dla dwóch funkcji wykres pierwszej funkcji może w pewnym punkcie może leżeć poniżej wykresu drugiej funkcji, a w innym punkcie może leżeć powyżej niż dla drugiej funkcji- dlatego wtedy żadna z tych dwóch funkcji nie jest mniejsza, i porządek nie musi być liniowy. Udowodniłem też, że jeśli w \(\displaystyle{ Y}\) (zachowując oznaczenia), jeśli w \(\displaystyle{ Y}\) jest element najmniejszy \(\displaystyle{ a\in Y}\), to funkcja stale równa \(\displaystyle{ a}\) jest elementem najmniejszym względem porządku na funkcjach, podobnie jeśli w \(\displaystyle{ Y}\) jest element największy \(\displaystyle{ b\in Y}\), to funkcja stale równa \(\displaystyle{ b}\) jest elementem największym. Podobne zależności udowodniłem dla relacji na funkcjach (zachowując oznaczenia), takiej, że jedna funkcja jest większa od drugiej, gdy wykres jej leży w każdym punkcie dziedziny poniżej lub na równi niż wykres funkcji mniejszej, tzn. ze jest to również relacja porządku, ale nie liniowego, i też wyznaczyłem, przy pewnych założeniach elementy najmniejsze i największe. Przedstawię teraz dowody tych ciekawych faktów.

Uściślijmy, w zbiorze \(\displaystyle{ Y^{X}}\), czyli w zbiorze wszystkich funkcji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), rozważamy relację \(\displaystyle{ \sqsubseteq}\):

\(\displaystyle{ f_1\sqsubseteq f_2 \Longleftrightarrow \hbox{ dla każdego } x\in X\hbox{: } f_1(x) \le f_2(x).
}\)


Wykażemy, że \(\displaystyle{ \sqsubseteq}\) jest relacją porządku w \(\displaystyle{ Y^{X}.}\)

Dowód:

Jeśli \(\displaystyle{ X=\emptyset}\), to \(\displaystyle{ Y^X=\left\{ \hbox {funkcja pusta}\right\}}\), a wtedy ta relacja jest liniowym porządkiem w \(\displaystyle{ Y^{\emptyset}}\) ( jako relacja identyczności w zbiorze jednoelementowym). Załóżmy więc dalej, że \(\displaystyle{ X \neq \emptyset.}\)

Niech \(\displaystyle{ f\in Y^{X}}\). Pokażemy najpierw, że \(\displaystyle{ f\sqsubseteq f}\)( bo chcemy pokazać zwrotność). Niech więc \(\displaystyle{ x\in X}\), wtedy \(\displaystyle{ f(x)\in Y}\), więc ponieważ \(\displaystyle{ \left( Y, \le\right)}\) jest zbiorem liniowo uporządkowanym, więc \(\displaystyle{ \le}\) jest zwrotna, skąd \(\displaystyle{ f(x) \le f(x)}\). Z dowolności \(\displaystyle{ x\in X}\), daje to relacje:\(\displaystyle{ f\sqsubseteq f}\). Relacja \(\displaystyle{ \sqsubseteq}\) jest więc zwrotna.

Aby pokazać antysymetrię, to weźmy \(\displaystyle{ f_1,f_2\in Y^X}\), takie, że \(\displaystyle{ f_1\sqsubseteq f_2}\) i \(\displaystyle{ f_2\sqsubseteq f_1.}\) Wtedy \(\displaystyle{ f_1,f_2: X \rightarrow Y}\), i dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_1(x) \le f_2(x);}\) podobnie druga relacja daje, że dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_2(x) \le f_1(x).}\) Niech \(\displaystyle{ x\in X}\), wtedy \(\displaystyle{ f_1(x) \le f_2(x)}\) i \(\displaystyle{ f_2(x) \le f_1(x)}\), ponieważ \(\displaystyle{ f_1(x), f_2(x)\in Y}\), i \(\displaystyle{ \le}\) jest antysymetryczna, wiec \(\displaystyle{ f_1(x)=f_2(x).}\) Z dowolności \(\displaystyle{ x\in X}\), otrzymujemy, że \(\displaystyle{ f_1=f_2}\). A zatem relacja \(\displaystyle{ \sqsubseteq}\) jest antysymetryczna.

Aby pokazać przechodniość, weźmy trzy funkcje \(\displaystyle{ f_1,f_2, f_3\in Y^X}\), (równoważnie \(\displaystyle{ f_1,f_2,f_3:X \rightarrow Y}\)), takie, że \(\displaystyle{ f_1\sqsubseteq f_2\sqsubseteq f_3}\) i pokażmy że \(\displaystyle{ f_1\sqsubseteq f_3}\). Z założonych relacji otrzymujemy, ze:
dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_1(x) \le f_2(x)}\), i
dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_2(x) \le f_3(x).}\)

Niech \(\displaystyle{ x\in X}\), wtedy \(\displaystyle{ f_1(x) \le f_2(x)}\) i \(\displaystyle{ f_2(x) \le f_3(x)}\), ponieważ \(\displaystyle{ f_1(x), f_2(x), f_3(x)\in Y}\), i relacja \(\displaystyle{ \le}\) jest przechodnia, więc wnioskujemy, że \(\displaystyle{ f_1(x) \le f_3(x).}\) Z dowolności \(\displaystyle{ x\in X}\), oznacza to, że \(\displaystyle{ f_1\sqsubseteq f_3}\), relacja \(\displaystyle{ \sqsubseteq}\) jest więc przechodnia.

A zatem \(\displaystyle{ \sqsubseteq}\) jest relacją porządku, i \(\displaystyle{ (Y^X,\sqsubseteq)}\) jest zbiorem uporządkowanym. \(\displaystyle{ \square}\)

Jednak nie musi to być zbiór liniowo uporządkowany, Aby podać kontrprzykład rozważmy przedział \(\displaystyle{ X=\left[ 0,1\right] }\), a za \(\displaystyle{ Y}\) połóżmy ten sam przedział z naturalnym porządkiem, wtedy \(\displaystyle{ (Y=\left[ 0,1\right] , \le _{[0,1] })}\) jest zbiorem liniowo uporządkowanym niepustym. Rozważmy dwie funkcje: \(\displaystyle{ f_1,f_2:X \rightarrow Y}\), dane jako \(\displaystyle{ f_1(x)=x, f_2(x)=1-x.}\)

Wtedy \(\displaystyle{ f_1(0)=0<1=f_2(0)}\), i \(\displaystyle{ f_1(1)=1>0=f_2(1)}\), a zatem \(\displaystyle{ f_1\not\sqsubseteq f_2}\) i \(\displaystyle{ f_2\not\sqsubseteq f_1}\), a zatem porządek \(\displaystyle{ \sqsubseteq}\) nie jest liniowy.

Wykażemy jeszcze, że jeśli w \(\displaystyle{ Y}\) jest element najmniejszy \(\displaystyle{ a\in Y}\), to funkcja \(\displaystyle{ f_0:X \rightarrow Y}\) stale równa \(\displaystyle{ a}\), tzn.
\(\displaystyle{ f_0(x)=a}\), dla każdego \(\displaystyle{ x\in X}\), wtedy funkcja \(\displaystyle{ f_0}\) jest elementem najmniejszym, względem tego porządku na funkcjach.

W tym celu niech \(\displaystyle{ f\in Y^{X}.}\) Pokażemy, że \(\displaystyle{ f_0\sqsubseteq f.}\) W tym celu weźmy \(\displaystyle{ x\in X}\). Wtedy \(\displaystyle{ f(x)\in Y}\), ponieważ \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ Y}\), więc \(\displaystyle{ f_0(x)=a \le f(x)}\), więc z dowolności \(\displaystyle{ x\in X}\), otrzymujemy \(\displaystyle{ f_0\sqsubseteq f}\), a więc \(\displaystyle{ f_0}\) jest elementem najmniejszym.

Analogicznie, symetrycznie udowadniamy, że jeśli w \(\displaystyle{ Y}\) jest element największy \(\displaystyle{ b\in Y}\), to funkcja \(\displaystyle{ f_1:X \rightarrow Y}\) stale równa \(\displaystyle{ b}\), tzn. \(\displaystyle{ f_1(x)=b}\), dla każdego \(\displaystyle{ x\in X}\), taka funkcja \(\displaystyle{ f_1}\) jest elementem największym. Dowód jest analogiczny.

Rozważmy jeszcze, gdy \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ \left( Y, \le\right)}\) niepustym zbiorem liniowo uporządkowanym, to w zbiorze \(\displaystyle{ Y^X}\), rozważmy relacje \(\displaystyle{ \preccurlyeq}\):

\(\displaystyle{ f_1\preccurlyeq f_2 \Longleftrightarrow \hbox { dla każdego } x\in X: f_2(x) \le f_1(x).}\)

Wykażemy, że \(\displaystyle{ \preccurlyeq}\) jest relacją porządku w \(\displaystyle{ Y^X}\). W tym celu wykażemy, że \(\displaystyle{ (\preccurlyeq)=\left( \sqsubseteq ^{-1}\right) , }\) gdzie \(\displaystyle{ \sqsubseteq}\) jest poprzednio rozważanym porządkiem w \(\displaystyle{ Y^X.}\)

Zauważmy najpierw, że \(\displaystyle{ (\sqsubseteq) \subset Y^X \times Y^X}\), więc \(\displaystyle{ (\sqsubseteq) ^{-1}\subset Y^X \times Y^X}\), i \(\displaystyle{ \preccurlyeq\subset Y^X \times Y^X}\), a więc są to relacje w \(\displaystyle{ Y^X}\).

Żeby było łatwiej tymi symbolami operować, to (oznaczmy \(\displaystyle{ R:=\left( \preccurlyeq\right)}\), \(\displaystyle{ S:=\left( \sqsubseteq\right) ^{-1} }\), \(\displaystyle{ T:=\sqsubseteq}\), wtedy \(\displaystyle{ S^{-1}=\sqsubseteq=T}\), a zatem \(\displaystyle{ T^{-1}=\left( S ^{-1}\right) ^{-1}=S}\)), i pokażmy, że \(\displaystyle{ R=S.}\)

Jeśli \(\displaystyle{ (f_1,f_2)\in S}\), wtedy \(\displaystyle{ (f_1, f_2)\in T^{-1}}\), a zatem z określenia relacji odwrotnej \(\displaystyle{ (f_2, f_1)\in T}\), inaczej mówiąc \(\displaystyle{ f_2(T) f_1}\) a zatem \(\displaystyle{ f_2\sqsubseteq f_1}\), a zatem z definicji \(\displaystyle{ \sqsubseteq}\) otrzymujemy, że dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_2(x) \le f_1(x)}\), co oznacza dokładnie, że \(\displaystyle{ f_1\preccurlyeq f_2}\), czyli \(\displaystyle{ (f_1,f_2)\in R}\). Zatem \(\displaystyle{ S\subset R.}\)

Jeśli \(\displaystyle{ (f_1,f_2)\in R}\), to innymi słowy \(\displaystyle{ f_1(R) f_2}\), czyli \(\displaystyle{ f_1\preccurlyeq f_2}\), a zatem dla każdego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_2(x) \le f_1(x)}\) , co oznacza dokładnie, że \(\displaystyle{ f_2\sqsubseteq f_1}\), a zatem \(\displaystyle{ f_1 (\sqsubseteq) ^{-1} f_2}\), czyli \(\displaystyle{ f_1(S) f_2}\), inaczej mówiąc \(\displaystyle{ (f_1,f_2)\in S}\). Zatem \(\displaystyle{ R\subset S}\).

Więc \(\displaystyle{ R=S}\), czyli \(\displaystyle{ \left( \preccurlyeq\right) =\left( \sqsubseteq ^{-1}\right) }\), ponieważ wcześniej wykazałem, że \(\displaystyle{ (\sqsubseteq) }\) jest relacją porządku, więc również \(\displaystyle{ \left( \preccurlyeq\right) =\left( \sqsubseteq ^{-1}\right) }\) jako relacja odwrotna do relacji porządku jest relacją porządku. \(\displaystyle{ \square}\) :lol: 8-)

Również nie musi być to liniowy porządek. Wystarczy rozważyć ten sam kontrprzykład co poprzedni, wtedy porządek \(\displaystyle{ \sqsubseteq}\) nie jest liniowy, zatem również \(\displaystyle{ \preccurlyeq}\) nie jest liniowy, gdyż gdyby był liniowy to również porządek \(\displaystyle{ \left( \preccurlyeq\right) ^{-1} }\)byłby liniowy, co wobec tego, że \(\displaystyle{ \left( \preccurlyeq\right) ^{-1}=\left(\sqsubseteq ^{-1}\right) ^{-1}=\left( \sqsubseteq\right)}\) oznaczałoby, że \(\displaystyle{ \sqsubseteq}\) jest liniowy- sprzeczność. \(\displaystyle{ \square }\):lol:

Zauważmy też, że jeśli element \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ Y}\), to funkcja \(\displaystyle{ f_0(x)=a}\), dla każdego \(\displaystyle{ x\in X}\), funkcja stale równa \(\displaystyle{ a}\), jest elementem największym względem \(\displaystyle{ \preccurlyeq}\). Wiemy bowiem już, że funkcja \(\displaystyle{ f_0}\) jest elementem najmniejszym względem \(\displaystyle{ \sqsubseteq}\), zatem funkcja \(\displaystyle{ f_0}\) jest elementem największym względem \(\displaystyle{ \left( \sqsubseteq^{-1} \right) =\left( \preccurlyeq\right) .}\)

Podobnie, jesli element \(\displaystyle{ b\in Y}\) jest największy w \(\displaystyle{ Y}\), to funkcja stale równa \(\displaystyle{ b}\) jest elementem najmniejszym względem \(\displaystyle{ \preccurlyeq}\). Wiemy już bowiem, że funkcja \(\displaystyle{ f_1}\) jest elementem największym względem \(\displaystyle{ \sqsubseteq}\), a więc funkcja \(\displaystyle{ f_1}\) jest elementem najmniejszym względem \(\displaystyle{ \left( \sqsubseteq ^{-1}\right) =\left( \preccurlyeq\right) .\square }\) :lol: :D
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Porządek na funkcjach

Post autor: Jakub Gurak »

Wczoraj wieczorem, przeglądając ważniaka, wpadłem na pomysł aby zamienić nierówności w pierwszej z definicji tych relacji porządku na funkcjach, na silne nierówności, i udowodniłem, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ \left( Y, \le\right) }\) jest niepustym zbiorem liniowo uporządkowanym, to w zbiorze wszystkich funkcji z \(\displaystyle{ X}\) do \(\displaystyle{ Y,}\) relacja, taka, że jedna funkcja jest mniejsza od drugiej funkcji, gdy wykres funkcji mniejszej, w każdym punkcie dziedziny, leży poniżej niż wykres funkcji większej, taka relacja jest relacją silnego częściowego porządku.
Udowodniłem również, że (przy tych samych założeniach) relacja pomiędzy funkcjami, taka, że jedna funkcja jest mniejsza od drugiej funkcji, gdy wykres funkcji mniejszej, w każdym punkcie dziedziny, leży powyżej tym razem niż wykres funkcji większej (lub gdy te funkcje są równe), taka relacja jest również relacją porządku.
Wykazałem również wczoraj wieczorem, na dwa sposoby, że jeśli w zbiorze \(\displaystyle{ X}\) mamy \(\displaystyle{ n}\) relacji przeciwzwrotnych \(\displaystyle{ R_1, R_2, \ldots, R_n,}\) to ich różnica symetryczna \(\displaystyle{ R_1\oplus R_2\oplus \ldots \oplus R_n}\) jest relacją przeciwzwrotną. Przedstawię teraz dowody tych ciekawych faktów.

Niech \(\displaystyle{ X}\) będzie niepustym zbiorem, a \(\displaystyle{ \left( Y, \le\right) }\) niech będzie niepustym zbiorem liniowo uporządkowanym. W zbiorze \(\displaystyle{ Y ^{X}}\), czyli w zbiorze wszystkich funkcji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) wprowadzamy relację \(\displaystyle{ R}\), daną jako:

\(\displaystyle{ f\left( R\right) g \Longleftrightarrow \left[ \hbox{ dla każdego } x \in X \hbox{: } f\left( x\right) < g(x) \right] \vee f=g.}\)

W powyższej nierówności pomiędzy wartościami funkcji zakładamy, że \(\displaystyle{ f\left( x\right) \neq g\left( x\right) }\), piszę tu to dla jasności.

Czyli jedna funkcja jest mniejsza od drugiej funkcji, gdy jej wykres, w każdym punkcie dziedziny, leży poniżej niż wykres funkcji większej, oto:

ILUSTRACJA TEGO FAKTU: \(\displaystyle{ \\}\)
Funkcja mniejsza od drugiej funkcji, wykres lezy poniżej niż wykres funkcji większej.jpg
\(\displaystyle{ \\}\)
Podajmy teraz dowód tego faktu. Oto:

DOWÓD TEGO FAKTU:

Rozważmy relację \(\displaystyle{ R'}\) na takich funkcjach:

\(\displaystyle{ f\left( R'\right)g \Longleftrightarrow \hbox{ dla każdego } x \in X \hbox{: } f(x) < g(x).}\)

Wykażemy, że relacja \(\displaystyle{ R'}\) jest przeciwzwrotna i przechodnia.

Niech \(\displaystyle{ f \in Y^X}\).
Niech \(\displaystyle{ x \in X \neq \left\{ \right\} }\). Wtedy, niewątpliwie: \(\displaystyle{ f\left( x\right)= f(x)}\), a więc \(\displaystyle{ f\left( x\right) \not< f(x)}\). Oznacza to, że \(\displaystyle{ \left( f,f\right) \not \in R',}\) i relacja \(\displaystyle{ R'}\) jest przeciwzwrotna.

Wykażemy teraz, że relacja \(\displaystyle{ R'}\) jest przechodnia.
W tym celu załóżmy, że \(\displaystyle{ f\left( R'\right)g}\) i \(\displaystyle{ g\left( R'\right)h}\). Oznacza to, że dla każdego \(\displaystyle{ x \in X}\), mamy: \(\displaystyle{ f(x) < g(x)}\); i, dla każdego \(\displaystyle{ x \in X}\): \(\displaystyle{ g(x) <h(x)}\). Niech \(\displaystyle{ x \in X.}\) Wtedy \(\displaystyle{ f\left( x\right)< g\left( x\right)}\) i \(\displaystyle{ g(x)< h(x)}\), a więc z przechodniości silnego porządku \(\displaystyle{ <}\) (mogę to dokładnie udowodnić, już robiłem takie formalne 'zabawy') otrzymujemy, że: \(\displaystyle{ f(h)< h(x)}\), co, wobec dowolności wyboru elementu \(\displaystyle{ x \in X}\), daje, że: \(\displaystyle{ f\left( R'\right) h}\), i relacja \(\displaystyle{ R'}\) jest przechodnia.

Wobec czego relacja \(\displaystyle{ R'}\) jest silnie antysymetryczna, bo gdyby tak nie byłoby, to mielibyśmy \(\displaystyle{ f\left( R'\right)g}\) i \(\displaystyle{ g\left( R'\right) f}\), dla pewnych funkcji \(\displaystyle{ f,g \in Y^X}\), a więc z przechodniości otrzymalibyśmy, że: \(\displaystyle{ f\left( R'\right)f}\)- co przeczy przeciwzwrotności relacji \(\displaystyle{ R'}\). Wobec czego relacja \(\displaystyle{ R'}\) jest silnie antysymetryczna, i jest silnym porządkiem częściowym.

Wobec czego relacja \(\displaystyle{ R''}\) dana jako:

\(\displaystyle{ f\left( R''\right) g \Longleftrightarrow f\left( R'\right)g \vee f=g;}\)

jest relacją porządku.

Wtedy \(\displaystyle{ R''=R}\), a więc również relacja \(\displaystyle{ R}\) jest relacją porządku,
i \(\displaystyle{ \left( Y ^{X}, R \right)}\) jest zbiorem uporządkowanym\(\displaystyle{ .\square}\) :lol:


Rozważmy teraz drugą relacje \(\displaystyle{ R}\) na funkcjach (przy tych samych założeniach):

\(\displaystyle{ f \left( R\right) g \Longleftrightarrow\left[ \hbox{ dla każdego } x \in X \hbox{: } f(x)>g(x)\right] \vee f=g}\).

Wykażemy, że jest to relacja porządku.

DOWÓD TEGO FAKTU:

Rozważmy relację \(\displaystyle{ R'}\) na takich funkcjach:

\(\displaystyle{ f\left( R'\right)g \Longleftrightarrow \left[ \hbox{ dla każdego } x \in X\hbox{: } f(x) < g(x) \right] \vee f=g}\).

Wiemy już, że relacja \(\displaystyle{ R'}\) jest relacją porządku.
A zatem również relacja do niej odwrotna \(\displaystyle{ S:= \left( R'\right) ^{-1}}\) jest relacją porządku. Łatwo jest pokazać, że \(\displaystyle{ S=R.}\) Ponieważ relacja \(\displaystyle{ S}\) jest relacją porządku, więc również relacja \(\displaystyle{ R}\), jako ta sama relacja, w tym samym zbiorze \(\displaystyle{ Y^X,}\) jest relacją porządku.\(\displaystyle{ \square}\)

Czyli względem tego porządku jedna funkcja jest mniejsza od drugiej funkcji, gdy wykres funkcji mniejszej, w każdym punkcie dziedziny, leży powyżej niż wykres funkcji większej. Oto:

ILUSTRACJA TEGO FAKTU: \(\displaystyle{ \\}\)
Funkcja mniejsza od drugiej funkcji, wykres lezy powyżej niż wykres funkcji większej.jpg
\(\displaystyle{ \\}\)
Wykażemy jeszcze, zgodnie z zapowiedzią, że jeśli w zbiorze \(\displaystyle{ X}\) mamy \(\displaystyle{ n}\) relacji przeciwzwrotnych, to ich różnica symetryczna jest relacją przeciwzwrotną.

Zauważmy najpierw, że jeśli w zbiorze \(\displaystyle{ X}\) mamy dwie relacje przeciwzwrotne \(\displaystyle{ R}\) i \(\displaystyle{ S}\), to ich różnica symetryczna jest relacją przeciwzwrotną, gdyż:

Z definicji różnicy symetrycznej:

\(\displaystyle{ R\oplus S \subset R \cup S}\),

gdzie relacja \(\displaystyle{ R \cup S}\), jako suma dwóch relacji przeciwzwrotnych jest relacją przeciwzwrotną, i w efekcie różnica symetryczna \(\displaystyle{ R\oplus S,}\) jako podzbiór relacji przeciwzwrotnej, jest relacją przeciwzwrotną.

Ponieważ operacja różnicy symetrycznej jest operacją łączną, to przez prostą indukcją otrzymamy, że jeśli w zbiorze \(\displaystyle{ X}\) mamy \(\displaystyle{ n}\) relacji przeciwzwrotnych \(\displaystyle{ R_1, R_2,\ldots, R_n}\), to ich różnica symetryczna \(\displaystyle{ R_1\oplus R_2\oplus \ldots \oplus R_n}\) jest relacją przeciwzwrotną.

Można też inaczej, wykorzystując charakteryzację różnicy symetrycznej zbiorów \(\displaystyle{ X_1, X_2,\ldots, X_n}\):

Różnica symetryczna \(\displaystyle{ X_1\oplus X_2\oplus \ldots\oplus X_n}\) składa się dokładnie z tych elementów sumy \(\displaystyle{ X_1 \cup X_2 \cup \ldots \cup X_n}\), które należą do dokładnie nieparzystej ilości zbiorów spośród zbiorów \(\displaystyle{ X_1, X_2,\ldots, X_n}\).

Np. dla \(\displaystyle{ n=2}\) możliwe ilości zbiorów, spośród zbiorów \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\), do których dany element może należeć to: \(\displaystyle{ 0,1}\) i \(\displaystyle{ 2}\). Tylko \(\displaystyle{ 1}\) jest liczbą nieparzystą; i rzeczywiście różnica symetryczna zbiorów \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\) składa się dokładnie z tych elementów, które należą do dokładnie jednego spośród tych dwóch zbiorów.
Np. dla \(\displaystyle{ n=3}\), możliwe ilości zbiorów spośród zbiorów \(\displaystyle{ X_1, X_2}\) i \(\displaystyle{ X_3}\) do których dany element może należeć to: \(\displaystyle{ 0,1,2}\) i \(\displaystyle{ 3.}\) Tylko \(\displaystyle{ 1}\) i \(\displaystyle{ 3}\) są liczbami nieparzystymi; I rzeczywiście, różnica symetryczna trzech zbiorów składa się z trzech kawałków które są kawałkami dokładnie jednego spośród tych trzech zbiorów, oraz z części wspólnej wszystkich tych trzech zbiorów. Oto:

ILUSTRACJA TEGO FAKTU: \(\displaystyle{ \\}\)
Różnica symetryczna trzech zbiorów.jpg
\(\displaystyle{ \\}\) Dla innych \(\displaystyle{ n}\)- trzeba to udowodnić, ale...- jest to znane, proste zadanie ze Wstępu do Matematyki.

Przejdźmy do dowodu naszego faktu:

DRUGI DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ x \in X}\), i rozważmy parę \(\displaystyle{ \left( x,x\right) \in I_X.}\)

Ponieważ relację \(\displaystyle{ R_i}\), dla \(\displaystyle{ i=1,2,\ldots, n}\) są przeciwzwrotne, to są rozłączne z przekątną \(\displaystyle{ I_X}\), skąd \(\displaystyle{ R_i \cap I_X= \left\{ \right\}}\) , a ponieważ \(\displaystyle{ \left( x,x\right) \in I_X}\), więc \(\displaystyle{ \left( x,x\right) \not\in R_i}\), i, otrzymujemy, że taka własność zachodzi dla każdego \(\displaystyle{ i=1,2,\ldots, n}\), czyli para \(\displaystyle{ \left( x,x\right) }\) nie należy do żadnej z tych relacji \(\displaystyle{ R_1, R_2, \ldots, R_n}\). Ponieważ \(\displaystyle{ 0}\) jest liczbą parzystą, więc na mocy przytoczonej charakteryzacji różnicy symetrycznej: \(\displaystyle{ \left( x,x\right) \not \in R_1\oplus R_2\oplus \ldots\oplus R_n;}\), i, z dowolności wyboru elementu \(\displaystyle{ x \in X,}\) otrzymujemy, że różnica symetryczna \(\displaystyle{ R_1\oplus R_2\oplus \ldots \oplus R_n}\) jest zbiorem rozłącznym z przekątną \(\displaystyle{ I_X}\), jest więc relacją przeciwzwrotną\(\displaystyle{ .\square }\) 8-)
ODPOWIEDZ