Let $A$ and $B$ non-empty sets, A is infinite and B is countably infinite($\sim \mathbb{N}$). Prove that if A is not countably infinite and $B\subseteq A$, then exists a bijection between $A\setminus B$ and $A$.

I thought that i can use Schröder–Bernstein theorem, so i defined two injective function: $id:A\setminus B \rightarrow A $ and $id:A\rightarrow A\setminus B$ ($id$ identity function) Is that conclude that there is a a bijection between $A\setminus B$ and $A$? Thanks in advance.

  • 1
    $\begingroup$ If $A$ and $B$ are disjoint and $B\subset A$, then $B=\emptyset$... $\endgroup$ – sranthrop Sep 9 '15 at 16:12
  • 1
    $\begingroup$ You may need the axiom of choice as described in an earlier question math.stackexchange.com/questions/46168/… $\endgroup$ – Henry Sep 9 '15 at 16:13
  • $\begingroup$ excuse me, i edited that $\endgroup$ – Ariel Marcelo Pardo Sep 9 '15 at 16:16
  • 2
    $\begingroup$ id :$ A \to A \setminus B$ is not even a function. for $x\in B$, $id(x)=x\notin A \setminus B$ $\endgroup$ – Terence Hang Sep 9 '15 at 16:21
  • 1
    $\begingroup$ @ArielMarceloPardo What is the identity function $A \to A\setminus B$? That doesn't make any sense. $\endgroup$ – user223391 Sep 9 '15 at 16:21

The assertion you want to prove is equivalent (in ZF) to the assertion that every infinite set has a countably infinite subset, an easy consequence of the axiom of choice which can't be proved in ZF.

First, suppose there is an infinite set $D$ with no countably infinite subset. Let $A=\mathbb N\cup D$ and let $B=\mathbb N.$ Then $A$ is uncountably infinite, $B$ is a countably infinite subset of $A$, but there is no injection from $B$ to $A\setminus B$ since $A\setminus B\subseteq D.$

Now, assume that every infinite set has a countably infinite subset. Suppose $A$ is an uncountably infinite set, and $B$ is a countable subset of $A.$ Then $A\setminus B$ is an infinite set (else $A$ would be countable), whence there is a countably infinite set $C\subseteq A\setminus B$. Now, writing $+$ for disjoint union, we have $$A=[A\setminus(B\cup C)]+(B\cup C)$$ and $$A\setminus B=[A\setminus(B\cup C)]+C.$$ Then $B\cup C$ is countably infinite, so there is a bijection from $B\cup C$ to $C,$ which can be extended to a bijection from $A$ to $A\setminus B.$

  • $\begingroup$ Shall we prove also that $A\setminus B$ is an infinite set? i understand that, but i don't know that if we have to prove that also. $\endgroup$ – Ariel Marcelo Pardo Sep 11 '15 at 14:40
  • $\begingroup$ Yes, of course. $A\setminus B$ must be infinite because, if it were finite, then $A=B\cup(A\setminus B)$ would be the union of a countable set and a finite set, and therefore countable. $\endgroup$ – bof Sep 11 '15 at 19:48

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.