Satisfaction is not absolute

  • J. D. Hamkins and R. Yang, “Satisfaction is not absolute,” to appear in the Review of Symbolic Logic, pp. 1-34, 2014.  
    @ARTICLE{HamkinsYang:SatisfactionIsNotAbsolute,
    author = {Joel David Hamkins and Ruizhi Yang},
    title = {Satisfaction is not absolute},
    journal = {to appear in the Review of Symbolic Logic},
    year = {2014},
    volume = {},
    number = {},
    pages = {1--34},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    source = {},
    eprint = {1312.0670},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/satisfaction-is-not-absolute},
    doi = {},
    }

$\newcommand\N{\mathbb{N}}\newcommand\satisfies{\models}$

Abstract. We prove that the satisfaction relation $\mathcal{N}\satisfies\varphi[\vec a]$ of first-order logic is not absolute between models of set theory having the structure $\mathcal{N}$ and the formulas $\varphi$ all in common. Two models of set theory can have the same natural numbers, for example, and the same standard model of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and the same arithmetic truths, yet disagree on their truths-about-truth, at any desired level of the iterated truth-predicate hierarchy; 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 the same $\langle H_{\omega_2},{\in}\rangle$ or the same rank-initial segment $\langle V_\delta,{\in}\rangle$, yet disagree on which assertions are true in these structures.

On the basis of these mathematical results, we argue that a philosophical commitment to the determinateness 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,\ldots\}$ itself, but rather, we argue, is an additional higher-order commitment requiring its own analysis and justification.

Many mathematicians and philosophers regard the natural numbers $0,1,2,\ldots\,$, along with their usual arithmetic structure, as having a privileged mathematical existence, a Platonic realm in which assertions have definite, absolute truth values, independently of our ability to prove or discover them. Although there are some arithmetic assertions that we can neither prove nor refute—such as the consistency of the background theory in which we undertake our proofs—the view is that nevertheless there is a fact of the matter about whether any such arithmetic statement is true or false in the intended interpretation. The definite nature of arithmetic truth is often seen as a consequence of the definiteness of the structure of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$ itself, for if the natural numbers exist in a clear and distinct totality in a way that is unambiguous and absolute, then (on this view) the first-order theory of truth residing in that structure—arithmetic truth—is similarly clear and distinct.

Feferman provides an instance of this perspective when he writes (Feferman 2013, Comments for EFI Workshop, p. 6-7) :

In my view, the conception [of the bare structure of the natural numbers] is completely clear, and thence all arithmetical statements are definite.

It is Feferman’s `thence’ to which we call attention.  Martin makes a similar point (Martin, 2012, Completeness or incompleteness of basic mathematical concepts):

What I am suggesting is that the real reason for confidence in first-order completeness is our confidence in the full determinateness of the concept of the natural numbers.

Many mathematicians and philosophers seem to share this perspective. The truth of an arithmetic statement, to be sure, does seem to depend entirely on the structure $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, with all quantifiers restricted to $\N$ and using only those arithmetic operations and relations, and so if that structure has a definite nature, then it would seem that the truth of the statement should be similarly definite.

Nevertheless, in this article we should like to tease apart these two ontological commitments, arguing that the definiteness of truth for a given mathematical structure, such as the natural numbers, the reals or higher-order structures such as $H_{\omega_2}$ or $V_\delta$, does not follow from the definite nature of the underlying structure in which that truth resides. Rather, we argue that the commitment to a theory of truth for a structure is a higher-order ontological commitment, going strictly beyond the commitment to a definite nature for the underlying structure itself.

We make our argument in part by proving that different models of set theory can have a structure identically in common, even the natural numbers, yet disagree on the theory of truth for that structure.

Theorem.

  • Two models of set theory can have the same structure of arithmetic $$\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_1}=\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_2},$$yet disagree on the theory of arithmetic truth.
  • Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is a well-order.
  • Two models of set theory that have the same natural numbers and the same reals, yet disagree on projective truth.
  • Two models of set theory can have a transitive rank initial segment in common $$\langle V_\delta,{\in}\rangle^{M_1}=\langle V_\delta,{\in}\rangle^{M_2},$$yet disagree about whether it is a model of ZFC.

The proofs use only elementary classical methods, and might be considered to be a part of the folklore of the subject of models of arithmetic. The paper includes many further examples of the phenomenon, and concludes with a philosophical discussion of the issue of definiteness, concerning the question of whether one may deduce definiteness-of-truth from definiteness-of-objects and definiteness-of-structure.

 

On the axiom of constructibility and Maddy’s conception of restrictive theories, Logic Workshop, February 2013

This is a talk for the CUNY Logic Workshop on February 15, 2013.

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

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 specific proposal.  For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive.  Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the $V\neq L$ via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of $V=L$.  In particular, every countable model of set theory is a transitive set inside a model of $V=L$.  I shall conclude the talk by explaining various senses in which $V=L$ remains compatible with strength in set theory.

The countable models of set theory are linearly pre-ordered by embeddability, Rutgers, November 2012

This will be a talk for the Rutgers Logic Seminar on November 19, 2012.

Abstract.  I will speak on my recent theorem that every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | Rutgers Logic Seminar

A multiverse perspective on the axiom of constructiblity

  • J. D. Hamkins, “A multiverse perspective on the axiom of constructibility,” in Infinity and Truth, World Sci. Publ., Hackensack, NJ, 2014, vol. 25, pp. 25-45.  
    @incollection {Hamkins2014:MultiverseOnVeqL,
    AUTHOR = {Hamkins, Joel David},
    TITLE = {A multiverse perspective on the axiom of constructibility},
    BOOKTITLE = {Infinity and Truth},
    SERIES = {Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.},
    VOLUME = {25},
    PAGES = {25--45},
    PUBLISHER = {World Sci. Publ., Hackensack, NJ},
    YEAR = {2014},
    MRCLASS = {03E45 (03A05)},
    MRNUMBER = {3205072},
    DOI = {10.1142/9789814571043_0002},
    url = {http://jdh.hamkins.org/multiverse-perspective-on-constructibility/},
    eprint = {1210.6541},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

This article expands on an argument that I made during my talk at the Asian Initiative for Infinity: Workshop on Infinity and Truth, held July 25–29, 2011 at the Institute for Mathematical Sciences, National University of Singapore, and will be included in a proceedings volume that is being prepared for that conference.

Abstract. I 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.

In section two, I provide a few new criticisms of Maddy’s proposed concept of `restrictive’ theories, pointing out that her concept of fairly interpreted in is not a transitive relation: there is a first theory that is fairly interpreted in a second, which is fairly interpreted in a third, but the first is not fairly interpreted in the third.  The same example (and one can easily construct many similar natural examples) shows that neither the maximizes over relation, nor the properly maximizes over relation, nor the strongly maximizes over relation is transitive.  In addition, the theory ZFC + `there are unboundedly many inaccessible cardinals’ comes out as formally restrictive, since it is strongly maximized by the theory ZF + `there is a measurable cardinal, with no worldly cardinals above it’.

To support the main philosophical thesis of the article, I survey a series of mathemtical results,  which reveal various senses in which the axiom of constructibility $V=L$ is compatible with strength in set theory, particularly if one has in mind the possibility of moving from one universe of set theory to a much larger one.  Among them are the following, which I prove or sketch in the article:

Observation. The constructible universe $L$ and $V$ agree on the consistency of any constructible theory. They have models of the same constructible theories.

Theorem. The constructible universe $L$ and $V$ have transitive models of exactly the same constructible theories in the language of set theory.

Corollary. (Levy-Shoenfield absoluteness theorem)  In particular, $L$ and $V$ satisfy the same $\Sigma_1$ sentences, with parameters hereditarily countable in $L$. Indeed, $L_{\omega_1^L}$ and $V$ satisfy the same such sentences.

Theorem. Every countable transitive set is a countable transitive set in the well-founded part of an $\omega$-model of V=L.

Theorem. If there are arbitrarily large $\lambda<\omega_1^L$ with $L_\lambda\models\text{ZFC}$, then every countable transitive set $M$ is a countable transitive set inside a structure $M^+$  that is a pointwise-definable model of ZFC + V=L, and $M^+$ is well founded as high in the countable ordinals as desired.

Theorem. (Barwise)  Every countable model of  ZF has an end-extension to a model of ZFC + V=L.

Theorem. (Hamkins, see here)  Every countable model of set theory $\langle M,{\in^M}\rangle$, including every transitive model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. In other words,  there is an embedding $j:M\to L^M$, which is elementary for quantifier-free assertions.

Another way to say this is that every countable model of set theory is a submodel of a model isomorphic to $L^M$. If we lived inside $M$, then by adding new sets and elements, our universe could be transformed into a copy of the constructible universe $L^M$.

(Plus, the article contains some nice diagrams.)

Related Singapore links:

Every countable model of set theory is isomorphic to a submodel of its own constructible universe, Barcelona, December, 2012

This will be a talk for a set theory workshop at the University of Barcelona on December 15, 2012, organized by Joan Bagaria.

Vestíbul Universitat de Barcelona

Abstract. Every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | Barcelona research group in set theory

Victoria Gitman

Victoria Gitman earned her Ph.D. under my supervision at the CUNY Graduate Center in June, 2007.  For her dissertation work, Victoria had chosen a very difficult problem, the 1962 question of Dana Scott to characterize the standard systems of models of Peano Arithmetic, a question in the field of models of arithmetic that had been open for over forty years. Victoria was able to make progress, now published in several papers, by using an inter-disciplinary approach, applying set-theoretic ideas—including a use of the proper forcing axiom PFA—to the problem in the area of models of arithmetic, where such methods hadn’t often yet arisen.  Ultimately, she showed under PFA that every arithmetically closed proper Scott set is the standard system of a model of PA.  This result extends the classical result to a large new family of Scott sets, providing for these sets an affirmative solution to Scott’s problem.  In other dissertation work, Victoria untangled the confusing mass of ideas surrounding various Ramsey-like large cardinal concepts, ultimately separating them into a beautiful hierarchy, a neighborhood of the vast large cardinal hierarchy intensely studied by set theorists.  (Please see the diagram in her dissertation.)  Victoria holds a tenure-track position at the New York City College of Technology of CUNY.

Victoria Gitman

web page | math genealogy | MathSciNet | ar$\chi$iv | google scholar | related posts

Victoria Gitman, “Applications of the Proper Forcing Axiom to Models of Peano Arithmetic,”  Ph.D. dissertation for the Graduate Center of the City University of New York, June 2007.

Abstract. In Chapter 1, new results are presented on Scott’s Problem in the subject of models of Peano Arithmetic. Some forty years ago, Dana Scott showed that countable Scott sets are exactly the countable standard systems of models of PA, and two decades later, Knight and Nadel extended his result to Scott sets of size $\omega_1$. Here it is shown that assuming the Proper Forcing Axiom, every arithmetically closed proper Scott set is the standard system of a model of PA. In Chapter 2, new large cardinal axioms, based on Ramsey-like embedding properties, are introduced and placed within the large cardinal hierarchy. These notions generalize the seldom encountered embedding characterization of Ramsey cardinals. I also show how these large cardinals can be used to obtain indestructibility results for Ramsey cardinals.

Every countable model of set theory embeds into its own constructible universe, Fields Institute, Toronto, August 2012

This will be a talk for the  Toronto set theory seminar at the Fields Institute, University of Toronto, on August 24, 2012.

Abstract.  Every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected Image: Igougo.comwith the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | my profile at set theory talks | Toronto Set Theory Seminar post