Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Shoenfield's Absoluteness Theorem states that if $\phi$ is any $\Sigma^1_2$ sentence of second-order arithmetic, then $\phi$ is absolute between any two models of $ZF$ which share the same ordinals. This means that such $\phi$ are unaffected by forcing, or by Axiom of Choice-related considerations (since for any $V\models ZF$, the corresponding subclass $L$ is a model of $ZFC$).

What I'm looking for is a simple example of either a $\Sigma^1_3$ or $\Pi^1_3$ sentence $\psi$ which is not absolute in this way - ideally, such a $\psi$ which is true in some $V\models ZFC$ and false in a generic extension $V[G]$. This is a purely pedagogical question for me - I'm trying to internalize Shoenfield Absoluteness, and I feel that a nice example of why it can't be made much stronger would help.

Thank you all in advance.

share|improve this question
add comment

3 Answers

up vote 11 down vote accepted

Noah: The sentence "there is a real not in $L$" is $\Sigma^1_3$: To say that $x\notin L$ means that for every $y$, if $y$ codes a model of the form $L_\alpha$, then $x$ is not in this model; but to say that $y$ codes an $L_\alpha$ (for a sufficiently "closed" $\alpha$) means that $y$ codes a structure $(M,E)$ (this is arithmetic) that satisfies, say, $KP+V=L$ (you can do this in, say, a $\Delta^1_1$ way); and you need to express that this structure is well-founded, for which you just have to say that no real codes a decreasing sequence through its ordinals.

Counting quantifiers, this comes out $\Sigma^1_3$. It is false in $L$ and true after adding a Cohen real.

On the other hand, if $\phi$ is $\Pi^1_3$ and holds in an outer model of $V$, then it holds in $V$: The sentence says that every real (in the extension) has an absolute property, so in particular every real in $V$ has that property, in $V$.

This, however, is not "the limit of absoluteness," as per your title, only of Shoenfield's absoluteness. Large cardinals in the universe grant you much stronger absoluteness properties between $V$ and its forcing extensions. Even at the level of (boldface) $\Sigma^1_3$ generic absoluteness, this involves sharps. A nice proof is sketched in my paper with Ralf Schindler, "Projective well-orderings of the reals" Archive for Mathematical Logic 45 (7) (2006), 783-793, available at my page.

Beyond this level but still looking at projective statements, strong cardinals are involved, by a nice result of Woodin. You can read the details in John Steel's "the derived model theorem," which also gives you a nice introduction to some of the topics that come up when studying absoluteness, such as universally Baire representations of sets. The paper is available at John's page.

Even beyond this level something can be said. Now you require Woodin cardinals, and absoluteness is tied up with determinacy. In fact, the statement that "no set forcing can change the theory of $L({\mathbb R})$, even allowing reals as parameters," is equivalent to saying that determinacy holds in $L({\mathbb R})$ in any set forcing extension. This in turns is equivalent, for example, to the statement that the mouse $M_\omega^\sharp$ exists and is fully iterable. $M_\omega^\sharp$ is a fine structural object (a generalization of a level of $L$ or of $L[\mu]$) with $\omega$ Woodin cardinals. Full iterability is a technical condition, but it ensures that in any forcing extension, $L({\mathbb R})$ is a derived model, a requirement from which determinacy follows.

And we can even continue beyond $L({\mathbb R})$ for a bit. But I'll stop here.

share|improve this answer
    
Thank you very much! This is an excellent answer. I've changed the title accordingly, and I'm starting to look at the papers you mentioned. –  Noah S Aug 3 '11 at 16:53
    
Glad to be of help. –  Andres Caicedo Aug 3 '11 at 16:57
add comment

The classical example is the statement:

Every real is constructible.

To see that this is $\Pi^1_3$, first note that if $T$ is any theory in a language containing $\in$, then "$T$ has a countable wellfounded model" is a $\Sigma^1_2$ statement. For each $r \subseteq \omega$, take $T_r$ to be a sufficiently large fragment of ZFC+V=L plus the axioms $R(n)$ (resp. $\lnot R(n)$) for $n \in r$ (resp. $n \notin r$), where $R$ is a new unary predicate and the $n$ are new constant symbols together with axioms which make them correspond to elements of $\omega$. Then $T_r$ has a countable wellfounded model for every $r \subseteq \omega$ iff every real is constructible. Choosing the $T_r$ judiciously gives a $\Pi^1_3$ formulation of the above.

share|improve this answer
add comment

Jensen and Solovay dealt with the question. For example $0^\#$ is a $\Delta^1_3$ real number, which is obviously not absolute because it cannot go deeper than $L[0^\#]$, and clearly it can't be absolute enough to be in $L$.

Jensen and Solovay point out that assuming a measurable cardinal, then there is such example. But what if one doesn't want to assume large cardinals?

Solovay constructed the following example. $M$ is a transitive countable model of $V=L$. Then there is $N=M[a]$ where $a$ is a real number and there is a $\Pi^1_2$ predicate $S(x)$ such that $N\models(\exists!x\subseteq\omega)S(x)$, and $N\models S(a)$, and moreover $N=M[a]$.

Jensen extended this result and showed that we can have that every $y\in\mathcal P(\omega)^L$ is recursive in $a$.

Both these results appear in the paper:

Jensen, R. B.; Solovay, R. M. "Some applications of almost disjoint sets." Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968) (1970) pp. 84–104.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.