4
$\begingroup$

Some of the strangest implications of AC are the "infinite hat" puzzles, which are on Wikipedia, and have been talked about on MO several times, including some variants.

There are different ways to formalize these puzzles, but most of them follow the same basic principle:

  1. There is a countably-indexed sequence of things (reals, naturals, bits, etc).
  2. You only have information about some partial subsequence: usually with one value missing, or an initial segment missing, etc.
  3. You get to use the axiom of choice to "mysteriously" infer some value from the original sequence that isn't in your partial subsequence.
  4. Informally, this inference can be made to agree with the original "arbitrarily often", such as failing in only a finite set of cases, despite having no knowledge of what the original sequence was.

The basic gist is usually that you use AC to get a "chosen" representative from each equivalence class of sequences with the same infinite "tail." Then, for your partial sequence, you interpolate some missing value based on what the representative says. This strategy is correct for all but a finite set of cases in some initial segment, leading to bizarre consequences.

My question:

It would be interesting to see what happens if you take, as an axiom, the deliberate negation that "infinite hat" puzzles admit any such strategy, and see how strong it is compared to just the negation of $AC$.

The simplest way to formalize this, that I can think of, is as follows:

  • Let $a$ be some sequence $\Bbb N \to S$, for some arbitrary set $S$.
  • For some $k \in \Bbb N$, let the knockout sequence $a \setminus k$ be the restriction of $a$ to the domain $\Bbb N \setminus k$. (i.e., one (index, value) pair is missing)
  • Let an interpolation function be some $f$ that takes as input some $a \setminus k$, and returns some value $s \in S$, which we interpret as its "suggestion" for the missing value at $k$.
  • For any such interpolation function $f$ and sequence $a$, we can define an agreement sequence $A_{f,a}[k]$, for which $A_{f,a}[k] = 1$ if $f(a \setminus k) = a[k]$ and $A_{f,a} = 0$ otherwise.
  • Likewise, we can define the agreement set $A_{f,a} = \{k: A_{f,a}[k] = 1\}$, the set of indices for which the agreement sequence is 1.

AC, then, says that for each choice of $S$, there exists an interpolation function $f$ such that for all $S$-sequences $a$, $A_{f,a}[k]$ is eventually constant at 1. Just let $f(a \setminus k) = r(a)[k]$, where $r(a)$ is the chosen representative from the equivalence class for $a$.

However, our negation can be much stronger: we can declare that no interpolation function $f$ can be guaranteed, for all sequences $a$, to have an agreement set with natural density greater than $1/|S|$ if $S$ is finite, or $0$ if it is infinite. That is, any such $f$ may do better for some particular sequence $a$, but cannot be guaranteed to do better for all $a$.

For uncountable $S$ we can get even stronger: not only should the natural density of the agreement set be $0$, but the agreement set can never be guaranteed to even be any larger than the empty set for all $a$. That is, given a sequence of reals, there can be no interpolator $f$ that is guaranteed, for all such sequences, to interpolate even one missing value correctly.


There is probably some better way to formalize the above, but at least it isn't that complicated, and formalizes the basic reservation that people often have with infinite hat puzzles. So I'm simply interested in what set theory looks like if we take that perspective and formalize it.

  • Have axioms similar to these been studied?
  • Are they known to be equivalent to, to imply, or to be implied by other well-known axioms that are incompatible with AC?
  • Is there some simpler way to formalize the above?
| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ You know, it's really great that you ask these things. But many of these questions were discussed previously either here or on math.SE. Specifically, the infinite hat "paradox" implies there are irregular sets. Namely, sets without the Baire property, sets which are not Lebesgue measurable, etc. $\endgroup$ – Asaf Karagila Jan 31 '19 at 21:36
  • $\begingroup$ I would appreciate links on the implications of the infinite hat "paradox" if you have them, but this is a totally different question than what I'm asking. I'm not asking about the implications of the paradox, I'm asking about the implications of its negation. For example, Banach-Tarski implies non-measurable sets of reals, but "not-Banach-Tarski" is not strong enough to imply the nonexistence of non-measurable sets of reals. $\endgroup$ – Mike Battaglia Jan 31 '19 at 21:51
  • 1
    $\begingroup$ Some of these infinite hat results can be derived from "there exists a nonprincipal ultrafilter on $\mathbb N$." I don't know how this fits into the bigger picture of consistency results. $\endgroup$ – Jalex Stark Jan 31 '19 at 22:12
6
$\begingroup$

Naturally, the more generalizations of the infinite hats puzzle we consider, the stronger it is to assert that none of them have a paradoxical solution. One of the variants you linked in your question is the box variation, where 100 mathematicians take turns entering a room with a countable infinity of boxes, each containing a real number, and after opening arbitrarily many boxes, must guess the contents of some unopened box. With AC, it can be shown there is a strategy where at most one mathematician fails.

One way to generalize the box puzzle is to have there be uncountably many boxes. For example, let's consider the box puzzle where there is one box for every set of reals, each box contains a real, and there are countably infinitely many mathematicians.

It doesn't seem like the increased number of boxes should make things easier on the mathematicians (they still have to guess the contents of some box without any apparently useful knowledge). But it turns out there are explicit winning strategies to this variant, where by "winning" I mean that all but (at most) one mathematician makes a correct guess. This is a theorem of fourth-order arithmetic. I sketch the details for a similar variant here https://mathoverflow.net/a/300556/109573.

If you accept that this is a paradox of the type you are interested in, then a consequence of "there are no paradoxical strategies for any guessing game" is $\mathcal{P}(\mathbb{R})$ does not exist. We would have to weaken our foundations to third-order arithmetic, with some antichoice principles like nonexistence of nonprincipal ultrafilters on $\mathbb{N}.$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Hi Elliot - if you look at the way I use interpolators, it's strong enough to rule out both the usual infinite hat puzzle and the 100 mathematician variant, since both depend on an interpolator $f$ that is guaranteed to make perfect guesses for some missing value eventually as the index goes to infinity. My negation was stronger than just saying no "eventually perfect" interpolator exists, it was saying no interpolator should be guaranteed for all sequences to give correct guesses with natural density greater than 1/|S| for finite S, or produce any correct guesses at all for uncountable S. $\endgroup$ – Mike Battaglia Feb 1 '19 at 6:29
  • $\begingroup$ Is it strong enough to rule out the variant I describe in the second paragraph? My answer isn't about the standard 100 mathematician puzzle. $\endgroup$ – Elliot Glazer Feb 1 '19 at 6:31
  • $\begingroup$ Sorry, writing comments at the same time - I thought about using $\Bbb R$ as an index set instead of $\Bbb N$, or to let there be arbitrary index sets, but wasn't certain how that would make anything stronger. But your version seems to use well-ordered subsets of $\Bbb R$, "modded out by isomorphism" - what do you mean by that last part? $\endgroup$ – Mike Battaglia Feb 1 '19 at 6:38
  • $\begingroup$ The variant in the linked post is slightly different. Rather than there being one box for every set of reals (i.e. the index set is $\mathcal{P}(\mathbb{R})$), I have the index set $X$ be the Hartogs number of $\mathbb{R}.$ I was just describing how to construct this set. $\endgroup$ – Elliot Glazer Feb 1 '19 at 6:42
  • $\begingroup$ Ok, I got tripped up at the part where you say $X \cong 2 \times \omega \times X$. Does $\times$ refer to ordinal multiplication? I thought you were splitting $X$ into two interleaved subsequences, but I may be confused here. $\endgroup$ – Mike Battaglia Feb 1 '19 at 7:04

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.