# Thread: Prove Cardinality of the sets

1. ## Prove Cardinality of the sets

Show that if A, B, and C are sets, then $\left|{A \cup B \cup C}\right|$= $\left|{A}\right|$ + $\left|{B}\right|$ + $\left|{C}\right|$ - $\left|{A \cap B}\right|$ - $\left|{A \cap C}\right|$ - $\left|{B \cap C}\right|$ + $\left|{A \cap B \cap C}\right|$.

So i know that $\left|{A \cup B}\right|$ = $\left|{A}\right|$ + $\left|{B}\right|$ - $\left|{A \cap B}\right|$. But i have no idea how to get to that final form

2. Originally Posted by bfpri
Show that if A, B, and C are sets, then $\left|{A \cup B \cup C}\right|$= $\left|{A}\right|$ + $\left|{B}\right|$ + $\left|{C}\right|$ - $\left|{A \cap B}\right|$ - $\left|{A \cap C}\right|$ - $\left|{B \cap C}\right|$ + $\left|{A \cap B \cap C}\right|$.

So i know that $\left|{A \cup B}\right|$ = $\left|{A}\right|$ + $\left|{B}\right|$ - $\left|{A \cap B}\right|$. But i have no idea how to get to that final form
Inclusion exclusion principle?

Or $\text{card}A\cup B\cup C=\text{card }A\cup\left(B\cup C\right)=\text{card }A+\text{card }B\cup C-\text{card }A\cap (B\cup C)$. Go from there?

3. $\left|{A \cup B \cup C}\right|$= $\left|{A}\right|$ + $\left|{B \cup C}\right|$ - $\left|{A \cap (B \cup c)}\right|$
= $\left|{A}\right|$ + $\left|{B }\right|$ + $\left|{C}\right|$ - $\left|{B \cap C }\right|$- $\left|{A \cap (B \cup C) }\right|$
= $\left|{A}\right|$ + $\left|{B }\right|$ + $\left|{C}\right|$ - $\left|{B \cap C }\right|$- $\left|{(A \cap B) \cup (A \cap C) }\right|$
= $\left|{A}\right|$ + $\left|{B }\right|$ + $\left|{C}\right|$ - $\left|{B \cap C }\right|$-( $\left|{A \cap B}\right|$ + $\left|{A \cap C}\right|$- $\left|{A \cap B \cup (A \cap C)}\right|)$

I think there is a parenthesis on the second half of the last line right? so that it distributes and makes $\left|{A \cap B \cup (A \cap C)}\right|$ positive? Then I know $\left|{A \cap B \cup (A \cap C)}\right|$ is equal to $\left|{A \cap B \cap C}\right|$ But i'm not sure how to prove it..

thanks for the help

4. Originally Posted by bfpri
Then I know $\left|{A \cap B \cup (A \cap C)}\right|$ is equal to $\left|{A \cap B \cap C}\right|$ But i'm not sure how to prove it..

thanks for the help
Do you know the distributive laws of union/intersection?

5. Originally Posted by Drexel28
Do you know the distributive laws of union/intersection?
Yes, but I'm not sure how to apply it to that.. btw i left out a parenthesis..it should be $\left|{(A \cap B) \cup (A \cap C)}\right|$. For the distributive laws i know that $A \cup (B \cap C)$= $(A \cup B) \cap (A \cup C)$. Is that what you're talking about?

6. Originally Posted by bfpri
For the distributive laws i know that $A \cup (B \cap C)$= $(A \cup B) \cap (A \cup C)$. Is that what you're talking about?
Indeed, obviously. But, you can do this for any set (intersection of sets, union of sets, etc.). Particularly, $\left(A\cap B\right)\cup\left(A\cap C\right)=\left(A\cup\left(A\cap C\right)\right)\cap\left(B\cup\left(A\cap C\right)\right)$

7. Originally Posted by Drexel28
Indeed, obviously. But, you can do this for any set (intersection of sets, union of sets, etc.). Particularly, $\left(A\cap B\right)\cup\left(A\cap C\right)=\left(A\cup\left(A\cap C\right)\right)\cap\left(B\cup\left(A\cap C\right)\right)$
Crap I meant $\left(A\cap B\right)\cap\left(A\cap C\right)$. that would be $\left(A\cap\left(A\cap C\right)\right)\cap\left(B\cap\left(A\cap C\right)\right)$right?

8. Originally Posted by bfpri
Crap I meant $\left(A\cap B\right)\cap\left(A\cap C\right)$. that would be $\left(A\cap\left(A\cap C\right)\right)\cap\left(B\cap\left(A\cap C\right)\right)$right?
Yezzir.

9. Originally Posted by Drexel28
Yezzir.
Wow, I just realized thats a heckuva lot of distributions I have to do to get $\left|{A \cap B \cap C}\right|$ . Maybe i should just say.."Because of the distributive laws $\left|{A \cap B \cup (A \cap C)}\right|$ = $\left|{A \cap B \cap C}\right|$.

10. Originally Posted by bfpri
Wow, I just realized thats a heckuva lot of distributions I have to do to get $\left|{A \cap B \cap C}\right|$ . Maybe i should just say.."Because of the distributive laws $\left|{A \cap B \cup (A \cap C)}\right|$ = $\left|{A \cap B \cap C}\right|$.
Haha! If it's right. To be one-hundred percent honest with you I haven't checked. In fact it isn't correct!

$A\cap \varnothing\cap C=\varnothing\ne \left(A\cap\varnothing\right)\cup\left(A\cap C\right)=A\cap C$

11. whoops can you check $\left(A\cap B\right)\cap\left(A\cap C\right)
$
.. I copied it wrong..again

12. Originally Posted by bfpri
whoops can you check $\left(A\cap B\right)\cap\left(A\cap C\right)
$
.. I copied it wrong..again
Oh, you! haha. Well in that case it's trivially true since the intersection operator is associative, commutative, and $A\cap A=A$

13. Alright, Thanks!