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

Consider the claim:

(C) There is a transitive set $S \in V$ such that the structure $(S, \in)$ is an elementary submodel of $(V, \in)$.

Obviously, this claim cannot be a theoreom of ZFC, by Godel's 2nd Incompleteness Theorem. But does (C) follow from ZFC+CON(ZFC)? Or are large cardinals needed to prove (C)? More generally (and vaguely), what is the weakest assumption needed to prove (C)?

share|improve this question

2 Answers 2

up vote 10 down vote accepted

A cardinal $\delta$ is correct if the theory $V_\delta\prec V$ holds, that is, if $V_\delta$ is an elementary substructure of $V$. This theory is expressible as a scheme in first order logic in the language of set theory augmented by a constant symbol for $\delta$ as the following scheme of statements:

$$\forall \vec a\in V_\delta\ \ (\ \varphi(\vec a)\quad\iff\quad V_\delta\models\varphi[\vec a]\ \ ).$$

Note that any set $\langle S,{\in}\rangle$ such as you desire must have the form $S=V_\delta$ for some $\delta$, since it will the union of the $V_\alpha$ for $\alpha<\delta$ because by elementarity it will be right about these $V_\alpha$, and so this is your main case.

The property of being correct is not expressible as a single assertion in ZFC, unless inconsistent, since otherwise there could be no least reflecting cardinal, since if $\delta$ is the least reflecting cardinal and this were expressible, then $V$ would have a reflecting cardinal, but $V_\delta$ would not. A similar argument applies directly to the existence of a set $\langle S,{\in}\rangle$ as in your question, showing that $S\prec V$ is not expressible as a single assertion in the language of set theory.

Meanwhile, as a scheme, the existence of a reflecting cardinal is equiconsistent with ZFC, and in particular it does not imply Con(ZFC). To see this, observe that if there is a model of ZFC, then by the reflection theorem, we may easily produce models of any given finite subset of the theory. So by compactness the theory $V_\delta\prec V$ is also consistent.

One may easily extend this theory to have a unbounded closed proper class $C$ of cardinals $\delta$ for which $V_\delta\prec V$, a theory known as the Feferman theory, and this also is equiconsistent with ZFC, with no increase of consistency strength, by the same argument. Feferman propsed this theory as a natural background set theory in which to undertake category theory, because it provides a robust universe concept (more robust than Grothendieck universes in that the universes all cohere into an elementary chain), but without the large cardinal commitment.

If one adds to the theory $V_\delta\prec V$ that $\delta$ is inaccessible, then $\delta$ is a reflecting cardinal, whose existence is equiconsistent with Ord is Mahlo.

If one desires a purely first-order concept, expressible as a single property in the language of set theory, then one may restrict to a less severe form of elementarity. For example, a cardinal $\delta$ is $\Sigma_2$-correct if $V_\delta\prec_{\Sigma_2} V$, that is, $V_\delta$ is elementary for formulas of complexity $\Sigma_2$, and $\Sigma_2$-reflecting if $\delta$ is also inaccessible. For example, the $\Sigma_2$-reflecting cardinals commonly arise in large cardinal arguments, and this is expressible in the language of set theory. More generally, one has the concept of a $\Gamma$-reflecting cardinal for any class $\Gamma$ of formulas, and if these have bounded complexity, then these also will be expressible.

For many purposes, the $\Sigma_2$-correct cardinals carry much of the useful power of what you want from $V_\delta\prec V$, since one of the equivalent formulations is that $\delta$ is $\Sigma_2$ correct if and only if whenever there is $\theta$ with $V_\theta\models\sigma$ for any assertion $\sigma$, using parameters in $V_\delta$, then there is $\theta\lt\delta$ with $V_\theta\models\sigma$. In other words, any thing that happens in a $V_\theta$ above $\delta$ also happens below $\delta$.

share|improve this answer
2  
One way of observing that the theory $V_\delta\prec V$ does not prove Con(ZFC) is that if it did, then this proof would use only finitely many of the assertions in the scheme $V_\delta\prec V$, but any finitely many of those assertions hold for some $V_\delta$ by the reflection theorem, and so this would mean that ZFC itself would imply Con(ZFC), which contradicts the incompleteness theorem unless ZFC is inconsistent. –  Joel David Hamkins Aug 2 '12 at 22:16
    
Joel, relating to your ending remark, would you mind elaborating a little on the difference between $\Sigma_2$-reflecting cardinals and the notion of totally indescribable cardinal? It almost seems like the equivalence you mention allows the first $\theta$ to be $\delta$ itself. But your final sentence indicates that $\theta$ is strictly above $\delta$. Do you mean to have $\theta$ strictly larger than $\delta4? –  Everett Piper Aug 3 '12 at 6:49
    
The thought I have is to let $\delta=\theta$ and suppose $V_\delta\models \varphi[x]$ for $\varphi$ arbitrary and $x\in V_\delta$. Then $\{x\}\subset V_\delta$ and $V_\delta\models \varphi^*[\{x}\]$ where $\varphi^*$ is $$\forall y (y\in\{x\})\wedge\varphi[y]$$. If $\delta$ is totally indescribable, doesn't it then follow that $V_\alpha\models \varphi^*[\{x\}]$ for some $\alpha<\delta$? –  Everett Piper Aug 3 '12 at 7:01
1  
Everett, my $\theta$ was arbitrary, and $\theta=\delta$ was allowed. Meanwhile, the two notions of reflection are orthogonal. For example, the existence of $\Sigma_2$ reflecting cardinals is provable in ZFC and thus much weaker than the totally indescribable cardinals in consistency strength (even inaccessible $\Sigma_2$-reflecting cardinals are weaker). –  Joel David Hamkins Aug 3 '12 at 11:38
    
....And on the other hand, the least totally indescribable cardinal $\kappa$ is definable in $V_{\kappa+\omega}$ and is therefore not $\Sigma_2$-reflecting, since if $\theta\geq\kappa+\omega$, then $V_\theta$ thinks there is a totally indescribable cardinal but no $\theta'\lt\kappa$ thinks that is true. –  Joel David Hamkins Aug 3 '12 at 11:39

Two comments on this:

First, it's not clear that one can formulate "there exists a transitive set $S\in V$ such that $S\prec V$" in first-order logic, so it's a bit tricky to phrase your question precisely.

More importantly, I claim that no theory $T$ can have the property you desire. Basically, suppose there were such a $T$. Then $T$ must prove "there exists a transitive model of $T$:" by elementarity, if $V\models T$ then $S\models T$. But then $T\models Con(T)$, which contradicts Goedel's theorem.

(One can also prove a weaker version of this without using Goedel: any theory $T$ containing Choice [EDIT: As Francois points out, Choice is unnecessary here] and Foundation cannot have the property you desire. Otherwise, $T$ would prove "there exists a transitive model of $T$." Now using Choice, we can build a sequence $S_1, S_2, . . . $ such that $S_i\models T$ and $S_{i+1}\in S_i$ for all $i$. But this contradicts Foundation.)

share|improve this answer
    
Excellent points. In reference to the first point, I suppose I should phrase the question semantically - is there some sort of axiom $A$ such that in every model of $A$, $C$ is true. Assuming that we are interested in (large cardinal) axioms that are first order definable and hold true in at least one well-founded model, your argument shows that the answer is no. –  curious Aug 2 '12 at 7:14
    
By the way, the parenthetical remark doesn't really need choice. If $(S_0,{\in}) \vDash T$ then $\lbrace S \in S_0 : (S,{\in}) \vDash T \rbrace$ (which exists by comprehension) has no ${\in}$-minimal element, which contradicts foundation. –  François G. Dorais Aug 2 '12 at 15:16
    
Oh, good point! Fixed. –  Noah S Aug 2 '12 at 15:22

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.