Math for kids: fun with orthoprojections!

Posted on by
3

I had the pleasure a few weeks ago to visit my daughter’s math class at her school and undertake some fun math activities with the sixth graders (11-12 years old, all girls). What a fun time we had!

The topic was orthoprojection and the problem of gaining insight about a three-dimensional object or arrangement by considering its various orthogonal projections.

I had prepared a collection of puzzles, which I hoped would challenge the students in spatial reasoning and abstract visualization. (The puzzle booklet is available at bottom.)

The puzzles involved orthogonal projections of arrangements of unit blocks.

Unit blocks are a certain kind of wooden block toy, which exhibit precise dimensions in the ratio $1\times 2\times 4$.  Thus, two blocks oriented the shortest way combine to the same thickness as one block oriented another way, or half the long length.  Thus, unit blocks can be flexibly combined in a huge variety of combinations, often leading to aesthetically pleasing and structurally sound creations. Furthermore, they are thought to help develop a child’s intuition for fractions in a completely natural and meaningful way, for often the child needs to build a support exactly $1/4$ unit or $1/2$ unit taller, or what have you, and in this way they are lead to see how the fractional units combine into wholes.

Unit blocks are commonly found in American elementary schools and kindergartens, and woodworkers will recognize that one can make a set of unit blocks from standard $2\times 4$ lumber, available at most hardware stores. You can also buy unit block sets online, and my opinion is that one hardly needs any other toy than a good unit block set for any child aged 2 to 102. Note: you do NOT need any of the fancy extra blocks, not following the unit block standard, that are sometimes available with these sets; the quality of play is best with just the unit blocks and half-units, thin units, double units and so on.

For the school visit, I brought sufficient blocks for all the girls, and explained that we were going to play with blocks the way that a mathematician or engineer might play with blocks.  And I had prepared a puzzle booklets, one per child (available below).

For each puzzle, one sees the front view, top view and right side view of an arrangement of blocks, and the challenge is to assemble the blocks so as to realize those views.  (In these puzzles, I had chosen not to show any hidden lines and edges, to make them slightly more challenging, although it would also make sense to me to show hidden lines; it would be customary to do so with a dashed line.)

Here are a few more easy examples with solutions.

It happens that these front/top/side projection view problems inspire some deep feelings in me, for they remind me of my father, who was a mechanical engineer. In my childhood, he would often bring home and show me blueprints of the machines or machine parts that he was designing or working with, and those blueprints were filled with front/top/side projection views of the various parts. In pre-computer design days, engineers would specify their machine parts by providing the various othogonal views. (Nowadays, of course, computers are used and one can compute orthogonal and perspective views from any angle.)

In my daughter’s classroom, the students took up the puzzles with a seriousness that shocked me. Once we had passed out the puzzle booklets and distributed the blocks, the girls just steamed through the puzzles, one after the other, totally absorbed. They didn’t want any hints or advice or help of any kind; they just went from each puzzle to the next, solving them one after another. There were a sufficient number of blocks for them all to work on the smaller puzzles on their own, but for the larger puzzles, they formed groups and combined blocks. It was a big success!

Without further ado, here are your puzzles. I’ve also included some photos below, out of order, and some puzzles do not match a photo and vice versa, but you can look at the photos if you need a hint.

 

 

 

 

 

 

 

 

 

 

 

 

 

After these puzzles, we moved on to the inverse problem. The girls made their own arrangement of blocks and then drew all six orthogonal projections: front, top, right, left, back, bottom.  You can draw them on the net of a cube, so that you can imagine folding the cube so as to realize the projections.

And after this, we moved beyond unit blocks to more general shapes. Can you solve the following projection puzzles?

 

 

 

 

 

The most challenging puzzle was the following. Can you imagine a solid that appears as a square from the front, a circle from the top and a triangle from the right side?

 

 

 

 

 

 

The complete puzzle booklet is available here: Fun with orthoprojections!

(And here is an alternative version of the puzzles made by David Butler for use with Jenga blocks, which have the dimensional ratios $3\times 5\times 15$ rather than $1\times2\times 4$: Jenga Views; see also this Twitter thread.)

Although I made the puzzles with six-graders in mind, the puzzles are interesting for people of any age, and I have proof:  a picture of some of my CUNY math-major college students solving the puzzles in my office.

And here are videos of some fascinating sculptures playing with orthoprojections:

Oxford University, Professor of Logic & Sir Peter Strawson Fellow, University College Oxford

Posted on by
11

In September 2018, I took up a new position in Oxford:

I am looking forward to starting this new chapter in my life and academic career.

Wish me luck!

 

Set-theoretic potentialism and the universal finite set, Scandinavian Logic Symposium, June 2018

Posted on by
Reply

This will be an invited talk at the Scandinavian Logic Symposium SLS 2018, held at the University of Gothenburg in Sweden, June 11-13, 2018.

Abstract. Providing a set-theoretic analogue of the universal algorithm, I shall define a certain finite set in set theory
$$\{x\mid\varphi(x)\}$$
and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficiently large $V_\theta$; the set is empty in any transitive model; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ of ZFC in which $\varphi$ defines the new set $z$. I shall draw out consequences of the universal finite set for set-theoretic potentialism and discuss several issues it raises in the philosophy of set theory.

The talk will include joint work with W. Hugh Woodin, Øystein Linnebo and others.

Slides: Set-theoretic potentialism and universal finite set SLS 2018

Infinite Sudoku and the Sudoku game

Posted on by
11

Consider what I call the Sudoku game, recently introduced in the MathOverflow question Who wins two-player Sudoku? posted by Christopher King (user PyRulez). Two players take turns placing numbers on a Sudoku board, obeying the rule that they must never explicitly violate the Sudoku condition: the numbers on any row, column or sub-board square must never repeat. The first player who cannot continue legal play loses. Who wins the game? What is the winning strategy?

The game is not about building a global Sudoku solution, since a move can be legal in this game even when it is not part of any global Sudoku solution, provided only that it doesn’t yet explicitly violate the Sudoku condition. Rather, the Sudoku game is about trying to trap your opponent in a maximal such position, a position which does not yet explicitly violate the Sudoku condition but which cannot be further extended.

In my answer to the question on MathOverflow, I followed an idea suggested to me by my daughter Hypatia, namely that on even-sized boards $n^2\times n^2$ where $n$ is even, then the second player can win with a mirroring strategy: simply copy the opponent’s moves in reflected mirror image through the center of the board. In this way, the second player ensures that the position on the board is always symmetric after her play, and so if the previous move was safe, then her move also will be safe by symmetry. This is therefore a winning strategy for the second player, since any violation of the Sudoku condition will arise on the opponent’s play.

This argument works on even-sized boards precisely because the reflection of every row, column and sub-board square is a totally different row, column and sub-board square, and so any new violation of the Sudoku conditions would reflect to a violation that was already there. The mirror strategy definitely does not work on the odd-sized boards, including the main $9\times 9$ case, since if the opponent plays on the central row, copying directly would immediately introduce a Sudoku violation.

After posting that answer, Orson Peters (user orlp) pointed out that one can modify it to form a winning strategy for the first player on odd-sized boards, including the main $9\times 9$ case. In this case, let the first player begin by playing $5$ in the center square, and then afterwards copy the opponent’s moves, but with the ten’s complement at the reflected location. So if the opponent plays $x$, then the first player plays $10-x$ at the reflected location. In this way, the first player can ensure that the board is ten’s complement symmetric after her moves. The point is that again this is sufficient to know that she will never introduce a violation, since if her $10-x$ appears twice in some row, column or sub-board square, then $x$ must have already appeared twice in the reflected row, column or sub-board square before that move.

This idea is fully general for odd-sized Sudoku boards $n^2\times n^2$, where $n$ is odd. If $n=2k-1$, then the first player starts with $k$ in the very center and afterward plays the $2k$-complement of her opponent’s move at the reflected location.

Conclusion.

  1. On even-sized Sudoku boards, the second player wins the Sudoku game by the mirror copying strategy.
  2. On odd-sized Sudoku boards, the first players wins the Sudoku game by the complement-mirror copying strategy.

Note that on the even boards, the second player could also play complement mirror copying just as successfully.

What I really want to tell you about, however, is the infinite Sudoku game (following a suggestion of Sam Hopkins). Suppose that we try to play the Sudoku game on a board whose subboard squares are $\mathbb{Z}\times\mathbb{Z}$, so that the full board is a $\mathbb{Z}\times\mathbb{Z}$ array of those squares, making $\mathbb{Z}^2\times\mathbb{Z}^2$ altogether. (Or perhaps you might prefer the board $\mathbb{N}^2\times\mathbb{N}^2$?)

One thing to notice is that on an infinite board, it is no longer possible to get trapped at a finite stage of play, since every finite position can be extended simply by playing a totally new label from the set of labels; such a move would never lead to a new violation of the explicit Sudoku condition.

For this reason, I should like to introduce the Sudoku Solver-Spoiler game variation as follows. There are two players: the Sudoku Solver and the Sudoku Spoiler. The Solver is trying to build a global Sudoku solution on the board, while the Spoiler is trying to prevent this. Both players must obey the Sudoku condition that labels are never to be explicitly repeated in any row, column or sub-board square. On an infinite board, the game proceeds transfinitely, until the board is filled or there are no legal moves. The Solver wins a play of the game, if she successfully builds a global Sudoku solution, which means not only that every location has a label and there are no repetitions in any row, column or sub-board square, but also that every label in fact appears in every row, column and sub-board square. That is, to count as a solution, the labels on any row, column and sub-board square must be a bijection with the set of labels. (On infinite boards, this is a stronger requirement than merely insisting on no repetitions.)

The Solver-Spoiler game makes sense in complete generality on any set $S$, whether finite or infinite. The sub-boards are $S^2=S\times S$, and one has an $S\times S$ array of them, so $S^2\times S^2$ for the whole board. Every row and column has the same size as the sub-board square $S^2$, and the set of labels should also have this size.

Upon reflection, one realizes that what matters about $S$ is just its cardinality, and we really have for every cardinal $\kappa$ the $\kappa$-Sudoku Solver-Spoiler game, whose board is $\kappa^2\times\kappa^2$, a $\kappa\times\kappa$ array of $\kappa\times\kappa$ sub-boards. In particular, the game $\mathbb{Z}^2\times\mathbb{Z}^2$ is actually isomorphic to the game $\mathbb{N}^2\times\mathbb{N}^2$, despite what might feel initially like a very different board geometry.

What I claim is that the Solver has a winning strategy in the all the infinite Sudoku Solver-Spoiler games, in a very general and robust manner.

Theorem. For every infinite cardinal $\kappa$, the Solver has a winning strategy to win the $\kappa$-Sudoku Solver-Spoiler game.

  • The strategy will win in $\kappa$ many moves, producing a full Sudoku solution.
  • The Solver can win whether she goes first or second, starting from any legal position of size less than $\kappa$.
  • The Solver can win even when the Spoiler is allowed to play finitely many labels at once on each turn, or fewer than $\kappa$ many moves (if $\kappa$ is regular), even if the Solver is only allowed one move each turn.
  • In the countably infinite Sudoku game, the Solver can win even if the Spoiler is allowed to make infinitely many moves at once, provided only that the resulting position can in principle be extended to a full solution.

Proof. Consider first the countably infinite Sudoku game, and assume the initial position is finite and that the Spoiler will make finitely many moves on each turn. Consider what it means for the Solver to win at the limit. It means, first of all, that there are no explicit repetitions in any row, column or sub-board. This requirement will be ensured since it is part of the rules for legal play not to violate it. Next, the Solver wants to ensure that every square has a label on it and that every label appears at least once in every row, every column and every sub-board. If we think of these as individual specific requirements, we have countably many requirements in all, and I claim that we can arrange that the Solver will simply satisfy the $n^{th}$ requirement on her $n^{th}$ play. Given any finite position, she can always find something to place in any given square, using a totally new label if need be. Given any finite position, any row and any particular label $k$, since can always find a place on that row to place the label, which has no conflict with any column or sub-board, since there are infinitely many to choose from and only finitely many conflicts. Similarly with columns and sub-boards. So each of the requirements can always be fulfilled one-at-a-time, and so in $\omega$ many moves she can produce a full solution.

The argument works equally well no matter who goes first or if the Spoiler makes arbitrary finite play, or indeed even infinite play, provided that the play is part of some global solution (perhaps a different one each time), since on each move the Solve can simply meet the requirement by using that solution at that stage.

An essentially similar argument works when $\kappa$ is uncountable, although now the play will proceed for $\kappa$ many steps. Assuming $\kappa^2=\kappa$, a consequence of the axiom of choice, there are $\kappa$ many requirements to meet, and the Solve can meet requirement $\alpha$ on the $\alpha^{th}$ move. If $\kappa$ is regular, we can again allow the Spoiler to make arbitrary size-less-than-$\kappa$ size moves, so that at any stage of play before $\kappa$ the position will still be size less than $\kappa$. (If $\kappa$ is singular, one can allow Spoiler to make finitely many moves at once or indeed even some uniform bounded size $\delta<\kappa$ many moves at once. $\Box$

I find it interesting to draw out the following aspect of the argument:

Observation. Every finite labeling of an infinite Sudoku board that does not yet explicitly violate the Sudoku condition can be extended to a global solution.

Similarly, any size less than $\kappa$ labeling that does not yet explicitly violate the Sudoku condition can be extended to a global solution of the $\kappa$-Sudoku board for any infinite cardinal $\kappa$.

What about asymmetric boards? It has come to my attention that people sometimes look at asymmetric Sudoku boards, whose sub-boards are not square, such as in the six-by-six Sudoku case. In general, one could take Sudoku boards to consist of a $\lambda\times\kappa$ array of sub-boards of size $\kappa\times\lambda$, where $\kappa$ and $\lambda$ are cardinals, not necessarily the same size and not necessarily both infinite or both finite. How does this affect the arguments I’ve given?

In the finite $(n\times m)\times (m\times n)$ case, if one of the numbers is even, then it seems to me that the reflection through the origin strategy works for the second player just as before. And if both are odd, then the first player can again play in the center square and use the mirror-complement strategy to trap the opponent. So that analysis will work fine.

In the case $(\kappa\times\lambda)\times(\lambda\times\kappa)$ where $\lambda\leq\kappa$ and $\kappa=\lambda\kappa$ is infinite, then the proof of the theorem seems to break, since if $\lambda<\kappa$, then with only $\lambda$ many moves, say putting a common symbol in each of the $\lambda$ many rectangles across a row, we can rule out that symbol in a fixed row. So this is a configuration of size less than $\kappa$ that cannot be extended to a full solution. For this reason, it seems likely to me that the Spoiler can win the Sudoko Solver-Spoiler game in the infinite asymmetric case.

Finally, let’s consider the Sudoku Solver-Spoiler game in the purely finite case, which actually is a very natural game, perhaps more natural than what I called the Sudoku game above. It seems to me that the Spoiler should be able to win the Solver-Spoiler game on any nontrivial finite board. But I don’t yet have an argument proving this. I asked a question on MathOverflow: The Sudoku game: Solver-Spoiler variation.

Kameryn J. Williams, PhD 2018, CUNY Graduate Center

Posted on by
Reply

Kameryn J. Williams successfully defended his dissertation under my supervision at the CUNY Graduate Center on April 6th, 2018, earning his Ph.D. degree in May 2018. He has accepted a position in mathematics at the University of Hawaii, to begin Fall 2018.

What a pleasure it was to work with Kameryn, an extremely talented mathematician with wide interests and huge promise.

Kameryn J Williams | MathOverflow | ar$\chi$iv

Kameryn J. Williams, The Structure of Models of Second-order Set Theories,  Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2018. arXiv:1804.09526.

Abstract. This dissertation is a contribution to the project of second-order set theory, which has seen a revival in recent years. The approach is to understand second-order set theory by studying the structure of models of second-order set theories. The main results are the following, organized by chapter. First, I investigate the poset of T-realizations of a fixed countable model of ZFC, where T is a reasonable second-order set theory such as GBC or KM, showing that it has a rich structure. In particular, every countable partial order embeds into this structure. Moreover, we can arrange so that these embedding preserve the existence/nonexistence of upper bounds, at least for finite partial orders. Second I generalize some constructions of Marek and Mostowski from KM to weaker theories. They showed that every model of KM plus the Class Collection schema “unrolls” to a model of ZFC− with a largest cardinal. I calculate the theories of the unrolling for a variety of second-order set theories, going as weak as GBC + ETR. I also show that being T-realizable goes down to submodels for a broad selection of second-order set theories T. Third, I show that there is a hierarchy of transfinite recursion principles ranging in strength from GBC to KM. This hierarchy is ordered first by the complexity of the properties allowed in the recursions and second by the allowed heights of the recurions. Fourth, I investigate the question of which second-order set theories have least models. I show that strong theories—such as KM or $\Pi^1_1$-CA—do not have least transitive models, while weaker theories—from GBC to GBC + ETR${}_{\text{Ord}}$—do have least transitive models.

In addition to his dissertation work and the research currently arising out of it, Kameryn has undertaken a number of collaborations with various international research efforts, including the following:

  • He is a co-author on The exact strength of the class forcing theorem. [bibtex key=”GitmanHamkinsHolySchlichtWilliams:The-exact-strength-of-the-class-forcing-theorem”]
  • He is co-author on a current joint project with Miha Habič, myself, Daniel Klausner and Jonathan Verner concerning the nonamalgamation phenomenon in the generic multiverse of a countable model of set theory.
  • He is co-author on a current joint project with myself and Philip Welch concerning the universal $\Sigma_1$-definable finite sequence, an analogue of the universal finite set, but for the constructible universe.

 

Different set theories are never bi-interpretable

Posted on by
11

I was fascinated recently to discover something I hadn’t realized about relative interpretability in set theory, and I’d like to share it here. Namely,

Different set theories extending ZF are never bi-interpretable!

For example, ZF and ZFC are not bi-interpretable, and neither are ZFC and ZFC+CH, nor ZFC and ZFC+$\neg$CH, despite the fact that all these theories are equiconsistent. The basic fact is that there are no nontrivial instances of bi-interpretation amongst the models of ZF set theory. This is surprising, and could even be seen as shocking, in light of the philosophical remarks one sometimes hears asserted in the philosophy of set theory that what is going on with the various set-theoretic translations from large cardinals to determinacy to inner model theory, to mention a central example, is that we can interpret between these theories and consequently it doesn’t much matter which context is taken as fundamental, since we can translate from one context to another without loss.

The bi-interpretation result shows that these interpretations do not and cannot rise to the level of bi-interpretations of theories — the most robust form of mutual relative interpretability — and consequently, the translations inevitably must involve a loss of information.

To be sure, set theorists classify the various set-theoretic principles and theories into a hierarchy, often organized by consistency strength or by other notions of interpretative power, using forcing or definable inner models. From any model of ZF, for example, we can construct a model of ZFC, and from any model of ZFC, we can construct models of ZFC+CH or ZFC+$\neg$CH and so on. From models with sufficient large cardinals we can construct models with determinacy or inner-model-theoretic fine structure and vice versa. And while we have relative consistency results and equiconsistencies and even mutual interpretations, we will have no nontrivial bi-interpretations.

(I had proved the theorem a few weeks ago in joint work with Alfredo Roque Freire, who is visiting me in New York this year. We subsequently learned, however, that this was a rediscovery of results that have evidently been proved independently by various authors. Albert Visser proves the case of PA in his paper, “Categories of theories and interpretations,” Logic in Tehran, 284–341, Lect. Notes Log., 26, Assoc. Symbol. Logic, La Jolla, CA, 2006, (pdf, see pp. 52-55). Ali Enayat gave a nice model-theoretic argument for showing specifically that ZF and ZFC are not bi-interpretable, using the fact that ZFC models can have no involutions in their automorphism groups, but ZF models can; and he proved the general version of the theorem, for ZF, second-order arithmetic $Z_2$ and second-order set theory KM in his 2016 article, A. Enayat, “Variations on a Visserian theme,” in Liber Amicorum Alberti : a tribute to Albert Visser / Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten (eds.) Pages, 99-110. ISBN, 978-1848902046. College Publications, London. The ZF version was apparently also observed independently by Harvey Friedman, Visser and Fedor Pakhomov.)

Meanwhile, let me explain our argument. Recall from model theory that one theory $S$ is interpreted in another theory $T$, if in any model of the latter theory $M\models T$, we can define (and uniformly so in any such model) a certain domain $N\subset M^k$ and relations and functions on that domain so as to make $N$ a model of $S$. For example, the theory of algebraically closed fields of characteristic zero is interpreted in the theory of real-closed fields, since in any real-closed field $R$, we can consider pairs $(a,b)$, thinking of them as $a+bi$, and define addition and multiplication on those pairs in such a way so as to construct an algebraically closed field of characteristic zero.

Two theories are thus mutually interpretable, if each of them is interpretable in the other. Such theories are necessarily equiconsistent, since from any model of one of them we can produce a model of the other.

Note that mutual interpretability, however, does not insist that the two translations are inverse to each other, even up to isomorphism. One can start with a model of the first theory $M\models T$ and define the interpreted model $N\models S$ of the second theory, which has a subsequent model of the first theory again $\bar M\models T$ inside it. But the definition does not insist on any particular connection between $M$ and $\bar M$, and these models need not be isomorphic nor even elementarily equivalent in general.

By addressing this, one arrives at a stronger and more robust form of mutual interpretability. Namely, two theories $S$ and $T$ are bi-interpretable, if they are mutually interpretable in such a way that the models can see that the interpretations are inverse. That is, for any model $M$ of the theory $T$, if one defines the interpreted model $N\models S$ inside it, and then defines the interpreted model $\bar M$ of $T$ inside $N$, then $M$ is isomorphic to $\bar M$ by a definable isomorphism in $M$, and uniformly so (and the same with the theories in the other direction). Thus, every model of one of the theories can see exactly how it itself arises definably in the interpreted model of the other theory.

For example, the theory of linear orders $\leq$ is bi-interpretable with the theory of strict linear order $<$, since from any linear order $\leq$ we can define the corresponding strict linear order $<$ on the same domain, and from any strict linear order $<$ we can define the corresponding linear order $\leq$, and doing it twice brings us back again to the same order.

For a richer example, the theory PA is bi-interpretable with the finite set theory $\text{ZF}^{\neg\infty}$, where one drops the infinity axiom from ZF and replaces it with the negation of infinity, and where one has the $\in$-induction scheme in place of the foundation axiom. The interpretation is via the Ackerman encoding of hereditary finite sets in arithmetic, so that $n\mathrel{E} m$ just in case the $n^{th}$ binary digit of $m$ is $1$. If one starts with the standard model $\mathbb{N}$, then the resulting structure $\langle\mathbb{N},E\rangle$ is isomorphic to the set $\langle\text{HF},\in\rangle$ of hereditarily finite sets. More generally, by carrying out the Ackermann encoding in any model of PA, one thereby defines a model of $\text{ZF}^{\neg\infty}$, whose natural numbers are isomorphic to the original model of PA, and these translations make a bi-interpretation.

We are now ready to prove that this bi-interpretation situation does not occur with different set theories extending ZF.

Theorem. Distinct set theories extending ZF are never bi-interpretable. Indeed, there is not a single model-theoretic instance of bi-interpretation occurring with models of different set theories extending ZF.

Proof. I mean “distinct” here in the sense that the two theories are not logically equivalent; they do not have all the same theorems. Suppose that we have a bi-interpretation instance of the theories $S$ and $T$ extending ZF. That is, suppose we have a model $\langle M,\in\rangle\models T$ of the one theory, and inside $M$, we can define an interpreted model of the other theory $\langle N,\in^N\rangle\models S$, so the domain of $N$ is a definable class in $M$ and the membership relation $\in^N$ is a definable relation on that class in $M$; and furthermore, inside $\langle N,\in^N\rangle$, we have a definable structure $\langle\bar M,\in^{\bar M}\rangle$ which is a model of $T$ again and isomorphic to $\langle M,\in^M\rangle$ by an isomorphism that is definable in $\langle M,\in^M\rangle$. So $M$ can define the map $a\mapsto \bar a$ that forms an isomorphism of $\langle M,\in^M\rangle$ with $\langle \bar M,\in^{\bar M}\rangle$. Our argument will work whether we allow parameters in any of these definitions or not.

I claim that $N$ must think the ordinals of $\bar M$ are well-founded, for otherwise it would have some bounded cut $A$ in the ordinals of $\bar M$ with no least upper bound, and this set $A$ when pulled back pointwise by the isomorphism of $M$ with $\bar M$ would mean that $M$ has a cut in its own ordinals with no least upper bound; but this cannot happen in ZF.

If the ordinals of $N$ and $\bar M$ are isomorphic in $N$, then all three models have isomorphic ordinals in $M$, and in this case, $\langle M,\in^M\rangle$ thinks that $\langle N,\in^N\rangle$ is a well-founded extensional relation of rank $\text{Ord}$. Such a relation must be set-like (since there can be no least instance where the predecessors form a proper class), and so $M$ can perform the Mostowski collapse of $\in^N$, thereby realizing $N$ as a transitive class $N\subseteq M$ with $\in^N=\in^M\upharpoonright N$. Similarly, by collapsing we may assume $\bar M\subseteq N$ and $\in^{\bar M}=\in^M\upharpoonright\bar M$. So the situation consists of inner models $\bar M\subseteq N\subseteq M$ and $\langle \bar M,\in^M\rangle$ is isomorphic to $\langle M,\in^M\rangle$ in $M$. This is impossible unless all three models are identical, since a simple $\in^M$-induction shows that $\pi(y)=y$ for all $y$, because if this is true for the elements of $y$, then $\pi(y)=\{\pi(x)\mid x\in y\}=\{x\mid x\in y\}=y$. So $\bar M=N=M$ and so $N$ and $M$ satisfy the same theory, contrary to assumption.

If the ordinals of $\bar M$ are isomorphic to a proper initial segment of the ordinals of $N$, then a similar Mostowski collapse argument would show that $\langle\bar M,\in^{\bar M}\rangle$ is isomorphic in $N$ to a transitive set in $N$. Since this structure in $N$ would have a truth predicate in $N$, we would be able to pull this back via the isomorphism to define (from parameters) a truth predicate for $M$ in $M$, contrary to Tarski’s theorem on the non-definability of truth.

The remaining case occurs when the ordinals of $N$ are isomorphic in $N$ to an initial segment of the ordinals of $\bar M$. But this would mean that from the perspective of $M$, the model $\langle N,\in^N\rangle$ has some ordinal rank height, which would mean by the Mostowski collapse argument that $M$ thinks $\langle N,\in^N\rangle$ is isomorphic to a transitive set. But this contradicts the fact that $M$ has an injection of $M$ into $N$. $\Box$

It follows that although ZF and ZFC are equiconsistent, they are not bi-interpretable. Similarly, ZFC and ZFC+CH and ZFC+$\neg$CH are equiconsistent, but no pair of them is bi-interpretable. And again with all the various equiconsistency results concerning large cardinals.

A similar argument works with PA to show that different extensions of PA are never bi-interpretable.

The universal finite set, Rutgers Logic Seminar, April 2018

Posted on by
Reply

This will be a talk for the Rutgers Logic Seminar, April 2, 2018. Hill Center, Busch campus.

Abstract. I shall define a certain finite set in set theory $$\{x\mid\varphi(x)\}$$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficient $V_\theta$; the set is empty in any transitive model and others; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines the new set $z$.  The definition can be thought of as an idealized diamond sequence, and there are consequences for the philosophical theory of set-theoretic top-extensional potentialism.

This is joint work with W. Hugh Woodin.

Determinacy for open class games is preserved by forcing, CUNY Set Theory Seminar, April 2018

Posted on by
5

This will be a talk for the CUNY Set Theory Seminar, April 27, 2018, GC Room 6417, 10-11:45am (please note corrected date).

Abstract. Open class determinacy is the principle of second order set theory asserting of every two-player game of perfect information, with plays coming from a (possibly proper) class $X$ and the winning condition determined by an open subclass of $X^\omega$, that one of the players has a winning strategy. This principle finds itself about midway up the hierarchy of second-order set theories between Gödel-Bernays set theory and Kelley-Morse, a bit stronger than the principle of elementary transfinite recursion ETR, which is equivalent to clopen determinacy, but weaker than GBC+$\Pi^1_1$-comprehension. In this talk, I’ll given an account of my recent joint work with W. Hugh Woodin, proving that open class determinacy is preserved by forcing. A central part of the proof is to show that in any forcing extension of a model of open class determinacy, every well-founded class relation in the extension is ranked by a ground model well-order relation. This work therefore fits into the emerging focus in set theory on the interaction of fundamental principles of second-order set theory with fundamental set theoretic tools, such as forcing. It remains open whether clopen determinacy or equivalently ETR is preserved by set forcing, even in the case of the forcing merely to add a Cohen real.

Nonamalgamation in the Cohen generic multiverse, CUNY Logic Workshop, March 2018

Posted on by
Reply

This will be a talk for the CUNY Logic Workshop on March 23, 2018, GC 6417 2-3:30pm.

Abstract. Consider a countable model of set theory $M$ in the context of all its successive forcing extensions and grounds. This generic multiverse has long been known to exhibit instances of nonamalgamation: one can have two extensions $M[c]$ and $M[d]$, both adding a merely a generic Cohen real, which have no further extension in common. In this talk, I shall describe new joint work that illuminates the extent of non-amalgamation: every finite partial order (and more) embeds into the generic multiverse over any given model in a way that preserves amalgamability and non-amalgamability. The proof uses the set-theoretic blockchain argument (pictured above), which has affinities with constructions in computability theory in the Turing degrees. Other arguments, which also resemble counterparts in computability theory, show that the generic multiverse exhibits the exact pair phenonemon for increasing chains. This is joint work with Miha Habič, myself, Lukas Daniel Klausner and Jonathan Verner. The paper will be available this Spring.

https://plus.google.com/u/0/+JoelDavidHamkins1/posts/NJp2N7bkkrR

Nonstandard models of arithmetic arise in the complex numbers

Posted on by
23

I’d like to explain that one may find numerous nonstandard models of arithmetic as substructures of the field of complex numbers.

The issue arose yesterday at Hans Schoutens’s talk for the CUNY Logic Workshop. The main focus of the talk was the question, for a given algebraically closed field $k$ of characteristic zero and a given model of arithmetic $\Gamma\models$PA, whether $\Gamma$ and $k$ were jointly realizable as the set of powers (as he defines it) and the set of units of a model $S$ of the generalized theory of polynomial rings over fields. Very interesting stuff.

During the talk, a side question arose, concerning exactly which models of PA arise as substructures of the field of complex numbers.

Question. Which models of PA arise as substructures of the field of complex numbers $\langle\mathbb{C},+,\cdot\rangle$?

Of course the standard model $\mathbb{N}$ arises this way, and some people thought at first it should be difficult to realize nonstandard models of PA as substructures of $\mathbb{C}$. After some back and forth, the question was ultimately answered by Alfred Dolich in the pub after the seminar, and I’d like to give his argument here (but see the Mlček reference below).  This is a case where a problem that was initially confusing becomes completely clear!

Theorem. Every model of PA of size at most continuum arises as a sub-semiring of the field of complex numbers $\langle\mathbb{C},+,\cdot\rangle$.

Proof. Suppose that $M$ is a model of PA of size at most continuum. Inside $M$, we may form $M$’s version of the algebraic numbers $A=\bar{\mathbb{Q}}^M$, the field that $M$ thinks is the algebraic closure of its version of the rationals. So $A$ is an algebraically closed field of characteristic zero, which has an elementary extension to such a field of size continuum. Since the theory of algebraically closed fields of characteristic zero is categorical in all uncountable powers, it follows that $A$ is isomorphic to a submodel of $\mathbb{C}$. Since $M$ itself is isomorphic to a substructure of its rationals $\mathbb{Q}^M$, which sit inside $A$, it follows that $M$ is isomorphic to a substructure of $\mathbb{C}$, as claimed. QED

In particular, every countable model of PA can be found as a substructure of the complex numbers.

Essentially the same argument shows the following.

Theorem. If $k$ is an uncountable algebraically closed field of characteristic zero, then every model of arithmetic $M\models$PA of size at most the cardinality of $k$ embeds into $k$.

I’ve realized that the same collection of ideas shows the following striking way to look upon the complex numbers:

Theorem. The complex numbers $\mathbb{C}$ can be viewed as a nonstandard version of the algebraic numbers $\bar{\mathbb{Q}}^M$ inside a nonstandard model $M$ of PA. Indeed, for every uncountable algebraically closed field $F$ of characteristic zero and every model of arithmetic $M\models$PA of the same cardinality, the field $F$ is isomorphic to the nonstandard algebraic numbers $\bar{\mathbb{Q}}^M$ as $M$ sees them.

Proof. Fix any such field $F$, such as the complex numbers themselves, and consider any nonstandard model of arithmetic $M$ of the same cardinality. The field $\bar{\mathbb{Q}}^M$, which is $M$’s nonstandard version of the algebraic numbers, is an algebraically closed field of characteristic zero and same uncountable size as $F$. By categoricity, these fields are isomorphic. $\Box$

I had suspected that these results were folklore in the model-theoretic community, and it has come to my attention that proper credit for the main observation of this post seems to be due to Jozef Mlček, who proved it in 1973. Thanks to Jerome Tauber for the reference, which he provided in the comments.

Modal principles of potentialism, Oxford, January 2018

Posted on by
3

This was a talk I gave at University College Oxford to the philosophy faculty.

Abstract. One of my favorite situations occurs when philosophical ideas or issues inspire a bit of mathematical analysis, which in turn raises further philosophical questions and ideas, in a fruitful cycle. The topic of potentialism originates, after all, in the classical dispute between actual and potential infinity. Linnebo and Shapiro and others have emphasized the modal nature of potentialism, de-coupling it from infinity: the essence of potentialism is about approximating a larger universe or structure by means of partial structures or universe fragments. In several mathematical projects, my co-authors and I have found the exact modal validities of several natural potentialist concepts arising in the foundations of mathematics, including several kinds of set-theoretic and arithmetic potentialism. Ultimately, the variety of kinds of potentialism suggest a refocusing of potentialism on the issue of convergent inevitability in comparison with radical branching. I defended the theses, first, that convergent potentialism is implicitly actualist, and second, that we should understand ultrafinitism in modal terms as a form of potentialism, one with suprising parallels to the case of arithmetic potentialism.

Here are my lecture notes that I used as a basis for the talk:

https://photos.app.goo.gl/DcaXV3sLVU4enaxv8

For a fuller, more technical account of potentialism, see the three-lecture tutorial series I gave for the Logic Winter School 2018 in Hejnice: Set-theoretic potentialism, and follow the link to the slides.

The subseries number

Posted on by
2

[bibtex key=”BrendleBrianHamkins2019:The-subseries-number”]

Abstract. Every conditionally convergent series of real numbers has a divergent  subseries. How many subsets of the natural numbers are needed so that every conditionally convergent series diverges on the subseries corresponding to one of these sets? The answer to this question is defined to be the subseries number, a new cardinal characteristic of the continuum. This cardinal is bounded below by $\aleph_1$ and  above by the cardinality of the continuum, but it is not provably equal to either. We define three natural variants of the subseries number, and compare them with each other, with their corresponding rearrangement numbers, and with several well-studied cardinal characteristics of the continuum. Many consistency results are obtained from these comparisons, and we obtain another by computing the value of the subseries number in the Laver model.

This paper grew naturally out of our previous paper, The rearrangement number, which considered the minimal number of permutations of $\mathbb{N}$ which suffice to reveal the conditional convergence of all conditionally convergent series. I had defined the subseries number in my answer to a MathOverflow question, On Hamkins’s answer to a question of Michael Hardy’s, asked by M. Rahman in response to the earlier MO questions on the rearrangement number.

In the paper, we situation the subseries number ß (German sharp s) with respect to other cardinal characteristics, including the rearrangement numbers.

Corey Switzer, The Cichoń Diagram for Degrees of Relative Constructibility

Posted on by
1

My student Corey Switzer has just completed a paper:


Corey Switzer, The Cichoń Diagram for Degrees of Relative Constructibility, ArXiv e-print:1801.06497.

 

Abstract. Following a line of research initiated in Brendle/Brooke-Taylor/Ng/Nies, I describe a general framework for turning reduction concepts of relative computability into diagrams forming an analogy with the Cichoń diagram for cardinal characteristics of the continuum. I show that working from relatively modest assumptions about a notion of reduction, one can construct a robust version of such a diagram. As an application, I define and investigate the Cichoń Diagram for degrees of constructibility relative to a fixed inner model W. Many analogies hold with the classical theory as well as some surprising differences. Along the way I introduce a new axiom stating, roughly, that the constructibility diagram is as complex as possible.

This interesting paper concerns a generalization of the Cichoń diagram to arbitrary reducibility notions, focussing on the case of the constructibility degrees, or somewhat more generally, relative constructibility $\leq_W$ over a fixed inner model $W$.

The classes are defined by an abstract generalization of the ideas underlying the familiar cardinal characteristics and the classical Cichoń diagram. Namely, $B_{\leq}(R)$ is the set of reals that $\leq$-build a witness for the fact that the reals of $W$ are small with respect to the relation $R$, that is, an $R$-bound for the reals of $W$; and $D_{\leq}(R)$ is the set of reals that $\leq$-build a witness for the fact that the reals of $W$ are not big with respect to the relation $R$, that is, a real that is not $R$-dominated by any real in $W$.

These classes fit together in a way that forms a robust analogy with the classical Cichoń diagram.

In his paper, Corey proves that the diagram is complete with respect to the inclusions indicated, by analyzing the nature of the diagram in various forcing extensions of $W$, such as the following.

 

In the end, he shows that in a suitable (proper) forcing extension, one can achieve all the separations simultaneously.

Indeed, the assertion that all separations are attained can be taken as a set-theoretic principle or axiom of its own, the complete Cichoń diagram assertion CD. He proves, for example, that CD is a consequence of the maximality principle.

See Corey’s blog post about his paper.

The modal logic of arithmetic potentialism and the universal algorithm

Posted on by
5

[bibtex key=”Hamkins:The-modal-logic-of-arithmetic-potentialism”]

Abstract. Natural potentialist systems arise from the models of arithmetic when they are considered under their various natural extension concepts, such as end-extensions, arbitrary extension, $\Sigma_n$-elementary extensions, conservative extensions and more. For these potentialist systems, I prove, a propositional modal assertion is valid in a model of arithmetic, with respect to assertions in the language of arithmetic with parameters, exactly when it is an assertion of S4. Meanwhile, with respect to sentences, the validities of a model are always between S4 and S5, and these bounds are sharp in that both endpoints are realized. The models validating exactly S5 are the models of the arithmetic maximality principle, which asserts that every possibly necessary statement is already true, and these models are equivalently characterized as those satisfying a maximal $\Sigma_1$ theory. The main proof makes fundamental use of the universal algorithm, of which this article provides a self-contained account.

 

In this article, I consider the models of arithmetic under various natural extension concepts, including end-extensions, arbitrary extensions, $\Sigma_n$-elementary extensions, conservative extensions and more. Each extension concept gives rise to an arithmetic potentialist system, a Kripke model of possible arithmetic worlds, and the main goal is to discover the modal validities of these systems.

For most of the extension concepts, a modal assertion is valid with respect to assertions in the language of arithmetic, allowing parameters, exactly when it is an assertion of the modal theory S4. For sentences, however, the modal validities form a theory between S4 and S5, with both endpoints being realized. A model of arithmetic validates S5 with respect to sentences just in case it is a model of the arithmetic maximality principle, and these models are equivalently characterized as those realizing a maximal $\Sigma_1$ theory.

The main argument relies fundamentally on the universal algorithm, the theorem due to Woodin that there is a Turing machine program that can enumerate any finite sequence in the right model of arithmetic, and furthermore this model can be end-extended so as to realize any further extension of that sequence available in the model. In the paper, I give a self-contained account of this theorem using my simplified proof.

The paper concludes with philosophical remarks on the nature of potentialism, including a discussion of how the linear inevitability form of potentialism is actually much closer to actualism than the more radical forms of potentialism, which exhibit branching possibility. I also propose to view the philosphy of ultrafinitism in modal terms as a form of potentialism, pushing the issue of branching possibility in ultrafinitism to the surface.

Discussion of McCallum’s paper on Reinhardt cardinals in ZF

Posted on by
42

Update: Rupert has withdrawn his claim. See the final bullet point below.

Rupert McCallum has posted a new paper to the mathematics arXiv

Rupert McCallum, The choiceless cardinals are inconsistent, mathematics arXiv 2017: 1712.09678.

He is claiming to establish the Kunen inconsistency in ZF, without the axiom of choice, which is a long-standing open question. In particular, this would refute the Reinhardt cardinals in ZF and all the stronger ZF large cardinals that have been studied.

If correct, this result will constitute a central advance in large cardinal set theory.

I am making this post to provide a place to discuss the proof and any questions that people might have about it. Please feel free to post comments with questions or answers to other questions that have been posted. I will plan to periodically summarize things in the main body of this post as the discussion proceeds.

  • My first question concerns lemma 0.4, where he claims that $j’\upharpoonright V_{\lambda+2}^N$ is a definable class in $N$. He needs this to get the embedding into $N$, but I don’t see why the embedding should be definable here.
  • I wrote to Rupert about this concern, and he replied that it may be an issue, and that he intends to post a new version of his paper, where he may retreat to the weaker claim refuting only the super-Reinhardt cardinals.
  • The updated draft is now available. Follow the link above. It will become also available on the arXiv later this week.
  • The second January 2 draft has a new section claiming again the original refutation of Reinhardt cardinals.
  • New draft January 3. Rupert has reportedly been in communication with Matteo Viale about his result.
  • Rupert has announced (Jan 3) that he is going to take a week or so to produce a careful rewrite.
  • He has made available his new draft, January 7. It will also be posted on the arXiv.
  • January 8:  In light of the issues identified on this blog, especially the issue mentioned by Gabe, Rupert has sent me an email stating (and asking me to post here) that he is planning to think it through over the next couple of weeks and will then make some kind of statement about whether he thinks he can save the argument.  For the moment, therefore, it seems that we should consider the proof to be on hold.
  • January 24: After consideration, Rupert has withdrawn the claim, sending me the following message:

    “Gabriel has very kindly given me extensive feedback on many different drafts. I attach the latest version which he commented on [January 24 draft above]. He has identified the flaw, namely that on page 3 I claim that $\exists n \forall Y \in W_n \psi(Y)$ if and only if $\forall Y \in U \psi(Y)$. This claim is not justified, and this means that there is no way that is apparent to me to rescue the proof of Lemma 1.2. Gabriel has directed me to a paper of Laver which does indeed show that my mapping e is an elementary embedding but which does not give the stronger claim that I want.

     

    …So, I withdraw my claim. It is possible that this method of proof can work somehow, but some new insight is needed to make it work.”

     

    -Rupert McCallum, January 24, 2018