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

From the Incompleteness theorems, if ZF is consistent, one knows there are models of ZF satisfying ¬Con(ZF). These models must be non-standard (in the sense of being models whose ordinals are not well-ordered), and so must be the proof of an inconsistency from the axioms of ZF in them.

Now, ¬Con(ZF) is a very special kind of arithmetical statement. My question is, are there other kinds of statements consistent with ZF known to require the existence of non-standard models to hold?

If there are any, how does one recognize them?

share|improve this question
1  
false statements about $V_{\omega}\cup Ord$ that are consistent with ZF –  Ricky Demer Oct 5 '10 at 13:29
    
the main problem is that you cannot tell which is the "standard model" anyway. the standard model is - in the end - defined by a set of formulas, and undecidable formulas are undecidable until you decide which of them are "standard". –  Christoph-Simon Senjak Oct 5 '10 at 17:23
1  
The standard model has too many particles, anyways. –  drvitek Oct 5 '10 at 17:52
    
By "the standard model", one of course means "this universe". The problem is then that we have incomplete knowledge about this universe to know whether certain statements about it are true. As @drvitek points out, we do know that this universe is mathematically over-complicated, so for some purposes it is better to replace it by a simpler model. –  Theo Johnson-Freyd Oct 5 '10 at 18:03
1  
Thanks, I missed that completely. –  Carl Mummert Nov 2 '10 at 13:49
show 1 more comment

1 Answer

up vote 4 down vote accepted

Here's another example. By a "computable well ordering" I will mean an index for a well-founded computable (total) linear order on $\omega$. Because ZFC is an effective theory, there must be some computable well ordering $\zeta$ that ZFC does not prove is a well ordering. This is because:

  • The set of indices of computable well orderings is strictly $\Pi^1_1$ but, because ZFC is an effective theory, the set of computable linear orderings that ZFC proves are well founded is $\Sigma^0_1$. So it cannot be true that a computable linear ordering is well founded if and only if ZFC proves it is well founded.

  • ZFC is a true theory, so if ZFC proves that a computable linear order $L$ is well founded then $L$ really is well founded.

Because ZFC does not prove that $\zeta$ is a well ordering, there is some model of ZFC in which $\zeta$ is either not a total linear ordering, or $\zeta$ is not well founded. Either of these can only happen in a non-well-founded model of ZFC, since by definition $\zeta$ really is a well ordering.

Although this type of example is related to the type from the question, the proof method sketched here does not make use of consistency statements, so I feel this counts as an essentially different example of the same underlying phenomenon.

share|improve this answer
    
Thanks a lot for your answer, Carl. I guess there's another difference. Can one effectively write a formula defining such a $\zeta$? –  Marc Alcobé García Nov 3 '10 at 14:02
1  
Yes. The index for $\zeta$ is a natural number that encodes a computable function, and there is a formula $\phi(n)$ in the language of ZFC that says that the natural number $n$ is the index of a computable well ordering. Specifically, $\phi$ says that $n$ defines a total function from $\omega \times \omega$ to $\{0,1\}$ and that this function is the characteristic function of a well ordering. –  Carl Mummert Nov 3 '10 at 14:27
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.