5.0 Theorems based on Subsets

Theorem 1. Every set is a subset of itself.

Proof: Each element in set $A$ belongs to set $A$ itself.

i.e. $$\begin{equation} \begin{aligned} \forall \;x \in A,\;x \in A\;itself \\ \Rightarrow A \subseteq A \\\end{aligned} \end{equation} $$

Theorem 2. The null set is a subset of every set.

Proof by contradiction: Let's say that we have the empty set $\emptyset $ and a set $A$.

Based on the definition, $\emptyset $ is a not subset of $A$ if and only if there is some element in $\emptyset $ that does not belong to $A$.

This means there is some element in $\emptyset $.

But $\emptyset $ has no elements and hence it is a contradiction.

Thus,

$$\emptyset \subseteq A$$

Theorem 3. The total number of subsets of a finite set containing $n$ elements is ${2^n}$

Proof: Let $A$ be a finite set containing $n$ elements.

Let $0 \le r \le n$.

Consider those subsets of $A$ that have $r$ elements each. We know that the number of ways in which $r$ elements can be chosen out of $n$ elements is $$^n{C_r}$$

Hence the total number of subsets of $A$ is

$$\begin{equation} \begin{aligned} { = ^n}{C_0}{ + ^n}{C_1}{ + ^n}{C_2} + ......{ + ^n}{C_n} \\ = {(1 + x)^n}{\mkern 1mu} where{\mkern 1mu} x = 1 \\ = {2^n} \\\end{aligned} \end{equation} $$