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

Some logicians-such as G. Kreisel-have stated that the Continuum Hypothesis is decided in ZFC2 ("Second-Order ZFC") although we do not know which way it is decided. This is rather confusing, since it is not usually made clear just what the collection of axioms (both logical and non-logical) of ZFC2-as a formalized theory-is to include. ZFC2 is presumably formalized in the Classical Second-Order Predicate Calculus which is not recursively axiomatizable. Is (at least) the following weaker alternative to Kreisel"s statement correct? "If T is any consistent and recursively axiomatizable sub-theory of ZFC2, then neither the Continuum Hypothesis nor its Negation is provable in T."

share|improve this question
1  
I am not sure what you mean by "consistent" (there is no natural syntactic notion). Also, I don't see how your notion of ZFC2 is more explicit than Kreisel's. If T is satisfiable, then at least one of T+CH, T+nonCH is also satisfiable, and both of these systems are as recursive as T is. –  Goldstern Oct 17 '11 at 17:12

2 Answers 2

Think of it this way: Let $V$ be a model of $ZFC_2$. Then I claim CH holds in $V$ if and only if $CH$ is actually true (note that in order for second-order logic to make sense, we have to make a commitment to an underlying "real" universe of sets). The proof of this is as follows. First, $\omega^V$ has order type $\omega$: clearly it has a subset of order type $\omega$, and by the second-order version of the powerset axiom, $P^V(\omega^V)=P(\omega^V)$, so if $\omega^V$ had the wrong order type $V$ would "see" the error. A fortiriori, we can deduce that $\omega^V$ is countable.

By similar reasoning, $P^V(P^V(\omega^V))=P(P(\omega^V))$. Now CH is false if and only if $P(P(\omega^V))$ contains three infinite sets $X, Y, Z$ no two of which have the same cardinalities (left-to-right is trivial; right-to-left follows from the countability of $\omega^V$).

Suppose $CH$ is false; let $X, Y, Z$ be as above. Since $P(P(\omega^V)=P^V(P^V(\omega^V))$, we have $X, Y, Z\in V$; by the axiom of extensionality, $V$ sees that the cardinalities of $X$, $Y$, and $Z$ are different, and by the second-order powerset axiom $V$ sees that $X$, $Y$, and $Z$ are infinite. So $CH\implies (ZFC_2\models \neg CH)$.

Suppose now that $CH$ is true. Let $X, Y, Z\in P(P(\omega^V))$; again, we have $X, Y, Z\in V$. Since $CH$ holds, by the second-order powerset axiom plus separation we can find a bijection $f$ between two of $X, Y, Z$, so $CH$ holds in $V$. So $\neg CH\implies (ZFC_2\models CH)$.

This shows that $ZFC_2\models CH$ or $ZFC_2\models \neg CH$. The point is that the full power of second-order logic allows $V$ to "ask" certain set-theoretic questions of the "real" underlying universe of sets; these questions include ``Is CH true?" Similarly, it seems to me that they include all questions of the form "Does $V_\alpha\models \phi$ hold?" where $\alpha$ is a computable ordinal and $\phi$ is $\Sigma_1$ over $V_\alpha$ ($\Sigma_1$ is somewhat arbitrary; higher quantifier depth can (I believe) be achieved by passing to larger computable $\alpha$).

I'd imagine that in fact this phenomenon extends much further than what I've outlined, and that a staggeringly large class of sentences of set theory are known to be decided in $ZFC_2$, even if we don't know which way they are decided.


I just realized that I didn't answer your actual question.

As Andreas says above, your statement is not correct: both $ZFC+CH$ and $ZFC+\neg CH$ are recursively axiomatizable, and consistent (assuming $ZFC$ is), and one of them is a subtheory of $ZFC_2$ (although we can't tell which). You could try to add some effectiveness criterion to your statement - something along the lines of, "There is no recursively axiomatizable consistent theory $T$ which decides CH and that is provably a subtheory of $ZFC_2$" - but it's unclear to me how to do this in a way that results in a non-trivial, but also not false, statement. The moral is that second-order logic is really nasty. For instance, it wouldn't even make sense to ask for a derivation of CH (or $\neg CH$) from $ZFC_2$, since there's no meaningful proof system for second-order logic. To understand how ridiculously awful this is, there are proof systems for some infinitary logics that are very useful in model theory and proof theory - Lopez-Escobar developed one that Barwise used (altered? my history is a little vague on this point), but I don't know a good reference - and logics that can express concepts like "is uncountable" or can quantify over automorphisms of certain kinds of structures are even compact. Basically, second-order logic is totally unusable (although, as always, there are exceptions).

Also, it occurs to me that we don't even need all of $ZFC_2$ to decide CH. Look at the natural second-order version of the first-order theory which is commonly called, annoyingly enough, "second-order arithmetic" (so I guess its second-order counterpart should be called "second-order analysis"). This will be enough to decide CH, since the arguments above will all go through.

share|improve this answer
    
See my comment in response to the answer of Andreas above. –  Garabed Gulbenkian Oct 14 '11 at 18:21
    
Actually I thought that my statement in quotes is equivalent to your statement in quotes, but maybe I am missing something. –  Garabed Gulbenkian Oct 14 '11 at 18:32

Either first-order ZFC plus CH is a counterexample to your weaker alternative, or first-order ZFC plus not-CH is a counterexample. The point is that, by Kreisel's observation, one of these is a sub-theory of ZFC2.

share|improve this answer
    
In response to your answer, Andreas, I should have explained more clearly what I mean by saying that a theory A is a sub-theory of a theory B. I mean that the set of axioms (both logical and non-logical) of A is a subset of the set of axioms of B. How do you know that either CH or its negation are among the axioms of ZFC2 since the set of axioms of ZFC2 is not recursively enumerable. Perhaps neither CH nor its negation is an axiom of ZFC2. –  Garabed Gulbenkian Oct 14 '11 at 18:15
    
Since you want the question to refer to the sets of axioms, I'm curious what you take to be the set of axioms of ZFC2; in other words, what set should T be a subset of? I suppose the set-theoretic axioms should be those of first-order ZFC except that the replacement schema is replaced with the obvious single second-order axiom. But what should the logical axioms be? –  Andreas Blass Oct 14 '11 at 19:02
    
Yes, you definitely need to clarify what you mean by $ZFC_2$ here. My gut instinct is what I said below: there's no good way to get what you want to be true. (Also, @Andreas: is second-order replacement enough to get second-order powerset? Because I'd think we'd definitely want second-order powerset.) –  Noah S Oct 14 '11 at 20:54
    
In the last chapter of the book "Theory of Recursive Functions and Effective Computability" by Hartley Rogers, it is stated that the set L of logical axioms of Second-order Arithmetic (and thus no doubt of ZFC2 also) is not only non-recursively enumerable but is of high rank in the Analytical Hierarchy of Descriptive Set Theory. –  Garabed Gulbenkian Oct 17 '11 at 15:02
    
@Garabed: Looking up "second-order arithmetic" in the index of Rogers's book, I come to Section 16.2, where I see nothing about "logical axioms of second-order arithmetic". A footnote on page 389 gives a recursive set of axioms and says that this is not what's under discussion. The rest of the section is about truth (not axiomatics) of statements of second-order arithmetic. It's shown (among other things) that this notion of truth is not in the analytical hierarchy. So I still have no clear idea what you mean by axioms of ZFC2. –  Andreas Blass Oct 17 '11 at 15:21

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.