Cardinality of Sets
The cardinality of a set is the number of elements in the set. The notation for this is $\vert A\vert$ where $A$ is a set to be counted.
Power Set and Bit Vectors
We use the correspondence between bit vectors and subsets: $\left\vert \textit{Pow}(A)\right\vert$ is the number of bit vectors of length $n$.
\[A\ s.t \left\vert A \right\vert = n,\ S_n = \langle\ldots\rangle\] \[B \subseteq A \rightarrow X_b = \underbrace{\left[\frac{0}{1},\ldots,\frac{0}{1}\right]}_n\]A bit vector of the set $C$ is represented by the vector $X_C$:
\[X_c=\left[\ldots\right] \rightarrow C\]This means that provided you know the set you and reconstruct a subset from the bit vector of that subset.
The Number of $n$-bit vectors in $2^n$
We prove the statement by induction
Base Case:
$n=1$
There are two bit vectors of length 1:
$\left[0\right], \left[1\right]$
$2^1=2$
Inductive Step:
Assume that the property holds for $n=m$, so the number of $m$-bit vectors is $2^m$. Now consider the set $B$ of all $(m+1)$-bit vectors. We must show that $\left\vert B\right\vert =2^{m+1}$.
We know that all elements of $B$ are bit vectors of length $m+1$:
\[\underbrace{\left[\hspace{0.5cm},\right]}_{m+1}\in B\]The first elements apart from the last one are put in a new bit vector:
\[\underbrace{\left[\ldots\right]}_m\]Given any bit vector there are only two ways of filling in the last value, with a 0 or a 1. As there are two ways of extending a bit vector then you times the bit vector by two.
\[\left\vert B \right\vert = 2 \times 2^m = 2^{m+1}\]Computing the Cardinality of a Union of Two Sets
If $A$ and $B$ are sets then:
\[\left\vert A \cup B \right\vert = \left\vert A \right\vert + \left\vert B \right\vert - \left\vert A\cap B \right\vert\]Example
Suppose there are 100 third-year students. 40 of them take the module “Sequential Algorithms” and 80 of them take the module “Multi-Agent Systems”. 25 of them took both modules. How many students took neither modules?
\[\begin{aligned} S&=\{s\in \text{Student} \vert s \text{ takes Seq. Alg.}\}\\ M&=\{s\in \text{Student} \vert s \text{ takes M. Agent Systems}\} \end{aligned}\]- $\vert \text{Students}\vert =100$
- $\vert S\vert =40$
- $\vert M\vert = 80$
- $\vert S\cap M\vert =25$
$40+80-25=95=\vert S\cup M\vert $ $\vert \sim(S\cup M)\vert =100-95=5$
Therefore, 5 students took neither as they were part of the universal set but not part of the union of the two subsets.
Computing the Cardinality of a Union of Three Sets
If $A$, $B$ and $C$ are sets then:
\[\begin{aligned} \vert A\cup B \cup C\vert &= \vert A\vert +\vert B\vert + \vert C\vert\\ &- \vert A\cap B\vert -\vert A\cap C\vert - \vert B\cap C\vert\\ &+ \vert A\cap B\cap C\vert \end{aligned}\]This and the last union are special cases of the principle of inclusion and exclusion.
Principle of Inclusion and Exclusion
Let $A_1,A_2,\ldots,A_n$ be sets.
Then:
\[\begin{aligned} \left\vert A_1\cup\ldots\cup A_n\right\vert =&\sum_{1\leq k\leq n} \left\vert A_i\right\vert -\sum_{1\leq j\leq k\leq n} \left\vert A_j \cap A_k\right\vert\\ &+\sum_{1\leq i\leq j\leq k\leq n} \left\vert A_i \cap A_j \cap A_k\right\vert\\ &-\ldots+(-1)^{n-1}\left\vert A_1\cap\ldots\cap A_n\right\vert \end{aligned}\]