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.
If $B\subset A$ and the exist a injection $A\rightarrow B$, then $A$ and $B$ has same cardinality?
-
0You can prove this without and prior to CBS Theorem. See http://math.ucsd.edu/~wgarner/reference/math109_wi08/bernstein_schroeder_theorem.pdf. – 2013-10-30
3 Answers
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.
-
0@Mathematics in the finite case, you should use $B \subseteq A$ rather than proper $\subset$. – 2012-03-20
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|$.
-
0@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](http://en.wikipedia.org/wiki/Dedekind-infinite_set). 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. – 2012-03-18
Yes that's right. $B\subset A$ implies that $|B|\le |A|$. The injection forces $|A|\le|B|$. Therefore they have the same cardinality.
-
1My 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$ ". – 2012-03-17