How to prove that |A∪B|+|A∩B| = |A|+|B|.

[yangbin990]

Hi,

I am teaching myself the discrete math using the "Discrete Mathematics
Lecture Notes, Yale University, Spring 1999".

And I don't how to prove the practice question below:
Prove that |A∪B|+|A∩B| = |A|+|B|.

The textbook provide answer like below:
The common elements of A and B are counted twice on both sides; the elements in
either A or B but not both are counted once on both sides.

But I think it may be some mathematical way to prove that.

If someone can give me a hand that will be very appreciated.

 

[Office_Shredder]

That sounds like a pretty mathematical answer to me.

 

[Stephen Tashi]

But I think it may be some mathematical way to prove that.

Is your idea of a "mathematical way" to have a series of symbolic manipulations? If so, you are misguided. Mathematical proofs are often given using words.

Let's assume you know that proofs use words. There are various levels of "rigor" in math and you are correct that a more rigorous proof could be given. Whether it ought to be given depends on the audience for the proof. When you do self-study then you are the audience. When a proof doesn't convince you, you can seek a more rigorous proof or you can try harder to take the point of view of the proof that was given. Both methods are useful.

For the theorem you gave, it isn't easy to write a more rigorous proof! The book's short remark implies it is reasoning about the results produced by two processes of counting.

The process for the left hand side (LHS) of the alleged equation is: Count the elements in $A \cup B$, count the element in $A \cap B$ and add these two counts.

The process for the right side (RHS) of the alledged equation is count the elements in $A$ , count the elements in $B$ and add these two counts.


A sketch of a proof (to my personal standard of rigor) would be:.

Let x be an element. There are two possibilities for x's membership in each set, making 4 possibilities for its joint membership in the two sets. These are:

Case 1) x is in A and x is in B
Case 2) x is in A and x is not in B
Case 3) x iis not in A and x is in B
Case 4) x is not in A and x is not in B

In Case 1) , the LHS process counts x exactly 2 times. It is counted once in the count of $A\cup B$ and once in the countof $A \cap B$. The RHS counts also counts x twice. It counts x once in the count of $A$ and once in the count of $B$.

In Case 2) , the LHS process counts x exactly 1 time. It is counted in the count of $A \cup B$. The RHS process also counts x exactly 1 time in the count of $A$.

... and we'd have to deal with the other cases in a similar manner

In the end we can conclude that "if x is counted exactly k times by the LHS process then x is counted exactly k times by the RHS process" since we showed this was true in all possible cases.


Different people will have different reactions to such a proof. Many will find it unnecessarily wordy. A few may find it lacks detail! You have to determine a practical standard for yourself. Generally speaking, the "average smart math person" sets a standard for proofs that let's them read papers and books at the speed they require. Their standard usually isn't high enough to prevent them from being fooled every now and then an invalid argument. They must use discussions with other people and "peer review" keep from getting too far off course.

 

[micromass]

The proof in the OP is fine. If you think it lacks rigor, then there are more rigorous proofs. For example:

1) Lemma: If $A$ and $B$ are disjoint, then $|A\cup B| = |A| + |B|$

I will not prove this lemma. I think it is intuitively obvious and a very intuitive argument can be given. In either case, a proof depends very much on the definition of $+$ and $|~|$. In a lot of cases, this lemma is seen as an axiom. In either case, the proof of the lemma relies on the specifics of your set theory.

2) Lemma: $|B\setminus A| + |A| = |B|$
Follows immediately from the lemma. Note that $A\setminus B$ and $B$ are disjoint.

3) Theorem: $|A\cup B| + |A\cap B| = |A| + |B|$
We know that $B = (B\setminus A)\cup (A\cup B)$ and this union is disjoint. Thus
$$|A| + |B| = |A| + |B\setminus A| + |A\cup B|$$
The lemma now implies the theorem.

 

[yangbin990]

Really appreciate everyone's help, especially Stephen's explanation.

And I will spend some time to digest micromass's reply as well.