Same structure, different truths, Stanford University CSLI, May 2016

This will be a talk for the Workshop on Logic, Rationality, and Intelligent Interaction at the CSLI, Stanford University, May 27-28, 2016.

Abstract. To what extent does a structure determine its theory of truth? I shall discuss several surprising mathematical results illustrating senses in which it does not, for the satisfaction relation of first-order logic is less absolute than one might have expected. Two models of set theory, for example, can have exactly the same natural numbers and the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, yet disagree on what is true in this structure; they have the same arithmetic, but different theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe $\langle V_\delta,{\in}\rangle$ in common, yet disagree about whether it is a model of ZFC. These theorems and others can be proved with elementary classical model-theoretic methods, which I shall explain. Indefinite arithmetic truthOn the basis of these observations, Ruizhi Yang (Fudan University, Shanghai) and I argue that the definiteness of the theory of truth for a structure, even in the case of arithmetic, cannot be seen as arising solely from the definiteness of the structure itself in which that truth resides, but rather is a higher-order ontological commitment.

Slides | Main article: Satisfaction is not absolute | CLSI 2016 | Abstract at CLSI

Open determinacy for games on the ordinals, Torino, March 2016

Loggiato

 

 

 

 

The Minerva Statue in front of the Rectorate Palace at the University of Turin.This will be a seminar talk I shall give on March 3, 2016 at the University of Torino, Italy, in the same department where Giuseppe Peano had his position.  I shall be in Italy for the dissertation defense of Giorgio Audrito, on whose dissertation committee I am serving as president.

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

Lewis ChessmenThis is joint work with Victoria Gitman. See our article, Open determinacy for class games, which is currently under review.

Freiling’s axiom of symmetry, or throwing darts at the real line, Graduate Student Colloquium, April 2016

This will be a talk I’ll give at the CUNY Graduate Center Graduate Student Colloquium on Monday, April 11 (new date!), 2016, 4-4:45 pm.  The talk will be aimed at a general audience of mathematics graduate students.

By PeterPan23 [Public domain], via Wikimedia Commons

Abstract. I shall give an elementary presentation of Freiling’s axiom of symmetry, which is the principle asserting that if $x\mapsto A_x$ is a function mapping every real $x\in[0,1]$ in the unit interval to a countable set of such reals $A_x\subset[0,1]$, then there are two reals $x$ and $y$ for which $x\notin A_y$ and $y\notin A_x$.  To argue for the truth of this principle, Freiling imagined throwing two darts at the real number line, landing at $x$ and $y$ respectively: almost surely, the location $y$ of the second dart is not in the set $A_x$ arising from that of the first dart, since that set is countable; and by symmetry, it shouldn’t matter which dart we imagine as being first. So it may seem that almost every pair must fulfill the principle. Nevertheless, the principle is independent of the axioms of ZFC and in fact it is provably equivalent to the failure of the continuum hypothesis.  I’ll introduce the continuum hypothesis in a general way and discuss these foundational matters, before providing a proof of the equivalence of $\neg$CH with the axiom of symmetry. The axiom of symmetry admits natural higher dimensional analogues, such as the case of maps $(x,y)\mapsto A_{x,y}$, where one seeks a triple $(x,y,z)$ for which no member is in the set arising from the other two, and these principles also have an equivalent formulation in terms of the size of the continuum.

Freiling axiom of symmetry on MathOverflow | On Wikipedia | Graduate Student Colloquium


The rearrangement number: how many rearrangements of a series suffice to verify absolute convergence? Vassar Math Colloquium, November 2015

This will be a talk for the Mathematics Colloquium at Vassar College, November 10, 2015, tea at 4:00 pm, talk at 4:15 pm, Rockefeller Hall 310

Abstract. The Riemann rearrangement theorem asserts that a series $\sum_n a_n$ is absolutely convergent if and only if every rearrangement $\sum_n a_{p(n)}$ of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. How many rearrangements $p$ suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum introduced just recently, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and an account of Freiling’s axiom of symmetry.

This talk is based in part on current joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

My notes are available here:

The rearrangement number, CUNY set theory seminar, November 2015

This will be a talk for the CUNY Set Theory Seminar on November 6, 2015.

The Riemann rearrangement theorem states that a convergent real series $\sum_n a_n$ is absolutely convergent if and only if the value of the sum is invariant under all rearrangements $\sum_n a_{p(n)}$ by any permutation $p$ on the natural numbers; furthermore, if the series is merely conditionally convergent, then one may find rearrangements for which the new sum $\sum_n a_{p(n)}$ has any desired (extended) real value or which becomes non-convergent.  In recent joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson, based on an exchange in reply to a Hardy’s MathOverflow question on the topic, we investigate the minimal size of a family of permutations that can be used in this manner to test an arbitrary convergent series for absolute convergence.

Specifically, we define the rearrangement number $\newcommand\rr{\mathfrak{rr}}\rr$ (“double-r”), a new cardinal characteristic of the continuum, to be the smallest cardinality of a set $P$ of permutations of the natural numbers, such that if a convergent real series $\sum_n a_n$ remains convergent and with the same sum after all rearrangements $\sum_n a_{p(n)}$ by a permutation $p\in P$, then it is absolutely convergent. The corresponding rearrangement number for sums, denoted $\newcommand\rrsum{\rr_{\scriptscriptstyle\Sigma}}
\rrsum$, is the smallest cardinality of a family $P$ of permutations, such that if a series $\sum_n a_n$ is conditionally convergent, then there is a rearrangement $\sum_n a_{p(n)}$, by some permutation $p \in P$, which converges to a different sum. We investigate the basic properties of these numbers, and explore their relations with other cardinal characteristics of the continuum. Our main results are that $\mathfrak{b}\leq\rr\leq\mathop{\bf non}(\mathcal{M})$, that $\mathfrak{d}\leq \rrsum$, and that $\mathfrak{b}<\rr$ is relatively consistent.

MathOverflow question | CUNY Set Theory Seminar

Open determinacy for games on the ordinals is stronger than ZFC, CUNY Logic Workshop, October 2015

This will be a talk for the CUNY Logic Workshop on October 2, 2015.

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

This is joint work with Victoria Gitman, with the helpful participation of Thomas Johnstone.

Related article and posts:

 

 

Upward closure in the generic multiverse of a countable model of set theory, RIMS 2015, Kyoto, Japan

Philosophers Walk Kyoto Japan (summer)This will be a talk for the conference Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Japan, September 16-18, 2015.

Abstract. Consider a countable model of set theory amongst its forcing extensions, the ground models of those extensions, the extensions of those models and so on, closing under the operations of forcing extension and ground model.  This collection is known as the generic multiverse of the original model.  I shall present a number of upward-oriented closure results in this context. For example, for a long-known negative result, it is a fun exercise to construct forcing extensions $M[c]$ and $M[d]$ of a given countable model of set theory $M$, each by adding an $M$-generic Cohen real, which cannot be amalgamated, in the sense that there is no common extension model $N$ that contains both $M[c]$ and $M[d]$ and has the same ordinals as $M$. On the positive side, however, any increasing sequence of extensions $M[G_0]\subset M[G_1]\subset M[G_2]\subset\cdots$, by forcing of uniformly bounded size in $M$, has an upper bound in a single forcing extension $M[G]$. (Note that one cannot generally have the sequence $\langle G_n\mid n<\omega\rangle$ in $M[G]$, so a naive approach to this will fail.)  I shall discuss these and related results, many of which appear in the “brief upward glance” section of my recent paper:  G. Fuchs, J. D. Hamkins and J. Reitz, Set-theoretic geology.


Universality and embeddability amongst the models of set theory, CTFM 2015, Tokyo, Japan

Tokyo Institute of TechnologyThis will be a talk for the Computability Theory and Foundations of Mathematics conference at the Tokyo Institute of Technology, September 7-11, 2015.  The conference is held in celebration of Professor Kazuyuki Tanaka’s 60th birthday.

Abstract. Recent results on the embeddability phenomenon and universality amongst the models of set theory are an appealing blend of ideas from set theory, model theory and computability theory. Central questions remain open.

A surprisingly vigorous embeddability phenomenon has recently been uncovered amongst the countable models of set theory. It turns out, for instance, that among these models embeddability is linear: for any two countable models of set theory, one of them embeds into the other. Indeed, one countable model of set theory $M$ embeds into another $N$ just in case the ordinals of $M$ order-embed into the ordinals of $N$. This leads to many surprising instances of embeddability: every forcing extension of a countable model of set theory, for example, embeds into its ground model, and every countable model of set theory, including every well-founded model, embeds into its own constructible universe.

V to LAlthough the embedding concept here is the usual model-theoretic embedding concept for relational structures, namely, a map $j:M\to N$ for which $x\in^M y$ if and only if $j(x)\in^N j(y)$, it is a weaker embedding concept than is usually considered in set theory, where embeddings are often elementary and typically at least $\Delta_0$-elementary. Indeed, the embeddability result is surprising precisely because we can easily prove that in many of these instances, there can be no $\Delta_0$-elementary embedding.

The proof of the embedding theorem makes use of universality ideas in digraph combinatorics, including an acyclic version of the countable random digraph, the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraïssé limits, leading to the hypnagogic digraph, a universal homogeneous graded acyclic class digraph, closely connected with the surreal numbers. Thus, the methods are a blend of ideas from set theory, model theory and computability theory.

Results from Incomparable $\omega_1$-like models of set theory show that the embedding phenomenon does not generally extend to uncountable models. Current joint work of myself, Aspero, Hayut, Magidor and Woodin is concerned with questions on the extent to which the embeddings arising in the embedding theorem can exist as classes inside the models in question. Since the embeddings of the theorem are constructed externally to the model, by means of a back-and-forth-style construction, there is little reason to expect, for example, that the resulting embedding $j:M\to L^M$ should be a class in $M$. Yet, it has not yet known how to refute in ZFC the existence of a class embedding $j:V\to L$ when $V\neq L$. However, many partial results are known. For example, if the GCH fails at an uncountable cardinal, if $0^\sharp$ exists, or if the universe is a nontrivial forcing extension of some ground model, then there is no embedding $j:V\to L$. Meanwhile, it is consistent that there are non-constructible reals, yet $\langle P(\omega),\in\rangle$ embeds into $\langle P(\omega)^L,\in\rangle$.

CFTM 2015 extended abstract | Article | CFTM | Slides

The hypnagogic digraph, with applications to embeddings of the set-theoretic universe, JMM Special Session on Surreal Numbers, Seattle, January 2016

JMM 2016 SeattleThis will be an invited talk for the AMS-ASL special session on Surreal Numbers at the 2016 Joint Mathematics Meetings in Seattle, Washington, January 6-9, 2016.

Abstract. The hypnagogic digraph, a proper-class analogue of the countable random $\mathbb{Q}$-graded digraph, is a surreal-numbers-graded acyclic digraph exhibiting the set-pattern property (a form of existential-closure), making it set-homogeneous and universal for all class acyclic digraphs. A natural copy of this canonical structure arises during the course of the usual construction of the surreal number line, using as vertices the surreal-number numerals $\{\ A \mid B\ \}$.  I shall explain the construction and elementary theory of the hypnagogic digraph and describe recent uses of it in connection with embeddings of the set-theoretic universe, such as in the proof that the countable models of set theory are linearly pre-ordered by embeddability.

Slides | schedule | related article | surreal numbers (Wikipedia)

The absolute truth about non-absolute truth, JAF – Weak Arithmetics Days, New York, July 2015

This will be a talk for the Journées sur les Arithmétiques Faibles – Weak Arithmetics Days conference, held in New York at the CUNY Graduate Center, July 7 – 9, 2015.

Abstract. I will discuss several fun theorems and folklore results illustrating that the satisfaction relation of first-order logic is less absolute than one might have expected. Two models of set theory, for example, can have the same natural numbers $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order and hence disagree about $\omega_1^{CK}$; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe $\langle V_\delta,{\in}\rangle$ in common, yet disagree about whether it is a model of ZFC. These theorems and others can be proved with elementary classical model-theoretic methods. Indefinite arithmetic truthOn the basis of these observations, Ruizhi Yang (Fudan University, Shanghai) and I have argued that the definiteness of the theory of truth for a structure, even in the case of arithmetic, cannot be seen as arising solely from the definiteness of the structure itself in which that truth resides, but rather is a higher-order ontological commitment.

Slides |  Main article: Satisfaction is not absolute

The weakly compact embedding property, Apter-Gitik celebration, CMU 2015

This will be a talk at the Conference in honor of Arthur W. Apter and Moti Gitik at Carnegie Mellon University, May 30-31, 2015.  I am pleased to be a part of this conference in honor of the 60th birthdays of two mathematicians whom I admire very much.

Moti GitikArthur W. Apter

 

 

 

 

 

 

 

 

Abstract. The weakly compact embedding property for a cardinal $\kappa$ is the assertion that for every transitive set $M$ of size $\kappa$ with $\kappa\in M$, there is a transitive set $N$ and an elementary embedding $j:M\to N$ with critical point $\kappa$. When $\kappa$ is inaccessible, this property is one of many equivalent characterizations of $\kappa$ being weakly compact, along with the weakly compact extension property, the tree property, the weakly compact filter property and many others. When $\kappa$ is not inaccessible, however, these various properties are no longer equivalent to each other, and it is interesting to sort out the relations between them. In particular, I shall consider the embedding property and these other properties in the case when $\kappa$ is not necessarily inaccessible, including interesting instances of the embedding property at cardinals below the continuum, with relations to cardinal characteristics of the continuum.

This is joint work with Brent Cody, Sean Cox, myself and Thomas Johnstone.

Slides | Article | Conference web site

Carnegie Mellon University, College of Fine Arts

The continuum hypothesis and other set-theoretic ideas for non-set-theorists, CUNY Einstein Chair Seminar, April, 2015

At Dennis Sullivan’s request, I shall speak on set-theoretic topics, particularly the continuum hypothesis, for the Einstein Chair Mathematics Seminar at the CUNY Graduate Center, April 27, 2015, in two parts:

  • An introductory background talk at 11 am, Room GC 6417
  • The main talk at 2 – 4 pm, Room GC 6417

I look forward to what I hope will be an interesting and fruitful interaction. There will be coffee/tea and lunch between the two parts.

Abstract. I shall present several set-theoretic ideas for a non-set-theoretic mathematical audience, focusing particularly on the continuum hypothesis and related issues.

At the introductory background talk, in the morning (11 am), I shall discuss and prove the Cantor-Bendixson theorem, which asserts that every closed set of reals is the union of a countable set and a perfect set (a closed set with no isolated points), and explain how it led to Cantor’s development of the ordinal numbers and how it establishes that the continuum hypothesis holds for closed sets of reals. We’ll see that there are closed sets of arbitrarily large countable Cantor-Bendixson rank. We’ll talk about the ordinals, about $\omega_1$, the long line, and, time permitting, we’ll discuss Suslin’s hypothesis.

At the main talk, in the afternoon (2 pm), I’ll begin with a discussion of the continuum hypothesis, including an explanation of the history and logical status of this axiom with respect to the other axioms of set theory, and establish the connection between the continuum hypothesis and Freiling’s axiom of symmetry. I’ll explain the axiom of determinacy and some of its applications and its rich logical situation, connected with large cardinals. I’ll briefly mention the themes and goals of the subjects of cardinal characteristics of the continuum and of Borel equivalence relation theory.  If time permits, I’d like to explain some fun geometric decompositions of space that proceed in a transfinite recursion using the axiom of choice, mentioning the open questions concerning whether there can be such decompositions that are Borel.

Dennis has requested that at some point the discussion turn to the role of set theory in the foundation for mathematics, compared for example to that of category theory, and I would look forward to that. I would be prepared also to discuss the Feferman theory in comparison to Grothendieck’s axiom of universes, and other issues relating set theory to category theory.

I know that you know that I know that you know…., CSI Undergraduate Conference on Research, Scholarship, and Performance, April 2015

UGCI shall give the plenary talk at the CSI Undergraduate Conference on Research, Scholarship, and Performance, April 30, 2015. My presentation will be followed by a musical performance.

This is a conference where undergraduate students show off their various scholarly and creative research projects, spanning all disciplines.

In my talk, I’ll present various logic puzzles that involve reasoning about knowledge, including knowledge of knowledge or knowledge of the lack of knowledge.  I’ll discuss the solution of Cheryl’s birthday problem, recently in the news, as well as other classic puzzles and some new ones.

It will be fun!

Slides

Embeddings of the universe into the constructible universe, current state of knowledge, CUNY Set Theory Seminar, March 2015

This will be a talk for the CUNY Set Theory Seminar, March 6, 2015.

I shall describe the current state of knowledge concerning the question of whether there can be an embedding of the set-theoretic universe into the constructible universe.

V to L

Question.(Hamkins) Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ into the constructible universe $L$, when $V\neq L$?

The notion of embedding here is merely that $$x\in y\iff j(x)\in j(y),$$ and such a map need not be elementary nor even $\Delta_0$-elementary. It is not difficult to see that there can generally be no $\Delta_0$-elementary embedding $j:V\to L$, when $V\neq L$.

Nevertheless, the question arises very naturally in the context of my previous work on the embeddability phenomenon, Every countable model of set theory embeds into its own constructible universe, where the title theorem is the following.

Theorem.(Hamkins) Every countable model of set theory $\langle M,\in^M\rangle$, including every countable transitive model of set theory, has an embedding $j:\langle M,\in^M\rangle\to\langle L^M,\in^M\rangle$ into its own constructible universe.

The methods of proof also established that the countable models of set theory are linearly pre-ordered by embeddability: given any two models, one of them embeds into the other; or equivalently, one of them is isomorphic to a submodel of the other. Indeed, one model $\langle M,\in^M\rangle$ embeds into another $\langle N,\in^N\rangle$ just in case the ordinals of the first $\text{Ord}^M$ order-embed into the ordinals of the second $\text{Ord}^N$. (And this implies the theorem above.)

In the proof of that theorem, the embeddings $j:M\to L^M$ are defined completely externally to $M$, and so it was natural to wonder to what extent such an embedding might be accessible inside $M$. And I realized that I could not generally refute the possibility that such a $j$ might even be a class in $M$.

Currently, the question remains open, but we have some partial progress, and have settled it in a number of cases, including the following, on which I’ll speak:

  • If there is an embedding $j:V\to L$, then for a proper class club of cardinals $\lambda$, we have $(2^\lambda)^V=(\lambda^+)^L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$ and indeed no embedding $j:P(\omega)\to L$.
  • If there is an embedding $j:V\to L$, then the GCH holds above $\aleph_0$.
  • In the forcing extension $V[G]$ obtained by adding $\omega_1$ many Cohen reals (or more), there is no embedding $j:V[G]\to L$, and indeed, no $j:P(\omega)^{V[G]}\to V$. More generally, after adding $\kappa^+$ many Cohen subsets to $\kappa$, for any regular cardinal $\kappa$, then in $V[G]$ there is no $j:P(\kappa)\to V$.
  • If $V$ is a nontrivial set-forcing extension of an inner model $M$, then there is no embedding $j:V\to M$. Indeed, there is no embedding $j:P(\kappa^+)\to M$, if the forcing has size $\kappa$. In particular, if $V$ is a nontrivial forcing extension, then there is no embedding $j:V\to L$.
  • Every countable set $A$ has an embedding $j:A\to L$.

This is joint work of myself, W. Hugh Woodin, Menachem Magidor, with contributions also by David Aspero, Ralf Schindler and Yair Hayut.

See my related MathOverflow question: Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?

Talk Abstract

An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014


This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Value omega cubedAbstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, is not currently known.

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