Funkcje, operacje mnogościowe na nich

[Jakub Gurak]

Udowodniłem wczoraj parę faktów odnośnie funkcji. Przedstawię teraz rezultaty.

Zacznijmy od oczywistego spostrzeżenia, że jeśli \(\displaystyle{ X_1,X_2}\) są zbiorami rozłącznymi, a \(\displaystyle{ Y}\) jest zbiorem, \(\displaystyle{ f_1:X_1 \rightarrow Y, f_2:X_2 \rightarrow Y}\), to \(\displaystyle{ f_1\cup f_2}\) jest funkcją z \(\displaystyle{ X_1\cup X_2}\) w \(\displaystyle{ Y}\). Uogólnijmy na \(\displaystyle{ n}\) funkcji, jeśli \(\displaystyle{ X_1,X_2,\ldots, X_n}\) są zbiorami rozłącznymi, \(\displaystyle{ Y}\) jest zbiorem, a \(\displaystyle{ f_1:X_1 \rightarrow Y, f _{2}:X_2 \rightarrow Y;\ldots f_n:X_n \rightarrow Y}\) dowolnymi funkcjami, to \(\displaystyle{ f_1 \cup f_2 \cup \ldots \cup f_n}\) jest funkcją z \(\displaystyle{ X_1 \cup X_2 \cup \ldots \cup X_n}\) w \(\displaystyle{ Y}\).

Pewnie można przez indukcję, ja udowodniłem z definicji.

Dowód:

Zauważmy najpierw, że \(\displaystyle{ f_i:X_i \rightarrow Y}\), dla \(\displaystyle{ i=1,2,\ldots,n}\), a zatem \(\displaystyle{ f_i\subset X_i \times Y}\), zatem tym bardziej \(\displaystyle{ f_i\subset \left( X_1 \cup X_2 \cup \ldots \cup X_n\right) \times Y}\), i to dla każdego \(\displaystyle{ i=1,2,\ldots,n;}\) więc również suma \(\displaystyle{ f_1 \cup f_2 \cup\ldots \cup f_n}\) jest podzbiorem tego zbioru \(\displaystyle{ f_1 \cup f_2 \cup\ldots f_n\subset \left( X_1\cup X_2\cup \ldots X_n \right) \times Y}\), a zatem \(\displaystyle{ f_1\cup f_2\cup \ldots \cup f_n}\) jest relacją z \(\displaystyle{ X_1\cup X_2\cup \ldots\cup X_n}\) do \(\displaystyle{ Y.}\) Sprawdźmy, że jest funkcją. Mamy \(\displaystyle{ \left( \bigcup_{i=1}^{n} f_i\right)_L= \bigcup_{i=1}^{n} \left( f_i\right)_L}\), dalej, ponieważ dla każdego \(\displaystyle{ i=1,2,\ldots,n}\): \(\displaystyle{ f_i:X_i \rightarrow Y}\), wiec z definicji funkcji \(\displaystyle{ \left( f_i\right) _L=X_i}\), a zatem \(\displaystyle{ \left( \bigcup_{i=1}^{n} f_i\right)_L= \bigcup_{i=1}^{n} \left( f_i\right)_L= \bigcup_{i=1}^{n} X_i= X_1\cup X_2\cup \ldots \cup X_n}\), a więc \(\displaystyle{ (f_1\cup f_2\cup\ldots \cup f_n)_L=X_1\cup X_2\cup\ldots \cup X_n.}\)

Pozostaje pokazać punkt drugi w definicji funkcji: Niech \(\displaystyle{ (x,y_1);(x,y_2)\in f_1\cup f_2\cup\ldots \cup f_n}\). Wtedy \(\displaystyle{ (x,y_1)\in f_i}\) dla pewnego \(\displaystyle{ i \in \left\{ 1,2,\ldots,n\right\}}\) , oraz \(\displaystyle{ (x,y_2)\in f_j}\), gdzie \(\displaystyle{ j \in \left\{ 1,2,\ldots,n\right\}}\), wtedy \(\displaystyle{ x\in (f_i)_L=X_i}\), podobnie \(\displaystyle{ x\in (f_j)_L =X_j}\), zatem \(\displaystyle{ x\in X_i\cap X_j}\), ale zbiory \(\displaystyle{ X_1,X_2,\ldots, X_n}\) są rozłączne, zatem \(\displaystyle{ i=j}\), i w konsekwencji \(\displaystyle{ f_i=f_j}\). A zatem \(\displaystyle{ (x,y_1);(x,y_2)\in f_i}\), i ponieważ \(\displaystyle{ f_i}\) jest funkcją, to \(\displaystyle{ y_1=y_2.}\)

Zatem \(\displaystyle{ f_1 \cup f_2 \cup \ldots \cup f_n}\) jest funkcją z \(\displaystyle{ X_1 \cup X_2 \cup \ldots X_n}\) w \(\displaystyle{ Y. \square}\)

Rozważmy teraz cztery zbiory \(\displaystyle{ X_1,X_2, Y_1, Y_2}\), gdzie zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, oraz dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\), wtedy\(\displaystyle{ f_1 \cup f_2}\) jest funkcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2.}\)

Dowód:

Wynika to z poprzedniego faktu dla \(\displaystyle{ n=2}\), oraz faktu, że jeśli \(\displaystyle{ f:X \rightarrow Y}\) oraz mamy zbiór \(\displaystyle{ Z\supset Y}\), to \(\displaystyle{ f:X \rightarrow Z}\) jest funkcją- łatwo się o tym przekonać. Wobec czego ponieważ (zachowując oznaczenia z twierdzenia) \(\displaystyle{ Y_1\subset Y_1\cup Y_2}\), to \(\displaystyle{ f_1:X_1 \rightarrow Y_1\cup Y_2}\), i \(\displaystyle{ f_2:X_2 \rightarrow Y_1 \cup Y_2}\) są istotnie funkcjami, wiec obydwie przeciwdziedziny są takie same( i zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne), więc z poprzedniego faktu \(\displaystyle{ f_1\cup f_2}\) jest funkcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2.\square}\)

Uogólnijmy, rozważmy \(\displaystyle{ n}\) par zbiorów \(\displaystyle{ (X_1,Y_1); (X_2,Y_2); \ldots (X_n,Y_n)}\) wraz z funkcjami \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2,\ldots, f_n: X_n \rightarrow Y_n}\), tak aby dziedziny \(\displaystyle{ X_i}\) były parami rozłączne, i pokażmy, że \(\displaystyle{ f_1\cup f_2\cup \ldots \cup f_n}\) jest funkcją z \(\displaystyle{ X_1\cup X_2\cup \ldots\cup X_n}\) do \(\displaystyle{ Y_1\cup Y_2\cup \ldots\cup Y_n. }\) Niewątpliwie \(\displaystyle{ f_1:X_1 \rightarrow Y_1 \cup Y_2 \cup \ldots Y_n; f_2:X_2 \rightarrow Y_1 \cup Y_2 \cup \ldots Y_n; \ldots; f_n:X_n \rightarrow Y_1\cup Y_2\cup \ldots Y_n}\) ( możemy rozważać funkcję o większej przeciwdziedzinie), zatem teraz już przeciwdziedzina jest stała, (i dziedziny \(\displaystyle{ X_i }\) są rozłączne), więc \(\displaystyle{ f_1\cup f_2\cup\ldots\cup f_n}\) jest funkcją z \(\displaystyle{ X_1 \cup X_2\cup \ldots X_n}\) do \(\displaystyle{ Y_1\cup Y_2\cup \ldots \cup Y_n.}\)

Łatwo to można również przez indukcję udowodnić.

Rozważmy teraz cztery zbiory \(\displaystyle{ X_1,X_2, Y_1,Y_2}\), oraz dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow Y_1; f_2:X_2 \rightarrow Y_2.}\) Wykażemy, że \(\displaystyle{ f_1\cup f_2}\) jest funkcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2}\), wtedy i tylko wtedy ,gdy dla każdego \(\displaystyle{ x\in X_1\cap X_2}\): mamy\(\displaystyle{ f_1(x)=f_2(x)}\)( czyli gdy w przekroju dziedzin tych dwóch funkcji funkcje te się pokrywają).

Dowód:

Łatwo sprawdzić, że istotnie \(\displaystyle{ f_1\cup f_2}\) jest relacją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2.}\)

Na początek sprawdźmy równoważność, gdy \(\displaystyle{ X_1\cap X_2=\emptyset.}\) Wtedy dla każdego \(\displaystyle{ x\in X_1\cap X_2=\emptyset: f_1(x)=f_2(x)}\) (prawda formalna), oraz zbiory\(\displaystyle{ X_1,X_2}\) są rozłączne, więc \(\displaystyle{ f_1\cup f_2}\) jest funkcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2}\). Równoważność więc zachodzi. Dalej więc przypuśćmy, że \(\displaystyle{ X_1\cap X_2}\) jest zbiorem niepustym.

Przypuśćmy, że dla pewnego \(\displaystyle{ x\in X_1\cap X_2}\) mamy \(\displaystyle{ f_1(x) \neq f_2(x)}\). Oznaczmy \(\displaystyle{ y_1:=f_1(x); y_2:=f_2(x)}\). Wtedy \(\displaystyle{ (x,y_1)\in f_1}\), więc \(\displaystyle{ (x,y_1)\in f_1\cup f_2.}\) oraz \(\displaystyle{ (x,y_2)\in f_2}\), zatem \(\displaystyle{ (x,y_2)\in f_1\cup f_2}\), ponieważ \(\displaystyle{ (x,y_1)\in f_1\cup f_2, (x,y_2)\in f_1\cup f_2}\), i ponieważ \(\displaystyle{ y_1 \neq y_2}\), to \(\displaystyle{ f_1\cup f_2}\) nie jest funkcją.

Przypuśćmy teraz, że dla każdego \(\displaystyle{ x\in X_1\cap X_2}\), mamy \(\displaystyle{ f_1(x)=f_2(x).}\)
Wtedy \(\displaystyle{ \left( f_1\cup f_2\right)_L= (f_1)_L\cup (f_2)_L=X_1\cup X_2.}\)
Niech \(\displaystyle{ (x,y_1);(x,y_2)\in f_1\cup f_2.}\) Jeśli \(\displaystyle{ (x,y_1)\in f_1; (x,y_2)\in f_1}\), to ponieważ \(\displaystyle{ f_1}\) jest to funkcja, to \(\displaystyle{ y_1=y_2.}\) Podobnie gdy \(\displaystyle{ (x,y_1)\in f_2\hbox{ i } (x,y_2)\in f_2}\). Rozważmy teraz przypadek \(\displaystyle{ (x,y_1)\in f_1, (x,y_2)\in f_2}\). Wtedy \(\displaystyle{ x\in (f_1)_L=X_1, x\in (f_2)_L=X_2}\), zatem \(\displaystyle{ x\in X_1\cap X_2}\). A zatem na mocy założenia \(\displaystyle{ y_1=f_1(x)=f_2(x)=y_2}\). Pozostał ostatni przypadek gdy \(\displaystyle{ (x,y_1)\in f_2; (x,y_2)\in f_1}\), wtedy \(\displaystyle{ x\in X_2\cap X_1}\), na mocy założenia otrzymujemy \(\displaystyle{ y_2=f_1(x)=f_2(x)=y_1}\), czyli \(\displaystyle{ y_1=y_2. }\)
Zatem \(\displaystyle{ f_1\cup f_2}\) jest funkcją.\(\displaystyle{ \square}\)

Wynika stąd, że jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ f,g:X \rightarrow Y}\) funkcjami, to \(\displaystyle{ f \cup g}\) jest funkcją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dokładnie wtedy, gdy \(\displaystyle{ f=g}\), gdy te funkcje są równe. W szczególności gdy są różne, to ich suma nie może być funkcją- niestety.

Na koniec wykażemy, że jeśli mamy cztery zbiory \(\displaystyle{ X_1,X_2; Y_1,Y_2}\) oraz dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\), oraz dla każdego \(\displaystyle{ x\in X_1\cap X_2}\),mamy \(\displaystyle{ f_1(x)=f_2(x)}\)(czyli gdy w przekroju dziedzin funkcji funkcje te się pokrywają), to \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2.}\)

UWAGA: Bez tego założenia związanego z przekrojem dziedzin może to się nie udać- co prawda będzie to funkcja, ale niekoniecznie na całym zbiorze \(\displaystyle{ X_1\cap X_2}\), na mniejszym zbiorze , w skrajnym przypadku może nawet będzie funkcją pustą . My jednak załóżmy też to dodatkowe założenie.

Dowód:

Zauważmy najpierw, ze z praw relacji wynika, że \(\displaystyle{ (f_1\cap f_2)_L\subset (f_1)_L\cap (f_2)_L=X_1\cap X_2.}\)
Podobnie \(\displaystyle{ (f_1\cap f_2)_P\subset \left( f_1\right)_P \cap \left( f_2\right)_P \subset Y_1\cap Y_2}\). Z ogólnych praw relacji otrzymujemy: \(\displaystyle{ f_1\cap f_2\subset (f_1\cap f_2)_L \times \left( f_1\cap f_2\right)_P\subset (X_1\cap X_2)\times (Y_1\cap Y_2)}\). A zatem \(\displaystyle{ f_1\cap f_2}\) jest relacją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2.}\)

Zauważmy najpierw, że jeżeli mamy dwa zbiory, funkcję cżęściową z pierwszego zbioru w drugi, to każdy jej podzbiór jest funkcją częściową, łatwo się o tym przekonać. Wobec czego ponieważ \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\) jest w szczególności funkcją częściową, to \(\displaystyle{ f_1 \cap f_2\subset f_1}\) jest funkcją cżęściową. Pozostaje pokazać, ze jest określona na całym zbiorze \(\displaystyle{ X_1\cap X_2}\). Niech \(\displaystyle{ x\in X_1\cap X_2.}\) Na mocy naszego założenia \(\displaystyle{ f_1(x)=f_2(x)}\) oznaczmy tą wartość jako \(\displaystyle{ y}\), wtedy \(\displaystyle{ (x,y)\in f_1, (x,y)\in f_2}\), zatem \(\displaystyle{ (x,y)\in f_1\cap f_2}\), a stąd \(\displaystyle{ x\in (f_1\cap f_2)_L}\). A zatem \(\displaystyle{ (f_1\cap f_2)_L=X_1\cap X_2}\). A zatem \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2. \square}\)

[Jakub Gurak]

Dzisiaj, na początek udowodniłem twierdzenie odwrotne do ostatniego faktu. Udowodniłem też dzisiaj, że jeśli mamy cztery zbiory \(\displaystyle{ X_1,X_2, Y_1,Y_2 }\) oraz dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow Y_1; f_2:X_2 \rightarrow Y_2,}\) oraz dla każdego \(\displaystyle{ x\in X_1\cap X_2}\), mamy \(\displaystyle{ f_1(x)=f_2(x)}\) (czyli gdy w przekroju dziedzin tych funkcji funkcje te się pokrywają), to \(\displaystyle{ f_1 \setminus f_2}\) jest funkcją z \(\displaystyle{ X_1 \setminus X_2}\) w \(\displaystyle{ Y_1}\), i różnica symetryczna \(\displaystyle{ f_1\oplus f_2}\) jest funkcją z \(\displaystyle{ X_1\oplus X_2}\) w \(\displaystyle{ Y_1\cup Y_2}\). Przedstawię teraz dowody tych ciekawych faktów, a na koniec podkreślę ten ciekawy niezwykły wynik do którego doszliśmy.


Niech \(\displaystyle{ X_1,X_2,Y_1,Y_2}\) będą zbiorami, a \(\displaystyle{ f_1:X_1 \rightarrow Y_1; f_2:X_2 \rightarrow Y_2}\) dowolnymi funkcjami. Wykazujemy, że \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2,}\) (nie zawsze), lecz wtedy i tylko wtedy, gdy dla każdego \(\displaystyle{ x\in X_1\cap X_2}\),mamy \(\displaystyle{ f_1(x)=f_2(x)}\)(czyli gdy w przekroju dziedzin tych funkcji, funkcje te się pokrywają). Czyli wtedy \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2.}\)

Zauważmy najpierw, że gdy \(\displaystyle{ X_1\cap X_2=\emptyset}\), to równoważność zachodzi-( zdanie po lewej stronie jest prawdziwe, otrzymujemy funkcję pustą, po prawej stronie otrzymujemy (formalnie) zdanie prawdziwe, zdanie ogólne ograniczone zasięgiem do zbioru pustego, formalnie prawdziwe). Równoważność więc zachodzi. Niech dalej będzie \(\displaystyle{ X_1\cap X_2 \neq \left\{ \right\} .}\)

W ostatnim poście sprawdziliśmy poprawność określenia, a następnie wynikanie z prawej strony do lewej. Wykażemy teraz drugą implikację.

Załóżmy, że \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2,}\) i przypuśćmy, dla dowodu nie wprost, że dla pewnego \(\displaystyle{ x\in X_1\cap X_2}\) mamy \(\displaystyle{ y_1=:f_1(x) \neq f_2(x):=y_2.}\) Wtedy \(\displaystyle{ (x,y_1)\in f_1,\hbox{ i } (x,y_2)\in f_2. }\) Ponieważ \(\displaystyle{ f_1\cap f_2}\) jest funkcją na \(\displaystyle{ X_1\cap X_2}\), to niech \(\displaystyle{ y_0=\left( f_1\cap f_2\right) (x).}\) Wtedy \(\displaystyle{ (x,y_0)\in f_1\cap f_2}\), więc\(\displaystyle{ (x,y_0)\in f_1,(x,y_0)\in f_2}\). Mamy \(\displaystyle{ (x,y_0)\in f_1}\) i \(\displaystyle{ (x,y_1)\in f_1. }\) Ponieważ \(\displaystyle{ f_1}\) jest funkcją, to \(\displaystyle{ y_0=y_1}\). Mamy \(\displaystyle{ (x,y_0)\in f_2, (x,y_2)\in f_2}\), ponieważ \(\displaystyle{ f_2}\) jest funkcją, to \(\displaystyle{ y_0=y_2.}\) Mamy \(\displaystyle{ y_0=y_1}\), więc \(\displaystyle{ y_1=y_2}\)-sprzeczność z założeniem.\(\displaystyle{ \square}\)

Przejdźmy do dalszych dowodów:

Zachowując oznaczenia, sprawdźmy najpierw poprawność określenia, że \(\displaystyle{ f_1 \setminus f_2}\) jest relacją z \(\displaystyle{ X_1 \setminus X_2}\) w \(\displaystyle{ Y_1.}\)
Niewątpliwie \(\displaystyle{ f_1 \setminus f_2\subset f_1\subset X_1\times Y_1}\) (bo \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\)). Chcemy pokazać, że \(\displaystyle{ f_1 \setminus f_2\subset (X_1 \setminus X_2) \times Y_1=(X_1\times Y_1) \setminus (X_2\times Y_1)\subset X_1\times Y_1.}\) Przypuśćmy nie wprost, że \(\displaystyle{ f_1 \setminus f_2\not\subset \left( X_1 \times Y_1\right) \setminus (X_2\times Y_1).}\) Wtedy \(\displaystyle{ f_1 \setminus f_2 \neq \left\{ \right\}}\) (gdyż zbiór pusty jest podzbiorem każdego zbioru), zatem zaprzeczając definicji zawierania otrzymujemy, że istnieje \(\displaystyle{ (x,y)\in f_1 \setminus f_2}\), taki, że \(\displaystyle{ (x,y)\not\in\left( X_1 \times Y_1\right) \setminus (X_2\times Y_1).}\) Ponieważ \(\displaystyle{ f_1 \setminus f_2\subset X_1 \times Y_1}\), to \(\displaystyle{ (x,y)\in X_1 \times Y_1}\), ale \(\displaystyle{ (x,y)\not\in\left( X_1 \times Y_1\right) \setminus (X_2\times Y_1)}\), więc musi być \(\displaystyle{ (x,y)\in X_2\times Y_1}\), a stąd \(\displaystyle{ x\in X_2, y\in Y_1}\). Mamy \(\displaystyle{ (x,y)\in X_1\times Y_1}\), więc\(\displaystyle{ x\in X_1}\), a zatem \(\displaystyle{ x\in X_1\cap X_2}\), na mocy założenia \(\displaystyle{ f_1(x)=f_2(x)=:y}\), oznaczmy tą wartość jako \(\displaystyle{ y}\). Inaczej mówiąc \(\displaystyle{ (x,y)\in f_1}\), i \(\displaystyle{ (x,y)\in f_2}\), a \(\displaystyle{ (x,y)\in f_1 \setminus f_2}\)- sprzeczność. Wobec czego musi być \(\displaystyle{ f_1 \setminus f_2\subset \left( X_1 \times Y_1\right) \setminus (X_2\times Y_1)=(X_1\setminus X_2)\times Y_1}\), i \(\displaystyle{ f_1 \setminus f_2}\) jest relacją z \(\displaystyle{ X_1 \setminus X_2}\) do \(\displaystyle{ Y_1}\).( Możliwe, że przekombinowałem, ale robiłem wpierw dowód bez tego założenia o tym, że w przekroju funkcje się pokrywają, co okazało się niemożliwe).

Łatwo teraz będzie pokazać, że różnica \(\displaystyle{ f_1 \setminus f_2}\) jest funkcją z \(\displaystyle{ X_1 \setminus X_2}\) w \(\displaystyle{ Y_1}\). Niewątpliwie\(\displaystyle{ f_1 \setminus f_2\subset f_1}\), gdzie \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\) jest w szczególności funkcją częściową, więc \(\displaystyle{ f_1 \setminus f_2}\) jako jej podzbiór jest funkcją częściową( każdy podzbiór funkcji częściowej jest funkcją częściową, to prosty fakt). Na mocy prawa relacji \(\displaystyle{ (f_1 \setminus f_2)_L\supset (f_1)_L \setminus (f_2)_L=X_1 \setminus X_2}\). W takim razie \(\displaystyle{ (f_1 \setminus f_2) _{L}=X_1 \setminus X_2}\). Ponieważ \(\displaystyle{ (f_1 \setminus f_2)\subset f_1}\), to \(\displaystyle{ \left( f_1 \setminus f_2\right)_P\subset (f_1)_P\subset Y_1.}\) W takim razie \(\displaystyle{ f_1 \setminus f_2}\) jest funkcją z \(\displaystyle{ (f_1 \setminus f_2)_L=X_1 \setminus X_2}\) w \(\displaystyle{ (f_1 \setminus f_2)_P,}\) a więc tym bardziej jest funkcją z \(\displaystyle{ X_1 \setminus X_2}\) w \(\displaystyle{ Y_1.\square}\)

Aha ten fakt jest mi znany, ale nie wiem czy wam, a nie wiem czy jest całkiem oczywisty:

DOŚĆ PROSTY DOWÓD:    

Jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ R,S\subset X \times Y}\) dowolnymi relacjami , to \(\displaystyle{ R_L \setminus S_L\subset \left( R \setminus S\right)_L. }\)

Dowód:

Niech \(\displaystyle{ x\in R_L \setminus S_L.}\) Wtedy \(\displaystyle{ x\in R_L, x\not\in S_L}\). Mamy \(\displaystyle{ x\in R_L}\), zatem \(\displaystyle{ (x,y)\in R}\), dla pewnego \(\displaystyle{ y\in Y.}\) Wtedy \(\displaystyle{ (x,y)\not\in S}\). Gdyby bowiem \(\displaystyle{ (x,y)\in S}\), to \(\displaystyle{ x\in S_L}\)- sprzeczność. A zatem \(\displaystyle{ (x,y)\in R \setminus S}\), a stąd \(\displaystyle{ x\in (R \setminus S)_L}\), wiec \(\displaystyle{ R_L \setminus S_L\subset (R \setminus S)_L.\square}\)
To chyba nie było takie trudne, nieco trudniej jest pokazać, że dla dowolnych trzech relacji pomiędzy odpowiednimi zbiorami, \(\displaystyle{ (R \setminus S)\circ T\supset (R\circ T) \setminus (S\circ T)}\), to chyba z tym dowodem mi się to pomyliło.

Łatwo będzie teraz pokazać (zachowując oznaczenia), że (jeśli w przekroju dziedzin funkcji funkcje się pokrywają), to różnica symetryczna \(\displaystyle{ f_1\oplus f_2}\) jest funkcją z \(\displaystyle{ X_1\oplus X_2}\) w \(\displaystyle{ Y_1\cup Y_2.}\)

Na mocy poprzedniego faktu z różnicą, \(\displaystyle{ f_1 \setminus f_2}\) jest funkcją z \(\displaystyle{ X_1 \setminus X_2 }\) w \(\displaystyle{ Y_1}\). Stosując ponownie ten fakt tym razem do pary funkcji \(\displaystyle{ (f_2,f_1)}\) (możemy, gdyż dla każdego \(\displaystyle{ x\in X_2 \cap X_1=X_1\cap X_2}\), mamy \(\displaystyle{ f_2(x)=f_1(x)}\) ), więc otrzymujemy, że \(\displaystyle{ f_2 \setminus f_1}\) jest funkcją z \(\displaystyle{ X_2 \setminus X_1}\) w \(\displaystyle{ Y_2.}\) Ponieważ zbiory \(\displaystyle{ X_1 \setminus X_2}\) oraz \(\displaystyle{ X_2 \setminus X_1}\) są rozłączne to suma tych funkcji \(\displaystyle{ \left( f_1 \setminus f_2 \right) \cup \left( f_2 \setminus f_1\right)=f_1\oplus f_2}\) jest funkcją z \(\displaystyle{ (X_1 \setminus X_2) \cup \left( X_2 \setminus X_1\right)= X_1\oplus X_2}\) w \(\displaystyle{ Y_1\cup Y_2.\square}\)

No to może podsumujmy:

Jeśli \(\displaystyle{ X_1,X_2,Y_1,Y_2}\) są zbiorami, a \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\) funkcjami, oraz dla każdego \(\displaystyle{ x\in X_1\cap X_2}\), mamy \(\displaystyle{ f_1(x)=f_2(x)}\) (czyli gdy w przekroju dziedzin tych funkcji funkcje się pokrywają), to:

1)\(\displaystyle{ f_1 \cup f_2}\) jest funkcją z \(\displaystyle{ X_1 \cup X_2}\) do \(\displaystyle{ Y_1 \cup Y_2}\),
2)\(\displaystyle{ f_1 \cap f_2}\) jest funkcją z \(\displaystyle{ X _{1} \cap X_2}\) do \(\displaystyle{ Y_1 \cap Y_2,}\)
3)\(\displaystyle{ f_1 \setminus f_2}\) jest funkcją z \(\displaystyle{ X_1 \setminus X_2}\) w \(\displaystyle{ Y_1,}\)
4)\(\displaystyle{ f_1\oplus f_2}\) jest funkcją z \(\displaystyle{ X_1\oplus X_2}\) w \(\displaystyle{ Y_1\cup Y_2.}\)

Myślę, że to jest bardzo ciekawy wynik.

[Jan Kraszewski]

Myślę, że to jest bardzo ciekawy wynik.

No cóż... Ale wiesz, że to są bardzo elementarne i dość oczywiste wyniki?

JK

[Jakub Gurak]

Tak podejrzewałem, ale dla mnie jest to bardzo ciekawe. Nie widzę problemu, zawsze przecież mówię, że robię proste rozumowania.

Wczoraj udowodniłem, że suma dwóch funkcji różnowartościowych określonych na zbiorach rozłącznych i mających rozłączne przeciwdziedziny, wtedy ich suma jest funkcją różnowartościową ze sumy dziedzin tych funkcji w sumę przeciwdziedzin. Uogólniłem przez indukcję na dowolną skończoną ilość. Udowodniłem też, że suma dwóch funkcji 'na' jest funkcją 'na'. Przedstawię teraz dowody tych ciekawych faktów.

Przypomnę może, że jeśli \(\displaystyle{ X_1,X_2}\) są zbiorami rozłącznymi, \(\displaystyle{ Y_1,Y_2}\) są zbiorami rozłącznymi, a \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\) bijekcjami ( róznowartościowe i 'na'), to suma \(\displaystyle{ f_1\cup f_2}\) jest funkcją bijekcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2}\), co udowodniłem TUTAJ ( tłustym drukiem , przed postem Dasia11 ). Będziemy z tego korzystać. Niech \(\displaystyle{ X_1,X_2,Y_1,Y_2}\) będą zbiorami, a \(\displaystyle{ f_1:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\) funkcjami różnowartościowymi, tak aby zbiory \(\displaystyle{ X_1,X_2}\) były rozłączne, i zbiory \(\displaystyle{ Y_1,Y_2}\) były rozłączne. Wykażemy, że \(\displaystyle{ f_1\cup f_2:X_1\cup X_2 \rightarrow Y_1 \cup Y_2}\) jest funkcją różnowartościową.

DOWÓD:

Zauważmy, że \(\displaystyle{ f_1:X_1 \stackrel {NA} {\rightarrow } (f_1)_P=:Z_1, f_2:X_2 \stackrel {NA}{\rightarrow} (f_2)_P=:Z_2}\) są funkcjami 'na' zbiór wartości. I są różnowartościowe, zatem są bijekcjami ze zbiorów odpowiednio \(\displaystyle{ X_1}\) do \(\displaystyle{ Z_1}\), i druga bijekcja jest z \(\displaystyle{ X_2 }\) do \(\displaystyle{ Z_2.}\) Zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, I zbiory \(\displaystyle{ Z_1,Z_2}\) również. Aby to uzasadnić, ponieważ \(\displaystyle{ Z_1\subset Y_1}\) (jest to zbiór wartości funkcji \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\)), podobnie \(\displaystyle{ Z_2\subset Y_2}\), a zatem \(\displaystyle{ Z_1\cap Z_2\subset Y_1\cap Y_2=\emptyset}\), gdyż zbiory \(\displaystyle{ Y_1,Y_2}\) są rozłączne,. W takim razie \(\displaystyle{ Z_1\cap Z_2=\emptyset}\), i zbiory \(\displaystyle{ Z_1,Z_2}\) są rozłączne. A zatem \(\displaystyle{ f_1:X_1 \rightarrow Z_1, f_2:X_2 \rightarrow Z_2}\) są bijekcjami, zbiory \(\displaystyle{ X_1,X_2 }\) są rozłączne, zbiory \(\displaystyle{ Z_1,Z_2}\) są rozłączne. A zatem na mocy przytoczonego faktu o sumie bijekcji funkcja \(\displaystyle{ f_1\cup f_2}\) jest bijekcją z \(\displaystyle{ X_1\cup X_2 }\) do \(\displaystyle{ Z_1\cup Z_2}\). Ponieważ \(\displaystyle{ Z_1\cup Z_2\subset Y_1\cup Y_2}\), to funkcja \(\displaystyle{ f_1\cup f_2:X_1\cup X_2 \rightarrow Y_1\cup Y_2}\) jest injekcją (jest różnowartościowa). \(\displaystyle{ \square }\)

Uogólnijmy na \(\displaystyle{ n}\) funkcji, rozważmy \(\displaystyle{ n}\) par zbiorów \(\displaystyle{ (X_1,Y_1); (X_2,Y_2); \ldots; (X_n, Y_n) }\) wraz z funkcjami różnowartościowymi \(\displaystyle{ f_1:X_1 \rightarrow Y_1; f_2:X_2 \rightarrow Y_2,\ldots, f_n: X_n \rightarrow Y_n}\), tak aby dziedziny \(\displaystyle{ X_i}\) były rozłączne, i przeciwdziedziny \(\displaystyle{ Y_i}\) były rozłączne. Wtedy \(\displaystyle{ f_1\cup f_2\cup \ldots \cup f_n: X_1\cup X_2\cup\ldots \cup X_n \rightarrow Y_1\cup Y_2\cup \ldots\cup Y_n}\) jest funkcją różnowartościową.

Dowód(indukcyjny):

Dla \(\displaystyle{ n=1}\) to oczywiście zachodzi, (gdyż \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\) jest z założenia funkcją różnowartościową).
Dla \(\displaystyle{ n=2}\) to zachodzi, na mocy poprzednio udowodnionego faktu.
Krok indukcyjny: Weźmy \(\displaystyle{ n \ge 2}\), i przypuśćmy, że twierdzenie zachodzi dla \(\displaystyle{ n}\). Pokażemy, że zachodzi dla \(\displaystyle{ (n+1).}\) W tym celu weźmy \(\displaystyle{ (n+1)}\) par zbiorów \(\displaystyle{ (X_1,Y_1); (X_2,Y_2);\ldots; (X_n,Y_n);(X_{n+1},Y_{n+1})}\) wraz z funkcjami różnowartościowymi \(\displaystyle{ f_1:X_1 \rightarrow Y_1; f_2:X_2 \rightarrow Y_2;\ldots ,f_n:X_n \rightarrow Y_n; f_{n+1}:X_{n+1} \rightarrow Y_{n+1}}\), tak aby zbiory \(\displaystyle{ X_i }\) były rozłączne, i zbiory \(\displaystyle{ Y_i}\) były rozłączne. Pokażemy, że \(\displaystyle{ f_1\cup f_2 \cup \ldots f_{n+1} }\) jest funkcją różnowartościową z \(\displaystyle{ X_1\cup X_2\cup \ldots\cup X_{n+1}}\) do \(\displaystyle{ Y_1\cup Y_2\cup\ldots Y_{n+1}}\). Zbiory \(\displaystyle{ X_1,X_2,\ldots, X_n}\) są rozłączne, podobnie zbiory \(\displaystyle{ Y_1,Y_2,\ldots, Y_n}\) są rozłączne. Możemy zatem do funkcji \(\displaystyle{ f_1,f_2,\ldots,f_n}\) zastosować założenie indukcyjne, i otrzymać, że \(\displaystyle{ f_1\cup f_2\cup \ldots f_n}\) jest funkcją różnowartościową z \(\displaystyle{ X_1\cup X_2\cup\ldots X_n}\) do \(\displaystyle{ Y_1\cup Y_2\cup\ldots Y_n}\). Oczywiście \(\displaystyle{ f_1\cup f_2\cup\ldots f_n\cup f_{n+1}=\left( f_1\cup f_2\cup\ldots f_n\right) \cup f_{n+1}}\), mamy też \(\displaystyle{ f_{n+1}:X_{n+1} \rightarrow Y_{n+1}}\) jest funkcją różnowartościową. Należy teraz pokazać, że zbiory \(\displaystyle{ \left( X_1\cup X_2\cup \ldots X_n\right)}\) oraz \(\displaystyle{ X_{n+1} }\) są rozłączne. Łatwo to pokazać ponieważ zbiory \(\displaystyle{ X_i}\) są parami rozłączne. Niewątpliwie mamy:

\(\displaystyle{ \left( X_1\cup X_2\cup \ldots X_n\right) \cap X _{n+1} =\left( X_1\cap X_{n+1}\right) \cup \left( X_2\cap X_{n+1}\right) \cup\ldots \left( X_n \cap X_{n+1}\right) = \underbrace {\emptyset\cup\emptyset\cup\ldots\emptyset}_{n}=\emptyset}\). A zatem zbiory \(\displaystyle{ X_1\cup X_2\cup\dots X_n}\) oraz \(\displaystyle{ X_{n+1}}\) są rozłączne. W podobny sposób uzasadniamy, że zbiory \(\displaystyle{ Y_1\cup Y_2\cup\ldots Y_n}\) oraz \(\displaystyle{ Y_{n+1}}\) są rozłączne. Ponieważ \(\displaystyle{ f_1\cup f_2\cup \ldots f_n:X_1\cup X_2\cup\ldots X_n \rightarrow Y_1\cup Y_2\cup\ldots Y_n}\) jest funkcją różnowartościową, oraz \(\displaystyle{ f_{n+1}:X_{n+1} \rightarrow Y_{n+1} }\) jest również funkcją różnowartościową, dziedziny tych funkcji są rozłączne, jak i przeciwdziedziny również, więc ich suma \(\displaystyle{ \left( f_1\cup f_2\cup \ldots f_n\right) \cup f_{n+1}:\left( X_1\cup X_2\cup \ldots X_n \right) \cup X_{n+1} \rightarrow \left( Y_1\cup Y_2\cup\ldots Y_n\right)\cup Y_{n+1}}\) jest funkcją różnowartościową. Krok indukcyjny został dowiedziony. Na mocy zasady indukcji matematycznej twierdzenie jest udowodnione.\(\displaystyle{ \square}\)

W podobny sposób (indukcyjny) można udowodnić, że jeżeli mamy \(\displaystyle{ n}\) bijekcji \(\displaystyle{ f _{1}:X_1 \rightarrow Y_1;f_2:X_2 \rightarrow Y _{2};\ldots; f:X _{n} \rightarrow Y _{n},}\) gdzie zbiory \(\displaystyle{ X_i}\) są rozłączne, i zbiory \(\displaystyle{ Y _{i} }\) są rozłączne, to suma \(\displaystyle{ f _{1}\cup f _{2} \cup\ldots f _{n}}\) jest bijekcją z \(\displaystyle{ X _{1} \cup X _{2} \cup \ldots X _{n} }\) do \(\displaystyle{ Y _{1} \cup Y _{2}\cup\ldots Y _{n}. }\)

W podanym linku prawie tuż przed tym dowodem jest przykład zastosowania tego ciekawego faktu, gdzie mamy sumę czterech bijekcji.

Udowodnimy jeszcze, że suma dwóch funkcji 'na' jest funkcją 'na'.

Niech \(\displaystyle{ X_1,X_2, Y_1,Y_2}\) będą zbiorami, a \(\displaystyle{ f_{1}:X_1 \rightarrow Y_1, f_2:X_2 \rightarrow Y_2}\) funkcjami 'na', tak aby w dowolnym punkcie \(\displaystyle{ x\in X_1 \cap X_2}\) byłoby \(\displaystyle{ f_1(x)=f_2(x)}\) (jak wykazałem niedawno ten warunek jest niezbędny ( i wystarczający) aby suma tych funkcji była funkcją ze sumy dziedzin tych funkcji w sumę przeciwdziedzin). Wykażemy, że \(\displaystyle{ f_1\cup f_2: X_1\cup X_2 \rightarrow Y_1\cup Y_2}\) jest funkcją 'na'.

Na mocy naszego założenia \(\displaystyle{ f_1\cup f_2}\) jest istotnie funkcją z \(\displaystyle{ X_1\cup X_2}\) do \(\displaystyle{ Y_1\cup Y_2}\), na mocy faktu z tego tematu powyżej .
Aby wykazać, że jest 'na' to niech \(\displaystyle{ y\in Y_1\cup Y_2}\). Jeśli \(\displaystyle{ y\in Y_1}\), ponieważ \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\) jest funkcją 'na', to \(\displaystyle{ y=f_1(x)}\), dla pewnego \(\displaystyle{ x\in X_1}\), inaczej mówiąc \(\displaystyle{ (x,y)\in f_1}\), a więc \(\displaystyle{ (x,y)\in f_1\cup f_2}\), mamy \(\displaystyle{ x\in X_1\cup X_2}\), więc \(\displaystyle{ y=\left( f_1\cup f_2\right)(x)}\), a więc \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ (f_1\cup f_2) .}\) Jeśli \(\displaystyle{ y\in Y_2}\), to rozumujemy analogicznie na podstawie tego, że \(\displaystyle{ f_2:X_2 \rightarrow Y_2}\) jest funkcją 'na. A więc (w obydwu przypakach) y jest wartością funkcji \(\displaystyle{ \left( f _{1} \cup f _{2} \right) }\). Z dowolności wyboru \(\displaystyle{ y \in Y _{1} \cup Y _{2} }\) wnioskujemy, że funkcja \(\displaystyle{ (f _{1}\cup f _{2}) }\) jest 'na'. \(\displaystyle{ \square }\)

[Jan Kraszewski]

Wczoraj udowodniłem, że suma dwóch funkcji różnowartościowych określonych na zbiorach rozłącznych i mających rozłączne przeciwdziedziny, wtedy ich suma jest funkcją różnowartościową ze sumy dziedzin tych funkcji w sumę przeciwdziedzin. Uogólniłem przez indukcję na dowolną skończoną ilość.

To teraz uogólnij na dowolną rodzinę funkcji różnowartościowych o parami rozłącznych dziedzinach i przeciwdziedzinach...

JK

[Jakub Gurak]

Nie wiem czy to jest jasno postawiony problem, czy to jest jasno określone.

Udowodniłem dzisiaj, że jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ \mathbb{S}}\) jest rodziną funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)- funkcji różnowartościowych, i gdy \(\displaystyle{ \mathbb{S}}\) jest łańcuchem względem relacji rozszerzania (przedłużania) funkcji, to \(\displaystyle{ \bigcup\mathbb{S}}\) jest funkcją różnowartościową. Zauważyłem też, że jeżeli mamy cztery zbiory \(\displaystyle{ X_1,X_2,Y_1,Y_2}\) oraz dwie funkcje różnowartościowe \(\displaystyle{ f_1:X_1 \stackrel {1-1}{\rightarrow} Y_1, f_2:X_2\stackrel {1-1} { \rightarrow} Y_2}\), oraz gdy w przekroju dziedzin tych funkcji funkcje się pokrywają, to przekrój \(\displaystyle{ f_1\cap f_2:X_1\cap X_2 \rightarrow Y_1\cap Y_2}\) jest funkcją różnowartościową, oraz różnica \(\displaystyle{ f_1 \setminus f_2:X_1 \setminus X_2 \rightarrow Y_1}\) jest funkcją różnowartościową. Przedstawię teraz dowody tych faktów.

Podam najpierw lemat:

Lemat o sumie funkcji częściowych:    

Jeśli \(\displaystyle{ \mathbb{S}}\) jest rodziną funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), taką, że dla dowolnych dwóch funkcji w \(\displaystyle{ \mathbb{S}}\) jedna z nich jest rozszerzeniem drugiej. to \(\displaystyle{ \bigcup\mathbb{S}}\) jest funkcją częściową z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\).

Dowód:

Niewątpliwie \(\displaystyle{ \bigcup \mathbb{S}\subset X\times Y}\) (suma podzbiorów \(\displaystyle{ X\times Y}\)). Aby wykazać, że jest to funkcja częściowa, to niech \(\displaystyle{ (x,y_1);(x,y_2)\in \bigcup \mathbb{S}}\), i pokażmy, że \(\displaystyle{ y_1=y_2}\). Ponieważ \(\displaystyle{ (x,y_1)\in\bigcup S}\), więc \(\displaystyle{ (x,y_1)\in f_1}\), dla pewnej funkcji \(\displaystyle{ f_1\in \mathbb{S}}\), podobnie drugie założenie obok daje, że \(\displaystyle{ (x,y_2)\in f_2}\), dla pewnej funkcji \(\displaystyle{ f_2\in \mathbb{S}.}\) Możemy to zapisać innymi słowy \(\displaystyle{ y_1=f_1(x)}\) i \(\displaystyle{ y_2=f_2(x)}\). Ponieważ \(\displaystyle{ f_1,f_2\in \mathbb{S}}\), więc na mocy założenia \(\displaystyle{ f_2}\) rozszerza \(\displaystyle{ f_1}\) lub \(\displaystyle{ f_1}\) rozszerza \(\displaystyle{ f_2.}\) Jeśli \(\displaystyle{ f_2}\) rozszerza \(\displaystyle{ f_1}\), to \(\displaystyle{ y_2=f_2(x)=f_1(x)=y_1}\), czyli \(\displaystyle{ y_1=y_2}\). Podobnie w drugim przypadku.\(\displaystyle{ \square}\)

Niech \(\displaystyle{ X,Y}\) będą zbiorami, a \(\displaystyle{ \mathbb{S}}\) dowolną rodziną funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) różnowartościowych, tak, że rodzina \(\displaystyle{ \mathbb{S}}\) jest łańcuchem względem relacji rozszerzania (przedłużania) funkcji( formalnie jest to relacja inkluzji na rodzinie wszystkich funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) różnowartościowych). Pokażemy, że relacja \(\displaystyle{ \bigcup\mathbb{S}}\) jest funkcją różnowartościową.

Ponieważ \(\displaystyle{ \mathbb{S}}\) jest łańcuchem względem relacji rozszerzania funkcji, tzn. dla dowolnych dwóch funkcji w \(\displaystyle{ \mathbb{S}}\) jedna z nich jest rozszerzeniem drugiej, więc \(\displaystyle{ \bigcup\mathbb{S}}\) jest funkcją, na mocy lematu. Aby wykazać, że ta funkcja jest różnowartościowa, to niech \(\displaystyle{ x_1,x_2\in \left( \bigcup\mathbb{S}\right) _L}\) będą takie, że \(\displaystyle{ \left( \bigcup\mathbb{S}\right) (x_1)= \left( \bigcup\mathbb{S}\right) (x_2)}\), oznaczmy tą wartość jako \(\displaystyle{ y}\). Wtedy \(\displaystyle{ (x_1,y)\in \bigcup\mathbb{S},}\) więc \(\displaystyle{ (x_1,y)\in f_1}\), dla pewnej funkcji \(\displaystyle{ f_1\in\mathbb{S}}\), i podobnie \(\displaystyle{ (x_2,y)\in f_2}\), dla pewnej funkcji \(\displaystyle{ f_2\in\mathbb{S}}\). Ponieważ \(\displaystyle{ f_1,f_2\in\mathbb{S}}\), a \(\displaystyle{ \mathbb{S}}\) jest łańcuchem względem relacji rozszerzania (formalnie inkluzji), więc \(\displaystyle{ f_1\supset f_2}\) lub \(\displaystyle{ f_2\supset f_1}\). Jeśli \(\displaystyle{ f_2\subset f_1}\), to \(\displaystyle{ (x_1,y);(x_2,y)\in f_1}\), ponieważ \(\displaystyle{ f_1\in\mathbb{S}}\) jest funkcją różnowartościową, więc \(\displaystyle{ x_1=x_2}\). Jeśli \(\displaystyle{ f_1\subset f_2}\), to rozumujemy analogicznie, co kończy dowód. \(\displaystyle{ \square}\)


Nim udowodnimy dwa pozostałe fakty z dwoma funkcjami udowodnimy fakt, że każdy podzbiór funkcji cżęściowej \(\displaystyle{ f}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) różnowartościowej jest funkcją różnowartościową.

Dowod:

Niech \(\displaystyle{ g\subset f}\). Wtedy \(\displaystyle{ g}\) jest funkcją częściową (każdy podzbiór funkcji częściowej jest funkcją częściową- jest to prosty fakt). Aby wykazać, że funkcja \(\displaystyle{ g}\) jest różnowartościowa, to niech \(\displaystyle{ x_1,x_2\in g_L}\), będą takie, że \(\displaystyle{ g(x_1)=g_(x_2)}\) oznaczmy tą wartość jako \(\displaystyle{ y}\). Wtedy, innymi słowy \(\displaystyle{ (x_1,y)\in g; (x_2,y)\in g}\). Ponieważ \(\displaystyle{ g\subset f}\), więc \(\displaystyle{ (x_1,y)\in f; (x_2,y)\in f}\), innymi słowy \(\displaystyle{ f(x_1)=y}\) i \(\displaystyle{ f(x_2)=y}\), czyli \(\displaystyle{ f(x_1)=f(x_2)}\), ponieważ \(\displaystyle{ f}\) jest różnowartościowa, to \(\displaystyle{ x_1=x_2}\). Zatem \(\displaystyle{ g}\) jest różnowartościowa.\(\displaystyle{ \square}\)

Aby uzasadnić te dwa pozostałe proste fakty, to rozważmy cztery zbiory \(\displaystyle{ X_1,X_2,Y_1,Y_2}\), oraz dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow Y_1;f_2:X_2 \rightarrow Y_2}\) różnowartościowe, takie, że dla każdego \(\displaystyle{ x\in X_1\cap X_2}\) byłoby \(\displaystyle{ f_1(x)=f_2(x)}\) (czyli aby w przekroju dziedzin funkcje się pokrywały) wtedy \(\displaystyle{ f_1\cap f_2:X_1\cap X_2 \rightarrow Y_1\cap Y_2}\) jest funkcją różnowartościową, a \(\displaystyle{ f_1 \setminus f_2:X_1 \setminus X_2 \rightarrow Y_1}\) jest funkcją różnowartościową.

Dowód:

Na mocy tego 'ciekawego wyniku' z tego wątku \(\displaystyle{ f_1\cap f_2}\) jest funkcją z \(\displaystyle{ X_1\cap X_2}\) do \(\displaystyle{ Y_1\cap Y_2}\). Ponieważ \(\displaystyle{ f_1\cap f_2\subset f_1}\), a \(\displaystyle{ f_1}\) jest funkcją róznowartościową (możemy ją traktować jako funkcje częściową), więc jej podzbiór \(\displaystyle{ f_1\cap f_2}\) jest funkcją różnowartościową, na mocy dowiedzionego przed chwilą faktu.
Podobnie dla różnicy, na mocy tego 'ciekawego wyniku' \(\displaystyle{ f_1 \setminus f_2:X_1 \setminus X_2 \rightarrow Y_1}\) jest funkcją; a ponieważ \(\displaystyle{ f_1 \setminus f_2 \subset f_1}\) i \(\displaystyle{ f _{1}}\) jest funkcją różnowartościową, więc również \(\displaystyle{ f_1 \setminus f_2}\) jest funkcją różnowartościową.\(\displaystyle{ \square}\)

[Jakub Gurak]

Ten fakt, że suma łańcucha funkcji różnowartościowych jest funkcją różnowartościową można wykorzystać aby udowodnić (przy założeniu aksjomatu wyboru, równoważnie Lematu Zorna), że dla dowolnych zbiorów \(\displaystyle{ X,Y}\) mamy: \(\displaystyle{ \left| X\right| \le\left| Y\right| }\) lub \(\displaystyle{ \left| Y\right| \le \left| X\right|. }\)(To nie jest mój pomysł, ja na takie coś bym nie wpadł, pochodzi z Guzickiego, ale mając ten fakt można 'zwinąć' dowód do prostszej postaci). Oto dowód:

Dowód:

Rozważmy rodzinę funkcji różnowartościowych:

\(\displaystyle{ \mathbb{B} =\left\{ f\subset X\times Y\Bigl| \ f \hbox{ jest funkcją różnowartościową }\right\}.}\)

Wtedy \(\displaystyle{ (\mathbb{B} ,\subset)}\) jest zbiorem uporządkowanym. Stosujemy do niego Lemat Zorna. W tym celu

Niech \(\displaystyle{ \mathbb{D} \subset\mathbb{B} }\) będzie łańcuchem. Jako ograniczenie górne kładziemy( jak zwykle) zbiór \(\displaystyle{ \bigcup\mathbb{D}}\). Ponieważ \(\displaystyle{ \mathbb{D} \subset \mathbb{B} }\) jest łańcuchem funkcji różnowartościowych, więc \(\displaystyle{ \bigcup\mathbb{D}}\) jest funkcją różnowartościową, na mocy przytoczonego faktu. A zatem \(\displaystyle{ \bigcup\mathbb{D}\in\mathbb{B}}\), czyli ta suma jest elementem zbioru uporządkowanego \(\displaystyle{ \mathbb{B}}\), a zatem \(\displaystyle{ \bigcup\mathbb{D} = \bigvee \mathbb{D} }\)- suma rodziny \(\displaystyle{ \mathbb{D} }\) jest jej supremum, więc w szczególności jest jej ograniczeniem górnym- tego łańcucha. Z dowolności wyboru tego łańcucha otrzymujemy, że w \(\displaystyle{ (\mathbb{B} ,\subset)}\) każdy łańcuch ma ograniczenie górne.

Stosując Lemat Zorna otrzymujemy element maksymalny \(\displaystyle{ f\in \mathbb{B} .}\) Wtedy \(\displaystyle{ f}\) jest funkcją różnowartościową. Jeśli \(\displaystyle{ f_L=X}\), to \(\displaystyle{ f:X \stackrel{1-1}{\rightarrow} Y}\), a więc \(\displaystyle{ \left| X\right| \le \left| Y\right|}\), co należało pokazać. Jeśli \(\displaystyle{ f_L \neq X}\), to \(\displaystyle{ f_L\subsetneq X}\). Wtedy \(\displaystyle{ f_P=Y. }\)
Przypuśćmy nie wprost, że tak nie jest. Wtedy \(\displaystyle{ f_P\subsetneq Y.}\) A zatem istnieje element \(\displaystyle{ y\in Y}\), taki, że \(\displaystyle{ y\not\in f_P}\). Ponieważ \(\displaystyle{ f_L\subsetneq X}\), więc istnieje element \(\displaystyle{ x\in X}\), spoza zbioru \(\displaystyle{ f_L}\), a więc taki, że \(\displaystyle{ x\not\in f_L}\). Ustalmy takie elementy, i rozważmy funkcję \(\displaystyle{ g=f \cup\left\{ \left( x,y\right) \right\} }\). Ponieważ \(\displaystyle{ x\not\in f_L}\), to \(\displaystyle{ g}\) jest funkcją, a ponieważ \(\displaystyle{ y\not\in f_P}\) (i \(\displaystyle{ f}\) jest róznowarościowa), to \(\displaystyle{ g}\) również jest różnowartościowa. A zatem \(\displaystyle{ g\in\mathbb{B}}\), i \(\displaystyle{ g\supsetneq f}\)( \(\displaystyle{ (x,y)\not\in f}\), o czym łatwo nie wprost się przekonać). A więc \(\displaystyle{ g}\) jest istotnie większym od \(\displaystyle{ f}\) elementem \(\displaystyle{ \mathbb{B} }\), a ponieważ \(\displaystyle{ f\in\mathbb{B}}\) był elementem maksymalnym, to nie ma w \(\displaystyle{ \mathbb{B} }\) elementów od niego silnie większych. Otrzymaliśmy więc sprzeczność.
A zatem \(\displaystyle{ f_P=Y, f_L\subsetneq X,}\) wtedy \(\displaystyle{ f:f_L \mathop{\stackrel {1-1 } { \rightarrow } } _{ NA} f_P=Y}\), zatem jest to bijekcja, zatem również \(\displaystyle{ f^{-1}:Y \rightarrow f_L\subset X}\) jest bijekcją, a zatem \(\displaystyle{ f^{-1}:Y \rightarrow X}\) jest róznowartościowa, a stąd \(\displaystyle{ \left| Y\right| \le \left| X\right|. \square}\)

[Jakub Gurak]

Udowodniłem przedwczoraj również, że jeśli mamy iloczyn kartezjański \(\displaystyle{ X\times Y}\), a \(\displaystyle{ \mathbb{B}}\) jest rodziną funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), tak aby dziedziny tych funkcji były rozłączne, to suma tych funkcji częściowych jest funkcją częściową, i jest funkcją ze sumy dziedzin tych funkcji w zbiór \(\displaystyle{ Y}\). Przedstawię teraz dowód tego ciekawego faktu.

Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), taką, że jeśli \(\displaystyle{ f_1,f_2\in\mathbb{B}}\) są różnymi funkcjami, to ich dziedziny \(\displaystyle{ (f_1)_L, (f_2)_L}\) są zbiorami rozłącznymi. Wykażemy, że zbiór \(\displaystyle{ \bigcup\mathbb{B}}\) jest funkcją częściową, i jest funkcją określoną na zbiorze \(\displaystyle{ \bigcup_{f\in\mathbb{B}} f_L}\) w zbiór \(\displaystyle{ Y.}\)

Dowód:

Niewątpliwie \(\displaystyle{ \bigcup\mathbb{B} \subset X \times Y}\) (suma podzbiorów \(\displaystyle{ X \times Y}\)), a więc jest to relacja z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\).

Aby wykazać, że taka relacja jest funkcją częściową, to weźmy pary \(\displaystyle{ (x,y_1); (x,y_2)\in \bigcup\mathbb{B},}\) i pokażmy, że \(\displaystyle{ y_1=y_2.}\) Ponieważ \(\displaystyle{ (x,y_1)\in \bigcup\mathbb{B}}\), to \(\displaystyle{ (x,y_1)\in f_1}\), gdzie \(\displaystyle{ f_1\in\mathbb{B}}\), podobnie dla drugiej pary otrzymujemy, że \(\displaystyle{ (x,y_2)\in f_2}\), gdzie \(\displaystyle{ f_2\in\mathbb{B}}\). Wtedy \(\displaystyle{ x\in (f_1)_L}\) i \(\displaystyle{ x\in (f_2)_L}\), a zatem \(\displaystyle{ x\in (f_1)_L \cap (f_2)_L}\). Wtedy \(\displaystyle{ f_1=f_2}\)( Gdyby byłoby \(\displaystyle{ f_1 \neq f_2}\), ponieważ \(\displaystyle{ f_1, f_2\in B}\), więc gdyby byłoby \(\displaystyle{ f_1 \neq f_2}\), więc z naszego założenia zbiory \(\displaystyle{ (f_1)_L}\) i \(\displaystyle{ (f_2)_L}\) musiałyby być rozłączne, a \(\displaystyle{ x\in (f_1)_L \cap (f_2)_L}\)- sprzeczność).

A zatem \(\displaystyle{ f_1=f_2}\), oznaczmy tą funkcję jako \(\displaystyle{ f}\). Ponieważ wtedy \(\displaystyle{ (x,y_1)\in f, (x,y_2)\in f}\), i ponieważ \(\displaystyle{ f}\) jest funkcją częściową, więc wnioskujemy, że \(\displaystyle{ y_1=y_2.}\) Wobec czego relacja \(\displaystyle{ \bigcup\mathbb{B}}\) jest funkcją częściową.


Łatwo będzie teraz pokazać, że jest to funkcja określona na sumie dziedzin tych funkcji, czyli na \(\displaystyle{ \bigcup_{f\in \mathbb{B} } f_L}\).
Ponieważ każda funkcja częściowa \(\displaystyle{ f}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) jest funkcją z \(\displaystyle{ f_L}\) w \(\displaystyle{ Y}\), więc również funkcja częściowa \(\displaystyle{ \bigcup \mathbb{B}}\) jest funkcja ze \(\displaystyle{ (\bigcup\mathbb{B})_L}\) w \(\displaystyle{ Y.}\)

Ale ponieważ dla dowolnej rodziny relacji \(\displaystyle{ \mathbb{A}}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) mamy \(\displaystyle{ (\bigcup\mathbb{A})_L= \bigcup_{R\in\mathbb{A}} R_L}\)- lewa dziedzina sumy rodziny relacji jest sumą lewych dziedzin tych relacji (łatwo można to pokazać- poprzez dwie proste inkluzje), więc u nas również \(\displaystyle{ (\bigcup\mathbb{B})_L= \bigcup_{f\in\mathbb{B}} f_L}\). Ponieważ \(\displaystyle{ \bigcup\mathbb{B}}\) jest funkcją ze \(\displaystyle{ ( \bigcup\mathbb{B} )_L}\) w \(\displaystyle{ Y}\), więc również \(\displaystyle{ \bigcup\mathbb{B}: \bigcup_{f\in\mathbb{B}} f_L \rightarrow Y. \square}\)