Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 10 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.