18
$\begingroup$

Consider the following situation:

There is an infinite set $G$ of giraffes. A lion comes and announces a set $C$ of all possible colours and an infinite cardinal $\kappa$. The hungry lion tells the giraffes that when she comes back, the following happens: The giraffes may no longer speak to each other. The lion gives each giraffe a scarf of some colour in the set $C$. Every giraffe sees all the scarves (including their own) but may be mistaken of the colour of strictly less than $\kappa$ scarves. The giraffes do not know which scarves they see correctly, only that there is a strict upper bound on the number of false colours. Then each giraffe must guess the colour of their own scarf. The lion eats all the giraffes that guess wrong. Can the giraffes agree on a survival strategy before the lion returns so that strictly less than $\kappa$ giraffes are eaten?

In the typical formulation of this problem $|G|=\kappa=\aleph_0$ and the giraffes have prior knowledge of which scarves they see. Let us ignore the practical issues related to this generalized savanna for a moment.

This is what the existence of a survival strategy means in more mathematical terms: Take any infinite set $G$, any nonempty set $C$ and any infinite cardinal $\kappa$. A survival strategy is a function $S:G\times C^G\to C$ (strategy) with the following property. Take any any function (colouring) $f\in C^G$ and any $o\in (C^G)^G$ (the giraffe $g\in G$ observes the colour pattern $o(g)$) so that $\left\lvert\{h\in G;o(g)(h)\neq f(h)\}\right\rvert<\kappa$ for all $g\in G$. Let $a\in C^G$ (the answers given by the giraffes) be defined by $a(g)=S(g,o(g))$. This $a$ always satisfies $\left\lvert\{g\in G;a(g)\neq f(g)\}\right\rvert<\kappa$. Note that to make sense of this existence we need not be able to compare all cardinals; it suffices that $|A|<\kappa$ is well defined. (I am not a set theorist myself. If this formulation seems inappropriate or does not seem to correspond to the story, let me know. If you know how to add clarifying details to this question, feel free to edit.)

Claim: The giraffes have a survival strategy in ZFC.

Proof: In the set $C^G$ of all possible scarf colourings define an equivalence relation $\sim$ by $$ a\sim b \iff \left\lvert\{g\in G;a(g)\neq b(g)\}\right\rvert<\kappa. $$ Let $q:C^G\to C^G/{\sim}$ be the quotient map and $r$ a right inverse for it. The giraffes can agree on the map $r$ based on the information given by the lion. Suppose the scarf colour pattern chosen by the lion is $f\in C^G$. All giraffes can see the equivalence class $q(f)$ but cannot be sure about $f$ itself. The giraffe $g\in G$ the guesses $r(q(f))(g)\in C$, so that the answers form the colour pattern $r(q(f))$. Since $r(q(f))\sim f$, the number of mistaken giraffes is strictly less than $\kappa$. In terms of the more mathematical formulation, the strategy is $S(g,v)=r(q(v))(g)$. $\square$

The problem: The proof relies heavily on the axiom of choice (the existence of $r$). But is it equivalent to it? That is, if we assume that the giraffes have a survival strategy for any $G$, $C$ and $\kappa$, can we deduce the axiom of choice?

My vague intuition suggests an affirmative answer, but I do not have any real arguments to support it. I have not seen such claims in lists of equivalent forms of the axiom of choice. One issue is that the strategy is somewhat indeterministic in the sense that it does not give any control over the identities of the surviving giraffes.

There are of course variations of the problem: Do we really need the strategy for all $G$, $C$ and $\kappa$, or is it enough let let one or two of them vary (perhaps $|G|=\kappa$ and $C=\{0,1\}$)? What if the giraffes have prior knowledge of which scarves they don't see correctly (e.g. their own)?

Note: One purpose of the animal story is to give simple and reasonably intuitive names for the objects. But my main purpose is that if the result indeed is equivalent with the axiom of choice, this could be used to demonstrate what the axiom of choice is about to non-mathematical (or choice-ignorant mathematical) audience. It is of course interesting as such that the existence of a survival strategy follows from AC, but it would be much more interesting if the existence had abstract consequences, AC itself or something else.

$\endgroup$
  • 4
    $\begingroup$ Note that the implicit assumption in the problem that cardinalities can always be compared (in the requirement of "strictly less than $\kappa$" errors) is already equivalent to the AC. Even the notion of a "cardinal" is somewhat ill-defined without AC because there may be sets which are not in bijection with any ordinal number. You should reformulate the problem such that it makes sense without AC. $\endgroup$ – Johannes Hahn Oct 14 '14 at 20:18
  • 1
    $\begingroup$ @JohannesHahn, good point. Is there a problem if I denote by $|A|<|B|$ the statement that there is an injection $A\to B$ but no injection $B\to A$? The statement only requires that "$<$" is defined; there is no need for trichotomy. $\endgroup$ – Joonas Ilmavirta Oct 14 '14 at 20:25
  • 5
    $\begingroup$ I was never a fan of the stories. Just state the damn proposition! The math should speak for itself, there's no need to add minor inconveniences with giraffes and lions. $\endgroup$ – Asaf Karagila Oct 14 '14 at 22:26
  • 3
    $\begingroup$ @AsafKaragila: When the proposition is about a strategy in a game of partial information, I frankly find a story clearer than an abstract statement. $\endgroup$ – Joonas Ilmavirta Oct 15 '14 at 7:13
  • 1
    $\begingroup$ And a lot of people think that drawing a diagram of something makes it clear and understandable. I still don't know what's going on when there is no formal definition. And I still don't know what exactly is the proposition here that you are asking about. $\endgroup$ – Asaf Karagila Oct 15 '14 at 8:49
17
$\begingroup$

It is certainly true that some choice is required.

An isomorphic game (mapping (giraffes, scarves, lion) to (prisoners, hats, warden)) was considered by Hardin and Taylor in their stimulating (and elementary) paper

MR2501394 Hardin, Christopher S.; Taylor, Alan D. An introduction to infinite hat problems. Math. Intelligencer 30 (2008), no. 4, 20–25.

The claim you make in your question is called by them the Gabay-O'Connor theorem (though Gabay and O'Connor do not seem to have published it).

Hardin and Taylor show that, in the case $|G| = \kappa = \aleph_0$ and $|C|=2$, it is consistent with ZF+DC (where DC is the Axiom of Dependent Choice) that the giraffes cannot win - that for every survival strategy, the lion (knowing the strategy) can assign the scarves in such a way that $\aleph_0$ many giraffes are eaten. Specifically, the existence of a winning survival strategy would imply the existence of a subset of $\mathbb{R}$ which does not have the property of Baire (BP) - and it is a celebrated theorem of Shelah that it is consistent with ZF+DC that every subset of $\mathbb{R}$ has the BP.

It can also be shown that a survival strategy would imply the existence of a subset of $\mathbb{R}$ which is not Lebesgue measurable. (One way to show this is via the Lebesgue density theorem. I also worked out a kind of cute probabilistic argument a couple years ago, which I may put in here if anyone is interested or if I get bored.) Solovay has shown (thanks Asaf for the correction) that if "ZFC + there is an inaccessible cardinal" is consistent (which I understand is widely believed to be the case), then so is "ZF + DC + every subset of $\mathbb{R}$ is Lebesgue measurable." So again we see that more than DC is needed.

On the other hand, one should be able to produce a survival strategy (in the case $|C| = 2$) from a free ultrafilter, so the ultrafilter lemma is sufficient, and I believe the ultrafilter lemma is known to be strictly weaker than AC. So the existence of a survival strategy when $|C|=2$ cannot imply AC. (Maybe a similar argument applies for other finite $C$?) In principle, it could imply some weaker yet still interesting choice principle, but I do not know whether anyone has looked at that. I don't know what I was thinking when I wrote that, but in fact I do not know of any way to get a survival strategy for this particular game from a free ultrafilter. (There are variants where a free ultrafilter suffices, e.g. if the victory condition is changed to "either all giraffes guess correctly or all guess incorrectly".)

(Disclaimer: I am not a set theorist and most of this is stuff I have picked up from folklore because it sounded interesting, so I may well have something completely wrong. The real set theorists here are more than welcome to correct me.)

$\endgroup$
  • 2
    $\begingroup$ There is also the recent book by Hardin and Taylor - dx.doi.org/10.1007%2F978-3-319-01333-6 $\endgroup$ – François G. Dorais Oct 14 '14 at 22:49
  • 1
    $\begingroup$ This paper shows that it is even consistent with $\:$ZF+DC($\omega_1\hspace{-0.03 in}$)$\:$ that every set of reals has Baire property. $\hspace{.25 in}$ $\endgroup$ – user5810 Oct 14 '14 at 23:02
  • 2
    $\begingroup$ Minor correction, Solovay has shown that from the consistency of $\sf ZFC+\exists\kappa\text{ inaccessible}$ we can prove the consistency of $\sf ZF+DC+LM$. But it's perfectly possible that the resulting model will not have an inaccessible cardinal (well, at least in one of the definitions of inaccessibility, since without choice there are many). $\endgroup$ – Asaf Karagila Oct 15 '14 at 1:32
  • 1
    $\begingroup$ How does one exactly produce a strategy from a free ultrafilter? The ultrafilter argument given in the paper you quote only seems to work if each giraffe sees all scarves but their own and $\kappa=|G|=\aleph_0$. Existence of a more general survival strategy seems much stronger, and I don't see how to build one from an ultrafilter (even if $\kappa=|G|=\aleph_0$). $\endgroup$ – Joonas Ilmavirta Oct 16 '14 at 15:43
  • 2
    $\begingroup$ @JoonasIlmavirta: I revisited this post and realized that I do not know how to justify that claim about an ultrafilter and probably never did, so I have taken it out. $\endgroup$ – Nate Eldredge Feb 4 at 16:31
7
$\begingroup$

Here is one interesting observation:

If the giraffes form an amorphous set, which is an infinite set all of whose subsets are either finite or co-finite, then they have a winning strategy in the case that there are only finitely many colors. The reason is that because the giraffes are amorphous, every assignment the lion might pick must be constant on a co-finite set. All the giraffes will be able to detect that one infinite color, and announce it as their own. Only finitely many will be wrong.

This shows that it is not necessary to well-order $G$ to have a winning strategy. But meanwhile, as we just explained, in any model in which $G$ is amorphous, then for any finite $C$, we do still have a selector on $C^G$, precisely because all such functions are constant except on a finite set, and so we can select the constant coloring.

$\endgroup$
  • 2
    $\begingroup$ The argument is somewhat tricky, but I think it's also the case that if the giraffes form a strictly amorphous set (i.e., for all partitions of them, at most one piece is infinite and at most finitely many pieces have more than one element), then they have a winning strategy in the case that there are the same number of colors as giraffes. $\;$ $\endgroup$ – user5810 Oct 15 '14 at 0:29
5
$\begingroup$

The question makes sense when $\kappa=\aleph_0$ since the statement involves no choice. But according to the interesting book by Hardin and Taylor, "The mathematics of coordinated inference" (2013), mentioned above in a comment by François, even the existence of a survival strategy for $\kappa=\aleph_0$ and arbitrary $G$ and $C$ is not known to be equivalent to the Axiom of Choice. They state this as "the single most prominent open question" of chapter 3 (Question 3.6.1).

ADDENDUM

There is one reasonable reformulation of your question which avoids mentioning cardinalities (which are always tricky in a choiceless context) and which is equivalent to it in ZFC. It turns out that such a reformulation is actually a particular case of a theorem in the book that is unknown to imply AC, which would indicate that your question is also an open problem.

Fix any proper ideal $\mathcal{I}$ in the powerset of $G$. Then you can stipulate that the subset of scarves each giraffe sees wrongly is a member of $\mathcal{I}$, and ask whether there is a strategy under which only a member of $\mathcal{I}$ guesses wrong (when AC is available, the subsets of cardinality strictly less than $|G|$) would form such an ideal).

Under this reformulation, $G$ can be turned into a topological space in which the neighbourhood filter of a point consists precisely on those subsets containing the point whose complements belong to $\mathcal{I}$. For each $g \in G$ you can define an equivalence relation $\sim_g$ on $C^G$ by $f \sim_g f'$ if and only if $f$ and $f'$ agree on a deleted neighbourhood $U - \{g\}$ of $g$. Given an assignation $f$, each giraffe $g$ can detect the equivalence class of $f$ under $\sim_g$ and predict their own colour. This is precisely what Hardin and Taylor call a $\textit{near neighbourhood predictor}$. Moreover, one can easily see that all points in a given member $i \in \mathcal{I}$ are topologically isolated, and in particular any point in a nonempty subset of $i$ has a neighbourhood intersecting only finitely many points in that subset, making $i$ something which they call $\textit{weakly scattered}$. Their corollary 7.2.4 then states:

"For any space $X$ of agents and set $Y$ of colours, there exists a weakly scattered-error near neighbourhood predictor"

Once again, their list of open questions includes question 7.8.1, which asks whether the above proposition, provable in ZFC, actually implies AC over ZF.

$\endgroup$
4
$\begingroup$

This is related to Nate Eldredge's answer that shows some amount of choice is required. In the case $G=\mathbb{N}$, $\kappa = \omega_0$ and $C=2$, the equivalence relation you define is eventual equality of 0-1 sequences and it has a special name, $E_0$.

Choose one element from each equivalence class of $E_0$, and assume that this set is Borel. In this case, there would be a Borel map $f: 2^{\mathbb{N}} \rightarrow 2^{\mathbb{N}}$ such that $xE_0y \Leftrightarrow f(x)=f(y)$. Such Borel equivalence relations are known as "smooth" (check out this MO question) and $E_0$ is known to be not smooth. (You can see page 5 of this workshop talk by S. Thomas, or Su Gao's Invariant Descriptive Set Theory Proposition 6.1.7 on page 135)

Therefore, the giraffes' strategy you define is not Borel. To see that some amount of choice is necessary to construct this strategy, or any set that intersects each $E_0$-class at a single point, you can move to a model of set theory where choice fails badly and every set of reals is Borel (for example, see here). Of course, Nate Eldredge's answers reveals more than this argument but I thought it is worth mentioning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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