Transfinite recursion as a fundamental principle in set theory

Posted on by
23

$\newcommand\dom{\text{dom}}
\newcommand\ran{\text{ran}}
\newcommand\restrict{\upharpoonright}$
InfinityAt the Midwest PhilMath Workshop this past weekend, I heard Benjamin Rin (UC Irvine) speak on transfinite recursion, with an interesting new perspective.  His idea was to consider transfinite recursion as a basic principle in set theory, along with its close relatives, and see how they relate to the other axioms of set theory, such as the replacement axiom. In particular, he had the idea of using our intuitions about the legitimacy of transfinite computational processes as providing a philosophical foundation for the replacement axiom.

This post is based on what I learned about Rin’s work from his talk at the workshop and in our subsequent conversations there about it.  Meanwhile, his paper is now available online:

Benjamin Rin, Transfinite recursion and the iterative conception of set, Synthese, October, 2014, p. 1-26. (preprint).

Since I have a little different perspective on the proposal than Rin did, I thought I would like to explain here how I look upon it.  Everything I say here is inspired by Rin’s work.

To begin, I propose that we consider the following axiom, asserting that we may undertake a transfinite recursive procedure along any given well-ordering.

The Principle of Transfinite Recursion. If $A$ is any set with well-ordering $<$ and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for all $b\in A$, where $s\upharpoonright b$ denotes the function $\langle s(a)\mid a<b\rangle$.

We may understand this principle as an infinite scheme of statements in the first-order language of set theory, where we make separate assertions for each possible first-order formula defining the class function $F$, allowing parameters. It seems natural to consider the principle in the background theory of first-order Zermelo set theory Z, or the Zermelo theory ZC, which includes the axiom of choice, and in each case let me also include the axiom of foundation, which apparently is not usually included in Z.   (Alternatively, it is also natural to consider the principle as a single second-order statement, if one wants to work in second-order set theory.)

Theorem. (ZC) The principle of transfinite recursion is equivalent to the axiom of replacement. In other words,

ZC + transfinite recursion  =  ZFC.

Proof. Work in the Zermelo set theory ZC. The converse implication amounts to the well-known observation in ZF that transfinite recursion is legitimate. Let us quickly sketch the argument. Suppose we are given an instance of transfinite recursion, namely, a well-ordering $\langle A,<\rangle$ and a class function $F:V\to
V$. I claim that for every $b\in A$, there is a unique function $s:\{a\in A\mid a\leq b\}\to V$ obeying the recursive rule $s(d)=F(s\upharpoonright d)$ for all $d\leq b$. The reason is that there can be no least $b$ without such a unique function. If all $a<b$ have such a unique function, then by uniqueness they must cohere with one another, since any difference would show up at a least stage and thereby violate the recursion rule, and so by the replacement axiom of ZFC we may assemble these smaller functions into a single function $t$ defined on all $a<b$, and satisfying the recursion rule for those values. We may then extend this function $t$ to be defined on $b$ itself, simply by defining $u(b)=F(t)$ and $u\upharpoonright b=t$, which thereby satisfies the recursion at $b$. Uniqueness again follows from the fact that there can be no least place of disagreement. Finally, using replacement again, let $s(b)$ be the unique value that arises at $b$ during the recursions that work up to and including $b$, and this function $s:A\to V$ satisfies the recursive definition.

Conversely, assume the Zermelo theory ZC plus the principle of transfinite recursion, and suppose that we are faced with an instance of the replacement axiom. That is, we have a set $A$ and a formula $\varphi$, where every $b\in A$ has a unique $y$ such that $\varphi(b,y)$. By the axiom of choice, there is a well-ordering $<$ of the set $A$. We shall now define the function $F:V\to V$. Given a function $s$, where $\dom(s)=\{a\in A\mid a<b\}$ for some $b\in A$, let $F(s)=y$ be the unique $y$ such that $\varphi(b,y)$; and otherwise let $F(s)$ be anything you like. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for every $b\in A$. In this case, it follows that $s(b)$ is the unique $y$ such that $\varphi(a,b)$. Thus, since $s$ is a set, it follows in ZC that $\ran(s)$ is a set, and so we’ve got the image of $A$ under $\varphi$ as a set, which verifies replacement. QED

In particular, it follows that the principle of transfinite recursion implies that every well-ordering is isomorphic to a von Neumann ordinal, a principle Rin refers to as ordinal abstraction. One can see this as a consequence of the previous theorem, since ordinal abstraction holds in ZF by Mostowski’s theorem, which for any well-order $\langle A,<\rangle$ assigns an ordinal to each node $a\mapsto \alpha_a$ according to the recursive rule $\alpha_a=\{\alpha_b\mid b<a\}$. But one can also argue directly as follows, without using the axiom of choice. Assume Z and the principle of transfinite recursion. Suppose that $\langle A,<\rangle$ is a well-ordering. Define the class function $F:V\to V$ so that $F(s)=\ran(s)$, whenever $s$ is a function. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)=\ran(s\restrict b)$. One can now simply prove by induction that $s(b)$ is an ordinal and $s$ is an isomorphism of $\langle A,<\rangle$ with $\ran(s)$, which is an ordinal.

Let me remark that the principle of transfinite recursion allows us also to perform proper-class length recursions.

Observation. Assume Zermelo set theory Z plus the principle of transfinite recursion. If $A$ is any particular class with $<$ a set-like well-ordering of $A$ and $F:V\to V$ is any class function, then there is a class function $S:A\to V$ such that $S(b)=F(S\upharpoonright b)$ for every $b\in A$.

Proof. Since $\langle A,<\rangle$ is set-like, the initial segment $A\upharpoonright d=\{a\in A\mid a<d\}$, for any particular $d\in A$, is a set. It follows that the principle of transfinite recursion shows that there is a function $s_d:(A\upharpoonright d)\to V$ such that $s_d(b)=F(s_d\upharpoonright b)$ for every $b<d$. It is now easy to prove by induction that these $s_d$ must all cohere with one another, and so we may define the class $S(b)=s_d(b)$ for any $d$ above $b$ in $A$. (We may assume without loss that $A$ has no largest element, for otherwise it would be a set.) This provides a class function $S:A\to V$ satisfying the recursive definition as desired. QED

Although it appears explicitly as a second-order statement “there is a class function $S$…”, we may actually take this observation as a first-order theorem scheme, if we simply strengthen the conclusion to provide the explicit definition of $S$ that the proof provides. That is, the proof shows exactly how to define $S$, and if we make the observation state that that particular definition works, then what we have is a first-order theorem scheme. So any first-order definition of $A$ and $F$ from parameters leads uniformly to a first-order definition of $S$ using the same parameters.

Thus, using the principle of transfinite recursion, we may also take proper class length transfinite recursions, using any set-like well-ordered class that we happen to have available.

Let us now consider a weakening of the principle of transfinite recursion, where we do not use arbitrary well-orderings, but only the von Neumann ordinals themselves.

Principle of transfinite recursion on ordinals. If $F:V\to V$ is any class function, then for any ordinal $\gamma$ there is a function $s:\gamma\to V$ such that $s(\beta)=F(s\upharpoonright\beta)$ for all $\beta<\gamma$.

This is a weakening of the principle of transfinite recursion, since every ordinal is well-ordered, but in Zermelo set theory, not every well-ordering is necessarily isomorphic to an ordinal. Nevertheless, in the presence of ordinal abstraction, then this ordinal version of transfinite recursion is clearly equivalent to the full principle of transfinite recursion.

Observation. Work in Z. If every well-ordering is isomorphic to an ordinal, then the principle of transfinite recursion is equivalent to its restriction to ordinals.

Meanwhile, let me observe that in general, one may not recover the full principle of transfinite recursion from the weaker principle, where one uses it only on ordinals.

Theorem. (ZFC) The structure $\langle V_{\omega_1},\in\rangle$ satisfies Zermelo set theory ZC with the axiom of choice, but does not satisfy the principle of transfinite recursion. Nevertheless, it does satisfy the principle of transfinite recursion on ordinals.

Proof. It is easy to verify all the Zermelo axioms in $V_{\omega_1}$, as well as the axiom of choice, provided choice holds in $V$. Notice that there are comparatively few ordinals in $V_{\omega_1}$—only the countable ordinals exist there—but $V_{\omega_1}$ has much larger well-orderings. For example, one may find a well-ordering of the reals already in $V_{\omega+k}$ for small finite $k$, and well-orderings of much larger sets in $V_{\omega^2+17}$ and so on as one ascends toward $V_{\omega_1}$. So $V_{\omega_1}$ does not satisfy the ordinal abstraction principle and so cannot satisfy replacement or the principle of transfinite recursion. But I claim nevertheless that it does satisfy the weaker principle of transfinite recursion on ordinals, because if $F:V_{\omega_1}\to V_{\omega_1}$ is any class in this structure, and $\gamma$ is any ordinal, then we may define by recursion in $V$ the function $s(\beta)=F(s\restrict\beta)$, which gives a class $s:\omega_1\to V_{\omega_1}$ that is amenable in $V_{\omega_1}$. In particular, $s\restrict\gamma\in V_{\omega_1}$ for any $\gamma<\omega_1$, simply because $\gamma$ is countable and $\omega_1$ is regular. QED

My view is that this example shows that one doesn’t really want to consider the weakened principle of transfinite recursion on ordinals, if one is working in the Zermelo background ZC, simply because there could be comparatively few ordinals, and this imposes an essentially arbitrary limitation on the principle.

Let me point out, however, that there was a reason we had to go to $V_{\omega_1}$, rather than considering $V_{\omega+\omega}$, which is a more-often mentioned model of the Zermelo axioms. It is not difficult to see that $V_{\omega+\omega}$ does not satisfy the principle of transfinite recursion on the ordinals, because one can define the function $s(n)=\omega+n$ by recursion, setting $s(0)=\omega$ and $s(n+1)=s(n)+1$, but this function does not exist in $V_{\omega+\omega}$. This feature can be generalized as follows:

Theorem. Work in the Zermelo set theory Z. The principle of transfinite recursion on ordinals implies that if $\langle A,<\rangle$ is a well-ordered set, and $A$ is bijective with some ordinal, then $\langle A,<\rangle$ is order-isomorphic with an ordinal.

In other words, we get ordinal abstraction for well-orderings whose underlying set is bijective with an ordinal.

First, the proof of the first theorem above actually shows the following local version:

Lemma. (Z) If one has the principle of transfinite recursion with respect to a well-ordering $\langle A,<\rangle$, then $A$-replacement holds, meaning that if $F:V\to V$ is any class function, then the image $F”A$ is a set.

Proof of theorem. Suppose that $\langle A,<\rangle$ is a well-ordering, and that $A$ is bijective with some ordinal $\kappa$, and that $F:V\to V$ is a class function. Assume the principle of transfinite recursion for $\kappa$. We prove by induction on $d\in A$ that there is a unique function $s_d$ with $\dom(s)=\{a\in A\mid a\leq d\}$ and satisfying the recursive rule $s(b)=F(s\upharpoonright b)$. If this statement is true for all $d<d’$, then because the size of the predecessors of $d’$ in $\langle A,<\rangle$ is at most $\kappa$, we may by the lemma form the set $\{s_d\mid d<d’\}$, which is a set by $\kappa$-replacement. These functions cohere, and the union of these functions gives a function $t:(A\upharpoonright d’)\to V$ satisfying the recursion rule for $F$. Now extend this function one more step by defining $s(d’)=F(t)$ and $s\upharpoonright d’=t$, thereby handling the existence claim at $d’$. As in the main theorem, all these functions cohere with one another, and by $\kappa$-replacement we may form the set $\{s_d\mid d\in A\}$, whose union is the desired function $s:A\to V$ satisfying the recursion rule given by $F$, as desired. QED

For example, if you have the principle of transfinite recursion for ordinals, and $\omega$ exists, then every countable well-ordering is isomorphic to an ordinal. This explains why we had to go to $\omega_1$ to find a model satisfying transfinite recursion on ordinals. One can understand the previous theorem as showing that although the principle of transfinite recursion on ordinals does not prove ordinal abstraction, it does prove many instances of it: for every ordinal $\kappa$, every well-ordering of cardinality at most $\kappa$ is isomorphic to an ordinal.

It is natural also to consider the principle of transfinite recursion along a well-founded relation, rather than merely a well-ordered relation.

The principle of well-founded recursion. If $\langle A,\lhd\rangle$ is a well-founded relation and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)$ for all $b\in A$, where $s\restrict b$ means the function $s$ restricted to the domain of elements $a\in A$ that are hereditarily below $b$ with respect to $\lhd$.

Although this principle may seem more powerful, in fact it is equivalent to transfinite recursion.

Theorem. (ZC) The principle of transfinite recursion is equivalent to the principle of well-founded recursion.

Proof. The backward direction is immediate, since well-orders are well-founded. For the forward implication, assume that transfinite recursion is legitimate. It follows by the main theorem above that ZFC holds. In this case, well-founded recursion is legitimate by the familiar arguments. For example, one may prove in ZFC that for every node in the field of the relation, there is a unique solution of the recursion defined up to and including that node, simply because there can be no minimal node without this property.  Then, by replacement, one may assemble all these functions together into a global solution. Alternatively, arguing directly from transfinite recursion, one may put an ordinal ranking function for any given well-founded relation $\langle A,\lhd\rangle$, and then prove by induction on this rank that one may construct functions defined up to and including any given rank, that accord with the recursive rule. In this way, one gets the full function $s:A\to V$ satisfying the recursive rule. QED

Finally, let me conclude this post by pointing out how my perspective on this topic differs from the treatment given by Benjamin Rin. I am grateful to him for his idea, which I find extremely interesting, and as I said, everything here is inspired by his work.

One difference is that Rin mainly considered transfinite recursion only on ordinals, rather than with respect to an arbitrary well-ordered relation (but see footnote 17 in his paper). For this reason, he had a greater need to consider whether or not he had sufficient ordinal abstraction in his applications. My perspective is that transfinite recursion, taken as a basic principle, has nothing fundamentally to do with the von Neumann ordinals, but rather has to do with a general process undertaken along any well-order. And the theory seems to work better when one undertakes it that way.

Another difference is that Rin stated his recursion principle as a principle about iterating through all the ordinals, rather than only up to any given ordinal. This made the resulting functions $S:\text{Ord}\to V$ into class-sized objects for him, and moved the whole analysis into the realm of second-order set theory. This is why he was led to prove his main equivalence with replacement in second-order Zermelo set theory. My treatment shows that one may undertake the whole theory in first-order set theory, without losing the class-length iterations, since as I explained above the class-length iterations form classes, definable from the original class functions and well-orders. And given that a completely first-order account is possible, it seems preferable to undertake it that way.

Update. (August 17, 2018) I’ve now realized how to eliminate the need for the axiom of choice in the arguments above. Namely, the main argument above shows that the principle of transfinite recursion implies the principle of well-ordered replacement, meaning the axiom of replacement for instances where the domain set is well-orderable.  The point now is that in recent work with Alfredo Roque Freire, I have realized that The principle of well-ordered replacement is equivalent to full replacement over Zermelo set theory with foundation. We may therefore deduce:

Corollary. The principle of transfinite recursion is equivalent to the replacement axiom over Zermelo set theory with foundation.

We do not need the axiom of choice for this.

MathOverflow, the eternal fountain of mathematics: reflections on a hundred kiloreps

Posted on by
14


profile for Joel David Hamkins at MathOverflow, Q&A for professional mathematiciansIt seems to appear that I have somehow managed to pass  the 100,000 score milestone for reputation on MathOverflow.  A hundred kiloreps!  Does this qualify me for micro-celebrity status?  I have clearly been spending an inordinate amount of time on MO…  Truly, it has been a great time.

MathOverflow, an eternal fountain of mathematics, overflows with fascinating questions and answers on every imaginable mathematical topic, drawing unforeseen connections, seeking generalizations, clarification, or illustrative examples, questioning assumptions, or simply asking for an explanation of a subtle mathematical point.  The mathematics is sophisticated and compelling.  How could a mathematician not immediately plunge in?

I first joined MathOverflow in November 2009, when my colleague-down-the-hall Kevin O’Bryant dropped into my office and showed me the site.  He said that it was for “people like us,” research mathematicians who wanted to discuss mathematical issues with other professionals, and he was completely right.  Looking at the site, I found Greg Kuperberg’s answer to a question on the automorphism tower problem in group theory, which was one of the first extremely popular questions at that time, the top-rated question.  I was hooked immediately, and I told Kevin on that very first day that it was clear that MathOverflow was going to take a lot of time.

I was pleased to find right from the beginning that, although there were not yet many logicians participating on MO, there were nevertheless many logic questions, revealing an unexpectedly broad interest in math logic issues amongst the general mathematical community.  I found questions about definability, computability, undecidability, logical independence, about the continuum hypothesis and the axiom of choice and about large cardinals, asked by mathematicians in diverse research areas, who seemed earnestly to want to know the answer.  How pleased I was to find such a level of interest in the same issues that fascinated me; and how pleased I was also to find that I was often able to answer.

In the early days, I may have felt a little that I should be a kind of ambassador for logic, introducing the subject or aspects of it to those who might not know all about it yet; for example, in a few answers I explained and introduced the topic of cardinal characteristics of the continuum and the subject of Borel equivalence relation theory, since I had felt that mathematicians outside logic might not necessarily know much about it, even when it offered connections to things they did know about.  I probably wouldn’t necessarily answer the same way today, now that MO has many experts in those subjects and a robust logic community.  What a pleasure it has become.

A while back I wrote a post The use and value of MathOverflow in response to an inquiry of François Dorais, and I find the remarks I made then are as true for me today as ever.

I feel that mathoverflow has enlarged me as a mathematician.  I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics.  I’ve read some really great answers that opened up new perspectives for me.  But just as importantly, I’ve learned a lot when coming up with my own answers.  It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through.  How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer.  Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts.  This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk.  This kind of knowledge has helped me to improve my mathematical writing in general.

Thanks very much again, MathOverflow!  I am grateful.

A few posts come to mind:

There have been so many more great questions and posts.  If you are inclined, feel free to post comments below linking to your favorite MO posts!

Concerning the MO reputation system, I suppose some might suspect me of harboring unnatural thoughts on reputation — after all, I once proposed (I can’t find the link now) that the sole basis of tenure and promotion decisions for mathematics faculty, as well as choice of premium office space, should be:  MO reputation, ha! — but in truth, I look upon it all as a good silly game.  One may take reputation as seriously as one takes any game seriously, and many mathematicians can indeed take a game seriously.  My honest opinion is that the reputation and badge system is an ingenious piece of social engineering.  The designers must have had a good grasp on human psychology, an understanding of the kinds of reasons that might motivate a person to participate in such a site; one thinks, for example, of the intermittent reward theory.  I find it really amazing what the stackexchange designers have created, and who doesn’t love a good game?

Announcement on History of MathOverflow

Does definiteness-of-truth follow from definiteness-of-objects? NY Philosophical Logic Group, NYU, November 2014

Posted on by
Reply

This will be a talk for the New York Philosophical Logic Group, November 10, 2014, 5-7pm, at the NYU Philosophy Department, 5 Washington Place, Room 302.

Indefinite arithmetic truth

Abstract. This talk — a mix of mathematics and philosophy — concerns the extent to which we may infer definiteness of truth in a mathematical context from definiteness of the underlying objects and structure of that context. The philosophical analysis is based in part on the mathematical observation that the satisfaction relation for model-theoretic truth is less absolute than often supposed.  Specifically, two models of set theory can have the same natural numbers and the same structure of arithmetic in common, yet disagree about whether a particular arithmetic sentence is true in that structure. In other words, two models can have the same arithmetic objects and the same formulas and sentences in the language of arithmetic, yet disagree on their corresponding theories of truth for those objects. Similarly, two models of set theory can have the same natural numbers, the same arithmetic structure, and the same arithmetic truth, yet disagree on their truths-about-truth, and so on at any desired level of the iterated truth-predicate hierarchy.  These mathematical observations, for which I shall strive to give a very gentle proof in the talk (using only elementary classical methods), suggest that a philosophical commitment to the determinate nature of the theory of truth for a structure cannot be seen as a consequence solely of the determinateness of the structure in which that truth resides. The determinate nature of arithmetic truth, for example, is not a consequence of the determinate nature of the arithmetic structure N = {0,1,2,…} itself, but rather seems to be an additional higher-order commitment requiring its own analysis and justification.

This work is based on my recent paper, Satisfaction is not absolute, joint with Ruizhi Yang (Fudan University, Shanghai).

When does every definable set have a definable member? CUNY Set Theory Seminar, October 2014

Posted on by
2

This will be a talk for the CUNY set theory seminar, October 10, 2014, 12pm  GC 6417.

Abstract. Although the concept of `being definable’ is not generally expressible in the language of set theory, it turns out that the models of ZF in which every definable nonempty set has a definable element are precisely the models of V=HOD.  Indeed, V=HOD is equivalent to the assertion merely that every $\Pi_2$-definable set has an ordinal-definable element. Meanwhile, this is not true in the case of $\Sigma_2$-definability, because every model of ZFC has a forcing extension satisfying $V\neq\text{HOD}$ in which every $\Sigma_2$-definable set has an ordinal-definable element.

This is joint work with François G. Dorais and Emil Jeřábek, growing out of some questions and answers on MathOverflow, namely,

Definable collections without definable members
A question asked by Ashutosh five years ago, in which François and I gradually came upon the answer together.
Is it consistent that every definable set has a definable member?
A similar question asked last week by (anonymous) user38200
Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable member?
A question I had regarding the limits of an issue in my answer to the previous question.

In this talk, I shall present the answers to all these questions and place the results in the context of classical results on definability, including a review of basic concepts for graduate students.

My research collaborators

Posted on by
Reply

CollaborationI have been very fortunate in my research to have had the opportunity to work closely with a number of insightful researchers. I’ve learned a great deal from them, and I’m truly grateful.

So I’ve gathered here a list of my collaborators. In almost all cases, the collaboration resulted in a published joint research article, which you can find on my list of publications (in a few instances, for collaborations currently underway, a paper is not necessarily yet available).  Several of my collaborations have been sustained long-term affairs, leading to a series of joint publications on various topics over several years.  Naturally, I am hopeful that all my collaborations will continue to be fruitful for many years into the future.

The rule-making game

Posted on by
8

They said a king once ruled the forest, by Lizzie ThomasLet me tell you about a new game that we’ve been playing in our family, the rule-making game.  It is a talking game, requiring no pieces or objects of any kind, and it can easily be played whilst walking or traveling.  My children and I recently played several rounds of it walking around London on a recent visit there.

The game has no rules, initially, nor even any definite procedure — it is different every time — but things usually become clear soon enough.  It usually makes a better game to cooperate on the first several turns to lay the groundwork.

Let me explain how to play simply by example:

Papa:  The first rule is that the players shall take turns making rules, and that every rule shall have a rule number, which is incremented on each turn.

Horatio:  The second rule is that the players must state their rules in the form, “The first rule is…” or “the second rule is…” and so on, and that players are not allowed to ask what is the current rule number, or they lose.

Hypatia:  The third rule is that the other players must say, “thank you” after another player makes a rule.

     (… “thank you”…. “thank you”….)

Papa: The fourth rule is that the rules must not contradict each other, and no rule is allowed that abrogates an earlier rule.

     (… “thank you”…. “thank you”….)

Horatio:  The fifth rule is that after making an odd-numbered rule, the player must stomp on the ground.

     (STOMP… “thank you”…. “thank you”….)

Hypatia: The sixth rule is that no player may win immediately after their own rule.

     (… “thank you”…. “thank you”….)

Papa:  The seventh rule is that right after a player stomps according to rule five, the other two players must hop.

     (STOMP … “thank you”…. “thank you”….HOP….HOP…)

Horatio:  The eighth rule is that if a player loses, then the game continues without that person.

     (… “thank you”…. “thank you”….)

Hypatia: The ninth rule is that after stating a rule, the other two players must state a different color.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “blue”… “green”…)

Papa:  The tenth rule is that furthermore, those colors must never repeat, and they must be stated simultaneously, on the count of 1-2-3.

     (… “thank you”…. “thank you”…. “1-2-3: neon green / violet”)

Horatio: The eleventh rule is that if there is only one player left, then that player wins.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: red/orange”)

Hypatia:  The twelfth rule is that every player must jump up and down (…jump…) while stating their rule. (….jump jump jump…)

     (… “thank you”…. “thank you”…. “1-2-3: pink/turquoise”)

Papa: (jump jump…) The thirteenth rule is that (…jump…) in the case of dispute (…jump…), the question of whether or not someone has violated or followed a rule shall be decided by majority vote (…jump…).

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: yellow/brown”)

Horatio: (jump….) The fourteenth rule is that (…jump…) before stating their rule, the players must state a country, and that whoever repeats a country loses (…jump…)

     (… “thank you”…. “thank you”…. “1-2-3: black/gray”)

Hypatia:  (jump…)  Germany.  The fifteenth rule is that (…jump…) there can be at most twenty-five rules.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: sky blue / peach”)

Papa:  (jump…)  United States.  The sixteenth rule is that (…jump…) if all current players lose at the same time after a rule, then the player previous to that rule-maker is declared the “honorary winner”.  (…jump…)

(… “thank you”…. “thank you”…. “1-2-3: white / white”)

Oh no! Since both Horatio and Hypatia said “white”, they both lose.  And then Papa also loses in light of rule six. So we’ve all lost!  But then, in light of rule sixteen, Hypatia is declared the honorary winner! Hooray for Hypatia!

I hope you all get the idea.  Please enjoy!  And report your crazy or interesting rules in the comments below.

The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

Posted on by
Reply

Releasing the hordesI shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always 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, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The span of infinity, roundtable discussion at The Helix Center, October 2014

Posted on by
Reply

I was a panelist at The Span of Infinity, a roundtable discussion held at The Helix Center, at the New York Psychoanalytic Society & Institute, 247 E 82nd Street, on October 25, 2014, 2:30 – 4:30 pm.

The Helix Center describes the discussion topic as:

Perhaps no thing conceived in the mind has enjoyed a greater confluence of cosmological, mathematical, philosophical, psychological, and theological inquiry than the notion of the infinite. The epistemological tension between the concrete and the ideal, between the phenomenological and the ontological, is nowhere clearer in outline yet more obscure in content. These inherent paradoxes limn the vital, eternal questions we will explore about humankind’s place in the universe and the comprehensibility of existence.

The Helix Center Roundtable Series is described by:

Our roundtable format is designated the Theaetetus Table, an extempore discussion among five participants, all leaders in their respective fields, and named for the classical Greek mathematician and eponym for the Platonic dialogue investigating the nature of knowledge, who proved that there are five regular convex polyhedra, or Platonic solids. Each Theaetetus Table aspires to emulate the dialogue’s unhurried search for wisdom; and, like the five Platonic solids held to be the fundamental building blocks of the classical elements, the contributions of our five participants become the fundamental constituents of interdisciplinary insights emerging in the alchemy of the roundtable, insights that, in turn, transform the elemental thinking of those participants. The gathering of five discussants also symbolizes the five interrelated qualities of mind our interdisciplinary forums are intended to facilitate in our participants, and inculcate in our audience: curiosity, playfulness, inspiration, reflection, and wonder.

The video of the actual event is now available:

The pluralist perspective on the axiom of constructibility, MidWest PhilMath Workshop, Notre Dame, October 2014

Posted on by
8

University of Notre DameThis will be a featured talk at the Midwest PhilMath Workshop 15, held at Notre Dame University October 18-19, 2014.  W. Hugh Woodin and I will each give one-hour talks in a session on Perspectives on the foundations of set theory, followed by a one-hour discussion of our talks.

Abstract. I shall argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility V = L on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of V = L inside larger set-theoretic universes.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible. Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory. In this talk, I shall criticize Maddy’s proposal, pointing out that neither the fairly-interpreted-in relation nor the (strongly) maximizes-over relation is transitive, and furthermore, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s account, contrary to what had been desired. Ultimately, I shall argue that the V≠L via maximize position loses its force on a multiverse conception of set theory with an upwardly extensible concept of set, in light of the classical facts that models of set theory can generally be extended to models of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Slides

Large cardinals need not be large in HOD

Posted on by
1

[bibtex key=ChengFriedmanHamkins2015:LargeCardinalsNeedNotBeLargeInHOD]

Abstract. We prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal $\kappa$ need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in $V$, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals.

In this article, we prove that large cardinals need not generally exhibit their large cardinal nature in HOD, the inner model of hereditarily ordinal-definable sets, and there can be a divergence in strength between the large cardinals of the ambient set-theoretic universe $V$ and those of HOD. Our general theme concerns the questions:

Questions.

1. To what extent must a large cardinal in $V$ exhibit its large cardinal properties in HOD?

2. To what extent does the existence of large cardinals in $V$ imply the existence of large cardinals in HOD?

For large cardinal concepts beyond the weakest notions, we prove, the answers are generally negative. In Theorem 4, for example, we construct a model with a supercompact cardinal that is not weakly compact in HOD, and Theorem 9 extends this to a proper class of supercompact cardinals, none of which is weakly compact in HOD, thereby providing some strongly negative instances of (1). The same model has a proper class of supercompact cardinals, but no supercompact cardinals in HOD, providing a negative instance of (2). The natural common strengthening of these situations would be a model with a proper class of supercompact cardinals, but no weakly compact cardinals in HOD. We were not able to arrange that situation, however, and furthermore it would be ruled out by Conjecture 13, an intriguing positive instance of (2) recently proposed by W. Hugh Woodin, namely, that if there is a supercompact cardinal, then there is a measurable cardinal in HOD. Many other natural possibilities, such as a proper class of measurable cardinals with no weakly compact cardinals in HOD, remain as open questions.

CUNY talk | Rutgers talk | Luminy talk

A common forcing extension obtained via different forcing notions

Posted on by
14

I’d like to write about the situation that occurs in set theory when a forcing extension $V[G]=V[H]$ arises over a ground model $V$ in two different ways simultaneously, using generic filters over two different forcing notions $G\subset\mathbb{B}$ and $H\subset\mathbb{C}$. The general fact, stated in theorem 1, is that in this case, the two forcing notions are actually isomorphic on a cone $\mathbb{B}\upharpoonright b\cong\mathbb{C}\upharpoonright c$, with the isomorphism carrying the one generic filter to the other. In other words, below these respective conditions $b$ and $c$, the forcing notions and the respective generic filters are not actually different.

I have always assumed that this fact was part of the classical forcing folklore results, but it doesn’t seem to be mentioned explicitly in the usual forcing literature (it appears as lemma 25.5 in Jech’s book), and so I am writing an account of it here. Victoria Gitman and I have need of it in a current joint project. (Bob Solovay mentions in the comments below that the result is due to him, and provides a possible 1975 reference.)

Theorem 1. If $V[G]=V[H]$, where $G\subset \mathbb{B}$ and $H\subset\mathbb{C}$ are $V$-generic filters on the complete Boolean algebras $\mathbb{B}$ and $\mathbb{C}$, respectively, then there are conditions $b\in\mathbb{B}$ and $c\in\mathbb{C}$ such that $\mathbb{B}\upharpoonright b$ is isomorphic to $\mathbb{C}\upharpoonright c$ by an isomorphism carrying $G$ to $H$.

The proof will also establish the following related result, concerning the situation where one extension is merely contained in the other.

Theorem 2. If $V[H]\subset V[G]$, where $G\subset\mathbb{B}$ and $H\subset\mathbb{C}$ are $V$-generic filters on the complete Boolean algebras $\mathbb{B}$ and $\mathbb{C}$, respectively, then there are conditions $b\in\mathbb{B}$ and $c\in\mathbb{C}$ such that $\mathbb{C}\upharpoonright c$ is isomorphic to a complete subalgebra of $\mathbb{B}\upharpoonright b$.

By $\mathbb{B}\upharpoonright b$, where $b$ is a condition in $\mathbb{B}$ (that is, a nonzero element of $\mathbb{B}$), what I mean is the Boolean algebra consisting of the interval $[0,b]$ in $\mathbb{B}$, using relative complement $b-a$ as the negation of $a$. This is the complete Boolean algebra that arises when forcing with the conditions in $\mathbb{B}$ below $b$.

Proof: In order to prove theorem 2, let me assume at first only that $V[H]\subset V[G]$. It follows that $H=\dot H_G$ for some $\mathbb{B}$-name $\dot H$, and we may choose a condition $b\in G$ forcing that $\dot H$ is a $\check V$-generic filter on $\check{\mathbb{C}}$.

I claim that there is some $c\in H$ such that every $d\leq c$ has $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$. Note that every $d\in H$ has $[\![\check d\in\dot H]\!]\in G$ by the truth lemma, since $H=\dot H_G$, and so $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$ for $d\in H$. If $c\in H$ forces that every $d$ in the generic filter has that property, then indeed every $d\leq c$ has $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$ as claimed.
In other words, from the perspective of the $\mathbb{B}$ forcing, every $d\leq c$ has a nonzero possibility to be in $\dot H$.

Define $\pi:\mathbb{C}\upharpoonright c\to\mathbb{B}$ by $$\pi(d)=b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}.$$ Using the fact that $b$ forces that $\dot H$ is a filter, it is straightforward to verify that

  • $d\leq e\implies \pi(d)\leq\pi(e)$, since if $d\leq e$ and $d\in H$, then $e\in H$.
  • $\pi(d\wedge e)=\pi(d)\wedge \pi(e)$, since $[\![\check d\in\dot H]\!]\wedge[\![\check e\in \dot H]\!]=[\![\check{(b\wedge e)}\in\dot H]\!]$.
  • $\pi(d-e)=\pi(d)-\pi(e)$, since $[\![\check{(d-e)}\in\dot H]\!]=[\![\check d\in\dot H]\!]-[\![\check e\in\dot H]\!]$.

Thus, $\pi$ is a Boolean algebra embedding of $\mathbb{C}\upharpoonright c$ into $\mathbb{B}\upharpoonright\pi(c)$.

Let me argue that this embedding is a complete embedding. Suppose that $a=\bigvee A$ for some subset $A\subset\mathbb{C}\upharpoonright c$ with $A\in V$. Since $H$ is $V$-generic, it follows that $a\in H$ just in case $H$ meets $A$. Thus, $[\![\check a\in\dot H]\!]=[\![\exists x\in\check A\, x\in \dot H]\!]=\bigvee_{x\in A}[\![\check x\in\dot H]\!]$, and so $\pi(\bigvee A)=\bigvee_{x\in A}\pi(x)$, and so $\pi$ is complete, as desired. This proves theorem 2.

To prove theorem 1, let me now assume fully that $V[G]=V[H]$. In this case, there is a $\mathbb{C}$ name $\dot G$ for which $G=\dot G_H$. By strengthening $b$, we may assume without loss that $b$ also forces that, that is, that $b$ forces $\Gamma=\check{\dot G}_{\dot H}$, where $\Gamma$ is the canonical $\mathbb{B}$-name for the generic object, and $\check{\dot G}$ is the $\mathbb{B}$-name of the $\mathbb{C}$-name $\dot G$. Let us also strengthen $c$ to ensure that $c$ forces $\dot G$ is $\check V$-generic for $\check{\mathbb{C}}$. For $d\leq c$ define $\pi(d)=[\![\check d\in\dot H]\!]^{\mathbb{B}}$ as above, which provides a complete embedding of $\mathbb{C}\upharpoonright c$ to $\mathbb{B}\upharpoonright\pi(c)$. I shall now argue that this embedding is dense below $\pi(c)$. Suppose that $a\leq \pi(c)$ in $\mathbb{B}$. Since $a$ forces $\check a\in\Gamma$ and also $\check c\in\dot H$, it must also force that there is some $d\leq c$ in $\dot H$ that forces via $\mathbb{C}$ over $\check V$ that $\check a\in\dot G$. So there must really be some $d\leq c$ forcing $\check a\in\dot G$. So $\pi(d)$, which forces $\check d\in\dot H$, will also force $\check a\in\check{\dot G}_{\dot H}=\Gamma$, and so $\pi(d)\Vdash_{\mathbb{B}}\check a\in\Gamma$, which means $\pi(d)\leq a$ in ${\mathbb{B}}$. Thus, the range of $\pi$ on $\mathbb{C}\upharpoonright c$ is dense below $\pi(c)$, and so $\pi$ is a complete dense embedding of ${\mathbb{C}}\upharpoonright c$ to ${\mathbb{B}}\upharpoonright \pi(c)$. Since these are complete Boolean algebras, this means that $\pi$ is actually an isomorphism of $\mathbb{C}\upharpoonright c$ with $\mathbb{B}\upharpoonright \pi(c)$, as desired.

Finally, note that if $d\in H$ below $c$, then since $H=\dot H_G$, it follows that $[\![\check d\in\dot H]\!]\in G$, which is to say $\pi(d)\in G$, and so $\pi$ carries $H$ to $G$ on these cones. So $\pi^{-1}$ is the isomorphism stated in theorem 1.QED

Finally, I note that one cannot get rid of the need to restrict to cones, since it could be that $\mathbb{B}$ and $\mathbb{C}$ are the lottery sums of a common forcing notion, giving rise to $V[G]=V[H]$, together with totally different non-isomorphic forcing notions below some other incompatible conditions. So we cannot expect to prove that $\mathbb{B}\cong\mathbb{C}$, and are content to get merely that $\mathbb{B}\upharpoonright b\cong\mathbb{C}\upharpoonright c$, an isomorphism below respective conditions.

Large cardinals need not be large in HOD, International Workshop on Set Theory, CIRM, Luminy, September 2014

Posted on by
Reply

I shall speak at the 13th International Workshop on Set Theory, held at the CIRM Centre International de Rencontres Mathématiques in Luminy near Marseille, France, September 29 to October 3, 2014. 

Abstract.  I shall prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in $V$, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals. There are many open questions.

This talk will include joint work with Cheng Yong and Sy-David Friedman.

Article | Participants | Slides

A meeting at the crossroads – science, performance and the art of possibility, panel discussion, Underground Zero Festival, Intrinsic Value Project, July 2014

Posted on by
7

I shall be a panelist at A meeting at the crossroads – science, performance and the art of possibility, a panel discussion considering the intrinsic value of Art and Science, a part of the Intrinsic Value series at the Undergroundzero Festival 2014.

Are theatre and the arts vital to life here and now? Does science creatively address the larger questions of our time? This panel will bring together distinguished scientists and theatre professionals to answer these questions. They will consider how both areas are intrinsically valuable to society and investigate the performative possibilities when the two fields overlap.

At the the Abrazo Interno Gallery, Clemente Soto Vélez, 107 Suffolk Street New York NY 10002. (Venue and Tickets) July 9 & 10, 2014, 7-8 pm.

Local properties in set theory

Posted on by
12

V_thetaSet-theoretic arguments often make use of the fact that a particular property $\varphi$ is local, in the sense that instances of the property can be verified by checking certain facts in only a bounded part of the set-theoretic universe, such as inside some rank-initial segment $V_\theta$ or inside the collection $H_\kappa$ of all sets of hereditary size less than $\kappa$. It turns out that this concept is exactly equivalent to the property being $\Sigma_2$ expressible in the language of set theory.

Theorem. For any assertion $\varphi$ in the language of set theory, the following are equivalent:

  1. $\varphi$ is ZFC-provably equivalent to a $\Sigma_2$ assertion.
  2. $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \theta\, V_\theta\models\psi$,” where $\psi$ is a statement of any complexity.
  3. $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \kappa\, H_\kappa\models\psi$,” where $\psi$ is a statement of any complexity.

Just to clarify, the $\Sigma_2$ assertions in set theory are those of the form $\exists x\,\forall y\,\varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. The set $V_\theta$ refers to the rank-initial segment of the set-theoretic universe, consisting of all sets of von Neumann rank less than $\theta$. The set $H_\kappa$ consists of all sets of hereditary size less than $\kappa$, that is, whose transitive closure has size less than $\kappa$.

Proof. ($3\to 2$) Since $H_\kappa$ is correctly computed inside $V_\theta$ for any $\theta>\kappa$, it follows that to assert that some $H_\kappa$ satisfies $\psi$ is the same as to assert that some $V_\theta$ thinks that there is some cardinal $\kappa$ such that $H_\kappa$ satisfies $\psi$.

($2\to 1$) The statement $\exists \theta\, V_\theta\models\psi$ is equivalent to the assertion $\exists\theta\,\exists x\,(x=V_\theta\wedge x\models\psi)$. The claim that $x\models\psi$ involves only bounded quantifiers, since the quantifiers of $\psi$ become bounded by $x$. The claim that $x=V_\theta$ is $\Pi_1$ in $x$ and $\theta$, since it is equivalent to saying that $x$ is transitive and the ordinals of $x$ are precisely $\theta$ and $x$ thinks every $V_\alpha$ exists, plus a certain minimal set theory (so far this is just $\Delta_0$, since all quantifiers are bounded), plus, finally, the assertion that $x$ contains every subset of each of its elements. So altogether, the assertion that some $V_\theta$ satisfies $\psi$ has complexity $\Sigma_2$ in the language of set theory.

($1\to 3$) This implication is a consequence of the following absoluteness lemma.

Lemma. (Levy) If $\kappa$ is any uncountable cardinal, then $H_\kappa\prec_{\Sigma_1} V$.

Proof. Suppose that $x\in H_\kappa$ and $V\models\exists y\,\psi(x,y)$, where $\psi$ has only bounded quantifiers. Fix some such witness $y$, which exists inside some $H_\gamma$ for perhaps much larger $\gamma$. By the Löwenheim-Skolem theorem, there is $X\prec H_\gamma$ with $\text{TC}(\{x\})\subset X$, $y\in X$ and $X$ of size less than $\kappa$. Let $\pi:X\cong M$ be the Mostowski collapse of $X$, so that $M$ is transitive, and since it has size less than $\kappa$, it follows that $M\subset H_\kappa$. Since the transitive closure of $\{x\}$ was contained in $X$, it follows that $\pi(x)=x$. Thus, since $X\models\psi(x,y)$ we conclude that $M\models \psi(x,\pi(y))$ and so hence $\pi(y)$ is a witness to $\psi(x,\cdot)$ inside $H_\kappa$, as desired. QED

Using the lemma, we now prove the remaining part of the theorem. Consider any $\Sigma_2$ assertion $\exists x\,\forall y\, \varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. This assertion is equivalent to $\exists\kappa\, H_\kappa\models\exists x\,\forall y\,\varphi_0(x,y)$, simply because if there is such a $\kappa$ with $H_\kappa$ having such an $x$, then by the lemma this $x$ works for all $y\in V$ since $H_\kappa\prec_{\Sigma_1}V$; and conversely, if there is an $x$ such that $\forall y\, \varphi_0(x,y)$, then this will remain true inside any $H_\kappa$ with $x\in H_\kappa$. QED

In light of the theorem, it makes sense to refer to the $\Sigma_2$ properties as the locally verifiable properties, or perhaps as semi-local properties, since positive instances of $\Sigma_2$ assertions can be verified in some sufficiently large $V_\theta$, without need for unbounded search. A truly local property, therefore, would be one such that positive and negative instances can be verified this way, and these would be precisely the $\Delta_2$ properties, whose positive and negative instances are locally verifiable.

Tighter concepts of locality are obtained by insisting that the property is not merely verified in some $V_\theta$, perhaps very large, but rather is verified in a $V_\theta$ where $\theta$ has a certain closeness to the parameters or instance of the property. For example, a cardinal $\kappa$ is measurable just in case there is a $\kappa$-complete nonprincipal ultrafilter on $\kappa$, and this is verified inside $V_{\kappa+2}$. Thus, the assertion “$\kappa$ is measurable,” has complexity $\Sigma^2_1$ over $V_\kappa$. One may similarly speak of $\Sigma^n_m$ or $\Sigma^\alpha_m$ properties, to refer to properties that can be verified with $\Sigma_m$ assertions in $V_{\kappa+\alpha}$. Alternatively, for any class function $f$ on the ordinals, one may speak of $f$-local properties, meaning a property that can be checked of $x\in V_\theta$ by checking a property inside $V_{f(\theta)}$.

This post was made in response to a question on MathOverflow.

New York University, Visiting Professor of Philosophy, 2015

Posted on by
Reply

NYU PhilosophyI am Visiting Professor of Philosophy at New York University for the Spring 2015 semester, while on sabbatical from CUNY.  This is my second jaunt at NYU, since I was also Visiting Professor there in 2011, and I am hopeful this visit will be as productive as my last.

NYU faculty profile