A and B are arbitrary finite sets. I'm having trouble proving whether this claim is always true or sometimes false. If it's true what's the detailed proof that proves this statement? If not what is the counterexample?

My understanding here is that on the left side you have the cardinality of the set difference of A - B. On the right side you subtract the cardinality of both sets? Is this correct or am I missing something here?

So for example: Let A={17,18,19} and B={17,18,20} A - B gives me {19} so |A - B| is 1 Now |A| would be 3 and |B| would be 3 So 3-3 gives me 0

I think I might be misinterpreting the right side but I'm not sure. If someone can give me some clarity on the following question it would be much appreciated.

  • 1
    $\begingroup$ I think you have it right. $\endgroup$ – Robert Shore Mar 5 at 16:24
  • 1
    $\begingroup$ Your disproof is correct. $\endgroup$ – enedil Mar 5 at 16:24
  • $\begingroup$ @DonThousand That's silly. The elements of B that are not in A can't have anything to do with counting elements in A. $|A - B| = |A| - |B\cap A|$. $\endgroup$ – fleablood Mar 5 at 16:38
  • $\begingroup$ @fleablood Oops you are right, silly me $\endgroup$ – Don Thousand Mar 5 at 16:39

Your counter example is great.

Think of it this way.

There are elements in $A$ and not $B$. Elements in $B$ and not $A$ and elements in both. (And elements in neither.)

To count elements that are only in $A$, the elements in $B$ that are not in $A$ can't have anything to do with this and there could be gazillions (on none) elements in $B$ that are not in $A$ and they will have nothing to do with calculating $|A\setminus B|$.

... in fact you consider the three disjoint and distinct sets that "make up" $A$ and $B$:

$A\setminus B, B\setminus A, A \cap B$

it becomes clear:

$|A| = |A\setminus B| + |A \cap B|$

$|B| = |B\setminus A| + |A\cap B|$.

And that makes $|A\setminus B| =|A| - |A\cap B|$ so the equation is only true if $A\cap B = B$, or in other words only if $B \subset A$.

We can take this further.

$|A\setminus B| = |A| - |A\cap B| = |A| -(|B| - | B\setminus A|)$.

So $|A| \ge |A\setminus B| \ge |A| - |B|$.

$|A| = |A\setminus B|$ if and only if $A$ and $B$ are disjoint. (i.e. If $A\cap B=\emptyset$ or if $B\setminus A=B$)

$|A\setminus B| = |A| - |B|$ if and only if $B$ is a subset of $A$. (i.e. if $A\cap B = B$ or if $B\setminus A = \emptyset$)


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.