Games with the computable-play paradox

Posted on March 28, 2017 by Joel David Hamkins

Let me tell you about a fascinating paradox arising in certain infinitary two-player games of perfect information. The paradox, namely, is that there are games for which our judgement of who has a winning strategy or not depends on whether we insist that the players play according to a deterministic computable procedure. In the the space of computable play for these games, one player has a winning strategy, but in the full space of all legal play, the other player can ensure a win.

The fundamental theorem of finite games, proved in 1913 by Zermelo, is the assertion that in every finite two-player game of perfect information — finite in the sense that every play of the game ends in finitely many moves — one of the players has a winning strategy. This is generalized to the case of open games, games where every win for one of the players occurs at a finite stage, by the Gale-Stewart theorem 1953, which asserts that in every open game, one of the players has a winning strategy. Both of these theorems are easily adapted to the case of games with draws, where the conclusion is that one of the players has a winning strategy or both players have draw-or-better strategies.

Let us consider games with a computable game tree, so that we can compute whether or not a move is legal. Let us say that such a game is computably paradoxical, if our judgement of who has a winning strategy depends on whether we restrict to computable play or not. So for example, perhaps one player has a winning strategy in the space of all legal play, but the other player has a computable strategy defeating all computable strategies of the opponent. Or perhaps one player has a draw-or-better strategy in the space of all play, but the other player has a computable strategy defeating computable play.

Examples of paradoxical games occur in infinite chess. We described such a paradoxical position in my paper Transfinite games values in infinite chess by giving a computable infinite chess position with the property that both players had drawing strategies in the space of all possible legal play, but in the space of computable play, then white had a computable strategy defeating any particular computable strategy for black.

For a related non-chess example, let $T$ be a computable subtree of $2^{<\omega}$ having no computable infinite branch, and consider the game in which black simply climbs in this tree as white watches, with black losing whenever he is trapped in a terminal node, but winning if he should climb infinitely. This game is open for white, since if white wins, this is known at a finite stage of play. In the space of all possible play, Black has a winning strategy, which is simply to climb the tree along an infinite branch, which exists by König’s lemma. But there is no computable strategy to find such a branch, by the assumption on the tree, and so when black plays computably, white will inevitably win.

For another example, suppose that we have a computable linear order $\lhd$ on the natural numbers $\newcommand\N{\mathbb{N}}\N$, which is not a well order, but which has no computable infinite descending sequence. It is a nice exercise in computable model theory to show that such an order exists. If we play the count-down game in this order, with white trying to build a descending sequence and black watching. In the space of all play, white can succeed and therefore has a winning strategy, but since there is no computable descending sequence, white can have no computable winning strategy, and so black will win every computable play.

There are several proofs of open determinacy (and see my MathOverflow post outlining four different proofs of the fundamental theorem of finite games), but one of my favorite proofs of open determinacy uses the concept of transfinite game values, assigning an ordinal to some of the positions in the game tree. Suppose we have an open game between Alice and Bob, where the game is open for Alice. The ordinal values we define for positions in the game tree will measure in a sense the distance Alice is away from winning. Namely, her already-won positions have value $0$, and if it is Alice’s turn to play from a position $p$, then the value of $p$ is $\alpha+1$, if $\alpha$ is minimal such that she can play to a position of value $\alpha$; if it is Bob’s turn to play from $p$, and all the positions to which he can play have value, then the value of $p$ is the supremum of these values. Some positions may be left without value, and we can think of those positions as having value $\infty$, larger than any ordinal. The thing to notice is that if a position has a value, then Alice can always make it go down, and Bob cannot make it go up. So the value-reducing strategy is a winning strategy for Alice, from any position with value, while the value-maintaining strategy is winning for Bob, from any position without a value (maintaining value $\infty$). So the game is determined, depending on whether the initial position has value or not.

What is the computable analogue of the ordinal-game-value analysis in the computably paradoxical games? If a game is open for Alice and she has a computable strategy defeating all computable opposing strategies for Bob, but Bob has a non-computable winning strategy, then it cannot be that we can somehow assign computable ordinals to the positions for Alice and have her play the value-reducing strategy, since if those values were actual ordinals, then this would be a full honest winning strategy, even against non-computable play.

Nevertheless, I claim that the ordinal-game-value analysis does admit a computable analogue, in the following theorem. This came out of a discussion I had recently with Noah Schweber during his recent visit to the CUNY Graduate Center and Russell Miller. Let us define that a computable open game is an open game whose game tree is computable, so that we can tell whether a given move is legal from a given position (this is a bit weaker than being able to compute the entire set of possible moves from a position, even when this is finite). And let us define that an effective ordinal is a computable relation $\lhd$ on $\N$, for which there is no computable infinite descending sequence. Every computable ordinal is also an effective ordinal, but as we mentioned earlier, there are non-well-ordered effective ordinals. Let us call them computable pseudo-ordinals.

Theorem. The following are equivalent for any computable game, open for White.

White has a computable strategy defeating any computable play by Black.
There is an effective game-value assignment for white into an effective ordinal $\lhd$, giving the initial position a value. That is, there is a computable assignment of some positions of the game, including the first position, to values in the field of $\lhd$, such that from any valued position with White to play, she can play so as to reduce value, and with Black to play, he cannot increase the value.

Proof. ($2\to 1$) Given the computable values into an effective ordinal, then the value-reducing strategy for White is a computable strategy. If Black plays computably, then together they compute a descending sequence in the $\lhd$ order. Since there is no computable infinite descending sequence, it must be that the values hit zero and the game ends with a win for White. So White has a computable strategy defeating any computable play by Black.

($1\to 2$) Conversely, suppose that White has a computable strategy $\sigma$ defeating any computable play by Black. Let $\tau$ be the subtree of the game tree arising by insisting that White follow the strategy $\sigma$, and view this as a tree on $\N$, a subtree of $\N^{<\omega}$. Imagine the tree growing downwards, and let $\lhd$ be the Kleene-Brouwer order on this tree, which is the lexical order on incompatible positions, and otherwise longer positions are lower. This is a computable linear order on the tree. Since $\sigma$ is computably winning for White, the open player, it follows that every computable descending sequence in $\tau$ eventually reaches a terminal node. From this, it follows that there is no computable infinite descending sequence with respect to $\lhd$, and so this is an effective ordinal. We may now map every node in $\tau$, which includes the initial node, to itself in the $\lhd$ order. This is a game-value assignment, since on White’s turn, the value goes down, and it doesn’t go up on Black’s turn. QED

Corollary. A computable open game is computably paradoxical if and only if it admits an effective game value assignment for the open player, but only with computable pseudo-ordinals and not with computable ordinals.

Proof. If there is an effective game value assignment for the open player, then the value-reducing strategy arising from that assignment is a computable strategy defeating any computable strategy for the opponent. Conversely, if the game is paradoxical, there can be no such ordinal-assignment where the values are actually well-ordered, or else that strategy would work against all play by the opponent. QED

Let me make a few additional observations about these paradoxical games.

Theorem. In any open game, if the closed player has a strategy defeating all computable opposing strategies, then in fact this is a winning strategy also against non-computable play.

Proof. If the closed player has a strategy $\sigma$ defeating all computable strategies of the opponent, then in fact it defeats all strategies of the opponent, since any winning play by the open player against $\sigma$ wins in finitely many moves, and therefore there is a computable strategy giving rise to the same play. QED

Corollary. If an open game is computably paradoxical, it must be the open player who wins in the space of computable play and the closed player who wins in the space of all play.

Proof. The theorem shows that if the closed player wins in the space of computable play, then that player in fact wins in the space of all play. QED

Corollary. There are no computably paradoxical clopen games.

Proof. If the game is clopen, then both players are closed, but we just argued that any computable strategy for a closed player winning against all computable play is also winning against all play. QED

Buckets of fish!

Posted on March 4, 2017 by Joel David Hamkins

Let me tell you about the game Buckets of fish.

This is a two-player game played with finitely many buckets in a line on the beach, each containing a finite number of fish. There is also a large supply of additional fish available nearby, fresh off the boats.

Taking turns, each player selects a bucket and removes exactly one fish from it and then, if desired, adds any finite number of fish from the nearby supply to the buckets to the left.

For example, if we label the buckets from the left as 1, 2, 3 and so on, then a legal move would be to take one fish from bucket 4 and then add ten fish to bucket 1, no fish to bucket 2, and ninety-four fish to bucket 3. The winner is whoever takes the very last fish from the buckets, leaving them empty.

Since huge numbers of fish can often be added to the buckets during play, thereby prolonging the length of play, a skeptical reader may wonder whether the game will necessarily come to an end. Perhaps the players can prolong the game indefinitely? Or must it always come to an end?

Question. Does every play of the game Buckets of fish necessarily come to an end?

The answer is yes, every game must eventually come to a completion. I shall give several arguments.

Theorem. Every play of the game Buckets of fish ends in finitely many moves. All the fish in the buckets, including all the new fish that may have been added during play, will eventually run out by some finite stage during play.

That is, no matter how the players add fish to the buckets during play, even with an endless supply of fish from the boats, they will eventually run out of fish in the buckets and one of the players will take the last fish.

First proof. We prove the claim by (nested) induction on the number of buckets. If there is only one bucket, then there are no buckets to the left of it, and so there is no possibility in this case to add fish to the game. If the one bucket contains $k$ fish, then the game clearly ends in $k$ moves. Assume by induction that all plays using $n$ buckets end in finitely many moves, and suppose that we have a game situation with $n+1$ buckets, with $k$ fish in bucket $n+1$. We now prove by induction on $k$ that all such games terminate. This argument is therefore an instance of nested induction, since we are currently inside our proof by induction on $n$, in the induction step of that proof, and in order to complete it, we are undertaking a separate full induction on $k$. If $k=0$, then there are no fish in bucket $n+1$, and so the game amounts really to a game with only $n$ buckets, which terminates in finitely many steps by our induction hypothesis on $n$. So, let us assume that all plays with $k$ fish in bucket $n+1$ terminate in finitely many moves. Consider a situation where there are $k+1$ many fish in that bucket. I claim that eventually, one of those fish must be taken, since otherwise all the moves will be only on the first $n$ buckets, and all plays on only $n$ buckets terminate in finitely many moves. So at some point, one of the players will take a fish from bucket $n+1$, possibly adding additional fish to the earlier buckets. But this produces a situation with only $k$ fish in bucket $n+1$, which by our induction assumption on $k$ we know will terminate in finitely many steps. So we have proved that no matter how many fish are in bucket $n+1$, the game will end in finitely many moves, and so the original claim is true for $n+1$ buckets. Thus, the theorem is true for any finite number of buckets. QED

A second proof. Let me now give another proof, following an idea arising in a conversation with Miha Habič. We want to prove that there is no infinitely long play of the game Buckets of fish. Suppose toward contradiction that there is a way for the players to conspire to produce an infinite play, starting from some configuration of some finite number $n$ of buckets, each with finitely many fish in them. Fix the particular infinitely long play. Let $m$ be the right-most bucket from which a fish was taken infinitely often during that infinite course of play. It follows, for example, that $m<n$, since the top bucket can be used only finitely often, as it never gets replenished. Since bucket $m$ starts with only finitely many fish in it, and each time it is replenished, it is replenished with only finitely many fish, it follows that in order to have been used infinitely many times, it must also have been replenished infinitely often. But each time it was replenished, it was because there was some bucket further to the right that had been used. Since there are only finitely many buckets to the right of bucket $m$, it follows that one of them must have been used infinitely often. This contradicts the choice of $m$ as the right-most bucket that was used infinitely often. QED

A third proof. Let me now give a third proof, using ordinals. We shall associate with each Buckets-of-fish position a certain ordinal. With the position $$7\quad 2\quad 5\quad 24,$$ for example, we associate the ordinal $$\omega^3\cdot 24+\omega^2\cdot 5+\omega\cdot 2+7.$$ More generally, the number of fish in each bucket of a position becomes the coefficient of the corresponding power of $\omega$, using higher powers for the buckets further to the right. The key observation to make is that these associated ordinals strictly descend for every move of the game, since one is reducing a higher-power coefficient and increasing only lower-power coefficients. Since there is no infinite descending sequence of ordinals, it follows that there is no infinite play in the game Buckets of fish. This idea also shows that the ordinal game values of positions in this game are bounded above by $\omega^\omega$, and every ordinal less than $\omega^\omega$ is realized by some position. QED

OK, fine, so now we know that the game always ends. But how shall we play? What is the winning strategy? Say you are faced with buckets having fish in the amounts: $$4\quad 5\quad 2\quad 0\quad 7\quad 4$$ What is your winning move? Please give it some thought before reading further.

The winning strategy turns out to be simpler than you might have expected.

Theorem. The winning strategy in the game Buckets of fish is to play so as to ensure that every bucket has an even number of fish.

Proof. Notice first, as a warm-up, that in the case that there is only one bucket containing an even number of fish, then the second player will win, since the first player will necessarily make it odd, and then the second player will make it even again, and so on. So it will be the second player who will make it zero, winning the game. So with one bucket, the player who can make the bucket even will be the winner.

Next, notice that if you play so as to give your opponent an even number of fish in every bucket, then whatever move your opponent makes will result in an odd number of fish in the bucket from which he or she takes a fish (and possibly also an odd number of fish in some of the earlier buckets as well, if they happen to add an odd number of fish to some of them). So if you give your opponent an all-even position, then they cannot give you back an all-even position.

Finally, notice that if you are faced with a position that is not all-even, then you can simply take a fish from the right-most odd bucket, thereby making it even, and add fish if necessary to the earlier buckets so as to make them all even. In this way, you can turn any position that is not all-even into an all-even position in one move.

By following this strategy, a player will ensure that he or she will take the last fish, since the winning move is to make the all-zero position, which is an all-even position, and the opponent cannot produce an all-even position. QED

In the particular position of the game mentioned before the theorem, therefore, the winning move is to take a fish from the bucket with 7 fish and add an odd number of fish to the bucket with 5 fish, thereby producing an all-even position.

Finally, let’s consider a few variations of the game. It is clear that the all-even strategy works in the versions of the game where one is limited to add at most one fish to each of the earlier buckets, and this version of the game is actually playable, since the number of fish does not grow too much. A similar variation arises where one can either or add or remove any number of fish (or just at most one) from any of the earlier buckets, or where one can, say, add either 5 or 6 fish only to each of the earlier buckets. What is important in the argument is simply that one should be able to ensure the all-even nature of the buckets.

For a more interesting variation, consider what I call the Take 3 version of the game, where one can take either one, two or three fish from any bucket and then add any number of fish to the earlier buckets. The game must still eventually end, but what is the winning strategy?

Question. What is your strategy in the Take 3 variation of Buckets of fish?

Please post your answers in the comments, and I’ll post an answer later. One can generalize this to the Take $n$ variation, where on each turn, the player is allowed to take between 1 and $n$ fish from any bucket, and add as many fish as desired to the earlier buckets.

Another puzzling variation is where each player can take any number of fish from a bucket, and then add any number of fish to earlier buckets. Can you find a strategy for this version of the game? Please post in the comments.

Computable quotient presentations of models of arithmetic and set theory

Posted on February 27, 2017 by Joel David Hamkins

[bibtex key=GodziszewskiHamkins2017:Computable-quotient-presentations-of-models-of-arithmetic-and-set-theory]

Abstract. We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In this article, we engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

The implicitly constructible universe

Posted on February 27, 2017 by Joel David Hamkins

[bibtex key=”GroszekHamkins2019:The-implicitly-constructible-universe”]

Abstract. We answer several questions posed by Hamkins and Leahy concerning the implicitly constructible universe $\newcommand\Imp{\text{Imp}}\Imp$, which they introduced in their paper, Algebraicity and implicit definability in set theory. Specifically, we show that it is relatively consistent with ZFC that $\Imp \models \neg \text{CH}$, that $\Imp \neq \text{HOD}$, and that $\Imp \models V \neq \Imp$, or in other words, that $(\Imp)^{\Imp} \neq \Imp$.

Open and clopen determinacy for proper class games, VCU MAMLS April 2017

Posted on February 25, 2017 by Joel David Hamkins

This will be a talk for the Mid-Atlantic Mathematical Logic Seminar at Virginia Commonwealth University, a conference to be held April 1-2, 2017.

Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length $\omega$, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM. New work by Hachtman and Sato, respectively has clarified the separation of clopen and open determinacy for class games.

Lewis Chessmen This is joint work with Victoria Gitman. See our article, Open determinacy for class games.

Slides

Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

Posted on February 25, 2017 by Joel David Hamkins

This will be a talk for the CUNY Set Theory Seminar on March 10, 2017, 10:00 am in room 6417 at the CUNY Graduate Center.

Abstract. I shall prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. This is joint work with Michał Tomasz Godziszewski.

In my talk, I shall engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

All triangles are isosceles

Posted on February 11, 2017 by Joel David Hamkins

Let me share a mathematical gem with you, the following paradoxical “theorem.”

Theorem. Every triangle is isosceles.

Proof. Consider an arbitrary triangle $\triangle ABC$. Let $Q$ be the intersection of the angle bisector (blue) at $\angle A$ and the perpendicular bisector (green) of $BC$ at midpoint $P$.

Drop perpendiculars from $Q$ to $AB$ at $R$ and to $AC$ at $S$. Because $P$ is the midpoint of $BC$ and $PQ$ is perpendicular, we deduce $BQ\cong CQ$ by the Pythagorean theorem. Since $AQ$ is the angle bisector of $\angle A$, the triangles $AQR$ and $AQS$ are similar, and since they share a hypotenuse, they are congruent. It follows that $AR\cong AS$ and also $QR\cong QS$. Therefore $\triangle BQR$ is congruent to $\triangle CQS$ by the hypotenuse-leg congruence theorem. So $RB\cong SC$. And therefore,
$$AB\cong AR+RB\cong AS+SC\cong AC,$$
and so the triangle is isosceles, as desired. QED

Corollary. Every triangle is equilateral.

Proof. The previous argument proceeded from an arbitrary vertex of the triangle, and so any pair of adjacent sides in the triangle are congruent. So all three are congruent, and therefore it is equilateral. QED

Perhaps you object to my figure, because depending on the triangle, perhaps the angle bisector of $A$ passes on the other side of the midpoint $P$ of $BC$, which would make the point $Q$ lie outside the triangle, as in the following figure.

Nevertheless, essentially the same argument works also in this case. Namely, we again let $Q$ be the intersection of the angle bisector at $\angle A$ with the perpendicular bisector of $BC$ at midpoint $P$, and again drop the perpendiculars from $Q$ to $R$ and $S$. Again, we get $BQ\cong CQ$ by the Pythagorean theorem, using the green triangles. And again, we get $\triangle ARQ\cong\triangle ASQ$ since these are similar triangles with the same hypotenuse. So again, we conclude $\triangle BQR\cong\triangle CQS$ by hypotenuse-leg. So we deduce $AB\cong AR-BR\cong AS-CS\cong AC$, by subtracting rather than adding as before, and so the triangle is isosceles.

Question. What is wrong with these arguments?

Please post your answers in the comments below.

The argument is evidently due to W. W. Rouse Ball, Mathematical Recreations and Essays (1892). I first heard it years ago, when I was in graduate school. Shortly afterward, my advisor W. Hugh Woodin happened to be a little late to seminar, and so I leaped to the chalkboard and gave this proof, leaving the distinguished audience, including R. Solovay, scratching their heads for a while. Woodin arrived, but Solovay wouldn’t let him start the seminar, since he wanted to resolve the triangle argument. What fun!

Introduction to proofs, CSI Math 505, Spring 2017

Posted on January 27, 2017 by Joel David Hamkins

I shall be teaching a new course Introduction to Proofs at the CUNY College of Staten Island this semester.

The course is intended for aspiring mathematics students who are learning—perhaps for the first time in a serious way—how to write mathematical proofs. I think of it as a kind of mathematical coming-of-age course, for students on the cusp, maturing into mathematicians, who aspire to communicate mathematical truths to other mathematicians in the currency of mathematics, which is: proof.

I hope to help them learn how a mathematician makes an argument in order to establish a mathematical truth.

I have written a new book specifically for the course, Proof and the art of mathematical reasoning, which I hope will be available before too long. The text will be suitable for any kind of introduction-to-proofs or transition-to-proofs course at the undergraduate level, with a variety of elementary proofs from a broad swath of mathematical topics. I shall post some excerpts later, to give you an idea of the nature of the book, but for now let me simply list the current table of contents. The book begins in chapter one with the proof that $\sqrt{2}$ is irrational. The epilogue contains a variety of logic puzzles in epistemic logic.

Preface 5
A note to the instructor 11
Chapter 1. Begin with a classic 13
Chapter 2. Multiple proofs 21
Chapter 3. Number theory and the primes 27
Chapter 4. Mathematical Induction 37
Chapter 5. Discrete mathematics and finite combinatorics 45
Chapter 6. Pick’s theorem: a case study in Pólya’s advice 57
Chapter 7. Visual proofs 67
Chapter 8. Geometry and lattice-point regular polygons 77
Chapter 9. Relations 85
Chapter 10. Graph theory 95
Chapter 11. Order theory 105
Chapter 12. Theory of games 111
Chapter 13. Set theory 129
Chapter 14. Real analysis 139
Epilogue 153
Bibliography 171

Regula Krapf, Ph.D. 2017, University of Bonn

Posted on January 12, 2017 by Joel David Hamkins

Regula Krapf successfully defended her PhD dissertation January 12, 2017 at the University of Bonn, with a dissertation entitled, “Class forcing and second-order arithmetic.” I was a member of the dissertation examining committee. Peter Koepke was the dissertation supervisor.

Regula Krapf, Class forcing and second-order arithmetic, dissertation 2017, University of Bonn. (Slides)

Abstract. We provide a framework in a generalization of Gödel-Bernays set theory for performing class forcing. The forcing theorem states that the forcing relation is a (definable) class in the ground model (definability lemma) and that every statement that holds in a class-generic extension is forced by a condition in the generic filter (truth lemma). We prove both positive and negative results concerning the forcing theorem. On the one hand, we show that the definability lemma for one atomic formula implies the forcing theorem for all formulae in the language of set theory to hold. Furthermore, we introduce several properties which entail the forcing theorem. On the other hand, we give both counterexamples to the definability lemma and the truth lemma. In set forcing, the forcing theorem can be proved for all forcing notions by constructing a unique Boolean completion. We show that in class forcing the existence of a Boolean completion is essentially equivalent to the forcing theorem and, moreover, Boolean completions need not be unique.

The notion of pretameness was introduced to characterize those forcing notions which preserve the axiom scheme of replacement. We present several new characterizations of pretameness in terms of the forcing theorem, the preservation of separation, the existence of nice names for sets of ordinals and several other properties. Moreover, for each of the aforementioned properties we provide a corresponding characterization of the Ord-chain condition.

Finally, we prove two equiconsistency results which compare models of ZFC (with large cardinal properties) and models of second-order arithmetic with topological regularity properties (and determinacy hypotheses). We apply our previous results on class forcing to show that many important arboreal forcing notions preserve the $\Pi^1_1$-perfect set property over models of second-order arithmetic and also give an example of a forcing notion which implies the $\Pi^1_1$-perfect set property to fail in the generic extension.

Regula has now taken up a faculty position at the University of Koblenz.

Set-theoretic geology and the downward directed grounds hypothesis, Bonn, January 2017

Posted on January 10, 2017 by Joel David Hamkins

This will be a talk for the University of Bonn Logic Seminar, Friday, January 13, 2017, at the Hausdorff Center for Mathematics.

Abstract. Set-theoretic geology is the study of the set-theoretic universe $V$ in the context of all its ground models and those of its forcing extensions. For example, a bedrock of the universe is a minimal ground model of it and the mantle is the intersection of all grounds. In this talk, I shall explain some recent advances, including especially the breakthrough result of Toshimichi Usuba, who proved the strong downward directed grounds hypothesis: for any set-indexed family of grounds, there is a deeper common ground below them all. This settles a large number of formerly open questions in set-theoretic geology, while also leading to new questions. It follows, for example, that the mantle is a model of ZFC and provably the largest forcing-invariant definable class. Strong downward directedness has also led to an unexpected connection between large cardinals and forcing: if there is a hyper-huge cardinal $\kappa$, then the universe indeed has a bedrock and all grounds use only $\kappa$-small forcing.

Slides

Transfinite game values in infinite chess, including new progress, Bonn, January 2017

Posted on January 3, 2017 by Joel David Hamkins

This will be a talk January 10, 2017 for the Basic Notions Seminar, aimed at students, post-docs, faculty and guests of the Mathematics Institute, University of Bonn.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess — chess played on an infinite edgeless chessboard — as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question. This talk will include some of the latest progress, which includes a position with game value $\omega^4$.

It happens that I shall be in Bonn also for the dissertation defense of Regula Krapf, who will defend the same week, and who is one of the organizers of the seminar.

Transfinite game values in infinite chess | The mate-in-$n$ problem of infinite chess is decidable | A position in infinite chess with game value $\omega^4$ | more on infinite chess | Slides

The rearrangement number

Posted on December 26, 2016 by Joel David Hamkins

[bibtex key=BlassBrendleBrianHamkinsHardyLarson2020:TheRearrangementNumber]

Abstract. How many permutations of the natural numbers are needed so that every conditionally convergent series of real numbers can be rearranged to no longer converge to the same sum? We show that the minimum number of permutations needed for this purpose, which we call the rearrangement number, is uncountable, but whether it equals the cardinal of the continuum is independent of the usual axioms of
set theory. We compare the rearrangement number with several natural variants, for example one obtained by requiring the rearranged series to still converge but to a new, finite limit. We also compare the rearrangement number with several well-studied
cardinal characteristics of the continuum. We present some new forcing constructions designed to add permutations that rearrange series from the ground model in particular ways, thereby obtaining consistency results going beyond those that follow from comparisons with familiar cardinal characteristics. Finally we deal briefly with some variants concerning rearrangements by a special sort of permutations and with rearranging some divergent series to become (conditionally) convergent.

This project started with Michael Hardy’s question on MathOverflow, How many rearrangements must fail to alter the value of a sum before you conclude that none do? I had proposed in my answer that we should think of the cardinal in question as a cardinal characteristic of the continuum, the rearrangement number, since we could prove that it was uncountable and that it was the continuum under MA, and had begun to separate it from other familiar cardinal characteristics. Eventually, the research effort grew into the collaboration of this paper. What a lot of fun!

Colloquium talk at Vassar | Lecture notes | talk at CUNY | the original MathOverflow question

The lecture notes are for an introductory talk on the topic I had given at the Vassar College Mathematics Colloquium.

There are no regular polygons in the hexagonal lattice, except triangles and hexagons

Posted on December 8, 2016 by Joel David Hamkins

I should like to follow up my post last week about the impossibility of finding regular polygons in the integer lattice. This time, however, we shall consider the hexagonal and triangular lattices. It is easy to find lattice points that form the vertices of an equilateral triangle or a regular hexagon.

And similarly, such figures can be found also in the triangular lattice.

Indeed, the triangular and hexagonal lattices are each refinements of the other, so they will allow exactly the same shapes arising from lattice points.

But can you find a square? How about an octagon?

Question. Which regular polygons can be formed by vertices of the hexagonal or triangular lattices?

The answer is that in fact there are no other types of regular polygons to be found! I’d like to prove this by means of some elementary classical reasoning.

Theorem. The only non-degenerate regular polygons that arise from vertices in the hexagonal or triangular lattices are the equilateral triangles and regular hexagons.

This theorem extends the analysis I gave in my post last week for the integer lattice, showing that there are no regular polygons in the integer lattice, except squares.

Proof. The argument for the hexagonal and triangular lattices uses a similar idea as with the integer lattice, but there is a little issue with the square and pentagon case. We can handle both the hexagonal and triangular lattices at the same time. The crucial fact is that both of these lattices are invariant by $120^\circ$ rotation about any lattice vertex.

To get started, suppose that we can find a square in the hexagonal lattice. We may rotate this square by $120^\circ$ about the vertex $a$, and the square vertices will all land on lattice-vertex points. Next, we may rotate the resulting square about the point $b$, and again the vertices will land on lattice points. So we have described how to transform any square vertex point $a$ to another lattice point $c$ which is strictly inside the square. By applying that operation to each of the four vertices of the square, we thereby arrive by symmetry at a strictly smaller square. Thus, for any square in the hexagonal or triangular lattice, there is a strictly smaller square. But if there were any square in the lattice at all, there would have to be a square with smallest side-length, since there are only finitely many lattice distances less than any given length. So there can be no square in the hexagonal or triangular lattice.

The same construction works with pentagons.

If there is a pentagon in the lattice, then we may rotate it about point $a$, and then again about point $b$, resulting in point $c$ strictly inside the pentagon, which leads to an infinite sequence of strictly smaller pentagon, whose sizes (by similarity) go to zero. So there can be no pentagon in the hexagonal or triangular lattices.

If we attempt to apply this argument with triangles or hexagons, then the process simply leads back again to points in the original figure. But of course, since triangles and hexagons do arise in these grids, we didn’t expect the construction to work with them.

But also, this particular two-step rotation construction does not succeed with the heptagon (7-sides) or larger polygons, since the resulting point $c$ ends up outside the original heptagon, which means that the new heptagon we construct ends up being larger, rather than smaller than the original.

Fortunately, for the 7-gon and higher, we may fall back on the essential idea used in the square lattice case. Namely, because the interior angles of these polygons are now larger than $120^\circ$, we may simply rotate each side of the polygon by $120^\circ$ and thereby land at a lattice point. In this way, we construct a proportionally smaller instance of the same regular $n$-gon, and so there can be no smallest instance of such a polygon.

In summary, in every case of a regular polygon except the equilateral triangle and the regular hexagon, we found that by means of $120^\circ$ rotations we were able to find a strictly smaller instance of the polygon. Therefore, there can be no instances of such polygons arising from lattice points in the hexagonal or triangular tilings. QED

See my earlier post: there are no regular polygons in the integer lattice, except squares.

There are no nondegenerate regular polygons in the integer lattice, except for squares

Posted on December 4, 2016 by Joel David Hamkins

Consider a regular square lattice, formed by a grid of intersection points of uniformly spaced parallel horizontal and vertical lines in the plane. One may easily find points that form the vertices of a square in this lattice.

But can one find points that form the vertices of regular hexagon? Or a regular pentagon? How about an equilateral triangle? And so on.

The answer is that one cannot find these shapes using vertices in the square lattice.

Theorem. There is no regular pentagon in the square lattice, and no regular hexagon, no regular heptagon, and so on. Indeed, the only nondegenerate regular polygons to be found using vertices in a square lattice are squares themselves.

I think this must be a classical result. I was inspired by Vaughn Climenhaga’s beautiful image in his Proof without words answer on MathOverflow, which handled the case of a hexagon. Reflecting upon it, I realized that the same idea works with other regular polygons, and I endeavored to produce the corresponding images, below.

Proof. Suppose that we could find five vertices in the square lattice that formed a regular pentagon. Construct on each side a perpendicular of the same length, as pictured in brown below. Since the lattice is invariant under $90^\circ$ rotations centered at a lattice point, each of these new points is still a lattice point. And by symmetry, they form the vertices of a (proportionally smaller) regular pentagon. Therefore, there can be no regular pentagon at all in the square lattice, since if there is one, it is clear that there would have to be a smallest instance.

An alternative way to argue is: by similarity, the size of the smaller pentagon shrinks by the same factor with each step, and so in the limit the size approaches zero; but clearly, we cannot have a lattice-point regular pentagon whose size is smaller than the square lattice spacing itself. So there is no regular pentagon in the square lattice.

The same argument works with larger regular polygons. The main point to realize is that for all regular $n$-gons, where $n>4$, when you construct the perpendicular on one of the sides, the resulting point is strictly inside the original polygon, and this is why the resulting regular $n$-gon is strictly smaller than the original. This completes the proof for all $n$-gons for $n>4$.

The case of an equilateral triangle requires special care. If one attempts the same construction idea as above, building the perpendicular on the edges of a triangle, then the resulting triangle becomes larger, rather than smaller, and so the proof method breaks down.

Nevertheless, one can reduce the equilateral triangle case to a hexagon: if you could find an equilateral triangle in the square lattice, then since the lattice is invariant under translation via a lattice-point line segment, it follows that we could build a regular hexagon. But we have already showed that we cannot find a regular hexagon in the square lattice, and so we cannot find an equilateral triangle.

triangle-hexagon

So we’ve completed the proof for all nondegenerate regular polygons, except the square. QED

For those who might be interested, here is the tex code I used to generate the nested polygons. The code accepts input $n$ to produce a regular $n$-gon with the perpendiculars constructed.

\documentclass{minimal} \usepackage[rgb]{xcolor} \usepackage{tikz} \usetikzlibrary{positioning,calc} \usepackage{ifthen}

\begin{document}
\newcommand\nestedpolygon[1]{ \begin{tikzpicture}[scale=4] \pgfmathsetmacro\n{#1} \pgfmathsetmacro\m{\n-1} \pgfmathsetmacro\shrink{sqrt((sin(180/\n))^2+(cos(180/\n)-2*sin(180/\n))^2)} \pgfmathsetmacro\OffSet{acos((sin(180/\n)^2+cos(180/\n)*(cos(180/\n)-2*sin(180/\n)))/\shrink)} \pgfmathsetmacro\gc{360+100*exp((5-\n)/3.5)} \pgfmathsetmacro\gcc{640+120*exp((5-\n)/3)} \definecolor{GonColor}{wave}{\gc} \definecolor{GonColorC}{wave}{\gcc} \pgfmathsetmacro\d{8} \foreach \k in {0,...,\d} { \pgfmathsetmacro\R{\shrink^\k}; \pgfmathsetmacro\c{100*exp(-\k/6)}; \pgfmathsetmacro\a{2*\R*sin(180/\n)} \pgfmathsetmacro\f{\k*\OffSet} \foreach \i in {0,...,\m} { \coordinate (x) at (360*\i/\n+\f:\R); \coordinate (y) at (360*\i/\n+360/\n+\f:\R); % the perp indicator \ifthenelse{\k=0\AND\i=\m\AND\n<20}{\draw[very thin,black!\c!white] ($(x)!.85!(y)$) node (p) {} -- ($(p)!1!90:(y)$) node (q) {} -- ($(q)!1!90:(p)$);}{} % connecting to lower level \draw [line width=.5*exp(-\k/2),GonColorC!\c!white] (y) -- ($(y)!1!-90:(x)$); % edge and vertices of current gon \draw [line width=1.5*exp(-\k/2),GonColor!\c!white] (x) node [circle,scale=.3*\R,black!\c!white,fill=black!\c!white] {} -- (y); }

\draw (\f:\R) node [circle,scale=.3*\R,black!\c!white,fill=black!\c!white] {}; } \end{tikzpicture}}

\foreach\n in {5,6,7,8,9,10,12,16,20} { \eject $$\nestedpolygon{\n}$$ }
\end{document}

See my follow-up post on the regular polygons arising in the hexagonal and triangular lattices.

Mathematical logic, GC Math 712, Spring 2017

Posted on November 26, 2016 by Joel David Hamkins

I shall be teaching Mathematical Logic, Math 712 at the CUNY Graduate Center in Spring 2017. The course is 4.5 credits, and it will meet Tuesdays and Thursdays, 2:00 pm – 3:30 pm. There are no official pre-requisites, other than a willingness to engage with graduate-level mathematics. Students will benefit from having taken the first semester logic course, Math 711.

Course Description. This course is a graduate introduction to mathematical logic, in which we shall cover a variety of topics united by the theme of Gödel’s incompleteness theorem. In particular, during the semester we shall give several independent proofs of that theorem and its generalizations from different perspectives. We shall do so in the context of our studies of computability theory, decidability, strongly undecidable structures, the arithmetic hierarchy, arithmetization, definability and selected topics in proof theory, model theory and set theory, including the hierarchy of consistency strength. Students will complete weekly problem sets and write a term paper.

Check back here later for further information about the course.

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: