0
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2016 at 0:23

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ what do the w refer to ? is it the initial segment ? $\endgroup$
    – TedMosby
    Oct 26, 2016 at 22:23
  • $\begingroup$ Also, don't we require f and g to be injections in this case ? $\endgroup$
    – TedMosby
    Oct 26, 2016 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, 2016 at 22:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .