26
$\begingroup$

There is a population of people (finite or infinite). Any group of people (finite or infinite) in this population has someone assigned to be in charge of them. So someone is in charge of the whole population, someone is in charge the set of no people, each person has someone in charge of them (which may or may not be themselves) etc.

If the person in charge of a group of people belongs to the group, we call them the leader of the group. If the person in charge of a group of people does not belong to the group, we call them the ruler of that group.

Show that someone is both a ruler and a leader.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Now it's been solved, here is the background: A few years ago I taught Cantor's diagonal argument, that any map $f\colon X\to \mathcal{P}(X)$ is not surjective. For the midterm test I thought I would set the dual task of proving that every map $g\colon \mathcal{P}(X)\to X$ is not injective. In particular I asked: $${}$$Given $g\colon \mathcal{P}(X)\to X$, find $x\in X$ and $A,B\subseteq X$, such that $x\in A, x\notin B$ and $g(A)=x=g(B)$. $${}$$ This is of course the same as the question above, if you unpack the mathematical notation. $\endgroup$
    – tkf
    Commented Jun 6 at 0:45
  • 1
    $\begingroup$ -Who do you rule? -No one -Liar! I am the only ruler of no one! in memory of Raymond Smullyan. $\endgroup$
    – Alexey Birukov
    Commented Jun 6 at 9:21
  • $\begingroup$ Not true if the population is empty. SCNR. $\endgroup$
    – Torsten Schoeneberg
    Commented Jun 7 at 16:13
  • 4
    $\begingroup$ @Torsten Schoeneberg Population is not empty, because there is at least a person in charge of empty group. $\endgroup$
    – Alexey Birukov
    Commented Jun 7 at 22:31

3 Answers 3

Reset to default
22
$\begingroup$

Consider the group consisting of everyone who is a ruler of at least one group. Like all groups, someone is in charge of it. If that someone is not in that group, they're its ruler, but that contradicts the group containing every ruler. So, they are in the group, and hence its leader as well as a ruler.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What a beautiful construction! It reminds me of the barber paradox. $\endgroup$
    – DanDan面
    Commented Jun 5 at 23:36
  • 1
    $\begingroup$ ^my thought exactly! And in a neat twist, it is used to prove the existence of this leader/ruler, rather than the non-existence of the barber $\endgroup$
    – azi
    Commented Jun 5 at 23:38
  • 4
    $\begingroup$ It does make me wonder if this actually falls into a Russell-style paradox by defining sets with unrestricted comprehension. $\endgroup$
    – xnor
    Commented Jun 5 at 23:40
  • $\begingroup$ I was originally wondering “what if this group doesn’t exist?” or it’s the empty set, in which case it cannot have a leader. That’s why I wanted to add that this group has at least one person (the ruler of the empty set). $\endgroup$
    – azi
    Commented Jun 6 at 0:26
  • 1
    $\begingroup$ Right, just realized that this case is also encompassed by the logic. $\endgroup$
    – azi
    Commented Jun 6 at 0:32
2
$\begingroup$

(finite case; not sure if this extends to infinite case)

Suppose not; then every person in the population has to be either a leader or a ruler (or neither). In particular, a leader cannot rule another group, and a ruler cannot lead any group it is in.

Let person E be the ruler of the empty set, and let person F be the leader of the full population. Then someone other than E or F must rule the group (E), as E cannot be a leader, and F cannot be a ruler. Call the person in charge of this group "G"; G rules the group (E).

But now we can iterate: consider the group (E, G). It cannot be led by E, ruled by F, or led by G. Thus, this group must be ruled by some other person H. Now consider the group (E, G, H); it must be ruled by some other person I, and so on...

Eventually, you will run out of other people in the population, and will have no valid person to be in charge of the group - a contradiction!

Improve this answer
$\endgroup$
6
  • $\begingroup$ Small issue regarding the first paragraph - What if a person is neither a leader nor a ruler? $\endgroup$
    – DanDan面
    Commented Jun 5 at 23:29
  • $\begingroup$ The rest of the proof is really neat though! However I do not believe it generalizes to the uncountably infinite case $\endgroup$
    – DanDan面
    Commented Jun 5 at 23:30
  • $\begingroup$ I don't think that matters? We are using the fact that every group must have someone in charge. $\endgroup$
    – azi
    Commented Jun 5 at 23:31
  • $\begingroup$ You are right in that the rest of the proof is sound, there is just a slight imprecision in the statement 'every person in the population has to be either a leader or a ruler" $\endgroup$
    – DanDan面
    Commented Jun 5 at 23:32
  • $\begingroup$ ah gotcha, thanks! $\endgroup$
    – azi
    Commented Jun 5 at 23:32
-1
$\begingroup$

Edge case: A population of one. This one person is in charge of the whole population and of themself. If the only group is the whole population, this person is a leader.

The premise states that "someone is in charge of the set of no people". This someone does not belong to the set of no people, so this someone is the "ruler" of this empty set.

In a population of one, that one person would also have to take on this charge and be a ruler.

But is it meaningful to say that someone is the "ruler of no people"? Is "ruler" to be considered as a purely mathematical concept, empty of any sociological meaning? Or does it imply that there should be at least one person who should follow the ruler's rules?

If the conditions required for a mathematical statement to be true also require that the words used to make that statement lose all meaning, is that mathematical statement valid?

Improve this answer
$\endgroup$
3
  • $\begingroup$ All the people in the empty set have to follow the ruler's rules. To say that all the people a ruler rules, have to follow their rules, is more consistent with the sociological meaning than your version, where only one person need follow the ruler's rules. $\endgroup$
    – tkf
    Commented Jun 8 at 11:49
  • $\begingroup$ Your "only one" is not the same as my "at least one", and your "all the people in the empty set" equates to "no people", so I am not sure that you have addressed my concerns in any meaningful way. $\endgroup$
    – James Newton
    Commented Jun 8 at 13:11
  • $\begingroup$ "Only one" satisfies the requirement of "at least one" and sometimes "none" can be "all". All this comes very naturally to mathematicians, but you ask a valid question: Is it appropriate to use this language in the wider puzzling community? Both of us are new to the puzzling community (judging by our respective activity), but I would take the positive reception of the question as evidence that they are just as happy to accept the conventions of logic as mathematicians. $\endgroup$
    – tkf
    Commented Jun 9 at 0:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.