Infinite-time computable analogues of the universal algorithm, Generalized Computability Theory Workshop, Spain, August 2024

This will be a talk at the Generalized Computability Theory workshop in Castro Urdiales, Spain, a beautiful setting on the sea near Bilbao, 19-23 August 2024.

Abstract. I shall present infinite-time computable analogues of the universal algorithm, which can in principle produce any desired output stream, if only it is run in the right set-theoretic universe, and then extended as desired in further universes.

How to find pointwise definable and Leibnizian extensions of models of arithmetic and set theory, Oxford Logic Seminar, May 2023

This will be a talk (in person) for the Logic Seminar of the Mathematics Institute of the Univerisity of Oxford, May 18, 2023 5pm, Wiles Building L3.

By Alain Goriely - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=29752669

Abstract:  I shall present a new flexible method showing that every countable model of PA admits a pointwise definable end-extension, one in which every point is definable without parameters. Also, any model of PA of size at most continuum admits an extension that is Leibnizian, meaning that any two distinct points are separated by some expressible property. Similar results hold in set theory, where one can also achieve V=L in the extension, or indeed any suitable theory holding in an inner model of the original model.

Pointwise definable and Leibnizian extensions of models of arithmetic and set theory, Madison Logic Seminar, April 2023

Abstract. I shall present a new flexible method showing that every countable model of PA admits a pointwise definable-elementary end-extension. Also, any model of PA of size at most continuum admits an extension that is Leibnizian, meaning that any two distinct points are separated by some expressible property. Similar results hold in set theory, where one can also achieve V=L in the extension, or indeed any suitable theory holding in an inner model of the original model.

UW Madison Logic Seminar, Joel David Hamkins, April 4, 2023

The Math Tea argument: must there be numbers we can neither describe nor define? Barcelona March 2023

This will be a talk 15 March 2023 for the Mathematics Department of the University of Barcelona, organized jointly with the Set Theory Seminar.

Abstract. According to the math tea argument, perhaps heard at a good afternoon tea,
there must be some real numbers that we can neither describe nor define, since there
are uncountably many real numbers, but only countably many definitions. Is it correct?
In this talk, I shall discuss the phenomenon of pointwise definable structures in
mathematics, structures in which every object has a property that only it exhibits. A
mathematical structure is Leibnizian, in contrast, if any pair of distinct objects in it
exhibit different properties. Is there a Leibnizian structure with no definable elements?
We shall discuss many interesting elementary examples, eventually working up to the
proof that every countable model of set theory has a pointwise definable extension, in
which every mathematical object is definable, including every real number, every
function, every set. We shall discuss the relevance for the math tea argument.

Pointwise definable and Leibnizian extensions of models of arithmetic and set theory, MOPA seminar CUNY, November 2022

 This will be an online talk for the MOPA Seminar at CUNY on 22 November 2022 1pm. Contact organizers for Zoom access.

Abstract. I shall introduce a flexible new method showing that every countable model of PA admits a pointwise definable end-extension, one in which every individual is definable without parameters. And similarly for models of set theory, in which one may also achieve the Barwise extension result—every countable model of ZF admits a pointwise definable end-extension to a model of ZFC+V=L, or indeed any theory arising in a suitable inner model. A generalization of the method shows that every model of arithmetic of size at most continuum admits a Leibnizian extension, and similarly in set theory. 

Pointwise definable and Leibnizian models of arithmetic and set theory, realized in end extensions of a given model, Notre Dame Logic Seminar, October 2022

This will be a talk for the Notre Dame logic seminar, 11 October 2022, 2pm in Hales-Healey Hall.

Abstract.  I shall present very new results on pointwise definable and Leibnizian end-extensions of models of arithmetic and set theory. Using the universal algorithm, I shall present a new flexible method showing that every countable model of PA admits a pointwise definable $\Sigma_n$-elementary end-extension. Also, any model of PA of size at most continuum admits an extension that is Leibnizian, meaning that any two distinct points are separated by some expressible property. Similar results hold in set theory, where one can also achieve V=L in the extension, or indeed any suitable theory holding in an inner model of the original model.

Every countable model of arithmetic or set theory has a pointwise definable end extension

[bibtex key=”Hamkins:Every-countable-model-of-arithmetic-or-set-theory-has-a-pointwise-definable-end-extension”]

arXiv:2209.12578

Abstract. According to the math tea argument, there must be real numbers that we cannot describe or define, because there are uncountably many real numbers, but only countably many definitions. And yet, the existence of pointwise definable models of set theory, in which every individual is definable without parameters, challenges this conclusion. In this article, I introduce a flexible new method for constructing pointwise definable models of arithmetic and set theory, showing furthermore that every countable model of Zermelo-Fraenkel ZF set theory and of Peano arithmetic PA has a pointwise-definable end extension. In the arithmetic case, I use the universal algorithm and its $\Sigma_n$ generalizations to build a progressively elementary tower making any desired individual $a_n$ definable at each stage $n$, while preserving these definitions through to the limit model, which can thus be arranged to be pointwise definable. A similar method works in set theory, and one can moreover achieve $V=L$ in the extension or indeed any other suitable theory holding in an inner model of the original model, thereby fulfilling the resurrection phenomenon. For example, every countable model of ZF with an inner model with a measurable cardinal has an end extension to a pointwise-definable model of $\text{ZFC}+V=L[\mu]$.

The math tea argument—must there be numbers we cannot describe or define? Pavia Logic Seminar

Home

This will be a talk for the Philosophy Seminar at the IUSS, Scuola Universitaria Superiore Pavia, 28 September 2022.

(Note: This seminar will be held the day before the related conference Philosophy of Mathematics: Foundations, Definitions and Axioms, Italian Network for the Philosophy of Mathematics, 29 September to 1 October 2022. I shall be speaking at that conference on the topic, Fregean abstraction in set theory, a deflationary account.)

Abstract. According to the math tea argument, perhaps heard at a good afternoon tea, there must be some real numbers that we can neither describe nor define, since there are uncountably many real numbers, but only countably many definitions. Is it correct? In this talk, I shall discuss the phenomenon of pointwise definable structures in mathematics, structures in which every object has a property that only it exhibits. A mathematical structure is Leibnizian, in contrast, if any pair of distinct objects in it exhibit different properties. Is there a Leibnizian structure with no definable elements? We shall discuss many interesting elementary examples, eventually working up to the proof that every countable model of set theory has a pointwise definable extension, in which every mathematical object is definable.

Pointwise definable end-extensions of the universe, Sophia 2022, Salzburg

This will be an online talk for the Salzburg Conference for Young Analytical Philosophy, the SOPhiA 2022 Salzburgiense Concilium Omnibus Philosophis Analyticis, with a special workshop session Reflecting on ten years of the set-theoretic multiverse. The workshop will meet Thursday 8 September 2022 4:00pm – 7:30pm.

The name of the workshop (“Reflecting on ten years…”), I was amazed to learn, refers to the period since my 2012 paper, The set-theoretic multiverse, in the Review of Symbolic Logic, in which I had first introduced my arguments and views concerning set-theoretic pluralism. I am deeply honored by this workshop highlighting my work in this way and focussing on the developments growing out of it.

In this talk, I shall engage in that discussion by presenting some very new work connecting several topics that have been prominent in discussions of the set-theoretic multiverse, namely, set-theoretic potentialism and pointwise definability.

Abstract. Using the universal algorithm and its generalizations, I shall present new work on the possibility of end-extending any given countable model of arithmetic or set theory to a pointwise definable model, one in which every object is definable without parameters. Every countable model of Peano arithmetic, for example, admits an end-extension to a pointwise definable model. And similarly, every countable model of ZF set theory admits an end-extension to a pointwise definable model of ZFC+V=L, as well as to pointwise definable models of other sufficient theories, accommodating large cardinals. I shall discuss the philosophical significance of these results in the philosophy of set theory with a view to potentialism and the set-theoretic multiverse.

Definability and the Math Tea argument: must there be numbers we cannot describe or define? University of Warsaw, 22 January 2021

This will be a talk for a new mathematical logic seminar at the University of Warsaw in the Department of Hhilosophy, entitled Epistemic and Semantic Commitments of Foundational Theories, devoted to formal truth theories and implicit commitments of foundational theories as well as their conceptual surroundings.

My talk will be held 22 January 2021, 8 pm CET (7 pm UK), online via Zoom https://us02web.zoom.us/j/83366049995.

Tran Tuan, CC BY-SA 4.0 <https://creativecommons.org/licenses/by-sa/4.0>, via Wikimedia Commons

Abstract. According to the math tea argument, perhaps heard at a good afternoon tea, there must be some real numbers that we can neither describe nor define, since there are uncountably many real numbers, but only countably many definitions. Is it correct? In this talk, I shall discuss the phenomenon of pointwise definable structures in mathematics, structures in which every object has a property that only it exhibits. A mathematical structure is Leibnizian, in contrast, if any pair of distinct objects in it exhibit different properties. Is there a Leibnizian structure with no definable elements? We shall discuss many interesting elementary examples, eventually working up to the proof that every countable model of set theory has a pointwise definable extension, in which every mathematical object is definable.

Pointwise definable models of set theory

[bibtex key=”HamkinsLinetskyReitz2013:PointwiseDefinableModelsOfSetTheory”]

When does every definable set have a definable member? CUNY Set Theory Seminar, October 2014

This will be a talk for the CUNY set theory seminar, October 10, 2014, 12pm  GC 6417.

Abstract. Although the concept of `being definable’ is not generally expressible in the language of set theory, it turns out that the models of ZF in which every definable nonempty set has a definable element are precisely the models of V=HOD.  Indeed, V=HOD is equivalent to the assertion merely that every $\Pi_2$-definable set has an ordinal-definable element. Meanwhile, this is not true in the case of $\Sigma_2$-definability, because every model of ZFC has a forcing extension satisfying $V\neq\text{HOD}$ in which every $\Sigma_2$-definable set has an ordinal-definable element.

This is joint work with François G. Dorais and Emil Jeřábek, growing out of some questions and answers on MathOverflow, namely,

Definable collections without definable members
A question asked by Ashutosh five years ago, in which François and I gradually came upon the answer together.
Is it consistent that every definable set has a definable member?
A similar question asked last week by (anonymous) user38200
Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable member?
A question I had regarding the limits of an issue in my answer to the previous question.

In this talk, I shall present the answers to all these questions and place the results in the context of classical results on definability, including a review of basic concepts for graduate students.

Algebraicity and implicit definability in set theory

[bibtex key=HamkinsLeahy2016:AlgebraicityAndImplicitDefinabilityInSetTheory]

We aim in this article to analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity and its companion concept of implicit definability. In place of the class HOD of hereditarily ordinal definable sets, for example, we consider the class HOA of hereditarily ordinal-algebraic sets. In place of the pointwise definable models of set theory, we examine its (pointwise) algebraic models. And in place of G&ouml;del’s constructible universe L, obtained by iterating the definable power set operation, we introduce the implicitly constructible universe Imp, obtained by iterating the algebraic or implicitly definable power set operation. In each case we investigate how the change from definability to algebraicity affects the nature of the resulting concept. We are especially intrigued by Imp, for it is a new canonical inner model of ZF whose subtler properties are just now coming to light. Open questions about Imp abound.

Before proceeding further, let us review the basic definability definitions. In the model theory of first-order logic, an element $a$ is definable in a structure $M$ if it is the unique object in $M$ satisfying some first-order property $\varphi$ there, that is, if $M\models\varphi[b]$ just in case $b=a$. More generally, an element $a$ is algebraic in $M$ if it has a property $\varphi$ exhibited by only finitely many objects in $M$, so that $\{b\in M \mid M\models\varphi[b]\}$ is a finite set containing $a$. For each class $P\subset M$ we can similarly define what it means for an element to be $P$-definable or $P$-algebraic by allowing the formula $\varphi$ to have parameters from $P$.

In the second-order context, a subset or class $A\subset M^n$ is said to be definable in $M$, if $A=\{\vec a\in M\mid M\models\varphi[\vec a]\}$ for some first-order formula $\varphi$. In particular, $A$ is the unique class in $M^n$ with $\langle M,A\rangle\models\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, in the language where we have added a predicate symbol for $A$. Generalizing this condition, we say that a class $A\subset M^n$ is implicitly definable in $M$ if there is a first-order formula $\psi(A)$ in the expanded language, not necessarily of the form $\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, such that $A$ is unique such that $\langle M,A\rangle\models\psi(A)$. Thus, every (explicitly) definable class is also implicitly definable, but the converse can fail. Even more generally, we say that a class $A\subset M^n$ is algebraic in $M$ if there is a first-order formula $\psi(A)$ in the expanded language such that $\langle M,A\rangle\models\psi(A)$ and there are only finitely many $B\subset M^n$ for which $\langle M,B\rangle\models\psi(B)$. Allowing parameters from a fixed class $P\subset M$ to appear in $\psi$ yields the notions of $P$-definability, implicit $P$-definability, and $P$-algebraicity in $M$. Simplifying the terminology, we say that $A$ is definable, implicitly definable, or algebraic over (rather than in) $M$ if it is $M$-definable, implicitly $M$-definable, or $M$-algebraic in $M$, respectively. A natural generalization of these concepts arises by allowing second-order quantifiers to appear in $\psi$. Thus we may speak of a class $A$ as second-order definable, implicitly second-order definable, or second-order algebraic. Further generalizations are of course possible by allowing $\psi$ to use resources from other strong logics.

The main theorems of the paper are:

Theorem. The class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets: $$\text{HOA}=\text{HOD}.$$

Theorem. Every pointwise algebraic model of ZF is a pointwise definable model of ZFC+V=HOD.

In the latter part of the paper, we introduce what we view as the natural algebraic analogue of the constructible universe, namely, the implicitly constructible universe, denoted Imp, and built as follows:

$$\text{Imp}_0 = \emptyset$$

$$\text{Imp}_{\alpha + 1} = P_{imp}(\text{Imp}_\alpha)$$

$$\text{Imp}_\lambda = \bigcup_{\alpha < \lambda} \text{Imp}_\alpha, \text{ for limit }\lambda$$

$$\text{Imp} = \bigcup_\alpha \text{Imp}_\alpha.$$

Theorem.  Imp is an inner model of ZF with $L\subset\text{Imp}\subset\text{HOD}$.

Theorem.  It is relatively consistent with ZFC that $\text{Imp}\neq L$.

Theorem. In any set-forcing extension $L[G]$ of $L$, there is a further extension $L[G][H]$ with $\text{gImp}^{L[G][H]}=\text{Imp}^{L[G][H]}=L$.

Open questions about Imp abound. Can $\text{Imp}^{\text{Imp}}$ differ from $\text{Imp}$? Does $\text{Imp}$ satisfy the axiom of choice? Can $\text{Imp}$ have measurable cardinals? Must $0^\sharp$ be in $\text{Imp}$ when it exists? (An affirmative answer arose in conversation with Menachem Magidor and Gunter Fuchs, and we hope that $\text{Imp}$ will subsume further large cardinal features. We anticipate a future article on the implicitly constructible universe.)  Which large cardinals are absolute to $\text{Imp}$? Does $\text{Imp}$ have fine structure? Should we hope for any condensation-like principle? Can CH or GCH fail in $\text{Imp}$? Can reals be added at uncountable construction stages of $\text{Imp}$? Can we separate $\text{Imp}$ from HOD? How much can we control $\text{Imp}$ by forcing? Can we put arbitrary sets into the $\text{Imp}$ of a suitable forcing extension? What can be said about the universe $\text{Imp}(\mathbb{R})$ of sets implicitly constructible relative to $\mathbb{R}$ and, more generally, about $\text{Imp}(X)$ for other sets $X$? Here we hope at least to have aroused interest in these questions.

This article arose from a question posed on MathOverflow by my co-author Cole Leahy and our subsequent engagement with it.

Algebraicity and implicit definability in set theory, CUNY, May 2013

This is a talk May 10, 2013 for the CUNY Set Theory Seminar.

Abstract.  An element a is definable in a model M if it is the unique object in M satisfying some first-order property. It is algebraic, in contrast, if it is amongst at most finitely many objects satisfying some first-order property φ, that is, if { b | M satisfies φ[b] } is a finite set containing a. In this talk, I aim to consider the situation that arises when one replaces the use of definability in several parts of set theory with the weaker concept of algebraicity. For example, in place of the class HOD of all hereditarily ordinal-definable sets, I should like to consider the class HOA of all hereditarily ordinal algebraic sets. How do these two classes relate? In place of the study of pointwise definable models of set theory, I should like to consider the pointwise algebraic models of set theory. Are these the same? In place of the constructible universe L, I should like to consider the inner model arising from iterating the algebraic (or implicit) power set operation rather than the definable power set operation. The result is a highly interesting new inner model of ZFC, denoted Imp, whose properties are only now coming to light. Is Imp the same as L? Is it absolute? I shall answer all these questions at the talk, but many others remain open.

This is joint work with Cole Leahy (MIT).

NYlogic abstract | MathOverflow post