Relacje trójczłonowe

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

Relacje trójczłonowe

Post autor: Jakub Gurak »

Wczoraj udowodniłem, że jeśli \(\displaystyle{ X, Y}\) i \(\displaystyle{ Z}\) są zbiorami, i gdy rozważymy kostkę \(\displaystyle{ \left( X \times Y\right) \times Z}\), oraz dowolną relację trójczłonową \(\displaystyle{ R \subset \left( X \times Y\right) \times Z}\), to istnieje maksymalna, względem relacji przedłużania funkcji , istnieje maksymalna funkcja częściowa zawarta w relacji \(\displaystyle{ R}\).

Dla zbioru \(\displaystyle{ X}\), rozważmy zbiór:

\(\displaystyle{ I _{X} ^{3}= \left\{ \left( x,x,x\right)\Bigl| \ \ x \in X\right\} \subset X ^{3}= X \times X \times X.}\)

Taką przekątną sześcianu kartezjańskiego zbioru \(\displaystyle{ X,}\) nazwijmy trójidentycznością.

Dla relacji trójczłonowej \(\displaystyle{ R \subset X ^{3}}\), powiemy, że relacja \(\displaystyle{ R}\) jest trójzwrotna, gdy dla każdego \(\displaystyle{ x \in X}\), zachodzi: \(\displaystyle{ \left( x,x,x\right) \in R.}\)

Ostatnio udowodniłem również, że relacja \(\displaystyle{ R \subset X^3 }\) jest relacją trójzwrotną, dokładnie wtedy, gdy zawiera relację trójidentyczności.

Udowodniłem również, że przekrój dwóch relacji trójzwrotnych jest relacją trójzwrotną, jak i udowodniłem, że jeśli mamy dowolną relację \(\displaystyle{ R \subset X^3}\), relację trójzwrotną, to zarówno pierwsza dziedzina tej relacji, jaki i jej druga dziedzina, jak i jej trzecia dziedzina jest równa całemu zbiorowi \(\displaystyle{ X}\). Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R \subset X^3}\) niech będzie dowolną relacją. Wykażemy, że:

\(\displaystyle{ R \hbox{ jest relacją trójzwrotną} \Longleftrightarrow R\supset I_X ^{3},}\)

czyli relacja jest trójzwrotna, gdy zawiera trójidentyczność.
DOWÓD TEGO FAKTU::    
A zatem, łatwo jest udowodnić, że:

jeśli mamy relację \(\displaystyle{ R \subset X^3,}\) relację trójzwrotną, oraz mamy relację \(\displaystyle{ S \subset X^3}\), taką, że \(\displaystyle{ S\supset R}\), to relacja \(\displaystyle{ S}\) jest trójzwrotna;

czyli każda relacja \(\displaystyle{ S \subset X^3}\) (czyli relacja pomiędzy tymi samymi zbiorami, co relacja \(\displaystyle{ R}\) ), będąca nadzbiorem tej relacji trójzwrotnej, jest również relacją trójzwrotną- wynika to łatwo z faktu udowodnionego powyżej i na mocy przechodniości inkluzji, możemy łatwo to udowodnić.

Łatwo stąd wynika, że suma dwóch relacji trójzwrotnych \(\displaystyle{ R,S \subset X ^{3}}\) jest relacją trójzwrotną.

Wykażemy jeszcze, że jeśli mamy dwie relacje \(\displaystyle{ R,S \subset X ^{3}}\), relacje trójzwrotne, to ich przekrój \(\displaystyle{ R \cap S}\) jest relacją trójzwrotną.

DOWÓD TEGO FAKTU:

Ponieważ relacja \(\displaystyle{ R}\) jest trójzwrotna, to \(\displaystyle{ R\supset I _{X} ^{3}.}\) Podobnie otrzymujemy \(\displaystyle{ S\supset I_X ^{3}}\). A zatem trójidentyczność \(\displaystyle{ I _{X} ^{3}}\), zawiera się zarówno w relacji \(\displaystyle{ R}\) jak i w relacji \(\displaystyle{ S}\), a więc zawiera się również w ich przecięciu, czyli \(\displaystyle{ I_X ^{3} \subset R \cap S}\) , a więc relacja \(\displaystyle{ R \cap S}\) jest relacją trójzwrotną\(\displaystyle{ .\square}\)

Wykażemy jeszcze, że jeśli \(\displaystyle{ R \subset X^3}\) jest relacją trójzwrotną, to:

\(\displaystyle{ D _{1} \left( R\right) = X= D_2\left( R\right) = D_3 \left( R\right) ,}\)

czyli zarówno pierwsza dziedzina tej relacji \(\displaystyle{ R}\), jak i jej druga dziedzina, jak i jej trzecia dziedzina, są równe całermu zbiorowi \(\displaystyle{ X}\).

Podajmy najpierw pewien Lemat, który wykorzystamy tutaj :

Lemat. Jeśli \(\displaystyle{ X, Y}\) i \(\displaystyle{ Z}\) są zbiorami, to rozważmy kostkę \(\displaystyle{ \left( X \times Y\right) \times Z}\).
Rozważmy dwie relacje trójczłonowe \(\displaystyle{ R,S \subset \left( X \times Y\right) \times Z}\), takie, że \(\displaystyle{ R \subset S}\).
Wtedy:

1) \(\displaystyle{ D_1\left( R\right) \subset D_1\left( S\right) ;}\)
2) \(\displaystyle{ D_2\left( R\right) \subset D_2\left( S\right) ;}\)
3) \(\displaystyle{ D_3\left( R\right) \subset D_3\left( S\right) .}\)
PROSTY DOWÓD TEGO FAKTU::    
Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Łatwo jest zauważyć, że \(\displaystyle{ D_1\left( I_{X} ^{3} \right) =X= D_2\left( I _{X} ^{3} \right) = D_3\left( I_{X} ^{3} \right) ,}\)

a ponieważ relacja \(\displaystyle{ R}\) jest trójzwrotna, więc \(\displaystyle{ R\supset I _{X} ^{3},}\) a zatem, na mocy powyższego Lematu:

\(\displaystyle{ D_1\left( R\right) \supset D_1\left( I _{X} ^{3} \right) =X,}\)

czyli \(\displaystyle{ D_1\left( R\right) \supset X,}\) i stąd \(\displaystyle{ D_1\left( R\right) =X.}\)

Podobnie, na mocy naszego Lematu: \(\displaystyle{ D_2\left( R\right) \supset D_2\left( I _{X} ^{3} \right)=X,}\) i \(\displaystyle{ D_2\left( R\right) =X;}\)

i w podobny sposób uzasadniamy, że \(\displaystyle{ D_3\left( R\right) =X.\square}\)


Rozważmy jeszcze jeden problem, ten z funkcjami częściowymi:

Rozważmy trzy zbiory \(\displaystyle{ X, Y}\) i \(\displaystyle{ Z.}\)
Rozważmy kostkę \(\displaystyle{ \left( X \times Y\right) \times Z}\), oraz dowolną relację \(\displaystyle{ R \subset \left( X \times Y\right) \times Z.}\)
Wykażemy, że istnieje maksymalna, względem inkluzji (czyli względem relacji przedłużania funkcji), istnieje maksymalna funkcja częściowa z \(\displaystyle{ X \times Y}\) do \(\displaystyle{ Z,}\) zawarta w relacji \(\displaystyle{ R}\).

DOWÓD TEGO FAKTU:

Niech:

\(\displaystyle{ \mathbb{B}= \left\{ f \subset \left( X \times Y\right) \times Z\Bigl| \ \ f\hbox{ jest funkcją częściową i } f \subset R \right\} .}\)

Wtedy \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) jest zbiorem uporządkowanym.

Stosujemy do niego Lemat Kuratowskiego-Zorna.

W tym celu ustalmy dowolny łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\). Jako ograniczenie górne bierzemy (jak zwykle) zbiór \(\displaystyle{ \bigcup\mathbb{D}}\).
Musimy jednak wpierw wykazać, że \(\displaystyle{ \bigcup\mathbb{D} \in \mathbb{B}}\) (ograniczenie górne danego łańcucha musi należeć do zbioru uporządkowanego, czyli u nas do zbioru \(\displaystyle{ \mathbb{B}}\) ).

Niewątpliwie:

\(\displaystyle{ \bigcup\mathbb{D} \subset \left( X \times Y\right) \times Z,}\) (jest to suma podzbiorów zbioru \(\displaystyle{ \left( X \times Y\right) \times Z}\)).

Wykażemy teraz, że dla dowolnych dwóch funkcji \(\displaystyle{ f_1,f_2 \in \mathbb{D}}\) jedna jest rozszerzeniem drugiej .
Niech \(\displaystyle{ f_1,f_2 \in \mathbb{D}}\) . Ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem, względem inkluzji, więc \(\displaystyle{ f_1 \subset f_2}\) lub \(\displaystyle{ f_2 \subset f_1}\). W pierwszym przypadku \(\displaystyle{ f_2}\) rozszerza \(\displaystyle{ f_1,}\) a w drugim \(\displaystyle{ f_1}\) rozszerza \(\displaystyle{ f_2}\). A zatem otrzymujemy, że rzeczywiście dla dowolnych dwóch funkcji \(\displaystyle{ f_1,f_2 \in \mathbb{D}}\) jedna jest rozszerzeniem drugiej.

A zatem, ponieważ rodzina \(\displaystyle{ \mathbb{D}}\) jest rodziną funkcji częściowych z \(\displaystyle{ \left( X \times Y\right)}\) do \(\displaystyle{ Z,}\) i rodzina \(\displaystyle{ \mathbb{D}}\) spełnia powyższy warunek, a więc, na mocy pewnego (prostego) faktu o sumie funkcji częściowych, otrzymujemy, że: zbiór \(\displaystyle{ \bigcup\mathbb{D}}\) jest funkcją częściową.

I mamy \(\displaystyle{ \bigcup\mathbb{D} \subset R}\), bo jeśli \(\displaystyle{ f \in \mathbb{D} \subset \mathbb{B}}\), to \(\displaystyle{ f \in \mathbb{B}}\) , a więc, z definicji rodziny \(\displaystyle{ \mathbb{B}}\), możemy wnioskować, że \(\displaystyle{ f \subset R}\); a zatem każda funkcja \(\displaystyle{ f \in \mathbb{D}}\) jest podzbiorem relacji \(\displaystyle{ R}\), więc również suma \(\displaystyle{ \bigcup\mathbb{D} \subset R}\) jest podzbiorem relacji \(\displaystyle{ R}\).

A zatem \(\displaystyle{ \bigcup\mathbb{D} \in \mathbb{B}}\), a zatem \(\displaystyle{ \bigcup\mathbb{D} = \bigvee \mathbb{D}}\)- suma rodziny \(\displaystyle{ \mathbb{D} }\) jest jej supremum, względem inkluzji, a więc w szczególności jest jej ograniczeniem górnym- tego łańcucha \(\displaystyle{ \mathbb{D} }\); i, z dowolności wyboru takiego łańcucha, otrzymujemy, że każdy łańcuch w \(\displaystyle{ \left( \mathbb{B}, \subset \right)}\) ma ograniczenie górne.

Korzystając z lematu Kuratowskiego- Zorna otrzymujemy element maksymalny \(\displaystyle{ f \in \mathbb{B} }\).
Jest to maksymalna, względem inkluzji, funkcja częściowa zawarta w relacji \(\displaystyle{ R.\square }\)


Na koniec dodam coś prostego:

Dla dowolnych zbiorów \(\displaystyle{ A,B}\), mamy:

jeśli \(\displaystyle{ A \cup B= B}\), to \(\displaystyle{ A \cap B =A .}\)

(Chodzi o sytuację gdy \(\displaystyle{ A \subset B}\)).

PROSTY DOWÓD TEGO FAKTU:

Niewątpliwie \(\displaystyle{ A \cap B \subset A.}\)

Aby pokazać inkluzję w drugą stronę, to skorzystamy z faktu mówiącego, że jeśli jeden i ten sam zbiór zawiera się w drugim i trzecim zbiorze, to zawiera się również w ich przecięciu- jest to prosty fakt.

Na mocy założenia, podstawiamy za zbiór \(\displaystyle{ B}\), i otrzymujemy:

\(\displaystyle{ A \cap B= A \cap \left( A \cup B\right) ,}\)

i ponieważ \(\displaystyle{ A \subset A}\),\(\displaystyle{ A \subset A \cup B}\), to na mocy wspomnianego faktu:

\(\displaystyle{ A \subset A \cap \left( A \cup B\right) =A \cap B}\),

i \(\displaystyle{ A \cap B=A.\square}\) :lol: 8-)

Dodano po 1 miesiącu 12 dniach 22 godzinach 20 minutach 58 sekundach:
Wczoraj udowodniłem, że jeśli mamy rodzinę relacji trójczłonowych pomiędzy trzema zbiorami, to pierwsza dziedzina, czyli rzut tej sumy na pierwszą oś, pierwsza dziedzina sumy tej rodziny relacji jest równa sumie pierwszych dziedzin relacji tej rodziny. Podobnie druga dziedzina sumy tej rodziny relacji jest równa sumie drugich dziedzin relacji tej rodziny, i podobny fakt zachodzi dla trzecich dziedzin.
Udowodniłem również, że jeśli mamy dwie relacje trójczłonowe w danym zbiorze, to pierwsza dziedzina przekroju tych dwóch relacji może być innym zbiorem niż przekrój pierwszych dziedzin tych relacji; i podobny fakt zachodzi dla drugich oraz dla trzecich dziedzin relacji. Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy kostkę \(\displaystyle{ \left( X \times Y\right) \times Z.}\)
Rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) relacji trójczłonowych pomiędzy zbiorami \(\displaystyle{ X, Y}\) i \(\displaystyle{ Z}\).
Wykażemy prawo:

\(\displaystyle{ D_1\left( \bigcup\mathbb{B}\right) = \bigcup_{R \in \mathbb{B}} D_1\left( R\right) }\),

czyli wykażemy, że pierwsza dziedzina sumy tej rodziny relacji jest równa sumie pierwszych dziedzin relacji tej rodziny, oraz:

\(\displaystyle{ D_2\left( \bigcup\mathbb{B}\right) = \bigcup_{R \in \mathbb{B}} D_2\left( R\right),}\)

druga dziedzina sumy tej rodziny relacji jest równa sumie drugich dziedzin relacji tej rodziny.

I podobny fakt zachodzi dla trzecich dziedzin, tzn.:

\(\displaystyle{ D_3\left( \bigcup\mathbb{B}\right) = \bigcup_{R \in \mathbb{B}} D_3\left( R\right).}\)

DOWÓD TEGO FAKTU:

Aby wykazać pierwszą równość, zauważmy najpierw, że zarówno zbiór po lewej stronie równości jak i zbiór po prawej stronie są podzbiorami zbioru \(\displaystyle{ X.}\)

Jeśli \(\displaystyle{ x \in D_1\left( \bigcup\mathbb{B}\right)}\) , to \(\displaystyle{ \left( x,y,z\right) \in \bigcup\mathbb{B}}\), dla pewnych elementów \(\displaystyle{ y \in Y}\) i \(\displaystyle{ z \in Z}\). Wtedy \(\displaystyle{ \left( x,y,z\right) \in R}\), gdzie \(\displaystyle{ R \in \mathbb{B}}\) , a zatem \(\displaystyle{ x \in D_1\left( R\right) }\), gdzie \(\displaystyle{ R \in \mathbb{B}}\), a zatem tym bardziej \(\displaystyle{ x \in \bigcup_{R \in \mathbb{B}} D_1\left( R\right) }\).

Jeśli \(\displaystyle{ x \in \bigcup_{R \in \mathbb{B}} D_1\left( R\right) }\), to \(\displaystyle{ x \in D_1\left( R\right) }\), gdzie \(\displaystyle{ R \in \mathbb{B}}\). Wtedy \(\displaystyle{ \left( x,y,z\right) \in R}\), dla pewnych elementów \(\displaystyle{ y}\) i \(\displaystyle{ z}\). Ponieważ \(\displaystyle{ R \in \mathbb{B}}\), to \(\displaystyle{ \left( x,y,z\right) \in \bigcup\mathbb{B}}\), a stąd \(\displaystyle{ x \in D_1\left( \bigcup\mathbb{B}\right)}\), co kończy dowód pierwszej równości.

W ukrytej treści poniżej przedstawiam dowód drugiej z tych równości:
DOWÓD TEGO FAKTU::    

Wykażemy teraz, że jeśli mamy dwie relacje trójczłonowe w danym zbiorze, to pierwsza dziedzina przekroju tych dwóch rekcji może być innym zbiorem niż przekrój pierwszych dziedzin tych relacji.

Niech \(\displaystyle{ X=Y=Z=\RR}\), i niech:
\(\displaystyle{ R= \left[ 0,1\right] \times \left[ 0,1\right] \times \left[ 0,1\right] }\), \(\displaystyle{ S= \left[ 0,1\right] \times \left[ 0,1\right] \times \left[ 2,3\right] .}\)

Wtedy relacje \(\displaystyle{ R}\) i \(\displaystyle{ S}\) są rozłączne, a zatem \(\displaystyle{ R \cap S= \left\{ \right\}}\), i wtedy \(\displaystyle{ D_1\left( \emptyset\right) = \emptyset}\), bo gdyby \(\displaystyle{ x \in D_1\left( \emptyset \right)}\), to \(\displaystyle{ \left( x,y,z\right) \in \emptyset}\), dla pewnych elementów \(\displaystyle{ y}\) i \(\displaystyle{ z}\)- sprzeczność. A zatem \(\displaystyle{ D_1\left( \emptyset\right) = \emptyset.}\)

A zatem:

\(\displaystyle{ D_1\left( R \cap S\right) = D_1\left( \emptyset\right) =\emptyset}\),

podczas gdy:

\(\displaystyle{ D_1\left( R\right) \cap D_1\left( S\right)= \left[ 0,1\right] \cap \left[ 0,1\right] = \left[ 0,1\right] \neq \left\{ \right\} = D_1\left( R \cap S\right) }\).

Podobnie, druga dziedzina przekroju dwóch relacji trójczłonowych w danym zbiorze może być innym zbiorem przekrój drugich dziedzin tych relacji.

Wystarczy rozważyć ten sam kontrprzykład co powyżej, tzn.:

\(\displaystyle{ X=Y=Z=\RR}\), oraz:
\(\displaystyle{ R= \left[ 0,1\right] \times \left[ 0,1\right] \times \left[ 0,1\right]}\) i \(\displaystyle{ S= \left[ 0,1\right] \times \left[ 0,1\right] \times \left[ 2,3\right] .}\)

Wtedy relacje \(\displaystyle{ R}\) i \(\displaystyle{ S}\) są rozłączne, a zatem \(\displaystyle{ R \cap S= \emptyset}\), a zatem \(\displaystyle{ D_2\left( \emptyset\right) = \emptyset}\), czyli \(\displaystyle{ D_2\left( R \cap S\right) = D_2\left( \emptyset\right) = \emptyset,}\) podczas gdy:

\(\displaystyle{ D_2\left( R\right) \cap D_2\left( S\right) = \left[ 0,1\right] \cap \left[ 0,1\right] = \left[ 0,1\right] \neq \left\{ \right\}= D_2 \left( R \cap S\right).}\)

I podobnie trzecia dziedzina przekroju dwóch relacji trójczłonowych w danym zbiorze może być innym zbiorem niż przekrój trzecich dziedzin tych relacji, co przedstawia ILUSTRACJA:\(\displaystyle{ \\}\)
Trzecia dzidzina przekroju dwóch relacji .jpg
Wystarczy zatem wziąć \(\displaystyle{ X=Y=Z=\RR,}\) i \(\displaystyle{ R= \left[ 0,1\right] \times \left[ 0,1\right] \times \left[ 0,1\right]}\) i \(\displaystyle{ S=\left[ 2,3\right] \times \left[ 0,1\right] \times \left[ 0,1\right].}\)

Wtedy \(\displaystyle{ D_3\left( R \cap S\right)= D_3\left( \emptyset \right) = \emptyset \neq \left[ 0,1\right] = D_3\left( R\right) \cap D_3\left( S\right).}\)

8-)
ODPOWIEDZ