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

$\endgroup$
3
  • 1
    $\begingroup$ What is the domain of $g$? What does "otherwise" mean? $\endgroup$ – user83827 Aug 14 '11 at 19:01
  • $\begingroup$ the Domain of g is A otherwise means x does not belong to (A-B) $\endgroup$ – Jason Aug 14 '11 at 19:05
  • $\begingroup$ 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$. $\endgroup$ – Nate Eldredge Aug 14 '11 at 20:37
10
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ You are the best answerer In the world :) Thanks man $\endgroup$ – Jason Aug 14 '11 at 19:20
  • $\begingroup$ @Jason: You just ask questions I am very familiar with the answers for. Thanks though :-) $\endgroup$ – Asaf Karagila Aug 14 '11 at 19:30
8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I'm not sure this holds for Infinite sets though. And I would prefer and answer that proves there is a bijective function (like my g). But thanks :) $\endgroup$ – Jason Aug 14 '11 at 19:05
  • 2
    $\begingroup$ @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). $\endgroup$ – Asaf Karagila Aug 14 '11 at 19:34

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.