The sentence asserting its own non-forceability by nontrivial forcing

At the meeting here in Konstanz, Giorgo Venturi and I considered the sentence $\sigma$, which asserts its own non-forceability by nontrivial forcing. That is, $\sigma$ asserts that there is no nontrivial forcing notion forcing $\sigma$. $$\sigma\quad\iff\quad \neg\exists\mathbb{B}\ \Vdash_{\mathbb{B}}\sigma.$$ The sentence $\sigma$ would be a fixed-point of the predicate for not being nontrivially forceable.

In any model of set theory $V$ in which $\sigma$ is true, then in light of what it asserts, it would not be forceable by nontrivial forcing, and so it would be false in all nontrivial forcing extensions of that model $V[G]$. And in any model $W$ where it is false, then because of what it asserts, it would be nontrivially forceable, and so it would be true in some forcing extension of that model $W[G]$.

But this is a contradiction! It cannot ever be true, since if it were true in $V$, it would have to be false in all extensions $V[G]$, and therefore true in some subsequent extension $V[G][H]$. But that model is a forcing extension of $V$, contradicting the claim that it is false in all such extensions.

So it must always be false, but this can’t happen, since then in any given model, in light of what it asserts, it would have to be true. So it cannot ever be true or false.

Conclusion: there is no such sentence σ that asserts its own nontrivial forceability. This is no fixed-point for not being nontrivially forceable.

But doesn’t this contradict the fixed-point lemma? After all, the fixed-point lemma shows that we can produce fixed points for any expressible assertion.

The resolution of the conundrum is that although for any given assertion $\varphi$, we can express “$\varphi$ is forceable”, we cannot express “x is the Gödel code of a forceable sentence”, for reasons similar to those for Tarski’s theorem on the nondefinability of truth.

Therefore, we are not actually in a situation to apply the fixed-point lemma. And ultimately the argument shows that there can be no sentence $\sigma$ that asserts “$\sigma$ is not forceable by nontrivial forcing”.

Ultimately, I find the logic of this sentence $\sigma$, asserting its own non-nontrivial forceability, to be a set-theoretic forcing analogue of the Yablo paradox. The sentence holds in a model of set theory whenever it fails in all subsequent models obtained by forcing, and that relation is exactly what arises in the Yablo paradox.

Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength

  • [DOI] J. D. Hamkins, Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength arXiv, 2022.
    [Bibtex]
    @misc{Hamkins:Nonlinearity-in-the-hierarchy-of-large-cardinal-consistency-strength,
    author = {Joel David Hamkins},
    title = {Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength},
    publisher = {arXiv},
    year = {2022},
    journal = {},
    volume = {},
    number = {},
    pages = {},
    doi = {10.48550/ARXIV.2208.07445},
    eprint = {2008.07445},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/nonlinearity-in-the-hierarchy-of-consistency-strength},
    }

arXiv:2208.07445

Abstract. Many set theorists point to the linearity phenomenon in the hierarchy of consistency strength, by which natural theories tend to be linearly ordered and indeed well ordered by consistency strength. Why should it be linear? In this paper I present counterexamples, natural instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength, as natural or as nearly natural as I can make them. I present diverse cautious enumerations of ZFC and large cardinal set theories, which exhibit incomparability and illfoundedness in consistency strength, and yet, I argue, are natural. I consider the philosophical role played by “natural” in the linearity phenomenon, arguing ultimately that we should abandon empty naturality talk and aim instead to make precise the mathematical and logical features we had found desirable.

Nonlinearity in the hierarchy of large cardinal consistency strength

This is currently a draft version only of my article-in-progress on the topic of linearity in the hierarchy of consistency strength, especially with large cardinals. Comments are very welcome, since I am still writing the article. Please kindly send me comments by email or just post here.

This article will be the basis of the Weeks 7 & 8 discussion in the Graduate Philosophy of Logic seminar I am currently running with Volker Halbach at Oxford in Hilary term 2021.

I present instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength—as natural or as nearly natural as I can make them—and consider philosophical aspects of the question of naturality with regard to this phenomenon.

It is a mystery often mentioned in the foundations of mathematics, a fundamental phenomenon to be explained, that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them will prove the consistency of the other.

Why should it be linear? Why should the large cardinal notions line up like this, when they often arise from completely different mathematical matters? Measurable cardinals arise from set-theoretic issues in measure theory; Ramsey cardinals generalize ideas in graph coloring combinatorics; compact cardinals arise with compactness properties of infinitary logic. Why should these disparate considerations lead to principles that are linearly related by direct implication and consistency strength?

The phenomenon is viewed by many in the philosophy of mathematics as significant in our quest for mathematical truth. In light of Gödel incompleteness, after all, we must eternally seek to strengthen even our best and strongest theories. Is the linear hierarchy of consistency strength directing us along the elusive path, the “one road upward” as John Steel describes it, toward the final, ultimate mathematical truth? That is the tantalizing possibility.

Meanwhile, we do know as a purely formal matter that the hierarchy of consistency strength is not actually well-ordered—it is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features, however, are weird self-referential assertions constructed in the Gödelian manner via the fixed-point lemma—logic-game trickery, often dismissed as unnatural.

Many set theorists claim that amongst the natural assertions, consistency strengths remain linearly ordered and indeed well ordered. H. Friedman refers to “the apparent comparability of naturally occurring logical strengths as one of the great mysteries of [the foundations of mathematics].” Andrés Caicedo says,

It is a remarkable empirical phenomenon that we indeed have comparability for natural theories. We expect this to always be the case, and a significant amount of work in inner model theory is guided by this belief.

Stephen G. Simpson writes:

It is striking that a great many foundational theories are linearly ordered by <. Of course it is possible to construct pairs of artificial theories which are incomparable under <. However, this is not the case for the “natural” or non-artificial theories which are usually regarded as significant in the foundations of mathematics. The problem of explaining this observed regularity is a challenge for future foundational research.

John Steel writes “The large cardinal hypotheses [the ones we know] are themselves wellordered by consistency strength,” and he formulates what he calls the “vague conjecture” asserting that

If T is a natural extension of ZFC, then there is an extension H axiomatized by large cardinal hypotheses such that T ≡ Con H. Moreover, ≤ Con is a prewellorder of the natural extensions of ZFC. In particular, if T and U are natural extensions of ZFC, then either T ≤ Con U or U ≤ Con T.

Peter Koellner writes

Remarkably, it turns out that when one restricts to those theories that “arise in nature” the interpretability ordering is quite simple: There are no descending chains and there are no incomparable elements—the interpretability ordering on theories that “arise in nature” is a wellordering.

Let me refer to this position as the natural linearity position, the assertion that all natural assertions of mathematics are linearly ordered by consistency strength. The strong form of the position, asserted by some of those whom I have cited above, asserts that the natural assertions of mathematics are indeed well-ordered by consistency strength. By all accounts, this view appears to be widely held in large cardinal set theory and the philosophy of set theory.

Despite the popularity of this position, I should like in this article to explore the contrary view and directly to challenge the natural linearity position.

Main Question. Can we find natural instances of nonlinearity and illfoundedness in the hierarchy of consistency strength?

I shall try my best.

You have to download the article to see my candidates for natural instances of nonlinearity in the hierarchy of large cardinal consistency strength, but I can tease you a little by mentioning that there are various cautious enumerations of the ZFC axioms which actually succeed in enumerating all the ZFC axioms, but with a strictly weaker consistency strength than the usual (incautious) enumeration. And similarly there are various cautious versions of the large cardinal hypothesis, which are natural, but also incomparable in consistency strength.

(Please note that it was Uri Andrews, rather than Uri Abraham, who settled question 16 with the result of theorem 17. I have corrected this from an earlier draft.)

A review of the Gödel fixed-point lemma, with generalizations and applications

This bried unpublished note (11 pages) contains an overview of the Gödel fixed-point lemma, along with several generalizations and applications, written for use in the Week 3 lecture of the Graduate Philosophy of Logic seminar that I co-taught with Volker Halbach at Oxford in Hilary term 2021. The theme of the seminar was self-reference, truth, and consistency strengths, and in this lecture we discussed the nature of Gödel’s fixed-point lemma and generalizations, with various applications in logic.

Contents

  1. Introduction
  2. Gödel’s fixed-point lemma
    An application to the Gödel incompleteness theorem
  3. Finite self-referential schemes
    An application to nonindependent disjunctions of independent sentences
  4. Gödel-Carnap fixed point lemma
    Deriving the double fixed-point lemma as a consequence
    An application to the provability version of Yablo’s paradox
  5. Kleene recursion theorem
    An application involving computable numbers
    An application involving the universal algorithm
    An application to Quine programs and Ouroborous chains
  6. References

Self reference in computability theory and the universal algorithm, Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, Bonn, February 2018

This will be a talk for the conference: Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, held in Bonn, February 16-18, 2018.

Abstract. I shall give an elementary account of the universal algorithm, due to Woodin, showing how the capacity for self-reference in arithmetic gives rise to a Turing machine program $e$, which provably enumerates a finite set of numbers, but which can in principle enumerate any finite set of numbers, when it is run in a suitable model of arithmetic. Furthermore, the algorithm can successively enumerate any desired extension of the sequence, when run in a suitable top-extension of the universe. Thus, the algorithm sheds some light on the debate between free will and determinism, if one should imagine extending the universe into a nonstandard time scale. An analogous result holds in set theory, where Woodin and I have provided a universal locally definable finite set, which can in principle be any finite set, in the right universe, and which can furthermore be successively extended to become any desired finite superset of that set in a suitable top-extension of that universe.

Ouroboros Bonn 2018 Conference Poster | Slides