# How much bigger is the power set -- explicitly

Recently, I gave a talk to highschool pupils about cardinality and explained them that, for any set $$X$$, there is no surjective map $$f:X\to \mathcal P(X)$$ because $$R=\{x\in X: x\notin f(x)\}$$ is not in the range of $$f$$.

Apparently, the pupils liked the interpretation that every member of $$X$$ organizes a party $$f(x)\subseteq X$$ (the invited people). Some people spoil every party they attend and, in order to keep their chances for the best party award, they do not invite themselves. Then, $$R$$ is the consolation party where exactly those poor spoilers are invited.

The question: Can one explicitly write down other parties which (given the map $$f$$) are certainly not organized by some $$x\in X$$?

• I think the question is fairly clear, but just in case someone doesn't: the question can be formalized as whether there is a first-order formula $\varphi(x,y)$ in the language of set theory such that for any set $X$ with at least two elements and any $f\!:X\to\mathcal P(X)$, and setting $A=\{x\in X: \varphi(x,f)\}$, the following two conditions hold: 1) $A\notin\mathrm{ran}(f)$, and 2) $A\ne\{x\in X: x\ne f(x)\}$. Commented Dec 1, 2019 at 19:35

I think Zwicker's survival game construction comes close to what you are looking for. It will not always yield a party different from the "consolation party", but it often will and is based on a rather different idea.

Once you have your $$X$$ and your $$f$$, for each $$x_0\in X$$ define a "survival game" as follows : you start at position $$x_0$$, and then you have to jump to a position $$x_1\in f(x_0)$$ (if $$f(x_0)$$ is empty you have lost from the start), then to a position in $$f(x_1)$$, etc. If you find a way to go on jumping forever (aka a cycle in mathematical parlance), you win ; otherwise you lose.

Clearly, there are winning and losing initial positions. Let $$A$$ be the set of losing initial positions. If $$A=f(a)$$ for some $$a\in X$$, then $$a$$ must be a losing position since all the positions immediately accessible from it are, so $$a\in A=f(a)$$, but then we can win by jumping and staying on $$a$$ forever, which is a contradiction.

Update 05/12/2019: here is a construction of a $$R'$$ that will always be different from your $$R$$.

As explained in Andres Caicedo's comment to the OP, we assume that $$X$$ has at least two elements ; call them $$x_1$$ and $$x_2$$. Let $$Y=X \setminus \lbrace x_1,x_2 \rbrace$$ ($$Y$$ may be empty).

Let $$R_Y=\lbrace y \in Y | y \not\in f(y) \rbrace$$. Then the four sets $$S_1=R_Y$$, $$S_2=R_Y \cup \lbrace x_1 \rbrace$$, $$S_3=R_Y\cup \lbrace x_2 \rbrace$$, and $$S_4=R_Y\cup \lbrace x_1,x_2 \rbrace$$ are all distinct. It follows that they cannot all lie in $$Z=\lbrace f(x_1),f(x_2),R \rbrace$$ since this latter set has at most three elements. So there one of the $$S_k$$'s (call it $$R'$$) which is not in $$Z$$. This $$R'$$ satisfies the requirements by construction.

• The solution given in the upadate is formally correct but somehow disappointing. Your first solution is just great. Commented Dec 6, 2019 at 8:27
• @Jochen I completely agree, the second solution is not very interesting, but I posted it all the same because it's not obvious, and therefore informative (however disappointing it may be). The brilliantly simple idea in the first is Zwicker's not mine. Commented Dec 6, 2019 at 10:43