Melissa writes,
I have a mathematical tattoo on my left forearm. It’s in Frege’s notation (from “Grundgesetze der Arithmetik”), which was one of the first modern logical notations. If it were written on a flat surface, it would start with the short vertical line, which is the assertion sign. What it asserts is: If {Cantor’s theorem} then {heart}.
Cantor’s Theorem says that the power set of any set is strictly larger than the set itself. (The power set of a set is the set of all its subsets.) For finite sets, this is pretty obvious; for example, the power set of {1,2} is {{}, {1}, {2}, {1,2}}. In general, if a finite set has n members, its power set has 2^n. But Cantor’s Theorem is also true for *infinite* sets, which is kind of unexpected. After all, the set of all even numbers is the same size as the set of all numbers — why does the power set of the set of all numbers have to be bigger?
That’s why the proof of the theorem is so cool. It proves it for finite sets and infinite sets, no matter how huge, at the same time. You start by assuming that some arbitrary set S has the same number of members as its power set P(S). That is, assume there’s a one-one function f which maps the members of S to the members of P(S). Now consider the set D, which consists of all and only the members of S that don’t get mapped to a set of which they’re a member. (So, for instance, if 7 is a member of S, and f(7) = {4, 5, 12}, then 7 is in D because it’s not a member of f(7).) D is a subset of S, so it’s a member of P(S). That means that f maps some member of S, call it d, to D. But: is d in D or not? If it is, then it’s a member of f(d), so by the definition of D, it’s not in D. If it’s not in D, then it’s not a member of f(d), so, again by the definition of D, it’s in D. Either way leads to a contradiction, and there’s only one way out: it’s not possible to have a one-one function from any set to its power set. QED! (Of course, you also have to prove that P(S) can’t be *smaller* than S, but that’s easy.)
When I saw how short and simple (and beautiful!) the proof of such a powerful theorem was, I knew I could spend the rest of my life doing set theory and logic. So last year, when I got my bachelor’s degree in philosophy and went on to grad school, I celebrated by getting the theorem tattooed on my arm. As for the tattoo itself, it’s easiest to read from the bottom. The stuff on the right-hand side of the ‘=’ means: for all a, if a is in r, then a is in u. (In other words, r is a subset of u.) The whole bottom line means: for all r, r is in v if and only if it’s a subset of u. (So v is the power set of u.) The bottom line and the one above it together mean: if v is the power set of u, then v is strictly bigger than u. So those two lines state Cantor’s Theorem, and the whole tattoo means: if Cantor’s Theorem, then {heart}. (Incidentally, I got that heart symbol from an illustration in “Alice in Wonderland”. It’s the top of the King of Hearts’s crown.)
You can see the rest of the Science Tattoo Emporium here or in my book,Science Ink: Tattoos of the Science Obsessed.
Originally published July 17, 2010. Copyright 2010 Carl Zimmer.