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

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

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.