Równoliczność zbiorów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
emong00
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 paź 2022, o 20:42
Płeć: Mężczyzna
wiek: 19
Podziękował: 21 razy

Równoliczność zbiorów

Post autor: emong00 »

Dane są zbiory \(\displaystyle{ X, Y, Z}\). Udowodnij, że \(\displaystyle{ ^{Y×Z}X}\) jest równoliczne z \(\displaystyle{ ^{^ZY}X}\).
Wiem, że muszę bijekcję pomiędzy tymi zbiorami znaleźć, ale nie umiem znaleźć jej. Jak podchodzić do tego typu zadań? Większość moich prób polegała przez to, że nie wiem czy te zbiory są równoliczne.
Jan Kraszewski
Administrator
Administrator
Posty: 34124
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Równoliczność zbiorów

Post autor: Jan Kraszewski »

Twój problem wynika zapewne z dość sporego skomplikowania tego przykładu - musisz wszak zdefiniować funkcję, której dziedziną jest zbiór funkcji, których wartościami są funkcje, a wartościami funkcje (czyli są trzy poziomy "funkcyjności")...

Potrzebujemy zdefiniować funkcję \(\displaystyle{ \Phi:\left( X^Y\right)^Z\to X^{Y\times Z}}\) (zapisuję zbiory funkcji nieco inaczej, niż Ty, ale myślę, że poradzisz sobie z tym...), która jest bijekcją. Zatem dla każdego \(\displaystyle{ f\in \left( X^Y\right)^Z}\), czyli \(\displaystyle{ f:Z\to X^Y}\) musisz określić, czym jest \(\displaystyle{ \Phi(f)}\), pamiętając o tym, że \(\displaystyle{ \Phi(f)\in X^{Y\times Z}}\), czyli \(\displaystyle{ \Phi(f):Y\times Z\to X}\). No ale żeby określić funkcję \(\displaystyle{ \Phi(f)}\) musisz dla dowolnej pary \(\displaystyle{ (y,z)\in Y\times Z}\) powiedzieć, czym jest \(\displaystyle{ \Phi(f)(z,y)}\) (pamiętając, że \(\displaystyle{ \Phi(f)(z,y)\in X}\)).

Podsumowując, mając \(\displaystyle{ f:Z\to X^Y}\) oraz \(\displaystyle{ (y,z)\in Y\times Z}\) (czyli \(\displaystyle{ y\in Y}\) i \(\displaystyle{ z\in Z}\)) musimy zmajstrować jakoś element zbioru \(\displaystyle{ X}\). No ale to da się zrobić w jedyny sensowny sposób: biorąc najpierw wartość \(\displaystyle{ f(z)}\), o której wiemy, że \(\displaystyle{ f(z)\in X^Y}\), czyli \(\displaystyle{ f(z):Y\to X}\), a potem \(\displaystyle{ (f(z))(y)}\), które jest już elementem zbioru \(\displaystyle{ X}\).

Czyli w wersji skompresowanej \(\displaystyle{ \Phi(f)(y,z)=f(z)(y)}\). Pozostaje pokazać, że funkcja \(\displaystyle{ \Phi}\) jest bijekcją.

JK
emong00
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 paź 2022, o 20:42
Płeć: Mężczyzna
wiek: 19
Podziękował: 21 razy

Re: Równoliczność zbiorów

Post autor: emong00 »

Dobra to dwie rzeczy. Mega to rozpisałeś i (wydaje mi się), że rozumiem, ale i tak bym upewniłbym się na innym zadanku czy na pewno. Poza tym mam problem z dowodem surjekcji, ewidentnie nie rozumiem tego pojęcia całkowicie, ale o tym później.

Dane są zbiory \(\displaystyle{ X,Y,Z}\). Tym razem mam udowodnić, że \(\displaystyle{ ^Z(X \times Y)}\) jest równoliczne z \(\displaystyle{ ^ZX \times ^ZY}\). Czyli nasza funkcja \(\displaystyle{ \Phi}\) wybiera funkcję \(\displaystyle{ f:Z \rightarrow X \times Y}\) i przypisuje jej funkcje \(\displaystyle{ \varphi_f :Z \rightarrow X}\) i funkcje \(\displaystyle{ \psi_f :Z \rightarrow Y}\). Niech \(\displaystyle{ \varphi_f}\) i \(\displaystyle{ \psi_f}\) są takie, że \(\displaystyle{ f(z)=(x,y)=(\varphi_f (z),\psi_f (z))}\). Wtedy możemy zapisać \(\displaystyle{ \Phi}\) jako \(\displaystyle{ \Phi (f)=(\varphi_f,\psi_f)}\). Teraz przechodzimy do udowadniania tego, że jest to bijekcja:

1)Hp. \(\displaystyle{ \Phi}\) nie jest injekcją. Bierzemy \(\displaystyle{ f \neq g}\) należące do \(\displaystyle{ ^Z(X \times Y)}\) takie, że \(\displaystyle{ \Phi (f)=\Phi (g) \Leftrightarrow (\varphi_f,\psi_f)=(\varphi_g,\psi_g) \Leftrightarrow \varphi_f=\varphi_g \wedge \psi_f=\psi_g}\). Czyli dla każdego \(\displaystyle{ z \in Z}\) obie funkcje przyjmują takie same wartośći w \(\displaystyle{ X}\) i w \(\displaystyle{ Y}\), wiec \(\displaystyle{ f=g}\), czyli sprzeczność.

2)Teraz ta nieszczęsna surjekcja. W tym wypadku mam udowodnić, że \(\displaystyle{ \Phi[^Z(X \times Y)]=^ZX \times ^ZY}\)? Zakładając, że tak, to i tak nie jestem pewien co do zapisu. Czy to ma jakikolwiek sens?
\(\displaystyle{ \Phi[^Z(X \times Y)]=\varphi_{[^Z(X \times Y)]} \times \psi_{[^Z(X \times Y)]}=^ZX \times ^ZY}\)
I jak w poprzednim zadaniu bym to miał zrobić?
Jan Kraszewski
Administrator
Administrator
Posty: 34124
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Równoliczność zbiorów

Post autor: Jan Kraszewski »

emong00 pisze: 29 lis 2022, o 22:42Dane są zbiory \(\displaystyle{ X,Y,Z}\). Tym razem mam udowodnić, że \(\displaystyle{ ^Z(X \times Y)}\) jest równoliczne z \(\displaystyle{ ^ZX \times ^ZY}\). Czyli nasza funkcja \(\displaystyle{ \Phi}\) wybiera funkcję \(\displaystyle{ f:Z \rightarrow X \times Y}\) i przypisuje jej funkcje \(\displaystyle{ \varphi_f :Z \rightarrow X}\) i funkcje \(\displaystyle{ \psi_f :Z \rightarrow Y}\). Niech \(\displaystyle{ \varphi_f}\) i \(\displaystyle{ \psi_f}\) są takie, że \(\displaystyle{ f(z)=(x,y)=(\varphi_f (z),\psi_f (z))}\). Wtedy możemy zapisać \(\displaystyle{ \Phi}\) jako \(\displaystyle{ \Phi (f)=(\varphi_f,\psi_f)}\).
Dobrze. Funkcje \(\displaystyle{ \varphi_f}\) i \(\displaystyle{ \psi_f}\) nazywają się funkcjami składowymi funkcji \(\displaystyle{ f}\), a funkcję \(\displaystyle{ \Phi}\) można zapisać ładnym wzorem: \(\displaystyle{ \Phi(f)=(\pi_X^{\ }\circ f,\pi_Y^{\ }\circ f)}\), gdzie \(\displaystyle{ \pi_X^{\ }, \pi_Y^{\ }}\) to rzuty na odpowiednie osie produktu \(\displaystyle{ X\times Y.}\)
emong00 pisze: 29 lis 2022, o 22:421) Hp. \(\displaystyle{ \red{\Phi}}\) nie jest injekcją. Bierzemy \(\displaystyle{ f\, \red{\neq}\, g}\) należące do \(\displaystyle{ ^Z(X \times Y)}\) takie, że \(\displaystyle{ \Phi (f)=\Phi (g) \Leftrightarrow (\varphi_f,\psi_f)=(\varphi_g,\psi_g) \Leftrightarrow \varphi_f=\varphi_g \wedge \psi_f=\psi_g}\). Czyli dla każdego \(\displaystyle{ z \in Z}\) obie funkcje przyjmują takie same wartośći w \(\displaystyle{ X}\) i w \(\displaystyle{ Y}\), wiec \(\displaystyle{ f=g}\), czyli sprzeczność.
Dobrze, tylko po co rozumować nie wprost? Jak wykreślisz czerwone fragmenty, to dostaniesz dowód wprost...
emong00 pisze: 29 lis 2022, o 22:422)Teraz ta nieszczęsna surjekcja. W tym wypadku mam udowodnić, że \(\displaystyle{ \Phi[^Z(X \times Y)]=^ZX \times ^ZY}\)?
Tak.
emong00 pisze: 29 lis 2022, o 22:42Zakładając, że tak, to i tak nie jestem pewien co do zapisu. Czy to ma jakikolwiek sens?
\(\displaystyle{ \Phi[^Z(X \times Y)]=\varphi_{[^Z(X \times Y)]} \times \psi_{[^Z(X \times Y)]}=^ZX \times ^ZY}\)
Nie bardzo ma sens (bo czymże są \(\displaystyle{ \varphi}\) i \(\displaystyle{ \psi}\) ?), no i nie ma żadnego uzasadnienia.

Inny sposób zapisu warunku surjektywności to

\(\displaystyle{ (\forall (\alpha,\beta)\in X^Z\times Y^Z)(\exists f\in (X\times Y)^Z)\,\Phi(f)=(\alpha,\beta).}\)

No i teraz postępujesz zgodnie z tym warunkiem. Ustalasz najpierw dowolne \(\displaystyle{ (\alpha,\beta)\in X^Z\times Y^Z}\) i szukasz odpowiedniej funkcji \(\displaystyle{ f\in (X\times Y)^Z}\). Jak nietrudno zauważyć wystarczy wziąć funkcję zadaną wzorem \(\displaystyle{ f(z)=(\alpha(z),\beta(z))}\). Wtedy \(\displaystyle{ \Phi(f)=(\pi_X^{\ }\circ f,\pi_Y^{\ }\circ f)=(\alpha,\beta)}\), bo dla każdego \(\displaystyle{ z\in Z}\) mamy \(\displaystyle{ \pi_X^{\ }\circ f(z)=\pi_X^{\ }(f(z))=\pi_X^{\ }((\alpha(z),\beta(z)))=\alpha(z)}\) oraz \(\displaystyle{ \pi_Y^{\ }\circ f(z)=\pi_Y^{\ }(f(z))=\pi_Y^{\ }((\alpha(z),\beta(z)))=\beta(z).}\)
emong00 pisze: 29 lis 2022, o 22:42I jak w poprzednim zadaniu bym to miał zrobić?
Podobnie. Masz pokazać, że dla dowolnej funkcji \(\displaystyle{ \alpha\in X^{Y\times Z}}\) istnieje funkcja \(\displaystyle{ \xi\in\left( X^Y\right) ^Z}\) taka, że \(\displaystyle{ \Phi(\xi)=\alpha}\). Ustalasz zatem dowolną funkcję \(\displaystyle{ \alpha\in X^{Y\times Z}}\) i przystępujesz do poszukiwań odpowiedniej funkcji \(\displaystyle{ \xi:Z\to X^Y}\). Ale to znów jest - jak się chwilę zastanowić (i popatrzeć na to, co ma wyjść) - dość oczywiste. Żeby zdefiniować funkcję \(\displaystyle{ \xi}\) musimy dla każdego \(\displaystyle{ z\in Z}\) zdefiniować funkcję \(\displaystyle{ \xi(z):Y\to X}\), czyli - dalej - dla każdego y\in Y musimy zdefiniować \(\displaystyle{ (\xi(z))(y)\green{\in X}}\). No to połóżmy \(\displaystyle{ \blue{(\xi(z))(y)=\alpha(y,z)}}\) (zgadza się, bo \(\displaystyle{ \alpha:Y\times Z\to \green{X}}\)) - oczywiście robimy tak po to, żeby wyszło... Mamy bowiem istotnie dla dowolnych \(\displaystyle{ (y,z)\in Y\times Z}\)

\(\displaystyle{ \Phi(\xi)(y,z)=\blue{\xi(z)(y)=\alpha(y,z)},}\) czyli \(\displaystyle{ \Phi(\xi)=\alpha,}\) tak jak chcieliśmy.

JK
junmisugi
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 8 gru 2022, o 23:40
Płeć: Mężczyzna
wiek: 27

Re: Równoliczność zbiorów

Post autor: junmisugi »

Jan Kraszewski pisze: 29 lis 2022, o 23:30
emong00 pisze: 29 lis 2022, o 22:42I jak w poprzednim zadaniu bym to miał zrobić?
Podobnie. Masz pokazać, że dla dowolnej funkcji \(\displaystyle{ \alpha\in X^{Y\times Z}}\) istnieje funkcja \(\displaystyle{ \xi\in\left( X^Y\right) ^Z}\) taka, że \(\displaystyle{ \Phi(\xi)=\alpha}\). Ustalasz zatem dowolną funkcję \(\displaystyle{ \alpha\in X^{Y\times Z}}\) i przystępujesz do poszukiwań odpowiedniej funkcji \(\displaystyle{ \xi:Z\to X^Y}\). Ale to znów jest - jak się chwilę zastanowić (i popatrzeć na to, co ma wyjść) - dość oczywiste. Żeby zdefiniować funkcję \(\displaystyle{ \xi}\) musimy dla każdego \(\displaystyle{ z\in Z}\) zdefiniować funkcję \(\displaystyle{ \xi(z):Y\to X}\), czyli - dalej - dla każdego y\in Y musimy zdefiniować \(\displaystyle{ (\xi(z))(y)\green{\in X}}\). No to połóżmy \(\displaystyle{ \blue{(\xi(z))(y)=\alpha(y,z)}}\) (zgadza się, bo \(\displaystyle{ \alpha:Y\times Z\to \green{X}}\)) - oczywiście robimy tak po to, żeby wyszło... Mamy bowiem istotnie dla dowolnych \(\displaystyle{ (y,z)\in Y\times Z}\)

\(\displaystyle{ \Phi(\xi)(y,z)=\blue{\xi(z)(y)=\alpha(y,z)},}\) czyli \(\displaystyle{ \Phi(\xi)=\alpha,}\) tak jak chcieliśmy.

JK
Przepraszam że odkopię ale chciałbym się upewnić, czy powyższy dowód to dowód na bijekcję?
emong00
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 paź 2022, o 20:42
Płeć: Mężczyzna
wiek: 19
Podziękował: 21 razy

Re: Równoliczność zbiorów

Post autor: emong00 »

Nie rozpisaliśmy chyba dowodu na injekcje do tego przykładu, jest tylko dowód na surjekcje.
Jan Kraszewski
Administrator
Administrator
Posty: 34124
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Równoliczność zbiorów

Post autor: Jan Kraszewski »

junmisugi pisze: 11 gru 2022, o 15:27Przepraszam że odkopię ale chciałbym się upewnić, czy powyższy dowód to dowód na bijekcję?
Zgodnie z tym, co napisał emong00 - oczywiście nie. Pytanie dotyczyło surjektywności, więc także odpowiedź.

Chyba widzisz, że nigdzie nie sprawdzamy różnowartościowości.

JK
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Równoliczność zbiorów

Post autor: Janusz Tracz »

Zbiory \(\displaystyle{ X^{Y \times Z}}\) oraz \(\displaystyle{ (X^Y)^Z}\) można sobie narysować. A dokładniej, narysować można elementy z jakich się składają:

Przechwytywanie.PNG
Zbiór \(\displaystyle{ X^{Y \times Z}}\) składa się z elementów którymi są funkcje dwóch zmiennych, czyli takie prostokątne tabelki z wartościami \(\displaystyle{ x\in X}\) wewnątrz. Zbiór \(\displaystyle{ (X^Y)^Z}\) to zbiór funkcji których wartości to funkcje.

Widać, że można zdefiniować dwa naturalne odwzorowania \(\displaystyle{ \Phi,\Psi}\) które będą zamieniać jedne tabelki na drugie ale tak by struktura tych wewnętrznych funkcji bądź ich cięć pozostała zgodna:

Przechwytywanie1.PNG

Teraz widać jak zdefiniować \(\displaystyle{ \Phi: (X^Y)^Z \to X^{Y \times Z}}\) albo widać dlaczego JK tak je zdefiniował. Więc dla \(\displaystyle{ f\in (X^Y)^Z}\) aby odtworzyć sytuację z obrazka kładziemy
\(\displaystyle{ \Phi(f)=\left[ \, Y \times Z\ni (y,z)\mapsto f(z)(y) \in X \right] }\)

oraz \(\displaystyle{ \Psi: X^{Y \times Z} \to (X^Y)^Z }\) definiujemy wzorem dla \(\displaystyle{ g\in X^{Y \times Z}}\)

\(\displaystyle{ \Psi(g)=\left[ \, Z\ni z\mapsto \left[ Y\ni y\mapsto g(y,z)\in X\right] \right] }\)

Ostatecznie wystarczy sprawdzić, że \(\displaystyle{ \Psi\circ \Phi = \mathrm{id}_{(X^Y)^Z}}\) oraz \(\displaystyle{ \Phi\circ \Psi = \mathrm{id}_{X^{Y \times Z}}}\). Policzmy

\(\displaystyle{
\begin{split}
(\Psi\circ \Phi)(f)& = \Psi\left(\left[ \, Y \times Z\ni (y,z)\mapsto f(z)(y) \in X \right] \right) \\[1ex]
&= \left[ \, Z\ni z\mapsto \left[ Y\ni y\mapsto \left[ \, Y \times Z\ni (y,z)\mapsto f(z)(y) \in X \right](y,z)\in X\right] \right] \\[1ex]
&= \left[ \, Z\ni z\mapsto \left[ Y\ni y\mapsto f(z)(y)\in X\right] \right]\\[1ex]
&=f
\end{split}
}\)

\(\displaystyle{
\begin{split}
(\Phi\circ \Psi)(g)& = \Phi\left( \left[ \, Z\ni z\mapsto \left[ Y\ni y\mapsto g(y,z)\in X\right] \right]\right) \\[1ex]
&=\left[ \, Y \times Z\ni (y,z)\mapsto \left[ \, Z\ni z\mapsto \left[ Y\ni y\mapsto g(y,z)\in X\right] \right](z)(y) \in X \right] \\[1ex]
&=\left[ \, Y \times Z\ni (y,z)\mapsto \left[ Y\ni y\mapsto g(y,z)\in X\right](y) \in X \right] \\[1ex]
&=\left[ \, Y \times Z\ni (y,z)\mapsto g(y,z) \in X \right]\\[1ex]
&=g
\end{split}
}\)

oznacza to, że \(\displaystyle{ \Phi,\Psi}\) to wzajemnie do siebie odwrotne bijekcje.
ODPOWIEDZ