Tag Archives: constructible universe

Embeddings of the universe into the constructible universe, current state of knowledge, CUNY Set Theory Seminar, March 2015

Posted on by
4

This will be a talk for the CUNY Set Theory Seminar, March 6, 2015.

I shall describe the current state of knowledge concerning the question of whether there can be an embedding of the set-theoretic universe into the constructible universe.

V to L

Question.(Hamkins) Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ into the constructible universe $L$, when $V\neq L$?

The notion of embedding here is merely that $$x\in y\iff j(x)\in j(y),$$ and such a map need not be elementary nor even $\Delta_0$-elementary. It is not difficult to see that there can generally be no $\Delta_0$-elementary embedding $j:V\to L$, when $V\neq L$.

Nevertheless, the question arises very naturally in the context of my previous work on the embeddability phenomenon, Every countable model of set theory embeds into its own constructible universe, where the title theorem is the following.

Theorem.(Hamkins) Every countable model of set theory $\langle M,\in^M\rangle$, including every countable transitive model of set theory, has an embedding $j:\langle M,\in^M\rangle\to\langle L^M,\in^M\rangle$ into its own constructible universe.

The methods of proof also established that the countable models of set theory are linearly pre-ordered by embeddability: given any two models, one of them embeds into the other; or equivalently, one of them is isomorphic to a submodel of the other. Indeed, one model $\langle M,\in^M\rangle$ embeds into another $\langle N,\in^N\rangle$ just in case the ordinals of the first $\text{Ord}^M$ order-embed into the ordinals of the second $\text{Ord}^N$. (And this implies the theorem above.)

In the proof of that theorem, the embeddings $j:M\to L^M$ are defined completely externally to $M$, and so it was natural to wonder to what extent such an embedding might be accessible inside $M$. And I realized that I could not generally refute the possibility that such a $j$ might even be a class in $M$.

Currently, the question remains open, but we have some partial progress, and have settled it in a number of cases, including the following, on which I’ll speak:

  • If there is an embedding $j:V\to L$, then for a proper class club of cardinals $\lambda$, we have $(2^\lambda)^V=(\lambda^+)^L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$ and indeed no embedding $j:P(\omega)\to L$.
  • If there is an embedding $j:V\to L$, then the GCH holds above $\aleph_0$.
  • In the forcing extension $V[G]$ obtained by adding $\omega_1$ many Cohen reals (or more), there is no embedding $j:V[G]\to L$, and indeed, no $j:P(\omega)^{V[G]}\to V$. More generally, after adding $\kappa^+$ many Cohen subsets to $\kappa$, for any regular cardinal $\kappa$, then in $V[G]$ there is no $j:P(\kappa)\to V$.
  • If $V$ is a nontrivial set-forcing extension of an inner model $M$, then there is no embedding $j:V\to M$. Indeed, there is no embedding $j:P(\kappa^+)\to M$, if the forcing has size $\kappa$. In particular, if $V$ is a nontrivial forcing extension, then there is no embedding $j:V\to L$.
  • Every countable set $A$ has an embedding $j:A\to L$.

This is joint work of myself, W. Hugh Woodin, Menachem Magidor, with contributions also by David Aspero, Ralf Schindler and Yair Hayut.

See my related MathOverflow question: Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?

Talk Abstract

The pluralist perspective on the axiom of constructibility, MidWest PhilMath Workshop, Notre Dame, October 2014

Posted on by
8

University of Notre DameThis will be a featured talk at the Midwest PhilMath Workshop 15, held at Notre Dame University October 18-19, 2014.  W. Hugh Woodin and I will each give one-hour talks in a session on Perspectives on the foundations of set theory, followed by a one-hour discussion of our talks.

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

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 proposal, pointing out that neither the fairly-interpreted-in relation nor the (strongly) maximizes-over relation is transitive, and furthermore, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s account, contrary to what had been desired. Ultimately, I shall argue that the V≠L via maximize position loses its force on a multiverse conception of set theory with an upwardly extensible concept of set, in light of the classical facts that models of set theory can generally be extended to models of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

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

Slides

Algebraicity and implicit definability in set theory

Posted on by
2

[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ö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.

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

Posted on by
3

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.

A multiverse perspective on the axiom of constructiblity

Posted on by
19

[bibtex key=Hamkins2014:MultiverseOnVeqL]

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: