The $\Sigma_1$-definable universal finite sequence

  • J. D. Hamkins and K. J. Williams, “The $\Sigma_1$-definable universal finite sequence,” ArXiv e-prints, 2019. (undeer review)  
    @ARTICLE{HamkinsWilliams:The-universal-finite-sequence,
    author = {Joel David Hamkins and Kameryn J. Williams},
    title = {The $\Sigma_1$-definable universal finite sequence},
    journal = {ArXiv e-prints},
    year = {2019},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {undeer review},
    abstract = {},
    keywords = {under-review},
    eprint = {1909.09100},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    source = {},
    doi = {},
    }

Abstract. We introduce the $\Sigma_1$-definable universal finite sequence and prove that it exhibits the universal extension property amongst the countable models of set theory under end-extension. That is, (i) the sequence is $\Sigma_1$-definable and provably finite; (ii) the sequence is empty in transitive models; and (iii) if $M$ is a countable model of set theory in which the sequence is $s$ and $t$ is any finite extension of $s$ in this model, then there is an end extension of $M$ to a model in which the sequence is $t$. Our proof method grows out of a new infinitary-logic-free proof of the Barwise extension theorem, by which any countable model of set theory is end-extended to a model of $V=L$ or indeed any theory true in a suitable submodel of the original model. The main theorem settles the modal logic of end-extensional potentialism, showing that the potentialist validities of the models of set theory under end-extensions are exactly the assertions of S4. Finally, we introduce the end-extensional maximality principle, which asserts that every possibly necessary sentence is already true, and show that every countable model extends to a model satisfying it.

  • The universal algorithm,
    • J. D. Hamkins and H. W. Woodin, “The universal finite set,” ArXiv e-prints, pp. 1-16, 2017. (manuscript under review)  
      @ARTICLE{HamkinsWoodin:The-universal-finite-set,
      author = {Joel David Hamkins and W. Hugh Woodin},
      title = {The universal finite set},
      journal = {ArXiv e-prints},
      year = {2017},
      volume = {},
      number = {},
      pages = {1--16},
      month = {},
      note = {manuscript under review},
      abstract = {},
      keywords = {under-review},
      source = {},
      doi = {},
      eprint = {1711.07952},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      url = {http://jdh.hamkins.org/the-universal-finite-set},
      }
  • The modal logic of arithmetic potentialism,
    • J. D. Hamkins, “The modal logic of arithmetic potentialism and the universal algorithm,” ArXiv e-prints, pp. 1-35, 2018. (under review)  
      @ARTICLE{Hamkins:The-modal-logic-of-arithmetic-potentialism,
      author = {Joel David Hamkins},
      title = {The modal logic of arithmetic potentialism and the universal algorithm},
      journal = {ArXiv e-prints},
      year = {2018},
      volume = {},
      number = {},
      pages = {1--35},
      month = {},
      eprint = {1801.04599},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      note = {under review},
      url = {http://wp.me/p5M0LV-1Dh},
      abstract = {},
      keywords = {under-review},
      source = {},
      doi = {},
      }
  • A new proof of the Barwise extension theorem
  • Kameryn’s blog post about the paper


Computational self-reference and the universal algorithm, Queen Mary University of London, June 2019

This will be a talk for the Theory Seminar for the theory research group in Theoretical Computer Science at Queen Mary University of London. The talk will be held 4 June 2019 1:00 pm, ITL first floor.

Abstract. Curious, often paradoxical instances of self-reference inhabit deep parts of computability theory, from the intriguing Quine programs and Ouroboros programs to more profound features of the Gödel phenomenon. In this talk, I shall give an elementary account of the universal algorithm, 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. In this sense, every function becomes computable, computed all by the same universal program, if only it is run in the right world. Furthermore, the universal algorithm can successively enumerate any desired extension of the sequence, when run in a suitable top-extension of the universe. 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.

The modal logic of potentialism, ILLC Amsterdam, May 2019

This will be a talk at the Institute of Logic, Language and Computation (ILLC) at the University of Amsterdam for events May 11-12, 2019. See Joel David Hamkins in Amsterdam 2019.

Job Adriaenszoon Berckheyde [Public domain]

Abstract: Potentialism can be seen as a fundamentally model-theoretic notion, in play for any class of mathematical structures with an extension concept, a notion of substructure by which one model extends to another. Every such model-theoretic context can be seen as a potentialist framework, a Kripke model whose modal validities one can investigate. In this talk, I’ll explain the tools we have for analyzing the potentialist validities of such a system, with examples drawn from the models of arithmetic and set theory, using the universal algorithm and the universal definition.