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.
-
0is it possible to prove with the definition ,the cardinality is the same iff there is a bijection – 2012-03-17
-
0That'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. – 2012-03-17
-
1@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. – 2012-03-17
-
5@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. – 2012-03-17
-
0is 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$. – 2012-03-18
-
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|$.
-
2In 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). – 2012-03-17
-
0@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.) – 2012-03-17
-
0Now, there is a question, is it necessary for A and B to be infinite set? – 2012-03-18
-
0you can refer what i ask in the comment to Andre – 2012-03-18
-
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.
-
0is it possible to prove with the definition ,the cardinality is the same iff there is a bijection – 2012-03-17
-
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