Infinite Games, Frivolities of the Gods, Logic at Large Lecture, May 2022

The Dutch Association for Logic and Philosophy of the Exact Sciences (VvL) has organized a major annual public online lecture series called LOGIC AT LARGE, where “well-known logicians give public audience talks to a wide audience,” and I am truly honored to have been invited to give this year’s lecture. This will be an online event, the second of the series, scheduled for May 31, 2022 (note change in date!), and further access details will be posted when they become available. Free registration can be made on the VvL Logic at Large web page.

Abstract. Many familiar finite games admit natural infinitary analogues, which often highlight intriguing issues in infinite game theory. Shall we have a game of infinite chess? Or how about infinite draughts, infinite Hex, infinite Go, infinite Wordle, or infinite Sudoku? Let me introduce these games and use them to illustrate various fascinating concepts in the theory of infinite games.

Come enjoy the lecture, and stay for the online socializing event afterwards. Hope to see you there!

Reflection in second-order set theory with abundant urelements bi-interprets a supercompact cardinal

  • J. D. Hamkins and B. Yao, “Reflection in second-order set theory with abundant urelements bi-interprets a supercompact cardinal,” Mathematics arXiv, 2022.
    [Bibtex]
    @ARTICLE{HamkinsYao:Reflection-in-second-order-set-theory-with-abundant-urelements,
    author={Joel David Hamkins and Bokai Yao},
    year={2022},
    eprint={2204.09766},
    archivePrefix={arXiv},
    primaryClass={math.LO},
    title = {Reflection in second-order set theory with abundant urelements bi-interprets a supercompact cardinal},
    journal = {Mathematics arXiv},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {manuscript under review},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/second-order-reflection-with-abundant-urelements},
    }

Download pdf at arXiv:2204.09766

Abstract. After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove, second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal $\kappa$ is supercompact if and only if every $\Pi^1_1$ sentence true in a structure $M$ (of any size) containing $\kappa$ in a language of size less than $\kappa$ is also true in a substructure $m\prec M$ of size less than $\kappa$ with $m\cap\kappa\in\kappa$.

See also my talk at the CUNY Set Theory Seminar: The surprising strength of reflection in second-order set theory with abundant urelements

The surprising strength of reflection in second-order set theory with abundant urelements, CUNY Set Theory seminar, April 2022

This was an online talk 15 April 12:15 for the CUNY Set Theory Seminar. Held on Zoom at 876 9680 2366.

Abstract. I shall give a general introduction to urelement set theory and the role of the second-order reflection principle in second-order urelement set theory GBCU and KMU. With the abundant atom axiom, asserting that the class of urelements greatly exceeds the class of pure sets, the second-order reflection principle implies the existence of a supercompact cardinal in an interpreted model of ZFC. The proof uses a reflection characterization of supercompactness: a cardinal $\kappa$ is supercompact if and only if for every second-order sentence $\psi$ true in some structure $M$ (of any size) in a language of size less than $\kappa$ is also true in a first-order elementary substructure $m\prec M$ of size less than $\kappa$. This is joint work with Bokai Yao.

See the article at: Reflection in second-order set theory with abundant urelements bi-interprets a supercompact cardinal

Infinite Wordle and the Mastermind numbers

  • J. D. Hamkins, “Infinite Wordle and the mastermind numbers,” Mathematics arXiv, 2022.
    [Bibtex]
    @ARTICLE{Hamkins:Infinite-Wordle-and-the-mastermind-numbers,
    author = {Joel David Hamkins},
    title = {Infinite Wordle and the mastermind numbers},
    journal = {Mathematics arXiv},
    year = {2022},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    eprint = {2203.06804},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/infinite-wordle-mastermind},
    }

Download article at arXiv:2203.06804

Abstract. I consider the natural infinitary variations of the games Wordle and Mastermind, as well as their game-theoretic variations Absurdle and Madstermind, considering these games with infinitely long words and infinite color sequences and allowing transfinite game play. For each game, a secret codeword is hidden, which the codebreaker attempts to discover by making a series of guesses and receiving feedback as to their accuracy. In Wordle with words of any size from a finite alphabet of $n$ letters, including infinite words or even uncountable words, the codebreaker can nevertheless always win in $n$ steps. Meanwhile, the mastermind number 𝕞, defined as the smallest winning set of guesses in infinite Mastermind for sequences of length $\omega$ over a countable set of colors without duplication, is uncountable, but the exact value turns out to be independent of ZFC, for it is provably equal to the eventually different number $\frak{d}({\neq^*})$, which is the same as the covering number of the meager ideal $\text{cov}(\mathcal{M})$. I thus place all the various mastermind numbers, defined for the natural variations of the game, into the hierarchy of cardinal characteristics of the continuum.

Infinite Wordle and the mastermind numbers, CUNY Logic Workshop, March 2022

This will be an in-person talk for the CUNY Logic Workshop at the Graduate Center of the City University of New York on 11 March 2022.

Abstract. I shall introduce and consider the natural infinitary variations of Wordle, Absurdle, and Mastermind. Infinite Wordle extends the familiar finite game to infinite words and transfinite play—the code-breaker aims to discover a hidden codeword selected from a dictionary $\Delta\subseteq\Sigma^\omega$ of infinite words over a countable alphabet $\Sigma$ by making a sequence of successive guesswords, receiving feedback after each guess concerning its accuracy. For any dictionary using the usual 26-letter alphabet, for example, the code-breaker can win in at most 26 guesses, and more generally in $n$ guesses for alphabets of finite size $n$. Meanwhile, for some dictionaries on an infinite alphabet, infinite play is required, but the code-breaker can always win by stage $\omega$ on a countable alphabet, for any fixed dictionary. Infinite Mastermind, in contrast, is a subtler game than Wordle because only the number and not the position of correct bits is given. When duplication of colors is allowed, nevertheless, the code-breaker can still always win by stage $\omega$, but in the no-duplication variation, no countable number of guesses (even transfinite) is sufficient for the code-breaker to win. I therefore introduce the mastermind number, denoted $\frak{mm}$, defined to be the size of the smallest winning no-duplication Mastermind guessing set, a new cardinal characteristic of the continuum, which I prove is bounded below by the additivity number $\text{add}(\mathcal{M})$ of the meager ideal and bounded above by the covering number $\text{cov}(\mathcal{M})$. In particular, the precise value of the mastermind number is independent of ZFC and can consistently be strictly between $\aleph_1$ and the continuum $2^{\aleph_0}$. In simplified Mastermind, where the feedback given at each stage includes only the numbers of correct and incorrect bits (omitting information about rearrangements), then the corresponding simplified mastermind number is exactly the eventually different number $\frak{d}(\neq^*)$.

I am preparing an article on the topic, which will be available soon.

Pluralism in the ontology of mathematics, MaMuPhi, Paris, February 2022

This will be a talk for the conference L’indépendance mathématique et ses limites logiques, an instance of the MAMUPHI seminar (mathématiques – musique – philosophie), organized by Mirna Džamonja, 12 February 2022. Most talks will be in-person in Paris, but my talk will be on Zoom via https://u-pec-fr.zoom.us/j/86448599486 at 4:30 pm CET (10:30 am EST).


Abstract: What is the nature of mathematical ontology—what does it mean to make existence assertions in mathematics? Is there an ideal mathematical realm, a mathematical universe, that those assertions are about? Perhaps there is more than one. Does every mathematical assertion ultimately have a definitive truth value? I shall lay out some of the back-and-forth in what is currently a vigorous debate taking place in the philosophy of set theory concerning pluralism in the set-theoretic foundations, concerning whether there is just one set-theoretic universe underlying our mathematical claims or whether there is a diversity of possible set-theoretic conceptions.

Infinite Hex is a draw

  • J. D. Hamkins and D. Leonessi, “Infinite Hex is a draw,” Mathematics arXiv, 2022.
    [Bibtex]
    @ARTICLE{HamkinsLeonessi:Infinite-Hex-is-a-draw,
    author = {Joel David Hamkins and Davide Leonessi},
    title = {Infinite Hex is a draw},
    journal = {Mathematics arXiv},
    year = {2022},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    eprint = {2201.06475},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/infinite-hex-is-a-draw},
    }

Download the article at https://arxiv.org/abs/2201.06475.

Abstract. We introduce the game of infinite Hex, extending the familiar finite game to natural play on the infinite hexagonal lattice. Whereas the finite game is a win for the first player, we prove in contrast that infinite Hex is a draw—both players have drawing strategies. Meanwhile, the transfinite game-value phenomenon, now abundantly exhibited in infinite chess and infinite draughts, regrettably does not arise in infinite Hex; only finite game values occur. Indeed, every game-valued position in infinite Hex is intrinsically local, meaning that winning play depends only on a fixed finite region of the board. This latter fact is proved under very general hypotheses, establishing the conclusion for all simple stone-placing games.

This is my second joint project with Davide Leonessi, the first being our work on Transfinite games values in infinite draughts, both projects growing out of his work on his MSc in MFoCS at Oxford, for which he earned a distinction in September 2021.

Here is a convenient online Hex player, for those who want to improve their game: http://www.lutanho.net/play/hex.html.

The model theory of set-theoretic mereology, Notre Dame Math Logic Seminar, February 2022

This will be a talk for the Mathematical Logic Seminar at the University of Notre Dame on 8 February 2022 at 2 pm in 125 Hayes Healy.

Abstract. Mereology, the study of the relation of part to whole, is often contrasted with set theory and its membership relation, the relation of element to set. Whereas set theory has found comparative success in the foundation of mathematics, since the time of Cantor, Zermelo and Hilbert, mereology is strangely absent. Can a set-theoretic mereology, based upon the set-theoretic inclusion relation ⊆ rather than the element-of relation ∈, serve as a foundation of mathematics? How well is a model of set theory ⟨M,∈⟩ captured by its mereological reduct ⟨M,⊆⟩? In short, how much set theory does set-theoretic mereology know? In this talk, I shall present results on the model theory of set-theoretic mereology that lead broadly to negative answers to these questions and explain why mereology has not been successful as a foundation of mathematics. (Joint work with Makoto Kikuchi)

Handwritten lecture notes

See the research papers:

  • Set-theoretic mereology
    • [DOI] J. D. Hamkins and M. Kikuchi, “Set-theoretic mereology,” Logic and Logical Philosophy, Special issue “Mereology and beyond, part II”, vol. 25, iss. 3, p. 285–308, 2016.
      [Bibtex]
      @ARTICLE{HamkinsKikuchi2016:Set-theoreticMereology,
      author = {Joel David Hamkins and Makoto Kikuchi},
      title = {Set-theoretic mereology},
      journal = {Logic and Logical Philosophy, Special issue ``Mereology and beyond, part II''},
      editor = {A.~C.~Varzi and R.~Gruszczy{\'n}ski},
      year = {2016},
      volume = {25},
      number = {3},
      pages = {285--308},
      month = {},
      doi = {10.12775/LLP.2016.007},
      note = {},
      eprint = {1601.06593},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      url = {http://jdh.hamkins.org/set-theoretic-mereology},
      abstract = {},
      keywords = {},
      source = {},
      ISSN = {1425-3305},
      MRCLASS = {03A05 (03E70)},
      MRNUMBER = {3546211},
      }
  • The inclusion relations of the countable models of set theory are all isomorphic
    • J. D. Hamkins and M. Kikuchi, “The inclusion relations of the countable models of set theory are all isomorphic,” ArXiv e-prints, 2017.
      [Bibtex]
      @ARTICLE{HamkinsKikuchi:The-inclusion-relations-of-the-countable-models-of-set-theory-are-all-isomorphic,
      author = {Joel David Hamkins and Makoto Kikuchi},
      title = {The inclusion relations of the countable models of set theory are all isomorphic},
      journal = {ArXiv e-prints},
      editor = {},
      year = {2017},
      volume = {},
      number = {},
      pages = {},
      month = {},
      doi = {},
      note = {Manuscript under review},
      eprint = {1704.04480},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      url = {http://jdh.hamkins.org/inclusion-relations-are-all-isomorphic},
      abstract = {},
      keywords = {under-review},
      source = {},
      }
Notre Dame campus in snow

Bi-interpretation in set theory, Oberwolfach Set Theory Conference, January 2022

This was a talk for the 2022 Set Theory Conference at Oberwolfach, which was a hybrid of in-person talks and online talks on account of the Covid pandemic. I gave my talk online 10 January 2022.

Abstract: Set theory exhibits a truly robust mutual interpretability phenomenon: in any model of one set theory we can define models of diverse other set theories and vice versa. In any model of ZFC, we can define models of ZFC + GCH and also of ZFC + ¬CH and so on in hundreds of cases. And yet, it turns out, in no instance do these mutual interpretations rise to the level of bi-interpretation. Ali Enayat proved that distinct theories extending ZF are never bi-interpretable, and models of ZF are bi-interpretable only when they are isomorphic. So there is no nontrivial bi-interpretation phenomenon in set theory at the level of ZF or above.  Nevertheless, for natural weaker set theories, we prove, including ZFC- without power set and Zermelo set theory Z, there are nontrivial instances of bi-interpretation. Specifically, there are well-founded models of ZFC- that are bi-interpretable, but not isomorphic—even $\langle H_{\omega_1},\in\rangle$ and $\langle H_{\omega_2},\in\rangle$ can be bi-interpretable—and there are distinct bi-interpretable theories extending ZFC-. Similarly, using a construction of Mathias, we prove that every model of ZF is bi-interpretable with a model of Zermelo set theory in which the replacement axiom fails. This is joint work with Alfredo Roque Freire.

Philosophy of Mathematics, Notre Dame Spring 2022

Philosophy of Mathematics
43906 01 (31349)

43906 02 (32481) – Reserved for Glynn Honors Program
Joel David Hamkins, Professor of Philosophy and Mathematics
3:30-4:45 TR, DeBartolo Hall 301
Cross-listed with MATH 40920 01

This series of self-contained seminar lectures on the philosophy of mathematics is intended for students in philosophy and mathematics. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light.

O’Hara Professor of Philosophy and Mathematics, University of Notre Dame

I have now taken up a position at the University of Notre Dame as the O’Hara Professor of Philosophy and Mathematics, beginning January 2022.

My appointment is with the Department of Philosophy with an affiliation with the Department of Mathematics. I expect to be teaching and working with students both in philosophy and mathematics.

Notre Dame offers a unique joint PhD degree program between mathematics and philosophy, the program in logic and the foundations of mathematics. For Notre Dame undergraduates of any major, I encourage you to consider the mathematical philosophy minor.

Notre Dame has strong research groups in logic in both philosophy and mathematics. In philosophy, Notre Dame recently came out very well in the speciality PGR rankings in philosophy of mathematics (#2, tied with NYU, Princeton, behind Harvard), mathematical logic (#2 tied with CMU, behind Harvard), and philosophical logic (group 2). In mathematics, Notre Dame has a strong research group in mathematical logic.

Coming to Agreement, a logic puzzle for Oxford admissions interviews

Let me dive right in with the main puzzle.

Main puzzle. You are a contestant on a game show, known for having perfectly logical contestants. There is another contestant, whom you’ve never met, but whom you can count on to be perfectly logical, just as logical as you are.

The game is cooperative, so either you will both win or both lose, together. Imagine the stakes are very high—perhaps life and death. You and your partner are separated from one another, in different rooms. The game proceeds in turns—round 1, round 2, round 3, as many as desired to implement your strategy.

On each round, each contestant may choose either to end the game and announce a color (any color) to the game host or to send a message (any kind of message) to their partner contestant, to be received before the next round. Messages are sent simultaneously, crossing in transit.

You win the game if on some round both players opt to end the game and announce a color to the host and furthermore they do so with exactly the same color. That is, you win if you both halt the game on the same round with the same color. lf only one player announces a color, or if both do but the colors don’t match, then the game is over, but you have lost.

Round 1 is about to begin. What do you do?

Before getting to solutions, I should also like to mention several variations of the puzzle.

Alternation variation. In this variation of the puzzle, the contestants alternate in their right to send messages—only contestant 1 can send on round 1, then contestant 2 on round 2 and so forth, but still they aim to announce the same color on a round. You are contestant 1—what do you do?

Collision variation. In this variation, players may opt on each round either to end the game and announce a color, to send a message, or to do nothing. But the new thing is that if both players opt to send a message, then the messages collide and are not delivered, although an error message is generated (so the players know what happened). What do you do?

Pigeon variation. This version is like the alternating turn variation, except that now the contestants are separated at much greater distance, and the messages are sent by carrier pigeon, so neither can be sure that the messages actually arrive. You are contestant 1—what do you do?

Post your solutions in the comments! Please do so before reading the rest of this post, and then come back to read more. There are lively discussions occuring on the Twitter thread about this puzzle, on Hacker News, on www.reddit/r/mathriddles, and on www.reddit/r/philosophy.

—————————–

We had used these puzzles in our admissions interviews of candidates for a place at Oxford University in the degree courses Math/philosophy, CS/philosophy, and PPE at University College, Oxford. The candidates were high-school students, mostly 17 years old, having made the interview shortlist on the basis of the rest of their applications, including A-level scores, university entrance exam, essay, and recommendations (all considered in light of relative advantage/disadvantage). The interviews were an in-depth back-and-forth discussion, as much as could be had in about 25 minutes. These interviews, of course, are just one component among many in regard to the difficult admissions decision, a chance for the candidate to show us how they think through a problem, how well they can explain their ideas, how well they take hints and suggestions. In every interview, we had paused at a certain stage, when the candidate had a fully formed argument for one of the variations, and asked them to undertake an integrative exercise, summarizing as clearly as they could the entire problem and solution and how they expected it to play out. Since these were interviews for joint philosophy degrees, in my view this step was a key part of the interview, measuring the ability of the candidate to integrate what they had learned from the discussion and to present a complete, coherent argument.

Several of these puzzles are rather open-ended, not necessarily with a clear-cut objectively correct answer, although there are certain important issues that arise and that we had hoped the candidates would realize. So let me now discuss the puzzles in detail and the aspects of them that I find interesting.

For the main puzzle, it seems clear that one should not announce a color to the host straight away in round 1, because it seems not likely enough that the other contestant would also do so with exactly the same color. Rather, one should use the messaging capability somehow to agree on the color and round number on which to end the game. We should only announce, if we have both clearly expressed a plan to announce a specific color on a specific round.

At first, it might seem reasonable to send a message along the lines of “Let’s both announce red on round 3; please confirm in round 2.” The hope would be that the other player would indeed confirm on round 2, and then both would announce the final color of red on round 3.

That idea would work, if we were taking turns in sending messages, as in the alternation version of the puzzle. But in the main puzzle, the players are sending their messages simultaneously, and there is a difficulty for the previous proposal that can be realized by considering what kind of message we might expect to be receiving from our partner on round 1. Namely, perhaps they had a similar idea. It would be a lucky case indeed, if they had had exactly the same idea, also proposing to announce red in round 3. In that event, we would both confirm in round 2 and win with red in round 3.

But a more problematic case would occur if our partner had had a very similar idea, but happened to have made the proposal with a different color. Perhaps in round 1 our partner would have sent the message, “Let’s both announce blue on round 3; please confirm in round 2.” What shall we do then in round 2? If I decide to try to stick with my original red color, I might say, “Let’s use red in round 3”, then the other player might similarly decide to stick with blue, and we would still be at an impasse. Alternatively, if I decide to defer and switch to blue, perhaps they also defer and switch to red. What is clear is that we can’t be sure of confirming on the same color in round 2, and clearly we shouldn’t announce in round 3 with the color choice still unsettled. So the procedure we have discussed so far seems unsuitable.

A deeper contemplation of the problem reveals that this issue of the other contestant doing something very similar, but perhaps with a different color, is a fundamental obstacle to many solution attempts. There is a fundamental symmetry in play between the contestants. Since the messages are sent and received at the same time, and both players are equally logical, it could be that we both end up sending the same kind of message each time, except with different colors. We need somehow to agree on a color and a round number, but it seems that however we decide to make a proposal, it would be equally logical for our partner to make a similar proposal, but with colors permuted somehow.

We seem to need to break the symmetry somehow. Perhaps one might hope to use the alphabetically least color, amongst the two colors that have been proposed so far. That would seem to be a perfectly reasonable way to break the symmetry. But the problem here is that there are also many other perfectly reasonable ways to break the symmetry—the shortest wavelength color, the shorter color word, the color proposed by the younger person, by the older person, and so on. The difficulty is that any given proposal might be faced with a similar but equally reasonable proposal about how to break the symmetry. If I had proposed one such criterion, perhaps my partner proposes another, and we haven’t made any progress, but rather only replaced the difficulty of agreeing on the color with the difficulty of agreeing on the decision criterion of how to decide.

A key insight comes with the idea to use randomness. Suppose I had said in round 1, “I suggest we both announce red next round; I shall do so, if you also suggest this,” but you had said, “I suggest we both announce blue next round; I shall do so, if you also suggest this.” But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color. That is, if in the first round we each happen to mention a color (whether or not my partner’s message was of the specific form I had mentioned), then I am going on every round to send a message as above, but using one of the two colors randomly. If you logically also choose to do this, then we are very likely to happen to choose the same color on some round eventually, and then win on the following round. This randomzing strategy thus seems fairly sound as a means to come to agreement, and if the partner also realizes this we should expect to win quickly, in just a few rounds with high likelihood. For this reason, I find this to be the best strategy.

A slightly more abstract way to describe the strategy I am proposing is that the symmetry between the players will need to be broken by us agreeing which of us will be leading the process and which of us will follow. I can flip a coin each round to decide if I should try to be leader or follower on that round. On heads, I shall propose a specific plan, “let’s say red next round, if your message indicates that you will follow my suggestion.” On tails, I shall send a message saying, “I am going to follow your plan of action, if you send one this round.” In this way, we are likely in a few rounds to have established a leader and follower, and win shortly afterward.

Some student candidates and commentators had proposed an interesting idea of trying to blend the two colors. This would be a way of coming to an agreement, but without needing to break the symmetry between the players. If I had proposed initially that we should announce red and you had proposed blue, then the idea is that logically we should both try to average these colors and say purple. I like this idea a lot, but it seems problematic in light of the fact that we don’t have such a clear and unambiguous means of combining colors. For example, should we mix the colors in the manner of mixing paint or rather in the manner of mixing colored light, which produces completely different results? Even when mixing red+blue, I might say purple and you might say violet. And what of stranger color combinations, such as orange+green? If we were using rgb colors, then some colors are simply adjacent in the color space (or an even distance away), and so they have no exact average mixing. Furthermore, why should we use rgb rather than cmyk or another color space system? And color mixing does not work identically for these two systems. For these reasons, I find the color mixing idea ultimately less than completely successful.

The alternation variation of the puzzle admits an easy solution, since the symmetry is broken already by the rules of the game. Player 1 will be the first to send a message, and can simply say, “I shall announce red on round 2; if you do so as well then we shall win.” There would be no reason for player 2 not to follow along, and so the players can expect to win on round 2.

Some candidates had suggested a confirmation round, having player 1 say, “let’s say red on round 3, confirm if that is agreeable.” Then both players would confirm the intention on round 2, and win on round 3. This is also successful, but it seems to me that the confirmation step is not strictly needed.

The collision variation is an interesting hybrid, because although there is a symmetry between the players in terms of how the rules apply to them, the symmetry is broken in the event that one sends a message and the other does not. The best solution here seems to be a random solution. Namely, flip a coin to decide whether to send a message or stay silent. On heads, send the message “Announce red on next round, if this message gets through.” On tails, do nothing, and plan to follow whatever is suggested on the message that might be received. Because of the randomness, it is very likely that in a few rounds a message gets through one way or the other, with a quick win straight afterward.

The pigeon variation is simply a version of the two-generals problem. The first player can try to propose a specific plan, naming a round and color, and ask for confirmation. But the confirmation itself will need to be confirmed, if the other player is to want certainty. But in this case the confirmation of the confirmation will need to be confirmed, and so on ad infinitum. No finite number of confirmations of receipt will be enough, even if all are received, since if $n$ confirmations suffice to attain mutual certainty, then the last confirmation needn’t be sent, since the protocol would work even if it didn’t arrive, and so $n-1$ should also suffice, a contradiction.

Meanwhile, one can attain very high degree of confidence in the plan. If on round 1 the first player sends the message, “We shall say red on round 1000, please confirm,” then he might hope it gets through and confirmation received. On each subsequent round, he should send this message again, together with a complete record of all prior messages sent/received. Player 2, if receiving the message on round 1 should simply follow along and send confirmations; but if nothing was received on round 1, he should not start a competing plan, which would only reintroduce the priority issue of the main puzzle, since the symmetry is already clearly broken for this version with player 1 in the leading role. So if no message was received, player 2 should simply reply with “sorry, no message received; please resend.” Eventually, messages are likely to get through and the two players will be on track to win with high probability. The players should plan on announcing red on round 1000 according to the plan, even if confirmations are missed. One can increase the probability by increasing round 1000 to a much higher number, presuming that the players can keep careful track of the round numbers. It would seem to be a mistake ever to try to change the round number or the color after some messages are sent, since perhaps the originals were received and only the cofirmations were missed, and there would be abundant confusion to have two or more plans in play.

In the admissions interviews, which were generally less than 25 minutes, we were happy if a candidate got to the realization of the symmetry issue in the main puzzle, before going on to the alternating version, which most students got quickly, and then the collision version, where the randomness idea seemed to arise more naturally. The best candidates were then able to realize how to apply the randomness idea to the main version. With the pigeon version of the puzzle, successful candidates realized the need to achieve confirmation and confirmation of confirmation, and a few put this together to mount the impossibility argument for the case of certainty, and most realized how to increase the likelihood of success by picking a distant round and repeating messages. It was quite enjoyable for me to discuss these problems with so many very sharp student candidates.

Let me close by mentioning a few observations that surprised me about using the puzzles in an interview setting.

The first observation is the remarkable amount of personality that was revealed by the candidate’s choices in the puzzles. Some candidates tended to follow what might be called a leader’s approach (or the bully strategy?), attempting in the main puzzle to achieve agreement by conveying obstinateness in the color choice, to convince the other person to change sides as a way of coming to agreement. An equal number of other candidates tried instead to be deferential, sending messages that they would agree to use whichever color the other person wanted. Of course, each of these strategies works fine when paired with the other, but when paired with exactly the same personality, the methods face the symmetry problem we discussed earlier. Some brilliant candidates pointed out that the role that these personality differences played in the puzzle—it was very unlikely that the two contestants would be perfectly balanced in their personalities, and so the symmetry would be broken simply because one candidate would be slightly more insistent or slightly more deferential. And I have to say that realistically, this is how the puzzle would actually be solved in practice.

Another observation was that the candidates overwhelmingly chose red as their color, whenever they mentioned a specific color. About 2/3 or more did so. Far behind this was blue, in second place, and then we had a very small number of mentions of orange, green, yellow, and black.

I really enjoyed using this puzzle for the interviews, and I feel it helped us to choose a really great incoming class.

Art by Erin Carmody.

The hierarchy of geometric constructibility: can we go back?

I have recently become interested in the hierarchy of relative constructibility in geometry (see the discussion on my Twitter thread). From a given collection of points in the plane, we may proceed to construct other points using the classical tools of straightedge and compass. This induces a hierarchy of relative constructiblity, namely, for any two sets of points $X$ and $Y$ in the plane, we may say that $X$ is constructible from $Y$, written as $$X\trianglelefteq Y$$ if for every point $A\in X$, there is a construction procedure using only straightedge and compass proceeding from points in $Y$ and constructing $A$. And so we are faced with a hierarchy of constructibility.

Perhaps one might ask immediately whether this is genuinely a hierarchy. A central case occurs with pairs of points, since one often proceeds in geometry with the idea of a unit segment having already been fixed.

Question 1. Given two distinct points A and B, suppose that distinct points C and D are constructible by straightedge and compass. Can we go back? That is, must A and B both be constructible from C and D?

The answer, surprisingly, is Yes! This is a sense in which the relative constructibility notion is an equivalence relation rather than a hierarchy, since it shows that if AB can construct CD, than it is also true conversely. Since constructibility is also transitive, this shows that the relative constructibility is an equivalence relation on pairs of points in the plane.

Before addressing the question, let me first dispense with a distracting line of reasoning that suggests a wrong answer to this question. Suppose that we have a segment AB of length $\sqrt[3]2$, a nonconstructible number. Since the constructible numbers are closed under multiplication, this might suggest that from AB we can construct a segment of length 2, and therefore also construct a segment CD of length 1. But from a segment of length 1, we can never construct a segment of length $\sqrt[3]2$, because the duplication of the cube is impossible. So this would suggest a negative answer to the question. Is it right?

But no, this distracting counter-argument is not correct. The reason is that although the constructible numbers are indeed closed under multiplication, the construction methods requires the consultation of a fixed unit segment. That is, to prove that from a segment of length $a$ and a segment of length $b$ one can construct a segment of length $ab$, we require the use of fixed unit segment of length $1$. Indeed, it will follow from our analysis here that one cannot omit this consultation of a unit segment from the construction—we cannot in general construct the cube of a segment just from the segment itself.

So let me prove the answer to question 1 is positive. Suppose that from distinct points AB we can construct distinct points CD. Performing excactly the same construction process again, but proceeding from points CD as input, we construct points EF. From points CD we can see how CD are related to EF, forming a quadrilateral CDFE.

The point is that we may now construct the points A and B from C and D by simply inverting this similarity. (This was also observed by user @ZenoRogue on Twitter.) Namely, the two quadrilaterals ABDC and CDFE are similar, and so have all the same angles. So the line AC is constructible from CD by the angle ACD, which is the same as CEF, and the distance AC is scaled from CE by the same factor that CD is related to EF. So from CD we can construct this similar quadrilateral, and thereby construct both A and B.

Question 2. Given three distinct points forming a triangle ABC, suppose that we can construct triangle DEF by straightedge and compass. Can we go back? That is, must A,B, and C be constructible from D,E,F?

The question is of course similar to question 1, which had a positive answer. Nevertheless, the answer here is negative. The reason is that the original idea we had with question 1 concerning $\sqrt[3]2$ now works here to refute question 2. Namely, let ABC be a right triangle where AB has length 1 but AC has length $\sqrt[3]2$.

From the triangle ABC, we may easily construct the triangle ABD, where AD has length 1, since in fact the point D is constructible from the segment AB alone. But from ABD, which is a right triangle with both legs of length 1, we shall be unable to construct the number $\sqrt[3]2$, and consequently unable to construct the point C. So although ABD is constructible from ABC, the point C is not constructible from points ABD. This is therefore a counterexample to question 2, which therefore must be answered in the negative.

Another argument, offered by Ed Wagstaff, is that from an angle trisection we can construct the original angle, but we can’t necessarily construct the trisection from the original angle.

Finally, I should like to understand the nature of the relative hierarchy of constructibility better. $$X\trianglelefteq Y$$ What is the nature of relative constructibility of sets of points in the plane? For example, one question I didn’t know how to answer at first is the following:

Question 3. Is the hierarchy of relative constructibility a dense order? That is, if the set $X$ is constructible from $Y$ but not conversely, must there be a set of points $Z$ strictly in between? $$X\lhd Y\quad\implies\quad\exists Z\quad X\lhd Z\lhd Y?$$

In an exchange on Twitter with David Madore, I had thought that we answered the question negatively, but now I am not at all sure of that argument (and thanks to Gabin for the comments below!), and so I have deleted the wrong argument here. Question 3 seems currently to be open.

I have now asked question 3 on MathOverflow: Is the hierarchy of relative geometric constructibility by straightedge and compass a dense order?

The surprising strength of reflection in second-order set theory with abundant urelements, Konstanz, December 2021

This will be talk for the workshop Philosophy of Set Theory held at the University of Konstanz, 3 – 4 December 2021 — in person!

Update: Unfortunately, the workshop has been cancelled (perhaps postponed to next year) in light of the Covid resurgence.

Abstract. I shall analyze the roles and interaction of reflection and urelements in second-order set theory. Second-order reflection already exhibits large cardinal strength even without urelements, but recent work shows that in the presence of abundant urelements, second-order reflection is considerably stronger than might have been expected—at the level of supercompact cardinals. This is joint work with Bokai Yao (Notre Dame).

Infinite draughts and the logic of infinitary games, Oslo, November 2021

This will be a talk 11 November 2021 for the Oslo Seminar in Mathematical Logic, meeting online via Zoom at 10:15am CET (9:15am GMT) at Zoom: 671 7500 0197

Abstract. I shall give an introduction to the logic of infinite games, including the theory of transfinite game values, using the case of infinite draughts as a principal illustrative instance. Infinite draughts, also known as infinite checkers, is played like the finite game, but on an infinite checkerboard stretching without end in all four directions. In recent joint work with Davide Leonessi, we proved that every countable ordinal arises as the game value of a position in infinite draughts. Thus, there are positions from which Red has a winning strategy enabling her to win always in finitely many moves, but the length of play can be completely controlled by Black in a manner as though counting down from a given countable ordinal. This result is optimal for games having countably many options at each move—in short, the omega one of infinite draughts is true omega one.