Inner-model reflection principles

February 2, 2019

Typical reflection principles in set theory are concerned with the height of the universe, or the relative height of certain stages. The resemblance between stages or between the universe itself and some of these stages is a very useful guiding principle that serves us to motivate large cardinal statements and many consequences of forcing axioms.

It is natural to wonder about similar reflection principles concerned instead with the width of the universe. In our paper Inner-model reflection principlesNeil BartonGunter FuchsJoel David HamkinsJonas ReitzRalf Schindler and I consider precisely this kind of reflection. Say that the inner-model reflection principle holds if and only if for any set a, any first-order property \varphi(a) true in the universe already holds in some proper inner model containing a as an element.

We establish the consistency of the principle relative to ZFC. In fact, we build a model of the stronger ground-model reflection principle, where we further require that any such first-order \varphi(a) reflects to a ground of V, that is, an inner model W with a\in W such that V is a set-generic extension of W. A formal advantage of this principle is that, using results in what we now call set-theoretic geology, ground-model reflection is formalizable as a first-order schema. Inner-model reflection, on the other hand, seems to genuinely require a second-order formalization. It is still open whether this is indeed the case, in our paper we explain some of the difficulties in showing this.

The paper studies the principle under large cardinals and forcing axioms, and compares it with other statements considered in recent years, such as the maximality principle or the inner model hypothesis. The most technically involved and interesting results in the paper show that inner-model reflection and even ground-model reflection hold in certain fine-structural inner models but also that this requires large cardinals, and that the large cardinal requirements differ for both principles (precisely a proper class of Woodin cardinals is needed for ground-model reflection).

Curiously, the paper started as a series of informal exchanges in response to a question on math.stackexchange.

See also here. The paper will appear in Studia Logica. Meanwhile, it can be accessed on the arXiv, or in my papers page.


Foundations of Mathematics

February 1, 2019

Foundations of Mathematics, Andrés E. Caicedo, James Cummings, Peter Koellner, and Paul B. Larson, eds., Contemporary Mathematics, vol. 690, Amer. Math. Soc., Providence, RI, 2017. DOI: 10.1090/conm/690. MR3656304. Zbl 06733965.

This book contains the proceedings of the conference in honor of Hugh Woodin’s 60th birthday, that I previously discussed on this blog (here, here, and here).

The AMS page for the volume can be found here, including the table of contents and links to the front- and endmatter (which I think are available to everybody) and links to the individual papers (which I imagine may not be).


Topological Ramsey numbers and countable ordinals

February 1, 2019

Paul Erdős and Eric Milner published in 1972 A theorem in the partition calculus, where they established that if \beta is a countable ordinal and n\in\omega, then there is a countable ordinal \alpha such that

\alpha\to(\beta,n)^2,

meaning that any graph whose set of vertices is \alpha either contains a clique (complete subgraph) whose set of vertices H has order type \beta or an independent set of size n.

The result is false if n is replaced by \omega, except for when \beta=\omega, in which case we can take \alpha=\omega as well, this is Ramsey’s theorem.

The least \alpha such that \alpha\to(\omega+1,\omega)^2 is \alpha=\omega_1, in which case a stronger result holds, namely \omega_1\to(\omega_1,\omega+1)^2. In fact, more is true: the homogeneous set H of order type \omega_1 can be taken to be a stationary subset of \omega_1, and the set of type \omega+1 can be required to be closed, meaning that its \omegath member is the supremum of the other members of the set. Since stationary sets contain closed subsets of any countable order type, we see that \omega_1\to_{cl}(\beta,\omega+1)^2 holds for any countable ordinal \beta, where the subindex cl indicates that the sets of vertices of type \beta or \omega+1 are required to be closed on their supremum.

It is thus natural to wonder whether a closed version of the Erdős-Milner theorem holds. Jacob Hilton and I establish precisely this result in our paper Topological Ramsey numbers and countable ordinals.

This was a problem I had been curious about for a while, but kept not finding time to investigate. Finally I found a student at Boise State interested in working on this question for their master’s thesis, which gave me the perfect excuse to think seriously about it. I wrote a series of detailed notes for my student, who ended up leaving the program early, so I decided to continue and turn the notes into a paper. I even gave a preliminary talk on the results I had, together with some other results on the partition calculus of small countable ordinals. Hilton was a graduate student at that point, and he contacted me when he found out I was studying the problem, since this was precisely the topic of his dissertation. We decided to combine what we had, and soon we managed to extend our results and solve the full problem.

Many questions remain, as we believe the general bounds we found can be significantly improved, and it seems interesting to compute the optimal value of \alpha such that \alpha\to_{cl}(\beta,n)^2 for specific values of \beta<\omega_1 and n<\omega. Omer Mermelstein has some striking results in this direction.

Our paper appeared in Foundations of Mathematics, the proceedings of the conference in honor of Hugh Woodin’s 60th birthday. It can also be found on the arXiv and on my papers page.


The fourteen Victoria Delfino problems and their status in the year 2019

February 1, 2019

The Cabal seminar in southern California was instrumental to the development of determinacy. The Delfino problems were suggested as a way to measure progress on this area. Fourteen problems were suggested in total through the years. Some were solved very quickly after their proposal, a few remain open.

Benedikt Löwe and I wrote a survey of their current status, cleverly titled The fourteen Victoria Delfino problems and their status in the year 2019. The cleverness has forced us to keep changing its title as its publication date kept being postponed. It is scheduled to appear in the fourth volume of the reissued Cabal volumes, which I am told is expected to finally be published this year. The volumes are being published by the Association for Symbolic Logic and Cambridge University Press as part of the Lecture Notes in Logic series.

The survey can be accessed through the Hamburger Beiträge zur Mathematik preprint server; it is paper 770 there. It can also be found through my papers page (currently under notes, and later on, once it appears, under papers).


Special Session

October 22, 2018

Two pictures from last weekend’s Session.

We rescued this one from Instagram a couple of minutes after it happened (Paul noticed that #determinacy was missing from the list):

Image-1

And a decent group picture. Missing: Maryanthe Malliaris (who took it), Harry Altman and Jeffrey Bergfalk:

20181021_102737

Many thanks to all the participants, and to the AMS for making it possible.


Large cardinals and combinatorial set theory

August 28, 2018

Paul Larson and I are organizing a special session at the Fall Central Sectional Meeting 2018 in Ann Arbor, on Large cardinals and combinatorial set theory. The session will take place Saturday October 20 and Sunday October 21. See here for the schedule and additional details. Paul and I are organizing dinner for the speakers for Saturday, at 7:30 p.m.

I transcribe the schedule below:

  • Saturday October 20, 2018, 8:30-11:20 a.m.

Room 2336, Mason Hall

  • Saturday October 20, 2018, 12:30-2:00 p.m. Open house at Mathematical Reviews.

416 Fourth Street

  • Saturday October 20, 2018, 2:00-4:20 p.m.

Room 2336, Mason Hall

Atrium, East Hall.

  • Sunday October 21, 2018, 8:00-10:20 a.m.

Room 2336, Mason Hall

  • Sunday October 21, 2018, 1:00-3:50 p.m.

Room 2336, Mason Hall


Professorship in Logic at the University of Vienna

February 4, 2018

I have been asked to help spread the word. Sy Friedman, the head of the Kurt Gödel Research Center at the University of Vienna (where I had my first postdoc), is retiring, and there is a search underway for a replacement. The KGRC has been significant in fostering a multitude of early career researchers in set theory, and it would be a shame if the position ended up in another discipline.

If you are interested, please consider applying. If you know of someone who may be interested, please help spread the word. The deadline is April 15.

http://personalwesen.univie.ac.at/en/jobs-recruiting/professorships/detail-page/news/mathematical-logic-taking-into-account-the-foundations-of-computer-science/

From the link, the position is for a “University Professor of Mathematical Logic Taking into Account the Foundations of Computer Science”. Applications should be submitted by e-mail to the Dean of the Faculty of Mathematics of the University of Vienna, Univ.-Prof. Dr. Christian Krattenthaler, Oskar-Morgenstern-Platz 1, 1090 Vienna (dekanat.mathematik@univie.ac.at). Further details are at the link.


Set theory, logic and Ramsey theory

October 16, 2017

José G. Mijares and I are organizing a special session at the 2018 Joint Mathematics Meetings in San Diego, cosponsored by the AMS and the ASL, on Set theory, logic and Ramsey theory. The session will take place the morning of Wednesday January 10 and the morning and afternoon of Thursday January 11. See here for the schedule and additional details. I transcribe the schedule below:


On anti-foundation and coding the hereditarily finite sets

August 27, 2016

I would like to highlight a cute question in a recent paper,

MR3400774
Giovanna D’Agostino, Alberto Policriti, Eugenio G. Omodeo, and Alexandru I. Tomescu.
Mapping sets and hypersets into numbers.
Fund. Inform. 140 (2015), no. 3-4, 307–328.

Recall that W. Ackermann verified what in modern terms we call the bi-interpretability of \mathsf{ZFfin} and \mathsf{PA}, where the latter is (first-order) Peano arithmetic, and the former is finite set theory, the result of replacing in \mathsf{ZF} the axiom of infinity with its negation (and with foundation formulated as the schema of \in-induction). The reference is

MR1513141
Wilhelm Ackermann.
Die Widerspruchsfreiheit der allgemeinen Mengenlehre.
Math. Ann. 114 (1937), no. 1, 305–315.

I have written about this before. Briefly, one exhibits (definable) translations between the collection \mathsf{HF} of hereditarily finite sets and \mathbb{N}, and verifies that the translation extends to a definable translation of the relations, functions and constants of the language of each structure in a way that \mathsf{PA} verifies that \mathsf{ZFfin} holds in the translation of (\mathsf{HF},\in), and \mathsf{ZFfin} verifies that \mathsf{PA} holds in the translation of {\mathbb N}=(\omega,+,\times,<,0,1). Recall that \mathsf{HF} consists of those sets a whose transitive closure is finite, that is, a is finite, and all its elements are finite, and all the elements of its elements are finite, and so on. Using foundation, one easily verifies that \mathsf{HF}=V_\omega=\bigcup_{n\in\omega}V_n, that is, it is the collection of sets resulting from iterating the power-set operation (any finite number of times) starting from the empty set.

In the direction relevant here, one defines a map h:\mathsf{HF}\to\mathbb{N} by

h(a)=\sum_{b\in a}2^{h(b)}.

One easily verifies, using induction on the set-theoretic rank of the sets involved, that this recursive definition makes sense and is injective (and, indeed, bijective).

Of course this argument uses foundation. In the D’Agostino-Policriti-Omodeo-Tomescu paper they consider instead the theory resulting from replacing foundation with the  anti-foundation axiom, and proceed to describe a suitable replacement for h that injects (codes) \mathsf{HF} into the real numbers. They do quite a bit more in the paper but, for the coding itself, I highly recommend the nice review by Randall Holmes in MathSciNet, linked to above.

The anti-foundation axiom \mathsf{AFA} became known thanks to the work of Peter Aczel, and it is his formulation that I recall below, although it was originally introduced in work of Forti and Honsell from 1983, where they call it X_1. Aczel’s presentation appears in the excellent book

MR0940014 (89j:03039)
Peter Aczel.
Non-well-founded sets. With a foreword by Jon Barwise.
CSLI Lecture Notes, 14. Stanford University, Center for the Study of Language and Information, Stanford, CA, 1988. xx+137 pp.
ISBN: 0-937073-22-9.

The original paper is

MR0739920 (85f:03054)
Marco Forti, Furio Honsell.
Set theory with free construction principles.
Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 10 (1983), no. 3, 493–522.

Given a binary relation R, its field \mathrm{fld}(R) is the union of its domain and codomain. A decoration of R is a function d:\mathrm{fld}(R)\to V satisfying

d(x)=\{d(y)\mid y\mathrel{R}x\}

for all x,y\in\mathrm{fld}(R). When R is \in and the sets in question are well-founded, the only decoration is the identity. Similarly, any well-founded relation R admits a unique decoration. Define \mathsf{AFA} as the statement that any binary R (whether well-founded or not) admits a unique decoration.

In \mathsf{ZF} with foundation replaced with \mathsf{AFA} one can prove the existence of many non-well-founded sets. One of the appealing aspects of \mathsf{AFA} is that the resulting univere is actually quite structured: Other anti-foundation axioms allow the existence of infinitely many Quine atoms, sets x such that x=\{x\}, for instance. Under \mathsf{AFA}, there is exactly one such x, usually called \Omega. The axiom is sometimes described as saying that it provides solutions to many “equations” among sets. For instance, consider the system of equations x=\{y\} and y=\{x\}. Under \mathsf{AFA} the system has x=y=\Omega as its unique solution. Note that assuming \mathsf{AFA}, \Omega is in \mathsf{HF}, as are many other non-well-founded sets.

Here is the open question from the D’Agostino-Policriti-Omodeo-Tomescu paper: Work in set theory with \mathsf{AFA} instead of foundation. Is there a unique, injective, function h:\mathsf{HF}\to \mathbb{R}  satisfying

h(x)=\sum_{y\in x}2^{-h(y)}

for all x,y\in\mathsf{HF}?

Note that there is a unique such h on the well-founded hereditarily finite sets, and it is in fact injective. In general, existence, uniqueness and injectivity of h appear to be open. The claim that there is such a function h is a statement about solutions of certain equations on the reals, and the claim that h is unique requires moreover uniqueness of such solutions. The expectation is that h(x) is transcendental for all non-well-founded hereditarily finite x but, even assuming this, the injectivity of h seems to require additional work.

For example, consider x=\Omega. The function h must satisfy

h(\Omega)=2^{-h(\Omega)}

and, indeed h(\Omega)=0.6411857\dots is the unique solution x of the equation x=2^{-x}

I would be curious to hear of any progress regarding this problem.


Smullyan

August 11, 2016

I have just posted on my papers page a preprint of a review of

MR3379889
Smullyan, Raymond
Reflections—the magic, music and mathematics of Raymond Smullyan.
World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. x+213 pp.
ISBN: 978-981-4644-58-7; 978-981-4663-19-9

that I have submitted to Mathematical Reviews.