An equivalent of the axiom of choice? [closed]

Question

There is such a thing as a math course for relatively non-mathematically inclined people that is intended to challenge students' intelligence more than to teach them some mathematics. (It is true that the first-year calculus course is used for that purpose by medical schools, etc., and if you don't know that that works very very very badly then you haven't paid attention. Here I have in mind courses that could work well.) And there is such a thing as textbooks designed only for such courses. In such a textbook one may find this:

You are guarding 100 murderers in a field, and you have a gun with a single bullet. If any one of the murderers has a non-zero probability of surviving, he will attempt to escape. If a murderer is certain of death, he will not attempt to escape. How do you stop them from escaping?

The well-ordering of the natural numbers solves this.

But now suppose infinitely many murderers. If infinitely many conspire to escape simultaneously, knowing exactly one would be shot, then each one's probability of survival exceeds your chance of surviving the hazards of getting out of bed in the morning, but if David Hilbert can talk about his "hotel", then we may suppose that no one will try to escape if it is certain that they will be shot. Here the well-orderability of all sets, equivalent to the axiom of choice, solves the problem.

My question is whether there is a converse: If you have a strategy for preventing all escapes, does the axiom of choice follow?

Answer 1

With such shared/common knowledge problems, even when AC isn't involved, I think a crucial first step is to get away from the "story" version. For example, since this is only interesting once the set of murderers is uncountable (since it needs to be non-wellorderable), talking about probabilities isn't going to be ultimately helpful.

---

Here's a first stab at a formalization:

Consider, for $X$ a set, a two-player game $\mathsf{Shoot}_X$ played as follows:

• First, player $1$ plays a function $f:\mathcal{P}(X)\rightarrow\mathcal{P}(X)$ satisfying $f(S)\subseteq S$ for all $S\subseteq X$.

• Next, player $2$ plays a function $g: X\rightarrow 2$.

• At this point, the game is done: player $2$ wins iff $f(g^{-1}(1))$ has more than one element.

The intuition here is that player $1$ is announcing their shooting strategy ("If the set of runners is $S$, I'll 'randomly' shoot someone in $f(S)$") and player $2$ is saying which murderers (= elements of $X$) will run. The condition that $f(g^{-1}(1))$ has more than one element corresponds to every runner having a chance of surviving.

This formalization more-or-less trivializes things (since the game itself is basically $\mathsf{AC}$ in disguise): a winning strategy for player $1$ must be a choice function for $\mathcal{P}_{\not=\emptyset}(X)$, and so the existence of a winning strategy for player $1$ for all $X$ is automatically equivalent to choice. In fact, I think this highlights the importance of making the infinitary version of the game more precise.

This does, however, raise an interesting follow-up question:

Is $\mathsf{ZF}$ + $\neg\mathsf{AC}$ + "Every $\mathsf{Shoot}_X$-game is determined" consistent?

I suspect there's an easy argument that the answer is negative (= that from a failure of choice we can build an undetermined shooting game), but I don't immediately see it.

Answer 2

Yes.

The problem's statement can be reformulated as follows. Suppose that for any set $X$ there exists a function $f: (2^X\setminus \{\emptyset\})\to X$ mapping any nonempty subset (of escapees) to one of its elements (which guarantees that a participant will refuse to participate in the escape). Is it equivalent to the Axiom Of Choice?

The Axiom of Choice states that for any set $X$ of nonempty sets $Y_i\in X$ there exists a function mapping any set $Y_i$ to an element of the set.

But the equivalence is fairly trivial. Indeed, the AOC follows by constructing the function $f$ for $\bigcup Y_i$ and applying it only to the sets $Y_i,$ while the function function $f: (2^X\setminus \{\emptyset\})\to X$ mapping any subset to its element is created by applying the AOC to all nonempty subsets of $X.$