6
$\begingroup$

I need to prove this $|A-B|=|B-A|\rightarrow|A|=|B|$ I managed to come up with this:

let $f:A-B\to B-A$ while $f$ is bijective.

then define $g\colon A\to B$ as follows: $g(x)=\begin{cases} f(x)& x\in (A-B) \\ x& \text{otherwise} \\ \end{cases}$

but I'm not managing to prove this function is surjective.

Is it not? or am I on the right path? if so how do I prove it?

Thanks

  • 0
    Note that the "otherwise" case is precisely the case that $x \in A \cap B$. Now to show $g$ is surjective, note that for any $y \in B$, either $y \in B - A$ or $y \in A \cap B$. In each case, find an $x$ with $g(x) = y$.2011-08-14

2 Answers 2

10

Your basic intuition is correct.

First prove that $g$ is injective.

Suppose $x,y\in A$ and $x\neq y$. Let us break this into four cases (two similar):

  1. If $x\in B$ and $y\notin B$ (or vice versa) then $g(x)=x$ while $g(y)=f(y)\notin A$, therefore $g(x)\neq g(y)$.

  2. If $x,y\in B$ then $f(x)\neq f(y)$ since $f$ is injective, and therefore $g(x)\neq g(y)$.

  3. Similarly for $x,y\notin B$, we have that $g(x)=x\neq y=g(y)$.

Therefore $g$ is an injective function.

To show $g$ is surjective, pick $x\in B$.

Either $x\in A$ and therefore $g^{-1}(x)=x$, or $x\notin A$ and therefore $f^{-1}(x)=a$ is defined; $a\in A\setminus B$; and $g(a)=f(a)=x$ as needed.

  • 0
    @Jason: You just ask questions I am very familiar with the answers for. Thanks though :-)2011-08-14
8

Note that

$\begin{align} |A| = |A \cap B| + |A \cap B^c| = |B \cap A| + |B \cap A^c| = |B|. \end{align}$

Here $E^c$ denotes the compliment of the event $E$ in the universal space $X$.

  • 2
    @Jason, DJC: This solution works for infinite sets as well. For better clarity replace $|A\cap B^c|$ with $|A\setminus B|$ (and similarly with $A^c$), and this will also take care of the case you're working in a setting where no universal set is given (although it is not very hard to produce one).2011-08-14