The rearrangement number: how many rearrangements of a series suffice to verify absolute convergence? Vassar Math Colloquium, November 2015

This will be a talk for the Mathematics Colloquium at Vassar College, November 10, 2015, tea at 4:00 pm, talk at 4:15 pm, Rockefeller Hall 310

Abstract. The Riemann rearrangement theorem asserts that a series $\sum_n a_n$ is absolutely convergent if and only if every rearrangement $\sum_n a_{p(n)}$ of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. How many rearrangements $p$ suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum introduced just recently, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and an account of Freiling’s axiom of symmetry.

This talk is based in part on current joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

My Lecture Notes are available. 

The rearrangement number, CUNY set theory seminar, November 2015

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

The Riemann rearrangement theorem states that a convergent real series $\sum_n a_n$ is absolutely convergent if and only if the value of the sum is invariant under all rearrangements $\sum_n a_{p(n)}$ by any permutation $p$ on the natural numbers; furthermore, if the series is merely conditionally convergent, then one may find rearrangements for which the new sum $\sum_n a_{p(n)}$ has any desired (extended) real value or which becomes non-convergent.  In recent joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson, based on an exchange in reply to a Hardy’s MathOverflow question on the topic, we investigate the minimal size of a family of permutations that can be used in this manner to test an arbitrary convergent series for absolute convergence.

Specifically, we define the rearrangement number $\newcommand\rr{\mathfrak{rr}}\rr$ (“double-r”), a new cardinal characteristic of the continuum, to be the smallest cardinality of a set $P$ of permutations of the natural numbers, such that if a convergent real series $\sum_n a_n$ remains convergent and with the same sum after all rearrangements $\sum_n a_{p(n)}$ by a permutation $p\in P$, then it is absolutely convergent. The corresponding rearrangement number for sums, denoted $\newcommand\rrsum{\rr_{\scriptscriptstyle\Sigma}}
\rrsum$, is the smallest cardinality of a family $P$ of permutations, such that if a series $\sum_n a_n$ is conditionally convergent, then there is a rearrangement $\sum_n a_{p(n)}$, by some permutation $p \in P$, which converges to a different sum. We investigate the basic properties of these numbers, and explore their relations with other cardinal characteristics of the continuum. Our main results are that $\mathfrak{b}\leq\rr\leq\mathop{\bf non}(\mathcal{M})$, that $\mathfrak{d}\leq \rrsum$, and that $\mathfrak{b}<\rr$ is relatively consistent.

MathOverflow question | CUNY Set Theory Seminar

Being HOD-of-a-set is invariant throughout the generic multiverse

Iowa State Capitol - Law Library _ Flickr - Photo Sharing!$\newcommand\HOD{\text{HOD}}$The axiom $V=\HOD$, introduced by Gödel, asserts that every set is ordinal definable. This axiom has a subtler foundational aspect than might at first be expected. The reason is that the general concept of “object $x$ is definable using parameter $p$” is not in general first-order expressible in set theory; it is of course a second-order property, which makes sense only relative to a truth predicate, and by Tarski’s theorem, we can have no first-order definable truth predicate. Thus, the phrase “definable using ordinal parameters” is not directly meaningful in the first-order language of set theory without further qualification or explanation. Fortunately, however, it is a remarkable fact that when we allow definitions to use arbitrary ordinal parameters, as we do with $\HOD$, then we can in fact make such qualifications in such a way that the axiom becomes first-order expressible in set theory. Specifically, we say officially that $V=\HOD$ holds, if for every set $x$, there is an ordinal $\theta$ with $x\in V_\theta$, for which which $x$ is definable by some formula $\psi(x)$ in the structure $\langle V_\theta,{\in}\rangle$ using ordinal parameters. Since $V_\theta$ is a set, we may freely make reference to first-order truth in $V_\theta$ without requiring any truth predicate in $V$. Certainly any such $x$ as this is also ordinal-definable in $V$, since we may use $\theta$ and the Gödel-code of $\psi$ also as parameters, and note that $x$ is the unique object such that it is in $V_\theta$ and satisfies $\psi$ in $V_\theta$. (Note that inside an $\omega$-nonstandard model of set theory, we may really need to use $\psi$ as a parameter, since it may be nonstandard, and $x$ may not be definable in $V_\theta$ using a meta-theoretically standard natural number; but fortunately, the Gödel code of a formula is an integer, which is still an ordinal, and this issue is the key to the issue.) Conversely, if $x$ is definable in $V$ using formula $\varphi(x,\vec\alpha)$ with ordinal parameters $\vec\alpha$, then it follows by the reflection theorem that $x$ is defined by $\varphi(x,\vec\alpha)$ inside some $V_\theta$. So this formulation of $V=HOD$ is expressible and exactly captures the desired second-order property that every set is ordinal-definable.

Consider next the axiom $V=\HOD(b)$, asserting that every set is definable from ordinal parameters and parameter $b$. Officially, as before, $V=\HOD(b)$ asserts that for every $x$, there is an ordinal $\theta$, formula $\psi$ and ordinals $\vec \alpha<\theta$, such that $x$ is the unique object in $V_\theta$ for which $\langle V_\theta,{\in}\rangle\models\psi(x,\vec\alpha,b)$, and the reflection argument shows again that this way of defining the axiom exactly captures the intended idea.

The axiom I actually want to focus on is $\exists b\,\left( V=\HOD(b)\right)$, asserting that the universe is $\HOD$ of a set. (I assume ZFC in the background theory.) It turns out that this axiom is constant throughout the generic multiverse.

Theorem. The assertion $\exists b\, (V=\HOD(b))$ is forcing invariant.

  • If it holds in $V$, then it continues to hold in every set forcing extension of $V$.
  • If it holds in $V$, then it holds in every ground of $V$.

Thus, the truth of this axiom is invariant throughout the generic multiverse.

Proof. Suppose that $\text{ZFC}+V=\HOD(b)$, and $V[G]$ is a forcing extension of $V$ by generic filter $G\subset\mathbb{P}\in V$. By the ground-model definability theorem, it follows that $V$ is definable in $V[G]$ from parameter $P(\mathbb{P})^V$. Thus, using this parameter, as well as $b$ and additional ordinal parameters, we can define in $V[G]$ any particular object in $V$. Since this includes all the $\mathbb{P}$-names used to form $V[G]$, it follows that $V[G]=\HOD(b,P(\mathbb{P})^V,G)$, and so $V[G]$ is $\HOD$ of a set, as desired.

Conversely, suppose that $W$ is a ground of $V$, so that $V=W[G]$ for some $W$-generic filter $G\subset\mathbb{P}\in W$, and $V=\HOD(b)$ for some set $b$. Let $\dot b$ be a name for which $\dot b_G=b$. Every object $x\in W$ is definable in $W[G]$ from $b$ and ordinal parameters $\vec\alpha$, so there is some formula $\psi$ for which $x$ is unique such that $\psi(x,b,\vec\alpha)$. Thus, there is some condition $p\in\mathbb{P}$ such that $x$ is unique such that $p\Vdash\psi(\check x,\dot b,\check{\vec\alpha})$. If $\langle p_\beta\mid\beta<|\mathbb{P}|\rangle$ is a fixed enumeration of $\mathbb{P}$ in $W$, then $p=p_\beta$ for some ordinal $\beta$, and we may therefore define $x$ in $W$ using ordinal parameters, along with $\dot b$ and the fixed enumeration of $\mathbb{P}$. So $W$ thinks the universe is $\HOD$ of a set, as desired.

Since the generic multiverse is obtained by iteratively moving to forcing extensions to grounds, and each such movement preserves the axiom, it follows that $\exists b\, (V=\HOD(b))$ is constant throughout the generic multiverse. QED

Theorem. If $V=\HOD(b)$, then there is a forcing extension $V[G]$ in which $V=\HOD$ holds.

Proof. We are working in ZFC. Suppose that $V=\HOD(b)$. We may assume $b$ is a set of ordinals, since such sets can code any given set. Consider the following forcing iteration: first add a Cohen real $c$, and then perform forcing $G$ that codes $c$, $P(\omega)^V$ and $b$ into the GCH pattern at uncountable cardinals, and then perform self-encoding forcing $H$ above that coding, coding also $G$ (see my paper on Set-theoretic geology for further details on self-encoding forcing). In the final model $V[c][G][H]$, therefore, the objects $c$, $b$, $P(\omega)^V$, $G$ and $H$ are all definable without parameters. Since $V\subset V[c][G][H]$ has a closure point at $\omega$, it satisfies the $\omega_1$-approximation and cover properties, and therefore the class $V$ is definable in $V[c][G][H]$ using $P(\omega)^V$ as a parameter. Since this parameter is itself definable without parameters, it follows that $V$ is parameter-free definable in $V[c][G][H]$. Since $b$ is also definable there, it follows that every element of $\HOD(b)^V=V$ is ordinal-definable in $V[c][G][H]$. And since $c$, $G$ and $H$ are also definable without parameters, we have $V[c][G][H]\models V=\HOD$, as desired. QED

Corollary. The following are equivalent.

  1. The universe is $\HOD$ of a set: $\exists b\, (V=\HOD(b))$.
  2. Somewhere in the generic multiverse, the universe is $\HOD$ of a set.
  3. Somewhere in the generic multiverse, the axiom $V=\HOD$ holds.
  4. The axiom $V=\HOD$ is forceable.

Proof. This is an immediate consequence of the previous theorems. $1\to 4\to 3\to 2\to 1$. QED

Corollary. The axiom $V=\HOD$, if true, even if true anywhere in the generic multiverse, is a switch.

Proof. A switch is a statement such that both it and its negation are necessarily possible by forcing; that is, in every set forcing extension, one can force the statement to be true and also force it to be false. We can always force $V=\HOD$ to fail, simply by adding a Cohen real. If $V=\HOD$ is true, then by the first theorem, every forcing extension has $V=\HOD(b)$ for some $b$, in which case $V=\HOD$ remains forceable, by the second theorem. QED

Upward countable closure in the generic multiverse of forcing to add a Cohen real

I’d like to discuss my theorem that the collection of models $M[c]$ obtained by adding an $M$-generic Cohen real $c$ over a fixed countable transitive model of set theory $M$ is upwardly countably closed, in the sense that every increasing countable chain has an upper bound.

I proved this theorem back in 2011, while at the Young Set Theory Workshop in Bonn and continuing at the London summer school on set theory, in a series of conversations with Giorgio Venturi. The argument has recently come up again in various discussions, and so let me give an account of it.

We consider the collection of all forcing extensions of a fixed countable transitive model $M$ of ZFC by the forcing to add a Cohen real, models of the form $M[c]$, and consider the question of whether every countable increasing chain of these models has an upper bound. The answer is yes!  (Actually, Giorgio wants to undertake forcing constructions by forcing over this collection of models to add a generic upward directed system of models; it follows from this theorem that this forcing is countably closed.) This theorem fits into the theme of my earlier post, Upward closure in the toy multiverse of all countable models of set theory, where similar theorems are proved, but not this one exactly.

Theorem. For any countable transitive model $M\models\text{ZFC}$, the collection of all forcing extensions $M[c]$ by adding an $M$-generic Cohen real is upward-countably closed. That is, for any countable tower of such forcing extensions
$$M[c_0]\subset M[c_1]\subset\cdots\subset M[c_n]\subset\cdots,$$
we may find an $M$-generic Cohen real $d$ such that $M[c_n]\subset M[d]$ for every natural number $n$.

Proof. $\newcommand\Add{\text{Add}}$Suppose that we have such a tower of forcing extensions $M[c_0]\subset M[c_1]\subset\cdots$, and so on. Note that if $M[b]\subset M[c]$ for $M$-generic Cohen reals $b$ and $c$, then $M[c]$ is a forcing extension of $M[b]$ by a quotient of the Cohen-real forcing. But since the Cohen forcing itself has a countable dense set, it follows that all such quotients also have a countable dense set, and so $M[c]$ is actually $M[b][b_1]$ for some $M[b]$-generic Cohen real $b_1$. Thus, we may view the tower as having the form:
$$M[b_0]\subset M[b_0\times b_1]\subset\cdots\subset M[b_0\times b_1\times\cdots\times b_n]\subset\cdots,$$
where now it follows that any finite collection of the reals $b_i$ are mutually $M$-generic.

Of course, we cannot expect in general that the real $\langle b_n\mid n<\omega\rangle$ is $M$-generic for $\Add(\omega,\omega)$, since this real may be very badly behaved. For example, the sequence of first-bits of the $b_n$’s may code a very naughty real $z$, which cannot be added by forcing over $M$ at all. So in general, we cannot allow that this sequence is added to the limit model $M[d]$. (See further discussion in my post Upward closure in the toy multiverse of all countable models of set theory.)

We shall instead undertake a construction by making finitely many changes to each real $b_n$, resulting in a real $d_n$, in such a way that the resulting combined real $d=\oplus_n d_n$ is $M$-generic for the forcing to add $\omega$-many Cohen reals, which is of course isomorphic to adding just one. To do this, let’s get a little more clear with our notation. We regard each $b_n$ as an element of Cantor space $2^\omega$, that is, an infinite binary sequence, and the corresponding filter associated with this real is the collection of finite initial segments of $b_n$, which will be an $M$-generic filter through the partial order of finite binary sequences $2^{<\omega}$, which is one of the standard isomorphic copies of Cohen forcing. We will think of $d$ as a binary function on the plane $d:\omega\times\omega\to 2$, where the $n^{th}$ slice $d_n$ is the corresponding function $\omega\to 2$ obtained by fixing the first coordinate to be $n$.

Now, we enumerate the countably many open dense subsets for the forcing to add a Cohen real $\omega\times\omega\to 2$ as $D_0$, $D_1$, and so on. There are only countably many such dense sets, because $M$ is countable. Now, we construct $d$ in stages. Before stage $n$, we will have completely specified $d_k$ for $k<n$, and we also may be committed to a finite condition $p_{n-1}$ in the forcing to add $\omega$ many Cohen reals. We consider the dense set $D_n$. We may factor $\Add(\omega,\omega)$ as $\Add(\omega,n)\times\Add(\omega,[n,\omega))$. Since $d_0\times\cdots\times d_{n-1}$ is actually $M$-generic (since these are finite modifications of the corresponding $b_k$’s, which are mutually $M$-generic, it follows that there is some finite extension of our condition $p_{n-1}$ to a condition $p_n\in D_n$, which is compatible with $d_0\times\cdots\times d_{n-1}$. Let $d_n$ be the same as $b_n$, except finitely modified to be compatible with $p_n$. In this way, our final real $\oplus_n d_n$ will contain all the conditions $p_n$, and therefore be $M$-generic for $\Add(\omega,\omega)$, yet every $b_n$ will differ only finitely from $d_n$ and hence be an element of $M[d]$. So we have $M[b_0]\cdots[b_n]\subset M[d]$, and we have found our upper bound. QED

Notice that the real $d$ we construct is not only $M$-generic, but also $M[c_n]$-generic for every $n$.

My related post, Upward closure in the toy multiverse of all countable models of set theory, which is based on material in my paper Set-theoretic geology, discusses some similar results.

Upward closure in the generic multiverse of a countable model of set theory, RIMS 2015, Kyoto, Japan

Philosophers Walk Kyoto Japan (summer)This will be a talk for the conference Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Japan, September 16-18, 2015.

Abstract. Consider a countable model of set theory amongst its forcing extensions, the ground models of those extensions, the extensions of those models and so on, closing under the operations of forcing extension and ground model.  This collection is known as the generic multiverse of the original model.  I shall present a number of upward-oriented closure results in this context. For example, for a long-known negative result, it is a fun exercise to construct forcing extensions $M[c]$ and $M[d]$ of a given countable model of set theory $M$, each by adding an $M$-generic Cohen real, which cannot be amalgamated, in the sense that there is no common extension model $N$ that contains both $M[c]$ and $M[d]$ and has the same ordinals as $M$. On the positive side, however, any increasing sequence of extensions $M[G_0]\subset M[G_1]\subset M[G_2]\subset\cdots$, by forcing of uniformly bounded size in $M$, has an upper bound in a single forcing extension $M[G]$. (Note that one cannot generally have the sequence $\langle G_n\mid n<\omega\rangle$ in $M[G]$, so a naive approach to this will fail.)  I shall discuss these and related results, many of which appear in the “brief upward glance” section of my recent paper:  G. Fuchs, J. D. Hamkins and J. Reitz, Set-theoretic geology.

Erin Carmody

Erin Carmody successfully defended her dissertation under my supervision at the CUNY Graduate Center on April 24, 2015, and she earned her Ph.D. degree in May, 2015. Her dissertation follows the theme of killing them softly, proving many theorems of the form: given $\kappa$ with large cardinal property $A$, there is a forcing extension in which $\kappa$ no longer has property $A$, but still has large cardinal property $B$, which is very slightly weaker than $A$. Thus, she aims to enact very precise reductions in large cardinal strength of a given cardinal or class of large cardinals. In addition, as a part of the project, she developed transfinite meta-ordinal extensions of the degrees of hyper-inaccessibility and hyper-Mahloness, giving notions such as $(\Omega^{\omega^2+5}+\Omega^3\cdot\omega_1^2+\Omega+2)$-inaccessible among others.

Erin Carmody

G+ profile | math genealogy | MathOverflow profileNY Logic profilear$\chi$iv

Erin Carmody, “Forcing to change large cardinal strength,”  Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2015.  ar$\chi$iv | PDF

Erin has accepted a professorship at Nebreska Wesleyan University for.the 2015-16 academic year.


Erin is also an accomplished artist, who has had art shows of her work in New York, and she has pieces for sale. Much of her work has an abstract or mathematical aspect, while some pieces exhibit a more emotional or personal nature. My wife and I have two of Erin’s paintings in our collection:

The weakly compact embedding property, Apter-Gitik celebration, CMU 2015

This will be a talk at the Conference in honor of Arthur W. Apter and Moti Gitik at Carnegie Mellon University, May 30-31, 2015.  I am pleased to be a part of this conference in honor of the 60th birthdays of two mathematicians whom I admire very much.

Moti GitikArthur W. Apter









Abstract. The weakly compact embedding property for a cardinal $\kappa$ is the assertion that for every transitive set $M$ of size $\kappa$ with $\kappa\in M$, there is a transitive set $N$ and an elementary embedding $j:M\to N$ with critical point $\kappa$. When $\kappa$ is inaccessible, this property is one of many equivalent characterizations of $\kappa$ being weakly compact, along with the weakly compact extension property, the tree property, the weakly compact filter property and many others. When $\kappa$ is not inaccessible, however, these various properties are no longer equivalent to each other, and it is interesting to sort out the relations between them. In particular, I shall consider the embedding property and these other properties in the case when $\kappa$ is not necessarily inaccessible, including interesting instances of the embedding property at cardinals below the continuum, with relations to cardinal characteristics of the continuum.

This is joint work with Brent Cody, Sean Cox, myself and Thomas Johnstone.

Slides | Article | Conference web site

Carnegie Mellon University, College of Fine Arts

Upward closure in the toy multiverse of all countable models of set theory

The Multiverse by KaeltykThe toy multiverse of all countable models of set theory is upward closed under countably many successive forcing extensions of bounded size…

I’d like to explain a topic from my recent paper

G. Fuchs, J. D. Hamkins, J. ReitzSet-theoretic geology, to appear in the Annals of Pure and Applied Logic.

We just recently made the final revisions, and the paper is available if you follow the title link through to the arxiv. Most of the geology article proceeds from a downward-oriented focus on forcing, looking from a universe $V$ down to its grounds, the inner models $W$ over which $V$ might have arisen by forcing $V=W[G]$. Thus, the set-theoretic geology project arrives at deeper and deeper grounds and the mantle and inner mantle concepts.

One section of the paper, however, has an upward-oriented focus, namely, $\S2$ A brief upward glance, and it is that material about which I’d like to write here, because I find it to be both interesting and comparatively accessible, but also because the topic proceeds from a different perspective than the rest of the geology paper, and so I am a little fearful that it may get lost there.

First is the observation that I first heard from W. Hugh Woodin in the early 1990s.


Observation. If $W$ is a countable model of ZFC set theory, then there are forcing extensions $W[c]$ and $W[d]$, both obtained by adding a Cohen real, which are non-amalgamable in the sense that there can be no model of ZFC with the same ordinals as $W$ containing both $W[c]$ and $W[d]$. Thus, the family of forcing extensions of $W$ is not upward directed.

Proof. Since $W$ is countable, let $z$ be a real coding the entirety of $W$. Enumerate the dense subsets $\langle D_n\mid n<\omega\rangle$ of the Cohen forcing $\text{Add}(\omega,1)$ in $W$. We construct $c$ and $d$ in stages. We begin by letting $c_0$ be any element of $D_0$. Let $d_0$ consist of exactly as many $0$s as $|c_0|$, followed by a $1$, followed by $z(0)$, and then extended to an element of $D_0$. Continuing, $c_{n+1}$ extends $c_n$ by adding $0$s until the length of $d_n$, and then a $1$, and then extending into $D_{n+1}$; and $d_{n+1}$ extends $d_n$ by adding $0$s to the length of $c_{n+1}$, then a $1$, then $z(n)$, then extending into $D_{n+1}$. Let $c=\bigcup c_n$ and $d=\bigcup d_n$. Since we met all the dense sets in $W$, we know that $c$ and $d$ are $W$-generic Cohen reals, and so we may form the forcing extensions $W[c]$ and $W[d]$. But if $W\subset U\models\text{ZFC}$ and both $c$ and $d$ are in $U$, then in $U$ we may reconstruct the map $n\mapsto\langle c_n,d_n\rangle$, by giving attention to the blocks of $0$s in $c$ and $d$. From this map, we may reconstruct $z$ in $U$, which reveals all the ordinals of $W$ to be countable, a contradiction if $U$ and $W$ have the same ordinals. QED

Most of the results here concern forcing extensions of an arbitrary countable model of set theory, which of course includes the case of ill-founded models. Although there is no problem with forcing extensions of ill-founded models, when properly carried out, the reader may prefer to focus on the case of countable transitive models for the results in this section, and such a perspective will lose very little of the point of our observations.

The method of the observation above is easily generalized to produce three $W$-generic Cohen reals $c_0$, $c_1$ and $c_2$, such that any two of them can be amalgamated, but the three of them cannot. More generally:

Observation. If $W$ is a countable model of ZFC set theory, then for any finite $n$ there are $W$-generic Cohen reals $c_0,c_1,\ldots,c_{n-1}$, such that any proper subset of them are mutually $W$-generic, so that one may form the generic extension $W[\vec c]$, provided that $\vec c$ omits at least one $c_i$, but there is no forcing extension $W[G]$ simultaneously extending all $W[c_i]$ for $i<n$. In particular, the sequence $\langle c_0,c_1,\ldots,c_{n-1}\rangle$ cannot be added by forcing over $W$.

Let us turn now to infinite linearly ordered sequences of forcing extensions. We show first in the next theorem and subsequent observation that one mustn’t ask for too much; but nevertheless, after that we shall prove the surprising positive result, that any increasing sequence of forcing extensions over a countable model $W$, with forcing of uniformly bounded size, is bounded above by a single forcing extension $W[G]$.

Theorem. If $W$ is a countable model of ZFC, then there is an increasing sequence of set-forcing extensions of $W$ having no upper bound in the generic multiverse of $W$. $$W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$$

Proof. Since $W$ is countable, there is an increasing sequence $\langle\gamma_n\mid n<\omega\rangle$ of ordinals that is cofinal in the ordinals of $W$. Let $G_n$ be $W$-generic for the collapse forcing $\text{Coll}(\omega,\gamma_n)$, as defined in $W$. (By absorbing the smaller forcing, we may arrange that $W[G_n]$ contains $G_m$ for $m<n$.) Since every ordinal of $W$ is eventually collapsed, there can be no set-forcing extension of $W$, and indeed, no model with the same ordinals as $W$, that contains every $W[G_n]$. QED

But that was cheating, of course, since the sequence of forcing notions is not even definable in $W$, as the class $\{\gamma_n\mid n<\omega\}$ is not a class of $W$. A more intriguing question would be whether this phenomenon can occur with forcing notions that constitute a set in $W$, or (equivalently, actually) whether it can occur using always the same poset in $W$. For example, if $W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$ is an increasing sequence of generic extensions of $W$ by adding Cohen reals, then does it follow that there is a set-forcing extension $W[G]$ of $W$ with $W[c_0]\cdots[c_n]\of W[G]$ for every $n$? For this, we begin by showing that one mustn’t ask for too much:

Observation. If $W$ is a countable model of ZFC, then there is a sequence of forcing extensions $W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$, adding a Cohen real at each step, such that there is no forcing extension of $W$ containing the sequence $\langle c_n\mid n<\omega\rangle$.

Proof. Let $\langle d_n\mid n<\omega\rangle$ be any $W$-generic sequence for the forcing to add $\omega$ many Cohen reals over $W$. Let $z$ be any real coding the ordinals of $W$. Let us view these reals as infinite binary sequences. Define the real $c_n$ to agree with $d_n$ on all digits except the initial digit, and set $c_n(0)=z(n)$. That is, we make a single-bit change to each $d_n$, so as to code one additional bit of $z$. Since we have made only finitely many changes to each $d_n$, it follows that $c_n$ is an $W$-generic Cohen real, and also $W[c_0]\cdots[c_n]=W[d_0]\cdots [d_n]$. Thus, we have $$W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots,$$ adding a generic Cohen real at each step. But there can be no forcing extension of $W$ containing $\langle c_n\mid n<\omega\rangle$, since any such extension would have the real $z$, revealing all the ordinals of $W$ to be countable. QED

We can modify the construction to allow $z$ to be $W$-generic, but collapsing some cardinals of $W$. For example, for any cardinal $\delta$ of $W$, we could let $z$ be $W$-generic for the collapse of $\delta$. Then, if we construct the sequence $\langle c_n\mid n<\omega\rangle$ as above, but inside $W[z]$, we get a sequence of Cohen real extensions $$W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$$ such that $W[\langle c_n\mid n<\omega\rangle]=W[z]$, which collapses $\delta$.

But of course, the question of whether the models $W[c_0][c_1]\cdots[c_n]$ have an upper bound is not the same question as whether one can add the sequence $\langle c_n\mid n<\omega\rangle$, since an upper bound may not have this sequence. And in fact, this is exactly what occurs, and we have a surprising positive result:

Theorem. Suppose that $W$ is a countable model of \ZFC, and $$W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$$ is an increasing sequence of forcing extensions of $W$, with $G_n\of\Q_n\in W$ being $W$-generic. If the cardinalities of the $\Q_n$’s in $W$ are bounded in $W$, then there is a set-forcing extension $W[G]$ with $W[G_n]\of W[G]$ for all $n<\omega$.

Proof. Let us first make the argument in the special case that we have $$W\of W[g_0]\of W[g_0][g_1]\of\cdots\of W[g_0][g_1]\cdots[g_n]\of\cdots,$$ where each $g_n$ is generic over the prior model for forcing $\Q_n\in W$. That is, each extension $W[g_0][g_1]\cdots[g_n]$ is obtained by product forcing $\Q_0\cross\cdots\cross\Q_n$ over $W$, and the $g_n$ are mutually $W$-generic. Let $\delta$ be a regular cardinal with each $\Q_n$ having size at most $\delta$, built with underlying set a subset of $\delta$. In $W$, let $\theta=2^\delta$, let $\langle \R_\alpha\mid\alpha<\theta\rangle$ enumerate all posets of size at most $\delta$, with unbounded repetition, and let $\P=\prod_{\alpha<\theta}\R_\alpha$ be the finite-support product of these posets. Since each factor is $\delta^+$-c.c., it follows that the product is $\delta^+$-c.c. Since $W$ is countable, we may build a filter $H\of\P$ that is $W$-generic. In fact, we may find such a filter $H\of\P$ that meets every dense set in $\bigcup_{n<\omega}W[g_0][g_1]\cdots[g_n]$, since this union is also countable. In particular, $H$ and $g_0\cross\cdots\cross g_n$ are mutually $W$-generic for every $n<\omega$. The filter $H$ is determined by the filters $H_\alpha\of\R_\alpha$ that it adds at each coordinate.

Next comes the key step. Externally to $W$, we may find an increasing sequence $\langle \theta_n\mid n<\omega\rangle$ of ordinals cofinal in $\theta$, such that $\R_{\theta_n}=\Q_n$. This is possible because the posets are repeated unboundedly, and $\theta$ is countable in $V$. Let us modify the filter $H$ by surgery to produce a new filter $H^*$, by changing $H$ at the coordinates $\theta_n$ to use $g_n$ rather than $H_{\theta_n}$. That is, let $H^*_{\theta_n}=g_n$ and otherwise $H^*_\alpha=H_\alpha$, for $\alpha\notin\{\theta_n\mid n<\omega\}$. It is clear that $H^*$ is still a filter on $\P$. We claim that $H^*$ is $W$-generic. To see this, suppose that $A\of\P$ is any maximal antichain in $W$. By the $\delta^+$-chain condition and the fact that $\text{cof}(\theta)^W>\delta$, it follows that the conditions in $A$ have support bounded by some $\gamma<\theta$. Since the $\theta_n$ are increasing and cofinal in $\theta$, only finitely many of them lay below $\gamma$, and we may suppose that there is some largest $\theta_m$ below $\gamma$. Let $H^{**}$ be the filter derived from $H$ by performing the surgical modifications only on the coordinates $\theta_0,\ldots,\theta_m$. Thus, $H^*$ and $H^{**}$ agree on all coordinates below $\gamma$. By construction, we had ensured that $H$ and $g_0\cross\cdots\cross g_m$ are mutually generic over $W$ for the forcing $\P\cross\Q_0\cross\cdots\cross\Q_m$. This poset has an automorphism swapping the latter copies of $\Q_i$ with their copy at $\theta_i$ in $\P$, and this automorphism takes the $W$-generic filter $H\cross g_0\cross\cdots\cross g_m$ exactly to $H^{**}\cross H_{\theta_0}\cross\cdots \cross H_{\theta_m}$. In particular, $H^{**}$ is $W$-generic for $\P$, and so $H^{**}$ meets the maximal antichain $A$. Since $H^*$ and $H^{**}$ agree at coordinates below $\gamma$, it follows that $H^*$ also meets $A$. In summary, we have proved that $H^*$ is $W$-generic for $\P$, and so $W[H^*]$ is a set-forcing extension of $W$. By design, each $g_n$ appears at coordinate $\theta_n$ in $H^*$, and so $W[g_0]\cdots[g_n]\of W[H^*]$ for every $n<\omega$, as desired.

Finally, we reduce the general case to this special case. Suppose that $W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$ is an increasing sequence of forcing extensions of $W$, with $G_n\of\Q_n\in W$ being $W$-generic and each $\Q_n$ of size at most $\kappa$ in $W$. By the standard facts surrounding finite iterated forcing, we may view each model as a forcing extension of the previous model $$W[G_{n+1}]=W[G_n][H_n],$$ where $H_n$ is $W[G_n]$-generic for the corresponding quotient forcing $\Q_n/G_n$ in $W[G_n]$. Let $g\of\text{Coll}(\omega,\kappa)$ be $\bigcup_n W[G_n]$-generic for the collapse of $\kappa$, so that it is mutually generic with every $G_n$. Thus, we have the increasing sequence of extensions $W[g][G_0]\of W[g][G_1]\of\cdots$, where we have added $g$ to each model. Since each $\Q_n$ is countable in $W[g]$, it is forcing equivalent there to the forcing to add a Cohen real. Furthermore, the quotient forcing $\Q_n/G_n$ is also forcing equivalent in $W[g][G_n]$ to adding a Cohen real. Thus, $W[g][G_{n+1}]=W[g][G_n][H_n]=W[g][G_n][h_n]$, for some $W[g][G_n]$-generic Cohen real $h_n$. Unwrapping this recursion, we have $W[g][G_{n+1}]=W[g][G_0][h_1]\cdots[h_n]$, and consequently $$W[g]\of W[g][G_0]\of W[g][G_0][h_1]\of W[g][G_0][h_1][h_2]\of\cdots,$$ which places us into the first case of the proof, since this is now product forcing rather than iterated forcing. QED

Definition. A collection $\{W[G_n]\mid n<\omega\}$ of forcing extensions of $W$ is finitely amalgamable over $W$ if for every $n<\omega$ there is a forcing extension $W[H]$ with $W[G_m]\of W[H]$ for all $m\leq n$. It is amalgamable over $W$ if there is $W[H]$ such that $W[G_n]\of W[H]$ for all $n<\omega$.

The next corollary shows that we cannot improve the non-amalgamability result of the initial observation to the case of infinitely many Cohen reals, with all finite subsets amalgamable.

Corollary. If $W$ is a countable model of ZFC and $\{W[G_n]\mid n<\omega\}$ is a finitely amalgamable collection of forcing extensions of $W$, using forcing of bounded size in $W$, then this collection is fully amalgamable. That is, there is a forcing extension $W[H]$ with $W[G_n]\of W[H]$ for all $n<\omega$.

Proof. Since the collection is finitely amalgamable, for each $n<\omega$ there is some $W$-generic $K$ such that $W[G_m]\of W[K]$ for all $m\leq n$. Thus, we may form the minimal model $W[G_0][G_1]\cdots[G_n]$ between $W$ and $W[K]$, and thus $W[G_0][G_1]\cdots [G_n]$ is a forcing extension of $W$. We are thus in the situation of the theorem, with an increasing chain of forcing extensions. $$W\of W[G_0]\of W[G_0][G_1]\of\cdots\of W[G_0][G_1]\cdots[G_n]\of\cdots$$ Therefore, by the theorem, there is a model $W[H]$ containing all these extensions, and in particular, $W[G_n]\of W[H]$, as desired. QED

Please go to the paper for more details and discussion.

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.