# If $B\subset A$ and the exist a injection $A\rightarrow B$, then $A$ and $B$ has same cardinality?

By using the definition, the cardinality is the same iff there is a bijection. So if $B\subset A$ and the exist a injection $f\colon A\rightarrow B$, then $A$ and $B$ has same cardinality.

-
You can prove this without and prior to CBS Theorem. See math.ucsd.edu/~wgarner/reference/math109_wi08/…. –  Law Area 51 Proposal - Commit Oct 30 '13 at 14:19

If $B \subset A$ then there exists an injection $g : B \to A$ defined in the natural way (identity). By existence of $g$ and the injection $f : A \to B,$ invoke Cantor–Bernstein–Schroeder theorem then there exist a bijection $h : A \to B.$ Hence $A$ and $B$ has the same cardinality.

-
is it possible to prove with the definition ,the cardinality is the same iff there is a bijection –  Mathematics Mar 17 '12 at 7:25
That's what I did. $B \subset A \implies$ existence of injection $g : A \to B.$ Existence of both $g : A \to B$ and $h : A \to B$ will give us bijection (by C-B-S theorem.) Once we have the bijection, we get the same cardinality statement proven. –  user2468 Mar 17 '12 at 7:27
@Mathematics It is not. The problem only provides an injection, so you need to prove that that bijection exists. The proof J.D. linked is necessary in order to do that. –  Carl Mar 17 '12 at 7:29
@Mathematics: That's exactly what the Cantor-Schroeder-Bernstein Theorem does. It proves that if there is an injection in each direction, then there is a bijection. And the result does not even require the Axiom of Choice. –  André Nicolas Mar 17 '12 at 7:30
is it A and B must be infinite set? If it is finite, it seems that there is a problem like $B\subset A$ but there is a injective function $f: A\rightarrow B$, so where does the element say $a_0$ where $a_0\in A$ but not $\in B$ maps to. If it maps $a_0$ to some element in B say $b_0$, of course we know there always exist another $a\in A$ s.t.$f(a)=b_0$ where a not equal to $a_0$ As injection mean 1 to 1, which mean as many element in A as B is mapped to B and left some element $\in A$ but not $\in B$. –  Mathematics Mar 18 '12 at 4:13

Any attempt to prove this result without explicitly using the Cantor–Bernstein–Schroeder Theorem will, in effect, end up re-proving the aforementioned theorem.

Let us call your statement "mini-CBS": Whenever $B \subseteq A$ are sets such that there is an injection $f : A \to B$, then $\left| A \right| = \left| B \right|$.

We now prove the CBS Theorem from mini-CBS: Suppose that $X$ and $Y$ are sets, and we have injections $f: X \to Y$ and $g : Y \to X$. Consider the set $X^\prime = \{ g(y) : y \in Y \}$. Clearly, $X^\prime \subseteq X$. Note that $g$ is in fact a bijection between $Y$ and $X^\prime$, and so $\left| X^\prime \right| = \left| Y \right|$. Consider now the composition $g \circ f : X \to X^\prime$. Since $f$ and $g$ are both one-to-one, it follows that $g \circ f$ is also one-to-one. By mini-CBS it follows that $\left| X^\prime \right| = \left| X \right|$, and therefore $\left| Y \right| = \left| X \right|$.

-
In the course I TA'd during the fall semester we prove the Cantor-Bernstein theorem by first proving this mini-theorem. I think this is the cleanest proof I know of the theorem (except of course the AC based one that just take the minimal well-ordering of $A$ and $B$ and show it is the same ordinal). –  Asaf Karagila Mar 17 '12 at 10:23
@Asaf: Yeah, it's a very nice reduction, and the proof is somewhat less cluttered than the "usual" Choice-less lemma beginning with $A^\prime \subseteq B \subseteq A$ with $\left| A^\prime \right| = \left| A \right|$. (At least that is how I recall seeing it proved in virtually every place I have seen a proof.) –  Arthur Fischer Mar 17 '12 at 11:13
Now, there is a question, is it necessary for A and B to be infinite set? –  Mathematics Mar 18 '12 at 4:06
you can refer what i ask in the comment to Andre –  Mathematics Mar 18 '12 at 4:16
@Mathematics: The proof would not depend on whether the sets A and B are finite or infinite. Of course, if $A$ is a proper subset of $B$ and there is an injection $f : B \to A$, this means that $B$ is Dedekind infinite. Without the Axiom of Choice we can show that all Dedekind infinite sets are infinite (meaning not equinumerous with any $\{ 0, \ldots , n-1 \}$), but the Axiom of Choice is required to show the converse, that every infinite set is Dedekind infinite. –  Arthur Fischer Mar 18 '12 at 5:16

Yes that's right. $B\subset A$ implies that $|B|\le |A|$. The injection forces $|A|\le|B|$. Therefore they have the same cardinality.

-
is it possible to prove with the definition ,the cardinality is the same iff there is a bijection –  Mathematics Mar 17 '12 at 7:21
My answer does that without explicitly saying so. The fact that $|B|\le|A|$ and $|A|\le |B|$ implies $|A|= |B|$ is just another way to state the CBS Theorem, and $|A| = |B|$ is just shorthand for "there is a bijection from $A$ to $B$ ". –  Patrick Mar 17 '12 at 20:23