9
$\begingroup$

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$?

$\endgroup$
1
  • 5
    $\begingroup$ 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)\}$. $\endgroup$
    – Andrés E. Caicedo
    Dec 1, 2019 at 19:35

1 Answer 1

Reset to default
3
+100
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The solution given in the upadate is formally correct but somehow disappointing. Your first solution is just great. $\endgroup$
    – Jochen
    Dec 6, 2019 at 8:27
  • $\begingroup$ @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. $\endgroup$
    – Ewan Delanoy
    Dec 6, 2019 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .