1
$\begingroup$

Please check whether my proof has any error! Thank you so much!

Theorem:

If $f:A\to B\subseteq A$ is injective, then there exists a bijection $h:A\to B$.

Proof:

Let $Y=A \setminus B$, and $X=\bigcup_{i\in \mathbb{N}}f^i(Y)$ where $ f^i(Y)=f(f(...f(Y)...)), i$ times.

$f(X)=f(\bigcup_{i \in \mathbb{N}}f^i(Y))=\bigcup_{i \in \mathbb{N}}f(f^i(Y))=\bigcup_{i \geq1}f^i(Y)$.

$X=\bigcup_{i \in \mathbb{N}}f^i(Y) = f^0(Y) \cup (\bigcup_{i \geq1}f^i(Y))=Y \cup (\bigcup_{i \geq1}f^i(Y))=Y \cup f(X)$.

To sum sup, $X=Y \cup f(X)$.

$A \setminus X=(Y\cup B) \setminus (Y\cup f(X))=B \setminus f(X)$.

We define $h:A\to B$ such that $h(x)=f(x)$ for all $x \in X$, and $h(x)=x$ for all $x \in A \setminus X$, then $h$ is bijective.

$\endgroup$
5
  • $\begingroup$ Compare with math.stackexchange.com/questions/1877323/… $\endgroup$ – Robert Z Apr 13 '18 at 5:28
  • $\begingroup$ @RobertZ I'm still unable to figure out why the OP in that link need to prove $X$ is a union of disjoint sets. Could you please explain this difference? $\endgroup$ – LE Anh Dung Apr 13 '18 at 8:42
  • $\begingroup$ Your final $h$ is a bijection from $A$ to $B$ iff $f$ is injective in $X$ (trivial) and $f(X)=B\setminus (A\setminus X)$. If you show it your proof is fine. $\endgroup$ – Robert Z Apr 13 '18 at 11:30
  • $\begingroup$ Did you mean that I used $(Y\cup B) \setminus (Y\cup f(X))=B \setminus f(X)$ without giving proof for this identity? If so, here is my proof for that identity: $(Y\cup B) \setminus (Y\cup f(X))=((Y\cup B) \setminus Y) \cap ((Y\cup B) \setminus f(X))=B \cap ((Y\cup B) \setminus f(X))=(B \cap (Y\cup B)) \setminus f(X)=(B \cap A) \setminus f(X)=B\setminus f(X)$. $\endgroup$ – LE Anh Dung Apr 13 '18 at 12:58
  • $\begingroup$ @RobertZ, I have presented a detail proof here math.stackexchange.com/questions/2735694/…, can you have a look at it and give some comments? $\endgroup$ – LE Anh Dung Apr 15 '18 at 4:57
0
$\begingroup$

Since $f:A \to B$ is injective, this implies that $|A| \leq |B|$. Now, since $B \subset A$, this implies that $|B| \leq |A|$. Combining these two inequalities, we have that $|A| =|B|$. Then, since $f$ is an injection, it is also a surjection and hence a bijection.

$\endgroup$
6
  • $\begingroup$ Do look at the pigeonhole principle! $\endgroup$ – A.Asad Apr 13 '18 at 7:11
  • $\begingroup$ The OP is trying to prove a theorem that implies the Cantor-Schröder-Bernstein theorem, so using it doesn't help. $\endgroup$ – egreg Apr 13 '18 at 7:21
  • $\begingroup$ @egreg, That's what I'm trying to do. Did you see any error in my proof? $\endgroup$ – LE Anh Dung Apr 13 '18 at 8:43
  • 2
    $\begingroup$ The Cantor–Bernstein theorem is the way to prove that $|A|\leq|B|$ and $|B|\leq|A|$ implies $|A|=|B|$. So as remarked by @egreg, this is entirely unhelpful as it would be circular. Unless, of course, you have a better way of proving that $\leq$ is antisymmetric on the cardinals. $\endgroup$ – Asaf Karagila Apr 13 '18 at 11:04
  • $\begingroup$ @AsafKaragila, could you please give a comment on the correctness of my proof? $\endgroup$ – LE Anh Dung Apr 13 '18 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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