# Thread: Prove Cardinality of the sets

1. ## Prove Cardinality of the sets

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

So i know that $\displaystyle \left|{A \cup B}\right|$ = $\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B}\right|$ - $\displaystyle \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 $\displaystyle \left|{A \cup B \cup C}\right|$=$\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B}\right|$ + $\displaystyle \left|{C}\right|$ - $\displaystyle \left|{A \cap B}\right|$ - $\displaystyle \left|{A \cap C}\right|$ - $\displaystyle \left|{B \cap C}\right|$ + $\displaystyle \left|{A \cap B \cap C}\right|$.

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

Or $\displaystyle \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. $\displaystyle \left|{A \cup B \cup C}\right|$=$\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B \cup C}\right|$ - $\displaystyle \left|{A \cap (B \cup c)}\right|$
= $\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B }\right|$ + $\displaystyle \left|{C}\right|$ - $\displaystyle \left|{B \cap C }\right|$-$\displaystyle \left|{A \cap (B \cup C) }\right|$
= $\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B }\right|$ + $\displaystyle \left|{C}\right|$ - $\displaystyle \left|{B \cap C }\right|$-$\displaystyle \left|{(A \cap B) \cup (A \cap C) }\right|$
=$\displaystyle \left|{A}\right|$ + $\displaystyle \left|{B }\right|$ + $\displaystyle \left|{C}\right|$ - $\displaystyle \left|{B \cap C }\right|$-($\displaystyle \left|{A \cap B}\right|$ + $\displaystyle \left|{A \cap C}\right|$-$\displaystyle \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 $\displaystyle \left|{A \cap B \cup (A \cap C)}\right|$ positive? Then I know $\displaystyle \left|{A \cap B \cup (A \cap C)}\right|$ is equal to $\displaystyle \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 $\displaystyle \left|{A \cap B \cup (A \cap C)}\right|$ is equal to $\displaystyle \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$\displaystyle \left|{(A \cap B) \cup (A \cap C)}\right|$. For the distributive laws i know that $\displaystyle A \cup (B \cap C)$=$\displaystyle (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 $\displaystyle A \cup (B \cap C)$=$\displaystyle (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, $\displaystyle \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, $\displaystyle \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 $\displaystyle \left(A\cap B\right)\cap\left(A\cap C\right)$. that would be $\displaystyle \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 $\displaystyle \left(A\cap B\right)\cap\left(A\cap C\right)$. that would be $\displaystyle \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 $\displaystyle \left|{A \cap B \cap C}\right|$ . Maybe i should just say.."Because of the distributive laws $\displaystyle \left|{A \cap B \cup (A \cap C)}\right|$ = $\displaystyle \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 $\displaystyle \left|{A \cap B \cap C}\right|$ . Maybe i should just say.."Because of the distributive laws $\displaystyle \left|{A \cap B \cup (A \cap C)}\right|$ = $\displaystyle \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!

$\displaystyle 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 $\displaystyle \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 $\displaystyle \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 $\displaystyle A\cap A=A$

13. Alright, Thanks!