# Proving cardinality of sets

• Apr 28th 2011, 12:44 PM
xEnOn
Proving cardinality of sets
Given that sets A, B, C are subsets of a finite set S prove that
$\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:
$Let \; x\in A\cup B\cup \bar{C}$
$\Rightarrow x\in A \; or \; x\in B \; or \; x\notin C$

Then I list out all the possible cases:
http://quicklatex.com/cache3/ql_c87e...40afa14_l3.png

Since in all the cases, the cardinality are equal to 1, can I say that hence the theorem is proven?
• Apr 28th 2011, 01:09 PM
Plato
Quote:

Originally Posted by xEnOn
Given that sets A, B, C are subsets of a finite set S prove that
$\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.
$|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:
$|\overline{C}|=|S|-|C|$
$|A\cap\overline{C}|=|A|-|A\cap C|$
$|B\cap\overline{C}|=|B|-|B\cap C|$
$|A\cap B\cap\overline{C}|=|A\cap B|-|A\cap B\cap C|$
Substitute.
• Apr 28th 2011, 11:08 PM
xEnOn
I suddenly got confused at one part.
Is $\left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
Because it feels like $A\cup B$ is already part of $\bar{C}$, ie: $(A\cup B) \subseteq \bar{C}$
Then so $\left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
• Apr 29th 2011, 03:20 AM
Plato
Quote:

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

$(A\cup B) \subseteq \overline{C}$, this true only if $(A\cup B)\cap C=\emptyset$.
Otherwise, it is not true.
• Apr 29th 2011, 08:19 AM
xEnOn
Quote:

Originally Posted by Plato
$(A\cup B) \subseteq \overline{C}$, this true only if $(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 $\overline{C}$, isn't it?
• Apr 29th 2011, 08:33 AM
Plato
Quote:

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 $\overline{C}$, isn't it?

$\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 $(A\cup B)\subseteq \overline C~?$
• Apr 29th 2011, 10:54 AM
xEnOn
Quote:

Originally Posted by Plato
$\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 $(A\cup B)\subseteq \overline C~?$

oh you are right! Maybe it is more appropriate to say $((A \cup B)\cap \overline{C})\subseteq \overline{C}$. Thanks!