# prove cardinality rule $|A-B|=|B-A|\rightarrow|A|=|B|$

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

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

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.

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

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

-
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 :) – Jason Aug 14 '11 at 19:05
@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). – Asaf Karagila Aug 14 '11 at 19:34