Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a previous question I learned that the power of statements of the form $\Pi_m^n$ or $\Sigma_m^n$ for arbitrary positive $m$ and $n$, is smaller than that of ZFC. For instance, the GCH cannot be expressed in such language, and there are totally indescribable cardinals, which mean they are not describable by a $\Pi_m^n$ formula for all positive integers $m$ and $n$.

The question is then if the most extreme natural extension of logic that I could find, $L(\infty,\infty)$, which allows statements of the form $\Pi_\alpha^\beta$ and $\Sigma_\alpha^\beta$, where $\alpha$ and $\beta$ are arbitrarily high cardinals, has the same expressive power of ZFC+any large cardinal axioms, or does set theory still remains more expressive? (if the last is true, is there any known infinitary logic or logic of other kind that has the same expressive power of set theory or perhaps more?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I'm no expert, but I think any extension of the language of set theory allowing infinitary conjunction or disjunction will be more expressive than the finitary language.

For example, in the article you linked to, take the author's final axiom under "Characterization of the standard model of arithmetic", and interpret it in the language of set theory: let $\phi$ be the formula $$ \left(\forall n\in\omega\right)\left(\bigvee_{i=0}^\infty n=S^i\left(0\right)\right). $$

Here, $S$ is the successor function, and for example $S^3\left(0\right)$ abbreviates $S\left(S\left(S\left(0\right)\right)\right)$.

Is there a finitary formula $\psi$ which is equivalent to $\phi$ in ZFC? Well, given that $\phi$ is not finitary, what do we mean by "equivalent"? Perhaps we mean syntactic (provable) equivalence in the infinitary language; I don't really know enough to talk about this though. I think we probably mean semantic equivalence (holding in the same models).

Well, by a standard application of the compactness theorem, if ZFC is consistent then there is a model of ZFC in which $\phi$ does not hold. Moreover, the same argument can be applied with ZFC replaced by any consistent extension of ZFC. So providing $\phi$ does not introduce an inconsistency to ZFC,* no such $\psi$ can exist, else ZFC+$\psi$ would not prove $\psi$, which is absurd. So (under this provision) our infinitary language must really have "more expressive power", as you put it, than any consistent extension of ZFC.

I think the moral of the story is the infinitary languages are weird, and results like the completeness theorem for finitary logic do not carry across. To illustrate the weirdness, observe that if Goldbach's conjecture is true, then it has a one-line proof in an infinitary language consisting of an infinite conjunction of expressions, one for each even integer greater than 2.

*I suspect, but have no idea how to prove, that if ZFC is consistent then there is a model of ZFC in which $\phi$ holds. EDIT: In fact the existence of a model of ZFC in which $\phi$ holds (a so-called $\omega$-model) is strictly stronger than Con(ZFC) since it implies Con(ZFC+Con(ZFC)) (see here and here).

share|improve this answer
    
It occurs to me that you might have wanted to consider an infinitary language allowing allowing some sort of infinite quantification, but not infinitary conjunction or disjunction. I imagine this could be reduced to finitary logic, since you could only ever "use up" finitely many variables. But this is not my area of expertise. –  Jacob H Apr 19 '13 at 14:26
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.