# Need help with proof in elementary set theory

At the risk of stretching the patience of readers here, I will try this once more. (See: Need help with proof about Dedekind-infinite sets for my initial debacle.)

Suppose we have

1. $C \subseteq B \subseteq A$
2. Bijection $f:A\rightarrow C$
3. $\forall x (x\in A \wedge x\notin C \rightarrow \neg\exists y (y\in A \wedge f(y)=x))$ (Edit: Turns out to be redundant)

Can we prove there exists bijection $g:B\rightarrow C$?

Hopefully without invoking the convoluted machinery of the Cantor-Bernstein-Schroder proof?

• @GitGud Changed $\subset$ to $\subseteq$ if that is more commonly used. – Dan Christensen Jun 2 '13 at 19:58
• @BrianM.Scott Don't you mean $f^{-1}(y)=x$? – Dan Christensen Jun 2 '13 at 20:05
• Never mind: I misread the direction of the bijection. – Brian M. Scott Jun 2 '13 at 20:07

Condition 3 follows from 2, as the codomain of $f$ is $C$.

Now, if you have a proof that 1 and 2 imply that there is a bijection between $B$ and $C$, then you would have a proof of Cantor-Bernstein. And no one has been able to prove Cantor-Bernstein without the "convoluted machinery".

• I personally find this version of Cantor-Bernstein somewhat easier to deal with than the usual one (where you have injections of two sets into each other). The "convoluted machinery" is still pretty much the same, but my mental picture of it is somewhat simpler. – Andreas Blass Jun 2 '13 at 21:29
• OK, I can see how 3 follows from 2. So, 3 is redundant. Thanks. – Dan Christensen Jun 3 '13 at 4:08

Let me try to describe the mental picture that I mentioned in my comment to Martin Argerami's answer. (Unfortunately, I have no idea how to produce an actual picture here, so I'll have to settle for a description. I assure you the picture can be drawn more quickly than the description can be read.) Imagine $A$ as a long horizontal rectangle; imagine $A-B$ as a small sub-rectangle $A_1$ at the right end; and therefore imagine $B$ as a long (but not quite so long as $A$) subrectangle of $A$, extending from the left end of $A$ to well beyond the middle. Imagine $B-C$ as a small rectangle $B_1$ at the left end of $B$; so $C$ is a (still rather long) rectangle occupying the middle of $A$. The given bijection $f$ maps $A$ into this sub-rectangle. Let $A_2=f[A_1]$ and imagine it as occupying the right end of $C$, adjacent to $A_1$; similarly, imagine $B_2=f[B_1]$ as occupying the left end of $C$, adjacent to $B_1$; so $f[C]$ is the middle part of $C$. $A_2$ and $B_2$, being part of $C$, are mapped by $f$ into this middle part $f[C]$. Imagine $A_3=f[A_2]$ at the right end of $f[C]$, $B_3=f[B_2]$ at the left end, and $f^2[C]$ (by which I mean $f[f[C]]$) in the middle. Continue in this way with $A_n=f[A_{n-1}]$ at the right and $B_n=f[B_{n-1}]$ at the left end of $f^{n-2}[C]$, with $f^{n-1}[C]$ in the middle.

So we have, starting at the right end, the sequence of sets $A_1,A_2,\dots$, each mapped to the next by $f$; similarly, starting at the left end, we have $B_1,B_2,\dots$ each mapped to the next by $f$. In the middle, there might be some points in $\bigcap_{n\in\mathbb N}f^n[C]$.

Now we can biject $B$ to $C$ by applying $f$ to everything in the $B_n$'s (shifting each $B_n$ one step to the right) while leaving everything else ($A_n$'s and $\bigcap_{n\in\mathbb N}f^n[C]$) fixed.

I don't know what's so convoluted about the proof of the Cantor-Bernstein theorem. It's a corollary of Knaster's fixed-point theorem:

For any function $\varphi:\mathcal P(C)\rightarrow\mathcal P(C)$ such that $X\subseteq Y\subseteq C\Rightarrow\varphi(X)\subseteq\varphi(Y)$, there is a set $X\subseteq C$ such that $\varphi(X)=X$.

The proof of Knaster's theorem can't require all that much "convoluted machinery", because it was a Putnam problem in 1956 or 1957. (It must have been the easiest problem on the Putnam that year, because it's the one I solved, not on the exam but by the next day.) To prove it, just define $X=\bigcup\mathcal S$ where $\mathcal S=\bigcup\{Z:Z\subseteq\varphi(Z)\}$, and show that $\varphi(X)=X$.

To see this, note that if $Z\in\mathcal S$ then $Z\subseteq X$ and so $Z\subseteq\varphi(Z)\subseteq\varphi(X)$. Since the elements of $\mathcal S$ are subsets of $\varphi(X)$, it follows that $X=\bigcup\mathcal S\subseteq\varphi(X)$ and so $\varphi(X)\subseteq\varphi(\varphi(X))$, which means that $\varphi(X)\in\mathcal S$, whence $\varphi(X)\subseteq X$.

Now suppose that $C\subseteq B\subseteq A$ and that $f:A\rightarrow C$ is an injection. Define $\varphi:\mathcal P(C)\rightarrow\mathcal P(C)$ by setting $\varphi(X)=C\setminus f(B\setminus X)$. Seeing as $X\subseteq Y$ implies $B\setminus X\supseteq B\setminus Y$ implies $f(B\setminus X)\supseteq f(B\setminus Y)$ implies $C\setminus f(B\setminus X)\subseteq C\setminus f(B\setminus Y)$ implies $\varphi(X)\subseteq\varphi(Y)$, it follows by Knaster's theorem that $\varphi(X)=X$ for some $X\subseteq C$, i.e., $C\setminus f(B\setminus X)=X$, or in other words, $f(B\setminus X)=C\setminus X$. Thus we get a bijection $g:B\rightarrow C$ by defining $g(x)=x$ for $x\in X$ and $g(x)=f(x)$ for $x\in B\setminus X$.

• Any hints on proving $\varphi(X)=X$ in Knaster's theorem? – Dan Christensen Jun 3 '13 at 15:08