# Thread: Proving cardinality of sets

1. ## Proving cardinality of sets

Given that sets A, B, C are subsets of a finite set S prove that
$\displaystyle \left | A\cup B\cup \bar{C} \right | =\left | S \right | -\left | C \right |+\left | A\cap C \right | +\left | B\cap C \right | -\left | A\cap B\cap C \right |$

So I started of throwing a dummy element into the sets that I will keep track of:
$\displaystyle Let \; x\in A\cup B\cup \bar{C}$
$\displaystyle \Rightarrow x\in A \; or \; x\in B \; or \; x\notin C$

Then I list out all the possible cases:

Since in all the cases, the cardinality are equal to 1, can I say that hence the theorem is proven?

2. Originally Posted by xEnOn
Given that sets A, B, C are subsets of a finite set S prove that
$\displaystyle \left | A\cup B\cup \bar{C} \right | =\left | S \right | -\left | C \right |+\left | A\cap C \right | +\left | B\cap C \right | -\left | A\cap B\cap C \right |$
I would start out with this.
$\displaystyle |A\cup B\cup\overline{C}|=|A|+|B|+|\overline{C}|-|A\cap B|-|A\cap\overline{C}|-|B\cap\overline{C}|+|A\cap B\cap\overline{C}|$
Then note four facts:
$\displaystyle |\overline{C}|=|S|-|C|$
$\displaystyle |A\cap\overline{C}|=|A|-|A\cap C|$
$\displaystyle |B\cap\overline{C}|=|B|-|B\cap C|$
$\displaystyle |A\cap B\cap\overline{C}|=|A\cap B|-|A\cap B\cap C|$
Substitute.

3. I suddenly got confused at one part.
Is $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
Because it feels like $\displaystyle A\cup B$ is already part of $\displaystyle \bar{C}$, ie: $\displaystyle (A\cup B) \subseteq \bar{C}$
Then so $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?

4. Originally Posted by xEnOn
I suddenly got confused at one part.
Is $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
Because it feels like $\displaystyle A\cup B$ is already part of $\displaystyle \bar{C}$, ie: $\displaystyle (A\cup B) \subseteq \bar{C}$
Then so $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
$\displaystyle (A\cup B) \subseteq \overline{C}$, this true only if $\displaystyle (A\cup B)\cap C=\emptyset$.
Otherwise, it is not true.

5. Originally Posted by Plato
$\displaystyle (A\cup B) \subseteq \overline{C}$, this true only if $\displaystyle (A\cup B)\cap C=\emptyset$.
Otherwise, it is not true.
Why is it true only if it is an empty set?
Any elements in A or in B or in both or somewhere in the universal set outside of C, as long as it is not in C, it is considered $\displaystyle \overline{C}$, isn't it?

6. Originally Posted by xEnOn
Why is it true only if it is an empty set?
Any elements in A or in B or in both or somewhere in the universal set outside of C, as long as it is not in C, it is considered $\displaystyle \overline{C}$, isn't it?
$\displaystyle \begin{gathered} S = \left\{ {0,1,2,3,4,5,6,7,8,9} \right\} \hfill \\ A = \left\{ {0,1,2,3,4} \right\} \hfill \\ B = \left\{ {1,3,5,7,9} \right\} \hfill \\ C = \left\{ {4,5,6,7} \right\}\;\& \;\overline C = \left\{ {0,1,2,3,8,9} \right\} \hfill \\ \end{gathered}$
Now is $\displaystyle (A\cup B)\subseteq \overline C~?$

7. Originally Posted by Plato
$\displaystyle \begin{gathered} S = \left\{ {0,1,2,3,4,5,6,7,8,9} \right\} \hfill \\ A = \left\{ {0,1,2,3,4} \right\} \hfill \\ B = \left\{ {1,3,5,7,9} \right\} \hfill \\ C = \left\{ {4,5,6,7} \right\}\;\& \;\overline C = \left\{ {0,1,2,3,8,9} \right\} \hfill \\ \end{gathered}$
Now is $\displaystyle (A\cup B)\subseteq \overline C~?$
oh you are right! Maybe it is more appropriate to say $\displaystyle ((A \cup B)\cap \overline{C})\subseteq \overline{C}$. Thanks!