Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

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|improve this answer
1  
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|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
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). –  Asaf Karagila Aug 14 '11 at 19:34

Your Answer

 
discard

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.