# Set Theory — Cardinality & Power Sets

### Part III — The Intuition Responsible For Allocation Decisions

January 29, 2019

Code & Design With basic notation & operations cleared in articles one & two in this series, we’ve now built a fundamental understanding of Set Theory. This third article further compounds this knowledge by zoning in on the most important property of any given set: the total number of unique elements it contains.

Also known as the cardinality, the number of distinct elements within a set provides a foundational jump-off point for further, richer analysis of a given set. For one, the cardinality is the first unique property we’ve seen that allows us to objectively compare different types of sets — checking if there exists a bijection (fancy term for function with slight qualifiers) from one set to another. Another form of application, as well as the topic for the remainder of this piece, the cardinality provides a window to all possible subsets that exist within a given set. Which quite literally translates to everyday decision allocation problems such as budgeting a grocery trip or balancing a portfolio.

The example to the left (above on mobile) depicts five separate sets with their respective cardinality to the right. As seen, the symbol for the cardinality of a set resembles the absolute value symbol — a variable sandwiched between two vertical lines. The examples are clear, except for perhaps the last row, which highlights the fact that only unique elements within a set contribute to the cardinality.

Remember subsets from the preceding article? It turns out that the cardinality of some set A & the number of possible subsets from set A have a fascinating relationship. Detailed below, the number of subsets that can be constructed from some subset increases with the order of cardinality by a predictable amount:

# of Possible Subsets in C= |C|²

We’ll walk-through an example below. However, let’s first take a moment to reflect on the intuition of the formula above. Imagine the cardinality as the total number of “slots” a set represents. When constructing some subset, a Boolean (yes/no) decision is made on every possible “slot.” Which means that every unique element added to a set (aka increasing the cardinality by one) increases the number of possible subsets by a factor of two. As a programmer or computer scientist, you might appreciate this logic a bit more once you realize that all subsets of a given set can be calculated using a table of purely binary numbers.

# The Power Set

Before we derive all the subsets for the example set C above, I’d like to introduce one last term — the power set. Notated with a capital S followed by a parenthesis containing the original set S(C), the power set is the set of all subsets of C, including the empty/null set & the set C itself. The table below demonstrates the power set S(C) with all the varying permutations of possible subsets for the set C contained within one large set.