0
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ If $A$ and $B$ are disjoint and $B\subset A$, then $B=\emptyset$... $\endgroup$
    – sranthrop
    Sep 9, 2015 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, 2015 at 16:13
  • $\begingroup$ excuse me, i edited that $\endgroup$
    – Ariel Marcelo Pardo
    Sep 9, 2015 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, 2015 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, 2015 at 16:21

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\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, 2015 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, 2015 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .