Proving cardinality of sets

**xEnOn** · April 28th 2011, 11:44 AM

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:

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

**Plato** · April 28th 2011, 12:09 PM

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.

**xEnOn** · April 28th 2011, 10:08 PM

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 |$ ?

**Plato** · April 29th 2011, 02:20 AM

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.

**xEnOn** · April 29th 2011, 07:19 AM

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?

**Plato** · April 29th 2011, 07:33 AM

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~?$

**xEnOn** · April 29th 2011, 09:54 AM

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!

Thread: Proving cardinality of sets

LinkBack

Thread Tools

Display

Proving cardinality of sets

Similar Math Help Forum Discussions

[SOLVED] Cardinality of Sets and Power Sets

Cardinality of these sets!

Cardinality of Sets

Cardinality of sets Q and R

Cardinality of sets

Search Tags