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

Background

Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being the set of natural numbers, so $\in$ will be some binary relation on the natural numbers.

Can such a relation ever be computable?

Partial results

One can show that the class of binary relations $R$ on the natural numbers such that $(\mathbb{N},R) \models ZFC$ forms a $\Pi_0^1$ class, and will be nonempty so long as ZFC is consistent. This already gives us some interesting results. For example, by the low basis theorem, there is a low $R$ such that $(\mathbb{N},R) \models ZFC$. But I have been unable to determine whether such a function can be made computable; the best I can do is show that if such a function is computable, then there is no effective way of finding, given a finite set D of natural numbers, the element n such that D={m : mRn}.

share|improve this question
add comment

3 Answers 3

up vote 13 down vote accepted

The Tennenbaum phenomenon is amazing, and that is totally correct, but let me give a direct proof using the idea of computable inseparability.

Theorem. There is no computable model of ZFC.

Proof: Suppose to the contrary that M is a computable model of ZFC. That is, we assume that the underlying set of M is ω and the membership relation E of M is computable.

First, we may overcome the issue you mention at the end of your question, and we can computably get access to what M thinks of as the nth natural number, for any natural number n. To see this, observe first that there is a particular natural number z, which M believes is the natural number 0, another natural number N, which M believes to the set of all natural numbers, and another natural number s, which M believes is the successor function on the natural numbers. By decoding what it means to evaluate a function in set theory using ordered pairs, We may now successively compute the function i(0)=z and i(n+1) = the unique number that M believes is the successor function s of i(n). Thus, externally, we now have computable access to what M believes is the nth natural number. Let me denote i(n) simply by n. (We could computably rearrange things, if desired, so that these were, say, the odd numbers).

Let A, B be any computably inseparable sets. That is, A and B are disjoint computably enumerable sets having no computable separation. (For example, A is the set of TM programs halting with output 0 on input 0, and B is the set of programs halting with output 1 on input 0.) Since A and B are each computably enumerable, there are programs p0 and p1 that enumerate them (in our universe). These programs are finite, and M agrees that p0 and p1 are TM programs that enumerate a set of what it thinks are natural numbers. There is some particular natural number c that M thinks is the set of natural numbers enumerated by p0 before they are enumerated by p1. Let A+ = { n | n E c }, which is the set of natural numbers n that M thinks are enumerated into M's version of A before they are enumerated into M's version of B. This is a computable set, since E is computable. Also, every member of A is in A+, since any number actually enumerated into A will be seen by M to have been so. Finally, for the same reason, no member of B is in A+, because M can see that they are enumerated into B by a (standard) stage, when they have not been enumerated into A. Thus, A+ is a computable separation of A and B, a contradiction. QED

Essentially this argument also establishes the version of Tennenbaum's theorem mentioned by Anonymous, that there is no computable nonstandard model of PA. But actually, Tennenbaum proved a stronger result, showing that neither plus nor times individually is computable in a nonstandard model of PA. And this takes a somewhat more subtle argument.

share|improve this answer
    
I agree that if we could compute the function i, that would be enough to prove that there is no computable model of ZFC. However, I still don't buy the argument that i is computable. I have the same problem as I did with the previous answer. In order to compute i(n+1) from i(n), we must find the unique number m such that (the number corresponding to) the set {i(n),{i(n),m}} is in s. If the function that, given input i(n),m, returned the number corresponding to the ordered pair (i(n),m) then we would be in great shape, but I don't see any reason why this function should be computable. –  David Diamondstone Jan 20 '10 at 18:29
    
But you have the number N, of which the E predecessors are precisely what M thinks of as the natural numbers, and this makes things easier. To get even easier, don't use the usual pairing function, but just think of s as the set of pairs of adjacent natural numbers. With this pairing function, x E N, there is precisely one y such that {x,y} E s. That is, there is precisely one y such that there is w E s with x E w and y E w. This y is i(x). But you can do essentially the same thing with the usual pairing function. –  Joel David Hamkins Jan 20 '10 at 18:42
    
Well, if you use that easier pairing function, you also have to exclude the already-used value below x. So I should say, precisely one y not-yet-used for which... –  Joel David Hamkins Jan 20 '10 at 18:43
    
Basically, the function i is computable because you can go and search for the unique element of s that encodes the pair (i(n),y). You will eventually find it, since it is really there. So look at all w for which w E s, and then look at all g,h E w, etc. unwrapping the usual pairing code. –  Joel David Hamkins Jan 20 '10 at 18:46
    
Gregory Igusa points out why the ordered pairing function is computable (actually, "computable enough"): pretend we have a set A of all two element sets. Then, given n and m, we can compute the ordered pair (n,m) by first finding a set y in A containing both n and m, and then finding a set x in A containing both n and y. Then x is the ordered pair (n,m). Of course, A is not actually a set, so this function isn't quite computable, but given any set X, there is a set of all two-element subsets of X, which lets you compute the ordered pair of any two elements of X, which is good enough. –  David Diamondstone Jan 20 '10 at 18:57
show 3 more comments

This can also be done using Godel-Roesser instead of Tennebaum. Suppose M is a model of ZFC. There is an element $a$ of that M believes is the set of Godel codes for the sentences true of the integers of M. Of course $a$ may contain nonstandard Godel codes, but if we let T be the set of standard sentences with Godel codes in $a$, then T will be a complete consistent extension of Peano Arithmetic. If M is computable, then T would be computable, but there are no computable complete consistent extensions of Peano Arithmetic.

Of course the appeal to Godel-Roesser just hides Joel's argument about recursive inseparable r.e. sets.

share|improve this answer
    
Good to see that you and your evil twin have merged ... –  Simon Thomas May 6 '10 at 0:48
add comment

No, it cannot be computable. It's a theorem of Tennenbaum from the 50's that there is no computable, non-standard model of Peano arithmetic. If there were a computable model of ZFC, then it would give a computable, non-standard model of Peano arithmetic. Specifically, it would contain some non-standard model for PA, specified by a set of elements and two relations, and the computability of the model of ZFC would imply computability there. (If, say, you want the sum of elements a and b in the model of PA, search by brute force for an element c of the model such that (a,b,c) is in the sum relation. This may be terribly slow, but it will eventually terminate.)

Edit: That's a good point about the computability of (a,b,c), and I'm not sure how to compute that. Fortunately, it turns out not to be needed here. Specifically, if we define (a,b,c) = ((a,b),c) and define (u,v) = {{u}, {u,v}}, then even though it's not clear whether you can computably produce (a,b,c) given a, b, and c, given something you know a priori is a triple, you can try to check whether it comes from a,b,c by finding appropriate elements. (In the simpler case of pairs, to check whether w = (u,v) given that it is some ordered pair, we just need to find x and y such that both are in w, u is in x, and u and v are in y.) Now we just do major brute force: not only searching over all possible choices of c, but also over the auxiliary elements that would establish that (a,b,c) is in the relation. I hope there's a nicer way to do this, but I think it works.

share|improve this answer
    
Doesn't that require that, given a, b, and c, you have a way of finding the triple (a,b,c) in order to determine whether it is in the sum relation? If the function that takes you from a, b, c to the ordered triple (a,b,c) is not computable, I don't see how this gives a contradiction. In other words, I don't see how you can conclude from the mere fact that you have a computable model of ZFC that you have a computable nonstandard model of PA. –  David Diamondstone Jan 20 '10 at 17:56
    
I explain this issue in my answer. You do find a computable model as Anonymous says. –  Joel David Hamkins Jan 20 '10 at 18:10
    
What makes the model of PA necessarily non-standard? –  David Feldman Jan 14 '11 at 10:05
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.