Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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.

share|improve this question
1  
Is there some specific reason why you want to avoid using the Cantor–Bernstein–Schroeder Theorem? – Arthur Fischer♦ Mar 17 '12 at 11:15

3 Answers

up vote 10 down vote accepted

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.

share|improve this answer
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
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. – Carl Mar 17 '12 at 7:29
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. – 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
show 1 more comment
up vote 5 down vote

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|$.

share|improve this answer
2  
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
up vote 2 down vote

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

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.