Bijektywne odwzorowanie - dowód

[Gods_Eater]

Treść:
Udowodnić, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, a jego podzbiór \(\displaystyle{ Y}\) jest skończony, to istnieje bijektywne odwzorowanie \(\displaystyle{ X \setminus Y \rightarrow X}\)
Ogółem mam taką wskazówkę:
Przedstawić zbiór \(\displaystyle{ X}\) w postaci \(\displaystyle{ (Y \cup A) \cup (X\setminus (Y \cup A))}\), gdzie \(\displaystyle{ A}\) jest takim zbiorem przeliczalnym, że \(\displaystyle{ A \cap Y = \emptyset}\), a zbiór \(\displaystyle{ X \setminus Y}\) zapisać w postaci \(\displaystyle{ A \cup (X \setminus (Y \cup A))}\). Następnie skorzystać z istnienia bijekcji \(\displaystyle{ Y \cup A \rightarrow A}\).
Nie ukrywam, że nie wiem, jak to zrobić. Wskazówka mi niewiele pomogła. Rozumiem, że takie rozbicie zbioru \(\displaystyle{ X}\) jest możliwe, bo przekrój zbiorów \(\displaystyle{ Y}\) oraz \(\displaystyle{ A}\) jest pusty. Tak samo wydaje mi się, że można stworzyć odwzorowanie będące bijekcją \(\displaystyle{ f: Y \cup A \rightarrow A}\), na przykład:
\(\displaystyle{
f(x) = \left\{ \begin{array}{ll}
a_n & \textrm{dla $y_n$}\\
a_{N + k} & \textrm{dla $a_k$}\\
\end{array} \right.
}\), gdzie \(\displaystyle{ y_n \in Y}\) - bo \(\displaystyle{ Y}\) jest skończony, więc możemy sobie posortować wyrazy i oznaczyć jako \(\displaystyle{ y_1, y_2, ..., y_n}\), gdzie \(\displaystyle{ n }\) jest skończone. Analogicznie możemy tak samo oznaczyć elementy w \(\displaystyle{ A}\), przy czym indeks dolny \(\displaystyle{ a_{N + k}}\) oznacza sumę dwóch indeksów, gdzie \(\displaystyle{ N}\) jest numerem ostatniego indeksu w zbiorze \(\displaystyle{ Y}\).
Tylko wciąż nie wiem, jak miałoby mi to pomóc w rozwiązaniu problemu. Będę wdzięczny za każdą pomoc w rozjaśnieniu mi tego

[Jakub Gurak]

Proponuje zmienić trochę zadanie aby uprościć rozwiązanie.

Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, a element \(\displaystyle{ a\in X}\), to \(\displaystyle{ X \setminus \left\{ a\right\}\sim X}\).

To niestety nie jest taki prosty fakt na jaki wygląda. Należy tutaj wykorzystać, że zbiór liczb naturalnych jest najmniejszym względem mocy zbiorem nieskończonym (dowód tego również nie jest prosty- wymaga aksjomatu wyboru).

Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym, niech \(\displaystyle{ a \in X. }\) Zauważmy, że zbiór \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony (w przeciwnym razie \(\displaystyle{ X}\) jako suma zbioru skończonego i jednoelementowego byłby skończony- sprzeczność). Ponieważ zbiór \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony, a zbiór liczb naturalnych \(\displaystyle{ \NN}\) jest najmniejszym zbiorem nieskończonym, to \(\displaystyle{ \left| \NN\right| \le \left| X \setminus \left\{ a\right\} \right| }\). A zatem istnieje funkcja różnowartościowa \(\displaystyle{ f:\NN \rightarrow X \setminus \left\{ a\right\} }\). Rozważmy zbiór wartości tej funkcji \(\displaystyle{ f_P}\). Funkcja \(\displaystyle{ f}\) jest różnowartościowa i 'na' zbiór wartości \(\displaystyle{ f_P}\), zatem jest bijekcją między \(\displaystyle{ \NN}\) a \(\displaystyle{ f_P}\). A zatem zbiór \(\displaystyle{ f_P}\) jest równoliczny z \(\displaystyle{ \NN}\) czyli jest przeliczalny, oznaczmy go jako \(\displaystyle{ B}\). Teraz należy rozważyć nową funkcję \(\displaystyle{ g: X \rightarrow X \setminus \left\{ a\right\} }\), która elementowi \(\displaystyle{ a}\) przypisuje \(\displaystyle{ f_0 \in X \setminus \left\{ a\right\}}\), \(\displaystyle{ f(0)}\) przesuwa na \(\displaystyle{ f(1)}\), \(\displaystyle{ f(1)}\) przesuwa na \(\displaystyle{ f(2)}\), ... a na pozostałych argumentach zbioru \(\displaystyle{ X}\) jest identycznością, tzn. dostając argument taki sam go zwraca. W ten sposób zbiór \(\displaystyle{ X}\) jest przekształcany na \(\displaystyle{ X \setminus \left\{ a\right\} }\).

Formalnie definiujemy funkcję \(\displaystyle{ g:X \rightarrow X \setminus \left\{ a\right\}}\) :

\(\displaystyle{ g\left( x\right)= \begin{cases} f(0), \hbox{ gdy } x=a,\\ f(n+1),\hbox{ gdy } x=f(n) \in B, \\ x, \hbox { w pozostałym przypadku.} \end{cases}}\)

Intuicyjnie jest oczywiste, że funkcja \(\displaystyle{ f_1: f(n) \rightarrow f\left( n+1\right)}\) jest bijekcją, może się nie będę nad tym rozczulał, i to zostawię Tobie. Ponieważ identyczność \(\displaystyle{ I _{X \setminus \left( B \cup \left\{ a\right\} \right) }}\) jest bijekcją (oznaczmy ją jako \(\displaystyle{ f_2}\)), ponieważ funkcja \(\displaystyle{ f_3: a \rightarrow f(0)}\) jest bijekcją, ponieważ zbiory \(\displaystyle{ X \setminus \left( B \cup \left\{ a\right\} \right) ,B,\left\{ a\right\} }\) (ich dziedziny) są rozłączne, ponieważ zbiory \(\displaystyle{ \left\{ f(0)\right\}, B \setminus \left\{ f(0)\right\} ,X \setminus \left( B \cup \left\{ a\right\} \right)}\) (ich zbiory wartości ) są rozłączne, więc ich sklejenie czyli suma \(\displaystyle{ f _{1} \cup f _{2} \cup f _{3}}\) jest bijekcją z \(\displaystyle{ X \setminus \left( B \cup \left\{ a\right\} \right) \cup B \cup \left\{ a\right\}=X}\) do \(\displaystyle{ \left\{ f(0)\right\} \cup \left( B \setminus \left\{ f(0)\right\} \right) \cup \left( X \setminus \left( B \cup \left\{ a\right\} \right)\right)=X \setminus \left\{ a\right\}. }\)

A dalej końcowe zadanie wynika stąd po przez prostą indukcję. \(\displaystyle{ \square}\)

[Jan Kraszewski]

funkcja \(\displaystyle{ f_1: f(n) \rightarrow f\left( n+1\right)}\) jest bijekcją,

A cóż to za dziwny zapis?

JK

[matmatmm]

Rozumiem, że takie rozbicie zbioru \(\displaystyle{ X}\) jest możliwe, bo przekrój zbiorów \(\displaystyle{ Y}\) oraz \(\displaystyle{ A}\) jest pusty.

Taki argument jest niedobry. Powinieneś uzasadnić istnienie zbioru \(\displaystyle{ A}\) spełniającego wszystkie żądane warunki.

Tak samo wydaje mi się, że można stworzyć odwzorowanie będące bijekcją \(\displaystyle{ f: Y \cup A \rightarrow A}\), na przykład:
\(\displaystyle{
f(x) = \left\{ \begin{array}{ll}
a_n & \textrm{dla $y_n$}\\
a_{N + k} & \textrm{dla $a_k$}\\
\end{array} \right.
}\), gdzie \(\displaystyle{ y_n \in Y}\) - bo \(\displaystyle{ Y}\) jest skończony, więc możemy sobie posortować wyrazy i oznaczyć jako \(\displaystyle{ y_1, y_2, ..., y_n}\), gdzie \(\displaystyle{ n }\) jest skończone. Analogicznie możemy tak samo oznaczyć elementy w \(\displaystyle{ A}\), przy czym indeks dolny \(\displaystyle{ a_{N + k}}\) oznacza sumę dwóch indeksów, gdzie \(\displaystyle{ N}\) jest numerem ostatniego indeksu w zbiorze \(\displaystyle{ Y}\).

Pomijając nie do końca poprawny zapis, jest to dobrze.

Tylko wciąż nie wiem, jak miałoby mi to pomóc w rozwiązaniu problemu. Będę wdzięczny za każdą pomoc w rozjaśnieniu mi tego

Niech \(\displaystyle{ f: Y \cup A \rightarrow A}\) będzie dowolną bijekcją. Definiujemy \(\displaystyle{ g:X\setminus Y\rightarrow X}\)

\(\displaystyle{ g(x)=\begin{cases}f^{-1}(x) & ,x\in A \\ x & , x\in X\setminus (Y\cup A)\end{cases}}\)

Polecam zrobić rysunek. Mnie znacznie pomógł.

[Gods_Eater]

Rozumiem, że takie rozbicie zbioru \(\displaystyle{ X}\) jest możliwe, bo przekrój zbiorów \(\displaystyle{ Y}\) oraz \(\displaystyle{ A}\) jest pusty.

Taki argument jest niedobry. Powinieneś uzasadnić istnienie zbioru \(\displaystyle{ A}\) spełniającego wszystkie żądane warunki.

Na pewno \(\displaystyle{ A}\) musi być podzbiorem zbioru \(\displaystyle{ X \setminus Y}\). To może korzystając z tego, że \(\displaystyle{ X \setminus Y}\) jest zbiorem nieskończonym, to można wybrać z niego taki podzbiór \(\displaystyle{ A}\), że jest zbiorem przeliczalnym i rozłącznym z \(\displaystyle{ Y}\)? Choć wciąż nie jestem pewny.

Tak samo wydaje mi się, że można stworzyć odwzorowanie będące bijekcją \(\displaystyle{ f: Y \cup A \rightarrow A}\), na przykład:
\(\displaystyle{
f(x) = \left\{ \begin{array}{ll}
a_n & \textrm{dla $y_n$}\\
a_{N + k} & \textrm{dla $a_k$}\\
\end{array} \right.
}\), gdzie \(\displaystyle{ y_n \in Y}\) - bo \(\displaystyle{ Y}\) jest skończony, więc możemy sobie posortować wyrazy i oznaczyć jako \(\displaystyle{ y_1, y_2, ..., y_n}\), gdzie \(\displaystyle{ n }\) jest skończone. Analogicznie możemy tak samo oznaczyć elementy w \(\displaystyle{ A}\), przy czym indeks dolny \(\displaystyle{ a_{N + k}}\) oznacza sumę dwóch indeksów, gdzie \(\displaystyle{ N}\) jest numerem ostatniego indeksu w zbiorze \(\displaystyle{ Y}\).

Pomijając nie do końca poprawny zapis, jest to dobrze.

Tak, troszkę chaotycznie. Jak można by to zapisać czytelniej?

Tylko wciąż nie wiem, jak miałoby mi to pomóc w rozwiązaniu problemu. Będę wdzięczny za każdą pomoc w rozjaśnieniu mi tego

Niech \(\displaystyle{ f: Y \cup A \rightarrow A}\) będzie dowolną bijekcją. Definiujemy \(\displaystyle{ g:X\setminus Y\rightarrow X}\)

\(\displaystyle{ g(x)=\begin{cases}f^{-1}(x) & ,x\in A \\ x & , x\in X\setminus (Y\cup A)\end{cases}}\)

Polecam zrobić rysunek. Mnie znacznie pomógł.

Tym się zaraz zajmę

[matmatmm]

Na pewno \(\displaystyle{ A}\) musi być podzbiorem zbioru \(\displaystyle{ X \setminus Y}\). To może korzystając z tego, że \(\displaystyle{ X \setminus Y}\) jest zbiorem nieskończonym, to można wybrać z niego taki podzbiór \(\displaystyle{ A}\), że jest zbiorem przeliczalnym i rozłącznym z \(\displaystyle{ Y}\)? Choć wciąż nie jestem pewny.

Tak, to dobra idea. Najpierw uzasadniamy, że \(\displaystyle{ X\setminus Y}\) jest nieskończony (gdyby był skończony, to \(\displaystyle{ X}\) byłby skończony jako suma dwóch zbiorów skończonych). Potem jedna z charakteryzacji zbiorów nieskończonych mówi, że zbiór nieskończony musi mieć podzbiór przeliczalny (tutaj ukryty jest pewnik wyboru). Wreszcie trzeba sprawdzić, że ten podzbiór przeliczalny spełnia wszystkie warunki (między innymi jest rozłączny z \(\displaystyle{ Y}\)).

Tak, troszkę chaotycznie. Jak można by to zapisać czytelniej?

Skoro \(\displaystyle{ A}\) jest przeliczalny, to istnieje ciąg różnowartościowy \(\displaystyle{ (a_n)_{n\in\NN}}\), którego obrazem jest \(\displaystyle{ A}\). Skoro \(\displaystyle{ Y}\) jest skończony, to istnieje ciąg skończony różnowartościowy \(\displaystyle{ (y_n)_{n\le N}}\)(dla pewnego \(\displaystyle{ N\in\NN}\)), którego obrazem jest \(\displaystyle{ Y}\). Wzór powinien wyglądać na przykład tak:

\(\displaystyle{
f(x) = \left\{ \begin{array}{ll}
a_n & \textrm{dla $x=y_n$}\\
a_{N + k} & \textrm{dla $x=a_k$}\\
\end{array} \right.
}\)

, przy czym poprawność tego wzoru wynika z rozłączności zbiorów \(\displaystyle{ A}\) oraz \(\displaystyle{ Y}\), a także z różnowartościowości tych ciągów.

I nie pisz, że \(\displaystyle{ n}\) jest skończone, tylko że \(\displaystyle{ n}\) jest liczbą naturalną.

[Gods_Eater]

Rozumiem i dziękuję. Spróbuję sobie użyte twierdzenia najpierw opanować, a później wrócę do zadania