User everett piper - MathOverflow

Set forcing and ultrapowers

2013-02-20T21:41:32Z

The following is a result of Woodin (the proof is found after Theorem 5 of "Generalizations of the Kunen Inconsistency" by Hamkins, Kirkmayer and Perlmutter):

(Woodin) Let $V[G]$ be a set-forcing extension of $V$. Then there is no non-trivial elementary embedding $$j:V[G]\prec V.$$ Corollary 6 gives the theorem from the perspective of the extension as: If $$j:V\prec M$$ is a non-trivial elementary embedding in $V$, then $M$ is not a set-forcing extension of $V$.

From the point-of-view of the generic extension, the corollary can be read as something like "I am not an ultrapower of the ground model by $U$." This must be true for every ultrafilter $U$ in the generic extension. Since the generic extension was an arbitrary set-forcing extension, it seems to me that the corollary implies that ultrapowers of $V$ (or maybe I should say "transitive collapses of ultrapowers of $V$"?) are not obtainable from set forcing (over $V$).

If this is true, I wonder if this was known before the proof presented in the "Generalizations..." paper and even if there is another, substantially different proof (whatever this could mean).

Further (and perhaps this is a silly question with an obvious answer) can ultrapowers of $V$ be obtained by class forcing? Given a transitive set/class $M$, could forcing over $M$ (where the p.o. is considered a class from the point-of-view of $M$) yield a set/class which is isomorphic to some (all?) ultrapower of $M$?

(Added later: I take Woodin's original result to say something like "the ground model is not the transitive collapse of any ultrapower by $U$" is true from the point-of-view of a set-forcing extension's point-of-view. Is this understanding correct?)

Elementary Embeddings and Relative Constructibility

2013-01-12T01:04:22Z

Suppose $$j:M\prec N$$ is a non-trivial elementary embedding. Under what conditions on the sets (classes?) $M$ and $N$ (or even the critical point of $j$) does $j$ extend to an elementary embedding $$k:L(M)\prec L(N)?$$

In the case where $M=N=V_{\lambda+1}$, the existence of such a $k$ is a strictly stronger assumption (this is Woodin's $I_0$ axiom), but need this always be the case?

A more specific question involves extendible cardinals: Recall that $\kappa$ is extendible if, for every $\eta >\kappa$ there exists a $\theta>\eta$ and an elementary embedding $j:V_{\eta+1}\prec V_{\theta+1}$ such that $crit(j)=\kappa$ and $j(\kappa)>\eta$. Does $j$ extend to a $$k:L(V_{\eta+1})\prec L(V_{\theta+1})?$$

Is the existence of such a $k$ a straight-forward construction or is it strictly stronger than the existence of an extendible cardinal?

Generic Extensions and $L(V_{\lambda+1})$

2012-10-11T02:46:40Z

Suppose $\lambda$ is a strong limit cardinal of cofinality $\omega$ and for $A$ a transitive set, define $L(A)$ in the usual fashion by setting $$L_0(A)=A;$$ $$L_{\alpha+1}(A) = L_\alpha (A)\cup \mathcal P_{Def}(L_\alpha(A));$$ $$L(A)=\bigcup_{\alpha\in Ord} L_\alpha (A).$$

In Woodin's longer article "The Continuum Hypothesis" (in LNL 19, Logic Colloquium 2000), the following facts are stated regarding $L(V_{\lambda+1})$:

(1) If $c$ is Cohen generic over $V$ then very likely $$(L(V_{\lambda+1}))^{V[c]}\neq L(V_{\lambda+1})[c].$$

(2) On the other hand, if $G\subset Coll(\omega_1,\mathbb{R})$ is $V$-generic then $$(L(V_{\lambda+1}))^{V[G]}= L(V_{\lambda+1})[G].$$

Can anyone give a (sketch of) proof of either (1) or (2)? Are these results given only in the context of a non-trivial elementary embedding $j:L(V_{\lambda+1})\prec L(V_{\lambda+1})$ with $crit(j)<\lambda$?

More generally, for a partial order $\mathbb{P}$ and a $G\subset \mathbb{P}$ which is $V$-generic, which properties of $\mathbb{P}$ are sufficient to ensure the equality $$(L(V_{\lambda+1}))^{V[G]}= L(V_{\lambda+1})[G]$$ holds? Fails? Is this even known?

Logical relationships between weakenings of AC

2012-05-06T03:38:42Z

What are the known logical implications between weak choice principles like $DC_\kappa$", theultrafilter theorem for sets of size $\kappa$" (by which I mean every filter over a set A of size $\kappa$ can be extended to a non-principle ultrafilter), and ``every relation $R$ over $A$ can be uniformized by a function $f$ with the same domain as $R$"?

Jech's book on the Axiom of Choice gives nice proofs that ``uniformization for $A$" and "the ultrafilter theorem for sets of size $|A|$ logically independent, i.e. neither implies the other. My concern is how either of these consequences of AC relate to uniformization.

I assume $DC_\kappa$ does not imply uniformization of sets of size larger than $\kappa$ but I have yet to see any proof of this fact.

Are the three principles logically independent of one another on a global scale? How do they relate on a more local level?

Theories and indiscernible propositions

2012-03-11T01:09:10Z

Are there known examples of statements which are strong from a proof-theoretic standpoint but which are indistinguishable by one set of axioms (or proof system) yet distinct according to a stronger set of axioms?

More specifically, I'm wondering if there are examples of the following kind:

Let $T_1$ and $T_2$ be theorems in some formal language $\mathcal{L}$. Let $A_1$ and $A_2$ be two distinct sets of axioms in $\mathcal{L}$ but which are not (obviously) incompatible. Are there known examples of $T_1$ and $T_2$ where $A_1$ proves "$T_1$ is equivalent to $T_2$" but $A_2$ proves "$T_1$ is strictly stronger than $T_2$"?

At first glance, this notion of "stronger" conflicts with the received notion of "stronger" as "proving the same and more theorems" so the notion of "stronger theory" I'm asking about rules out characterizations like "the collection of formulas deducible from $A_1$ is properly contained in the collection of formulas deducible from $A_2$". I'm wondering if there is a sense in which two theories can disagree on the equivalence of two propositions because the weaker theory views the propositions as the same in some sense and the stronger theory witnesses some kind of first-order (or higher?) distinction between the propositions. Is this a useful notion in general? Or would this require some kind of axiom like "indiscernible objects are identical" to make precise and/or useful?

A proposed axiom of Laver (updated)

2011-09-27T02:24:50Z

A few months back, I posted a question asking about a proposed axiom of Laver's and I, unfortunately, left out a critical piece. Here is the full axiom:

(L) Some elementary embedding $j:V_{\lambda+1}\prec V_{\lambda+1}$ extends to a non-trivial elementary embedding $h:HOD(ord^\lambda)\prec HOD(ord^\lambda)$ where it is assumed that $HOD(ord^\lambda)\models ZF +DC_\lambda + Unif(V_{\lambda+1})$.

Here $DC_\lambda$ denotes the axiom of $\lambda$-dependent choice and $Unif(V_{\lambda +1})$ is the axiom that uniformization holds for $V_{\lambda +1}$. More specifically, given any $R\subseteq V_{\lambda +1}\times V_{\lambda +1}$ there exists some function $f\subset R$ with the same domain as $R$.

This axiom is generically fragile in that any small forcing adding a real kills the axiom. This fragility is evidently a consequence of the further assumption about which axioms hold in $HOD(ord^\lambda)$, in particular $Unif(V_{\lambda +1})$.

As before, I have no indication about how this is established at the moment and I suspect that the problem is that I don't understand what the model $HOD(ord^\lambda)$ looks like in a generic extension. I am hoping someone can give me some indication as to the kinds of "damage" $HOD$-like models can undergo during a forcing.

Extension of Tao-Green Theorem

2011-09-27T03:18:56Z

The following result was proved by Tao and Green: For every $k$, there exist infinitely many arithmetic progressions of length $k$ contained in the sequence of prime numbers.

I think this is an interesting result from a recursion-theoretic point-of-view since it suggests that there is some linear kind of bound on the growth rate of any recursive function enumerating "big" subsets of the primes. (I'll get back to this point later.)

I have a different, though I think related, question:

Suppose we index the primes according to their natural order (i.e., $p_1 =2, p_2 =3, p_3=5$, etc.) and then consider the primes as the disjoint union of two infinite sets $A_1$ and $B_1$. $A_1$ contains only those primes that have prime index, and $B_1$ contains those primes which have composite index (including 1). For example, $A_1={3,5,11,17, \dots }$ and $B_1={2,7,13,19,\dots}$.

If I'm not mistaken, $B_1$ (or any finite truncation of it) has finite upper density (relative to the set of primes), hence by the Tao-Green theorem, $B_1$ contains for every $k$ infinitely many a.p.s of length $k$. (Is this correct?)

However, $A_1$ does not have positive upper density. Nevertheless, could it be the case that

$(*)$ for every $k$ there are infinitely many a.p.s of length $k$ contained in $A_1$?

What would happen if we re-indexed all the members of $A_1$ according to their order and defined the sets $A_{1,1}$ (containing those elements of $A_1$ with prime index) and $A_{1,2}$ (containing those elements with composite index incl. 1). (We could also do the same for for $B_1$...)

$(*_2)$ Does an analogue for $(*)$ hold in this 1-step iteration?

Iterating the process above n times:

$(*_{n+1})$ Does an analogue for $(*)$ hold in this $n$-step iteration?

How far can this kind of construction go?

Comment by Everett Piper

2013-05-08T03:25:24Z

As far as the other axioms of ZFC go, you might try to violate them by requiring some kind of definability constraint on $V_\theta$. What I have in mind here is something like: assume $\theta$ is worldly and every set (in $V_\theta$) is definable from parameters in some set $X$ (given ahead of time). Then could there be a forcing extension where, say, pairing fails in the sense that there are sets $a$ and $b$ where $\{a,b\}$ is not definable (from parameters in $X$)? I don't know if this situation could ever arise, but it seems like it could in contexts like $V=L$ or there is an $I_0$ cardinal

Comment by Everett Piper

2013-05-08T03:19:10Z

Second, the desired forcing would have to kill some particular axiom of ZFC. Joel suggests altering the truth-value of some particular instance of replacement, but couldn't we attack an instance of collection (I'm not sure if this even makes sense) or even introduce a set into $V_\theta$ that has no choice function, thereby violating choice instead? This seems to require that one look at a symmetric inner model $M$ and inspect its version of $V_\theta$ (though I'm guessing this isn't what you had in mind, Erin).

Comment by Everett Piper

2013-05-08T03:13:34Z

I have some thoughts on this, though I don't know if any of them are really that good. First, it is a theorem that set-forcing over a ground model of ZFC will only yield models of ZFC, so starting with $V_\theta$ itself won't work. However, in Joel's response, it appears that we could have started with $V_\theta$ and killed the worldliness of $\theta$. However, the requirement that $\theta$ be singular makes the forcing appear to be a class forcing from the point-of-view of $V_\theta$. If this is the case, then one can't eliminate the hypothesis that $\theta$ be singular here. Is this correct?

Comment by Everett Piper

2013-04-14T18:42:55Z

On a slightly different note, you may want to hunt down the following two articles: (I) Kent, C. F. The relation of $A$ to $Prov(A)$ in the Lindenbaum sentence algebra. J. Symbolic Logic 38 (1973), 295–298; (II) Macintyre, A.; Simmons, H. Gödel's diagonalization technique and related properties of theories. Colloq. Math. 28 (1973), 165–180.

Comment by Everett Piper

2013-04-14T18:38:09Z

particular instance of the reflection principle $Pr_\tau(\phi)\rightarrow\phi$ and then concatenate $\phi$. The penultimate line of this proof is justified since we merely appended an axiom of T to the original T-proof of $Pr_\tau(\phi)$ and the last line follows from a single application of modus ponens. So it's actually straight-forward to produce a number witnessing a T-proof of $\phi$ given a number witnessing T-proof of $Pr_\tau(\phi)$.

Comment by Everett Piper

2013-04-14T18:35:35Z

There is a more-or-less standard way to formalize $\Sigma_1^0$ soundness for ZFC: Given a formula $\tau$ enumerating the axioms of ZFC, construct the proof-predicate $Pr_\tau(x)$. Now construct the theory T. T has all axioms of ZFC and a schema of all sentences of the form $Pr_\tau(\varphi)\rightarrow \varphi$ where $\varphi$ is any formula in the language of ZFC. Sometimes T includes as an axiom "< is a well-ordering of $\omega$."Working in T, any proof of $Pr_\tau(\phi)$ can be transformed into a proof of $\phi$ in a simple way: copy the T-proof of $Pr_\tau(\phi)$, concatenate the

Comment by Everett Piper

2013-03-07T04:27:15Z

Erin, I'm curious about the specific reflection principle you're interested in. It seems you are interested primarily in set theory so it may very well be the case that you are interested in a set-theoretic reflection principle as opposed to a proof-theoretic principle. Proof-theoretic principles are typically formalized versions of the intuition that a particular proof-system or set of axioms is sound. Set-theoretic reflection principles seem to express the intuition that certain kinds of structure in V keep repeating or reflecting arbitrarily high up in the cumulative hierarchy.

Comment by Everett Piper

2013-03-07T04:16:14Z

principles. For example, there really is no "good" formalization of "is provable" in the sense that there are lots of non-standard proof predicates that can be constructed and there is no mathematical distinction between the non-standard and standard proof predicates. There is also ambiguity in the sentence(s) formalizing that S is a consistent theory (or has a model, or has an omega-model, etc.). There is an excellent article (and also a book) by Torkel Franzen. Smorynski's article in the Handbook of Mathematical Logic is also a good place to start. I can provide lots more info/literature if

Comment by Everett Piper

2013-03-07T04:10:02Z

It might be worthwhile to note the reflection principle mentioned by Jaykov is actually a schema; there is such a conditional for every sentence $\phi$ in the formal language being used. Further, the intuitive reading for each individual member of the scheme is something like "If S proves $\Phi$ then $\Phi$ is true (or $\Phi$ holds, or whatever variation you prefer)". For arbitrary $\Phi$ this is known as the Uniform Reflection Principle for S. Feferman (Turing, Beklemishev, Smorynski and others) have shown that there are all kinds of subtleties involving these proof-theoretic reflection

Comment by Everett Piper

2013-02-21T05:16:54Z

On my latest reading I have become confused. I have a sense that there is/was no distinction between an elementary embedding $j:V\prec V[G]$ and an elementary embedding $j:V[G]\prec V$ where $G$ is a $V$-generic subset of a set $\mathbb{P}$. I guess I'm still trying to understand the nuance here. But thank you for pointing out the historical relevance of your remarks.

Comment by Everett Piper

2013-02-21T05:10:55Z

Joel, I believe I was really asking about ultrapowers by class forcing when I originally posed my question. But if you're thinking of some wider class of transitive models I'm certainly curious. I've read your paper (thanks for the correction regarding Prof. Kirmayer, by the way) several times and this traverse through I had a new thought (which always seems to happen).

Comment by Everett Piper

2013-02-01T21:35:11Z

Are you only interested in the case where you specifically force to get just a Cohen subset, i.e. only $Add(\kappa,1)$, or could you allow forcings which generically adjoin a Cohen subset as a by-product of adjoining some other generic object?

Comment by Everett Piper

2012-10-28T18:25:02Z

Paul Larson's article "A Brief History of Determinacy" mentions that the proof you're looking for is due to Martin. See the paragraph just before Theorem 6.8 in users.muohio.edu/larsonpb/determinacy_cabal.pdf. There is, however, no list of references at the end of the article. So you may want to contact Prof. Larson directly.

Comment by Everett Piper

2012-10-19T23:15:34Z

(2) Can you sketch Cramer's extension of Large Perfect Set Theorem to the more general case where $X\in L(V_{\lambda+1})$?

Comment by Everett Piper

2012-10-19T23:14:01Z

X. Shi: Thank you so much for this answer. I have been immersed in the Large Perfect Set Theorem for a week now. I have two related questions as a result. (1) In your paper on the Robinson-Posner Theorem at $I_0$, you state the Large Perfect Set Theorem for $X\subset V_{\lambda+1}$ definable from parameters in $V_{\lambda+1}$, i.e., for $X\in L_1(V_{\lambda+1})$. Can you extend your argument there in some way to get the result for all large $X\in L_\lambda(V_{\lambda+1})$? I ask because Woodin's proof of Large Perfect Set in Lemma 22 uses the notion of $\mathbb{U}(j)$-representability.