# Is there a computable model of ZFC?

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}.

-

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.

-
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. – skeptical scientist 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. – skeptical scientist Jan 20 '10 at 18:57

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.

-
Good to see that you and your evil twin have merged ... – Simon Thomas May 6 '10 at 0:48

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.

-
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. – skeptical scientist 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
@David Feldman: a standard model would have to include subsets of $\omega$ such as $0'$, which are not computable. – Carl Mummert Nov 30 '15 at 12:46