Power sets and the Chef Paradox

The Chef Paradox

Suppose that there is a chef.  The chef cooks for all people who do not cook for themselves.  But he does not cook for anyone who cooks for themself.  Does the cook cook for himself?

If he cooks for himself, then he must not cook for himself.  If he does not cook for himself, then he must cook for himself.  It's a paradox.  The solution to the paradox is simple: the chef does not exist.  We were wrong to suppose that he did.

Normally, this is called the Barber Paradox (or Russell's paradox) because it's about the barber who shaves all men who do not shave themselves.  But I decided to use a chef instead.  I hope I don't get any hate mail for this.

The Chef paradox will reappear again, you'll see.

The power set

Let's say we have a set of three elements, {a, b, c}.  Call this set S.  We can define the power set of S, abbreviated P(S).  P(S) is the set of all possible subsets of S.  Here's the list of all elements in P(S):

{}
{a}
{b}
{c}
{a,b}
{a,c}
{b,c}
{a,b,c}

P(S) has eight elements in it, while S has only three.  Clearly P(S) is bigger than S.

There's a simple way to think of power sets in terms of chefs.  Suppose we have three chefs a, b, and c.  The chefs cook for each other.  For example, chef a might cook for a and b.  Chef b might cook for a and c.  Chef c might cook for no one at all.

a → {a,b}
b → {a,c}
c → {}

By stating which chef cooks for whom, I've just matched each element in S to an element in P(S).  So if S is the set of chefs, then each element in P(S) is a possible list of chefs that a chef could cook for.

But what if S is an infinite set?  Clearly P(S) will also be an infinite set.  But now that we've discussed that some infinite cardinalities are larger than others, we should consider the possibility that P(S) has a larger cardinality than S.  We will find that P(S) is indeed larger than S.  To prove it, we will first assume that P(S) and S have the same cardinality, and then show that this leads to a contradiction.

Assume that P(S) and S have the same cardinality.  This means that the elements in S can be matched exactly one to one to the elements in P(S).  Using the chef analogy:  Each element of P(S) is a list of chefs.  For every list in P(S), there exists a chef who cooks for exactly those people on the list.

Consider the list of all chefs who do not cook for themselves.  As I just said, there must be some chef who cooks for exactly the people on this list.  Therefore, there is a chef who cooks for those who do not cook for themselves.

As previously explained, such a chef is impossible.  So we have to backtrack to see where we made an incorrect assumption.  The incorrect assumption was that P(S) and S have the same cardinality.  This is not the case.  P(S) is always larger than S, no matter what S is.

An aside: If S is the set of positive integers, then P(S) has the same cardinality as the real numbers.  So this is another proof that there are more real numbers than positive integers.

The larger implications

We can take the power set of any set.  Any set.  That means that no matter what infinite set we choose, there is always a bigger set.

Why not take the power set of a power set?  P(P(S)) must be bigger than P(S), which must be bigger than S.  We can continue to take power sets and build a sequence of progressively bigger sets.

S
P(S)
P(P(S))
P³(S)
P⁴(S)
P⁵(S)
...

In fact, we can build a set that's even bigger than every set in the sequence!  Just join together all the sets in the sequence and call it Q.  (ETA: I'm not sure if this is allowable by set theory rules, so perhaps it was an error.)  Q is bigger than P^N(S), because Q contains all the elements in P^N+1(S), which is bigger than P^N(S).  However, Q is still not as big as P(Q) or P(P(Q)) and so on.  There's basically no end to the infinite cardinalities we can make.

The series on infinite sets:
Hilbert's Hotel
Doubling the Sphere
Larger infinities and the Diagonal Proof  
Power sets and the Chef Paradox
The unmeasurable set