Nov

16

Fri

Speaker: Kameryn Williams (UHM)

Title: The universal algorithm, the $Sigma_1$-definable universal finite sequence, and set-theoretic potentialism

Abstract: As shown by Woodin, there is an algorithm which will computably enumerate any finite list you want, so long as you run it in the correct universe. More precisely, there is a Turing machine $p$, with the following properties: (1) Peano arithmetic proves that $p$ enumerates a finite sequence; (2) running $p$ in $mathbb N$ it enumerates the empty sequence; (3) for any finite sequence $s$ of natural numbers there is a model of arithmetic $M$ so that running $p$ in $M$ it enumerates $s$; (4) indeed, if $p$ enumerates $s$ running in $M$ and $t$ in $M$ is any finite sequence extending $s$, then there is an end-extension $N$ of $M$ so that running $p$ in $N$ it enumerates $t$. In this talk, I will discuss the universal algorithm, along with an analogue from set theory due to Hamkins, Welch, and myself, which we call the $Sigma_1$-definable universal finite sequence.

These results have applications to the philosophy of mathematics. Set-theoretic potentialism is the view that the universe of sets is never fully completed and rather we only have partial, ever widening access. This is similar to the Aristotelian view that there is no actual, completed infinite, but rather only the potential infinite. A potentialist system has a natural associated modal logic, where a statement is necessary at a world if it is true in all extensions. Using the $Sigma_1$-definable universal finite sequence we can calculate the modal validities of end-extensional set-theoretic potentialism. As I will discuss in this talk, the modal validities of this potentialist system are precisely the theory S4.

## University of Hawaiʻi at Mānoa 2018