0

Definition I use:

$A \sim B$ means $A$ is equinumerous with $B$ which means there is a $f\colon A \rightarrow B$ that is a bijection.

My goal is to prove the following,

Suppose $A \subseteq B \subseteq C$ and $A \sim C$. Prove that $B \sim C$.

I know that since I need to prove $B \sim C$, I need to show that there is some function $g\colon B \rightarrow C$ that is a bijection. From my givens, I know that since $A \sim C$ there is a bijection $h\colon A \rightarrow C$. I don't understand how to reach my goal using the givens.

Any suggestions would be much appreciated.

Hagen von Eitzen
  • 374,180
ChemDude
  • 421

3 Answers3

1

we have a map $g : C \to A$ is a bijection. So it defines an injection from $C$ to $B$. We also have the inclusion map from $B$ to $C.$ This is clearly injective.

The Schroder--Bernstein Theorem constructs a bijection from two injections going the opposite ways so you are done.

(see eg my book "Proof Patterns")

Mark Joshi
  • 5,604
0

You have an injection $B\stackrel\subseteq\to C$ and an injection $C\stackrel{h^{-1}}\to A\stackrel\subseteq \to B$. Can you take it from there?

Hagen von Eitzen
  • 374,180
  • Is Cantor-Bernstein theorem part of what the O.P. is supposed to know? – Bernard Apr 25 '15 at 21:03
  • @Bernard Not sure, but isn't the prblem claim just as strong as Cantor-Bernstein? – Hagen von Eitzen Apr 25 '15 at 21:16
  • I'm afraid. I'm not a specialist of set theory, though. – Bernard Apr 25 '15 at 21:20
  • Well, if $f\colon X\to Y$ and $g\colon Y\to X$ are injective, we can let $C=Y$, $B=f(X)$ and $A=g(Y)$. Then if the OP claim holds we conclude that $X\sim Y$. Hence indeed the claim is very equivalent to C.-B. – Hagen von Eitzen Apr 25 '15 at 21:23
  • When I teach the Schröder-Bernstein theorem in class, I first show that it follows from the statement of this problem, and then I prove this statement, because I find this proof considerably easier to visualize than the (equivalent) direct proof of Schröder-Bernstein. – Andreas Blass Apr 25 '15 at 21:52
0

We can prove it with a special case of the Knaster-Tarski theorem, which we may prove without proving the general theorem:

Claim (Knaster-Tarski): Let $B$ be a set and $\phi:\mathcal P(B)\to \mathcal P(B)$ an order-preserving map with respect to inclus:ion. Then $\phi$ has a fixed point.

In the context of the question, we'll build a a bijection from $B$ to $C$ as follows:

  • First, we define an order-preserving map $\phi$ as in the claim with: $$X\subset B \longmapsto B\smallsetminus h^{-1}(C\smallsetminus X).$$ By the above claim, there is a subset $M\subset B$ such that $ B\smallsetminus h^{-1}(C\smallsetminus M)=M$.

  • Second, define $f:B\to C$ as: $$\begin{cases} f(x)=x &\text{if}\enspace x\in M,\\f(x)=h(x)&\text{if}\enspace x\in B\smallsetminus M. \end{cases}$$ The map $f$ is well-defined since $B\smallsetminus M=h^{-1}(C\smallsetminus M)\subset A$.

  • Third, check $f$ is bijective. It is injective, because its restrictions to $M$ and $B\smallsetminus M$ are injective, and the images of these restrictions are disjoint (the image is $M$ in the first case, and $h(B\smallsetminus M)\subset C\smallsetminus M$ in the second case). It is surjective: indeed, if $y\in C$, either $y\in M$, so it is its own image, or $y\in C\smallsetminus M$, and $y=h(h^{-1}(y))=f(h^{-1}(y))$.

Proof of claim:

  • In $\mathcal P(B)$, consider the subset $\mathcal M=\{X\mid \phi(X)\subset X\}$. Then for any $X\in \mathcal M$, $\phi(X)\in \mathcal M$. Indeed, since $\phi $ is order-preserving: $$\phi(X)\subset X \Rightarrow\phi(\phi(X))\subset \phi(X). $$

  • Let $M=\bigcap\limits_{X\in\mathcal M}X$. Then $M\in \mathcal M$: by definition, $M\subset X$ for all $X\in \mathcal M$. By order-preserving, we have: $$\phi(M)\subset\phi(X)\subset X. $$ Thus $\phi(M)$ is a lower bound for $\mathcal M$. However, $M$ is the greatest lower bound, hence $\phi(M)\subset M$, which means $M\in \mathcal M$.

  • The first point then implies $\phi(M)\in \mathcal M$, so $M\subset \phi(M)$ and finally $\phi(M)=M$.

Bernard
  • 175,478
  • Thank you for this response. But this is very confusing because I'm still a beginner to proofs. – ChemDude Apr 26 '15 at 02:09
  • I know it's not easy for a beginner, but It is the only self-contained proof I'm aware of. Otherwise it is much more direct using Cantor-Bernstein theorem. Note there is a proof of Cantor-Bernstein along the same lines. – Bernard Apr 26 '15 at 07:36