While trying Sweet & Salty Snack Mix Cheez-Its last night at my daughter’s recommendation (she was right–they’re great), I thought about Georg Cantor and set theory, which he invented and I’m trying to learn about. Before Cantor came along, people used the word “set” imprecisely; he gave it a useful rigor that helped make it a foundational concept of modern-day math. And amazing things resulted, like his finding that there are infinities of different sizes. Cheez-Its can help make this clear.
As the snack’s web page illustrates, there are 31 varieties of Cheez-Its, making the product line a set with 31 elements. One can also group the product line, however, into five sets: the traditional baked crackers, the ultrathin “Snap’d” line, the Grooves, the mashup-flavored Duoz, and the Snack Mixes. This is one thing sets are good for: helping us group things and think of them together. As Cantor put it, “A set is a Many that allows itself to be thought of as a One.”
Now let’s think about just the Snack Mixes, of which there are only three: the Sweet & Salty, the Double Cheese, and the Classic. This means the Snack Mixes is a set with three elements. One of the things Cantor noticed is that the set of all possible subsets of a set–what mathematicians refer to as the “power set” of a set–always has more elements than the set itself. In the case of the Snack Mixes, you could have a single-element set made up of only the Sweet & Salty, only the Double Cheese, or only the Classic; a two-element set of the Sweet & Salty and the Double Cheese, the Sweet & Salty and the Classic, or a set of the Double Cheese and the Classic; a set with nothing in it (mathematicians call this the “null set,” and it’s a subset of any set); or the original three-element set (because every set is a subset of itself). That means that for a three-element set, its power set has eight elements, and it turns out, as Cantor proved, that this follows a predictable rule: for any set with a number of elements represented by n, the number of elements in its power set is 2 raised to the power of n.
Now here’s where things get really cool. The number of Cheez-It varieties (at least so far) is finite. But in math there are infinite sets, like that of the integers. But if, for any set, the power set always has more elements than the set itself, it must be the case that while the set of the integers is infinite, the power set of the integers is even more so.
The idea that there are degrees of infinity, with some bigger than others, is something that freaked people out big time, in Cantor’s day; and it’s a lot to absorb even now. I think I’ll pause there for today; it’s something to chew on. Maybe with your own box of Cheez-Its.
Your post was an entertaining layman’s introduction to power sets.
It would be nice to have an addendum, which could draw some readers deeper into the actual mathematics. I noodled around with spelling things out in precise detail written for a laymen, but it became too long to fit in a comment. So I’ll just say a couple of things cryptically that I think could be spelled out well in a brief addendum with “A few more bytes of Cheeze-Its”.
In computer science, a “bit” is a choice between two value. It can be represented by a binary digit, either 0 or 1. A sequence of n binary digits has 2 raised to the power n (2^n) possible values. For example, a byte, which is eight digits, can take 2^8=256 possible values: 00000000, 00000001, 00000010, 00000011, …, 11111111.
Here is a one life proof that the size of the power set of a set R with n elements has 2 raised to the power n elements:
================
A choice of element in the power set of R, i.e. a choice of a a subset of R, corresponds to a binary choice of “in the subset” or “not in the subset” for each element of R.
Here is a mystical proof that a power set is always bigger than the original set:
============================================================
Just consider the set of all Cheez-Its types whose set does not contain itself.
To de-mystify a little bit:
==================
Let C be any set, and P be the power set of C.
If P is NOT bigger than C, there should be an “onto” mapping of C to P.
This means that there is some function, whose input is an element of C and whose
output an element of P, so that every element of P is obtained.
To make contact with the “mystical prooof above”, we will call the value of the function associated to a given element of C, it’s set.
We obtain a contradiction by considering the set of all elements of C whose set does not contain itself.
Additional point:
=============
The foundation of mathematics has to be completely rebuilt at the beginning of the 20th century because of contradiction when one consider the set of all sets that don’t contain themselves.