Matematyka.pl

Przypomnijmy, jeśli \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są zbiorami, a \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i mamy zbiór \(\displaystyle{ A \subset X}\), to obrazem zbioru \(\displaystyle{ A}\) przez relację \(\displaystyle{ R}\) nazywamy zbiór:

\(\displaystyle{ R(A)= \left[ R \cap \left( A \times Y\right) \right] _P}\),

czyli jest to przekrój tej relacji z pionowym pasem \(\displaystyle{ A \times Y,}\) i rzut takiego przekroju na oś \(\displaystyle{ Y. }\)
\(\displaystyle{ }\)
Oto ilustracja takiego zbioru:
\(\displaystyle{ \\}\)\(\displaystyle{ \\}\) Wczoraj wykazałem, że jeśli mamy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz mamy rodzinę podzbiorów pierwszej osi \(\displaystyle{ X}\), to obraz sumy tej rodziny przez relację \(\displaystyle{ R}\) jest równy sumie obrazów tych zbiorów. Wykazałem również, że jeśli zbiór \(\displaystyle{ A \subset X}\) jest nadzbiorem lewej dziedziny tej relacji, to jego obraz przez tą relację jest równy prawej dziedzinie tej relacji \(\displaystyle{ R_P}\). Przedstawię teraz dowody tych fascynujących faktów.


Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y.}\)
Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną podzbiorów zbioru \(\displaystyle{ X. }\)

Wykażemy równość:

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

czyli wykażemy, że obraz sumy rodziny zbiorów przez relację jest równy sumie obrazów tych zbiorów.

Oto ilustracja tego ciekawego faktu: \(\displaystyle{ \\}\) \(\displaystyle{ \\}\) Nim to udowodnimy, przypomnijmy, że jeśli \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są zbiorami, a \(\displaystyle{ \mathbb{B}}\) jest rodziną relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to prawa dziedzina sumy tej rodziny relacji jest równa sumie prawych dziedzin tych relacji, tzn. mamy prawo:

\(\displaystyle{ \left( \bigcup \mathbb{B}\right) _{P}= \bigcup_{R \in \mathbb{B}} R_P;}\)

można to łatwo udowodnić.

Oto: Przypomnijmy jeszcze, że jeśli \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów , a \(\displaystyle{ Y}\) jest zbiorem, to mamy prawo:

\(\displaystyle{ \bigcup\mathbb{B} \times Y= \bigcup_{A \in \mathbb{B}} \left( A \times Y\right) }\),

jest to dość podstawowy fakt.

Łatwo będzie teraz wykazać, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla rodziny \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X}\), mamy prawo:

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

obraz sumy tej rodziny zbiorów przez relację \(\displaystyle{ R}\) jest równy sumie obrazów tych zbiorów. Wykażemy teraz, że jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz mamy zbiór \(\displaystyle{ A \subset X}\), taki, że \(\displaystyle{ A\supset R_L}\), to jego obraz jest równy prawej dziedzinie tej relacji, czyli mamy: \(\displaystyle{ R\left( A\right) =R_P.}\)

Nim to udowodnimy, przypomnijmy, że już kiedyś wykazaliśmy podobne prawo dla przeciwobrazu, TUTAJ.

W podanym linku wykazałem również, że obraz zbioru przez daną relację jest równy przeciwobrazowi tego zbioru przez relacje do niej odwrotną- ten fakt przyda nam się.

Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Mamy \(\displaystyle{ R_L= R ^{-1}_P}\), a zatem \(\displaystyle{ A\supset R ^{-1}_P}\).

Wtedy dla relacji odwrotnej \(\displaystyle{ S:=R ^{-1}}\), mamy, na mocy faktu z linku \(\displaystyle{ S ^{-1} \left( A\right) =S_L}\), czyli przeciwobraz zbioru \(\displaystyle{ A}\) przez relację \(\displaystyle{ S=R ^{-1}}\) jest równy lewej dziedzinie tej relacji. Mamy również \(\displaystyle{ S ^{-1} \left( A\right)= R\left( A\right)}\) na mocy przytoczonego faktu, a zatem \(\displaystyle{ R\left( A\right) = S_L= R ^{-1}_{L}= R_P.\square}\)

Na koniec wykażemy, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A, B \subset X,}\) jeśli \(\displaystyle{ A \subset B}\), to \(\displaystyle{ R \left( A\right) \subset R\left( B\right),}\)

czyli obraz większego zbioru jest większy,

Oto ilustracja tego faktu: \(\displaystyle{ \\}\) \(\displaystyle{ \\}\) I:
Na koniec wprowadzę (gdyż na ważniaku nie wprowadzili jawnie tego pojęcia) pojęcie funkcji stałej, i udowodnię jeden fakt związany z takimi funkcjami stałymi.

Uzasadnijmy, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ a}\) jest dowolnym elementem, to uzasadnijmy, że można rozważać funkcję stałą na zbiorze \(\displaystyle{ X}\), stale równą elementowi \(\displaystyle{ a}\).

Wystarczy wziąć zbiór \(\displaystyle{ X \times \left\{ a\right\} . }\)

Taka relacja jest funkcją, gdyż jeśli \(\displaystyle{ \left( x, y_1\right) ; \left( x, y_2\right) \in X \times \left\{ a\right\} }\) , to \(\displaystyle{ y_1= a=y_2. }\)

A zatem jest to funkcja częściowa;

i oczywiście \(\displaystyle{ \left( X \times \left\{ a\right\} \right) _L= X}\).

A zatem relacja \(\displaystyle{ X \times \left\{ a\right\}}\) jest funkcją- jest to funkcja stała, na zbiorze \(\displaystyle{ X,}\) stale równa elementowi \(\displaystyle{ a.}\)

Wykażemy, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ a}\) jest elementem, i mamy rodzinę \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X}\) o niepustym przecięciu, i na każdym zbiorze tej rodziny mamy funkcję stałą, stale równą \(\displaystyle{ a}\), tzn. jeśli \(\displaystyle{ A \in \mathbb{B},}\) to mamy \(\displaystyle{ f_A= A \times \left\{ a\right\}}\), to przekrój tych funkcji \(\displaystyle{ \bigcap_{A \in \mathbb{B}} f_A}\) jest funkcja ze zbioru \(\displaystyle{ \bigcap\mathbb{B}}\) w zbiór \(\displaystyle{ \left\{ a\right\}}\) - jest to funkcja stała.

Nim to udowodnimy, przypomnijmy, że:

Jeśli \(\displaystyle{ \mathbb{A}}\) jest rodziną zbiorów, a \(\displaystyle{ Y}\) jest zbiorem, to mamy prawo:

\(\displaystyle{ \bigcap\mathbb{A} \times Y= \bigcap_{A \in \mathbb{A}} \left( A \times Y\right)}\), i łatwo stąd (i na mocy założenia niepustości przekroju) wynika ten fakt.

Jakub Gurak pisze: ↑14 lut 2023, o 23:45 Na koniec wprowadzę (gdyż na ważniaku nie wprowadzili jawnie tego pojęcia) pojęcie funkcji stałej,

Cóż za dramatyczne niedopatrzenie.

JK

I dramatyczna niedoróbka. W myśl tej pseudodefinicji funkcjami stałymi sa jedynie funkcje z `X` w singletony. Od kogoś, kto posługuje się formalizmami można chyba więcej wymagać.

Racja, lepiej te funkcje stałe zdefiniować tak, jak wspomnieli na ważniaku:

Funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest funkcją stałą, gdy ma jednoelementowy zbiór wartości, tzn. (spróbuje to doprecyzować): gdy dla jej zbioru wartości \(\displaystyle{ f_P,}\) mamy: \(\displaystyle{ f_P=\left\{ a\right\}}\), dla pewnego elementu \(\displaystyle{ a \in Y.}\)

Udowodniłem wczoraj, że jeżeli mamy \(\displaystyle{ (n+1)}\) zbiorów (gdzie \(\displaystyle{ n \ge 1}\)): \(\displaystyle{ X_1, X_2, \ldots, X_n, X _{n+1}}\), oraz jeśli mamy \(\displaystyle{ n}\) funkcji \(\displaystyle{ f_1: X_1 \rightarrow X_2, f_2:X_2 \rightarrow X_3, \ldots, f_n: X_n \rightarrow X _{n+1}}\), przy czym co najmniej jedna z tych funkcji jest funkcją stałą, to również ich złożenie \(\displaystyle{ \left( f_n\circ f _{n-1}\circ \ldots \circ f_1\right) }\) jest funkcją stałą.

Udowodniłem też wczoraj, że jeśli mamy dwa zbiory rozłączne \(\displaystyle{ A}\) i \(\displaystyle{ B}\), oraz gdy mamy dwa dowolne zbiory \(\displaystyle{ C}\) i \(\displaystyle{ D}\), to zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B \cap D}\) są rozłączne.
Przedstawię teraz dowody tych ciekawych faktów.


Podajmy najpierw dwa Lematy:

Lemat 1: Jeśli \(\displaystyle{ X, Y}\) i \(\displaystyle{ Z}\) są zbiorami, a \(\displaystyle{ f:X \rightarrow Y}\) i \(\displaystyle{ g :Y \rightarrow Z}\) są funkcjami, przy czym funkcja \(\displaystyle{ g}\) jest funkcją stałą, stale równą pewnemu elementowi \(\displaystyle{ a \in Z}\), to złożenie \(\displaystyle{ \left( g\circ f\right)}\) jest funkcją stałą, (stale równą elementowi \(\displaystyle{ a}\)).

Można to łatwo udowodnić.

Lemat 2: Jeśli \(\displaystyle{ X,Y}\) i \(\displaystyle{ Z}\) są zbiorami, a \(\displaystyle{ f:X \rightarrow Y}\) jest funkcją stałą, stale równą pewnemu elementowi \(\displaystyle{ a \in Y}\), oraz \(\displaystyle{ g:Y \rightarrow Z}\) jest dowolną funkcją, to złożenie \(\displaystyle{ \left( g\circ f\right):X \rightarrow Z}\) jest funkcją stałą (stale równą elementowi \(\displaystyle{ g\left( a\right)}\) ). Przyjmijmy, że dla dowolnych ustalonych zbiorów \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), oraz dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) złożeniem tylko jednej funkcji jest to ta sama funkcja, czyli \(\displaystyle{ \circ \left( f\right) =f}\)- dla naszego dowodu warto takie uogólnienie przyjąć.


Przejdźmy do naszego problemu:

Rozważmy \(\displaystyle{ \left( n+1\right)}\) zbiorów \(\displaystyle{ X_1, X_2, \ldots, X_n, X_{n+1}}\), oraz rozważmy \(\displaystyle{ n}\) funkcji \(\displaystyle{ f_1: X_1 \rightarrow X_2, f_2: X_2 \rightarrow X_3, \ldots , f_n: X_n \rightarrow X _{n+1}}\), gdzie co najmniej jedna z tych funkcji jest funkcją stałą.

Wykażemy, że również ich złożenie \(\displaystyle{ \left( f_n\circ f _{n-1}\circ \ldots \circ f_1 \right)}\) jest funkcją stałą.

INDUKCYJNY DOWÓD TEGO FAKTU:

Jeśli \(\displaystyle{ n=1}\), to \(\displaystyle{ f_1:X_1 \rightarrow X_2}\) jest funkcją stałą, czyli złożenie \(\displaystyle{ \circ \left( f_1\right) =f_1}\) jest funkcją stałą.

Jeśli \(\displaystyle{ n=2}\), to mamy dwie funkcje \(\displaystyle{ f_1:X_1 \rightarrow X_2}\) i \(\displaystyle{ f_2: X_2 \rightarrow X_3}\), przy czym co najmniej jedna z nich jest funkcją stałą.
Jeśli funkcja \(\displaystyle{ f_1}\) jest stała, stale równa elementowi \(\displaystyle{ a \in X_2}\), to z Lematu 2 wynika, że funkcja \(\displaystyle{ \left( f_2\circ f_1\right)}\) jest funkcją stałą, stale równą elementowi \(\displaystyle{ f_2\left( a\right).}\)
Podobnie, jeśli funkcja \(\displaystyle{ f_2}\) jest stała, to na mocy Lematu 1 funkcja \(\displaystyle{ \left( f_2\circ f_1\right)}\) jest funkcją stałą.

Krok indukcyjny: Niech \(\displaystyle{ n}\) będzie liczbą naturalną większą lub równą od \(\displaystyle{ 3}\), i przypuśćmy, że twierdzenie zachodzi dla dowolnych \(\displaystyle{ 1 \le m<n}\), dla dowolnych \(\displaystyle{ m}\) funkcji. Pokażemy, że twierdzenia zachodzi również dla \(\displaystyle{ n}\), dla \(\displaystyle{ n}\) funkcji.

Niech zatem:

\(\displaystyle{ f_1: X_1 \rightarrow X_2, f_2:X_2 \rightarrow X_3, \ldots, f_n:X_n \rightarrow X _{n+1}}\) będą dowolnymi funkcjami, takimi, że co najmniej jedna z nich jest funkcją stałą.

Rozważmy ich złożenie \(\displaystyle{ \left( f_n\circ f _{n-1}\circ \ldots \circ f_1 \right)}\).

Tutaj któreś złożenie wykonujemy jako ostatnie, więc to złożenie jest postaci \(\displaystyle{ f\circ g}\), gdzie:

\(\displaystyle{ f= f_n\circ \ldots \circ f_k}\) i \(\displaystyle{ g= f _{k-1}\circ \dots \circ f_1}\), gdzie \(\displaystyle{ k-1 < n}\) i \(\displaystyle{ k-1 \ge 1.}\)

Wtedy \(\displaystyle{ 2\le k \le n.}\)

Popatrzmy na złożenie \(\displaystyle{ \left( f_n\circ \ldots \circ f_k \right)}\).

Jeśli co najmniej jedna z funkcji \(\displaystyle{ f_n, f _{n-1},\ldots, f_k}\) jest stała, to ponieważ w tym złożeniu występuje dokładnie \(\displaystyle{ (n-k+1)}\) funkcji, a \(\displaystyle{ (n-k+1) \le n-1<n}\), więc możemy do tych funkcji zastosować założenie indukcyjne. i dostać, że funkcja \(\displaystyle{ f= \left( f_n\circ \ldots \circ f_k\right)}\) jest stała. A zatem, z badanego przypadku dla \(\displaystyle{ n=2}\) wynika, że: \(\displaystyle{ f\circ g=\left( f_n\circ f _{n-1}\circ \ldots \circ f_1 \right)}\) jest funkcją stałą.

Jeśli żadna z funkcji \(\displaystyle{ f_n,\ldots, f_k}\) nie jest stała, to ponieważ co najmniej jedna z funkcji \(\displaystyle{ f_1, f_2,\ldots, f_n}\) jest stała, więc musi co najmniej jedna z funkcji \(\displaystyle{ f _{k-1}, f _{k-2}, \ldots, f_1}\) być stała.

Ponieważ \(\displaystyle{ k-1<n}\), więc możemy do tych funkcji zastosować założenie indukcyjne, i dostać że funkcja \(\displaystyle{ g= f _{k-1} \circ f _{k-2} \circ \ldots \circ f_1}\) jest stała. Wtedy, z badanego przypadku dla \(\displaystyle{ n=2}\) wynika, że funkcja \(\displaystyle{ f\circ g=f_n\circ f _{n-1} \circ \ldots \circ f_1}\) jest stała, co dowodzi prawdziwości kroku indukcyjnego.

Zasada indukcji porządkowej kończy dowód tego faktu.\(\displaystyle{ \square}\)


Na koniec wykażemy, że jeśli zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są rozłączne, oraz \(\displaystyle{ C}\) i \(\displaystyle{ D}\) są dowolnymi zbiorami, to zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B \cap D}\) są rozłączne, oto:

ILUSTRACJA TEGO FAKTU \(\displaystyle{ \\}\) \(\displaystyle{ \\}\)
Dla dowodu podajmy najpierw:

Lemat 1: Mówiący, że jeśli zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są rozłączne, oraz \(\displaystyle{ C}\) jest dowolnym zbiorem, to zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B}\) są rozłączne- można to łatwo udowodnić nie wprost.

Podobnie:

Lemat 2: Jeśli zbiory \(\displaystyle{ A}\), \(\displaystyle{ B}\) są rozłączne, a \(\displaystyle{ C}\) jest dowolnym zbiorem, to zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B \cap C}\) są rozłączne- podobnie, łatwo można to udowodnić dowodem nie wprost.

Możemy zatem łatwo udowodnić nasz fakt mówiący, że jeśli zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są rozłączne, a \(\displaystyle{ C}\) i \(\displaystyle{ D}\) są dowolnymi zbiorami, to zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B \cap D}\) są rozłączne.

PROSTY DOWÓD TEGO FAKTU:

Wprost z Lematu 1 otrzymujemy, że zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B}\) są rozłączne. Stosując zatem Lemat 2 do tych zbiorów (oraz do zbioru \(\displaystyle{ D}\)) otrzymujemy, że zbiory \(\displaystyle{ A \cap C}\) i \(\displaystyle{ B \cap D}\) są rozłączne\(\displaystyle{ .\square}\)

Mamy też takie dwa proste fakty mówiące, że jeśli zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są rozłączne, a \(\displaystyle{ C}\) jest dowolnym zbiorem, to zbiory \(\displaystyle{ A \setminus C}\) i \(\displaystyle{ B}\) są rozłączne oraz zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B \setminus C}\) są rozłączne- można te fakty udowodnić łatwo dowodem nie wprost.

Oświeć mnie proszę
Rozumiem, że argumenty typu:
Jeżeli `f_k` jest stała i przyjmuje wartość `a`, to \(\displaystyle{ f_n\circ f_{n-1}\circ...\circ f_{k+1}\circ f_k\circ... \circ f_1(x)=f_n\circ f_{n-1}\circ...\circ f_{k+1}(a) }\)
lub
`(A\cap C)\cap(B\cap D)\subset A\cap B=\emptyset`
które wyprodukowałby student pierwszego roku, nie wpisują się w model pogłębionego podejścia do matematyki?