DEV Community

Samuel Kendrick
Samuel Kendrick

Posted on

The number of elements in a power set of size <= 1 is the size of the original set + 1 more element: the empty set .

Suppose ∣A∣=m|A|=m . What is the size of this set:

∣{X∈P(A)∈:∣X∣≤1}∣ | \{X \in \mathscr{P}(A) \in : |X| \leq 1 \} |

Let's start with a specific example:

∣{X∈P({1,2,3})∈:∣X∣≤1}∣ | \{X \in \mathscr{P}(\{1,2,3\}) \in : |X| \leq 1 \} |

First, let's create the power set, stopping once we hit an element whose size is greater than 1:

P({1,2,3})={∅,{1},{2},{3}} {\mathscr{P}(\{1,2,3\})} = \{\emptyset, \{1\}, \{2\}, \{3\} \}

Notice that the number of elements of size ≤1\leq 1 is the size of the original set + 1 more element: the empty set.

Thus:

∣{X∈P(A)∈:∣X∣≤1}∣=m+1 | \{X \in \mathscr{P}(A) \in : |X| \leq 1 \} | = m+1

Top comments (0)