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.
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.
How is a power set useful? Well, you’ve likely used the intuition behind power sets multiple times without knowing it. Any time you pick a subset of items from a larger set, you are selecting an item of a power set. For example, a kid perusing a candy store with $5 — which element of the power set of the set of all available candy will she choose? Or for the more technical, as software engineers, you might want to query all possible database users that also have property X & Y — another example where one subset is selected from all possible subsets.
We now understand the cardinality of a set, why it’s important, & it’s relation to the power set. So let’s backtrack for a moment to review something we glossed over at the very beginning of this piece: what exactly defines equivalency in Set Theory?
Arguably two sets with the same cardinality share some common property, but the the similarities stop there — what if one of the sets has an element repeated multiple times? What if two sets share the same cardinality & number of elements? There is no denying that they’re “equal” to some degree, but even in this scenario there is still room for differentiation as each set could have different elements repeated the same amount of times. The point here is that concept of equivalency in Set Theory is a bit foreign relative to other branches of math. Establishing equivalency in this world requires it’s own introduction & language. The final article in this series introduces the concepts of equivalency, as well it’s underlying properties such as a injective, bijective, & surjective functions.
