Hi I have been stuck on the following problem for quite some time now I don't find the trick to solve it. Any help would be much appreciated.

Let $f:A\to B$ and $g:B\to A$ be arbitrary functions. Show that there are subsets $A_1,A_2\subseteq A$ and $B_1,B_2\subseteq B$ such that $A_1\cup A_2=A$, $A_1\cap A_2=\varnothing$, $B_1\cup B_2=B$, $B_1\cap B_2=\varnothing$, and $$f(A_1)=B_1,\qquad g(B_2)=A_2\;.$$ Use this to give an alternative proof of the Cantor-Schröder-Bernstein theorem.

  • $\begingroup$ Start by experimenting with small sets $A, B$. (Say, $A = \{a, b, c\}$ and $B = \{1, 2\}$.) Then go on to larger finite ones, then try familiar infinite ones (say, the integers). $\endgroup$ – user8960 Oct 25 '16 at 0:23

The sets in this answer are called $X$ and $Y$ rather than $A$ and $B$; mentally rename them to $A$ and $B$, respectively. Then, using the notation in that answer for the subsets of $A$ and $B$, you can take

$$\begin{align*} A_1&=X_\omega\cup\bigcup_{n\in\Bbb N}X_{2n}\;,\\ B_1&=Y_\omega\cup\bigcup_{n\in\Bbb N}Y_{2n+1}\;,\\ A_2&=\bigcup_{n\in\Bbb N}X_{2n+1}\;,\text{ and}\\ B_2&=\bigcup_{n\in\Bbb N}Y_{2n}\;; \end{align*}$$

I’ll leave it to you to check that this really does work and to show how to use it to get a bijection from $A$ to $B$ when $f$ and $g$ are injections.

  • $\begingroup$ what do the w refer to ? is it the initial segment ? $\endgroup$ – TedMosby Oct 26 '16 at 22:23
  • $\begingroup$ Also, don't we require f and g to be injections in this case ? $\endgroup$ – TedMosby Oct 26 '16 at 22:24
  • $\begingroup$ @TeddyRoze: It’s an omega, not a w, and in this particular argument it’s really just a subscript used to identify a specific subset of $A$ and a specific subset of $B$; those subsets are defined in the other answer. \\ No, the result in this question is for arbitrary $f$ and $g$. When this result is subsequently used to prove the C-S-B theorem it will be applied to injections, but this result itself does not require that. $\endgroup$ – Brian M. Scott Oct 26 '16 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.