Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am wondering if there exists a model of set theory (KPU or ZFC) that has decidable theory?


share|cite|improve this question
Such a model will be able to solve the halting problem. – Yuval Filmus Sep 15 '12 at 14:51
what do you mean by a model having a decidable theorem? – Levon Haykazyan Sep 15 '12 at 14:51
I mean , is there a model of set theory for which we can design an algorithm to decide all the first order formula sastified in it .... Thanks , obviously I am not talking here about all theorem of the structure ... – Dehn Sep 15 '12 at 15:09
Do you have the references of the work you mentionned of David Harris ? Please... – Dehn Sep 15 '12 at 16:28
@Dehn: I believe that Peter Smith is talking about David Harris's answer below. – arjafi Sep 15 '12 at 17:38

Any model of set theory includes the full true theory of arithmetic. Even very weak theories of arithmetic, let alone the full True Arithmetic, are undecidable.

share|cite|improve this answer
That, and we don't even know for sure if there exists any model of ZFC. :) – tomasz Sep 15 '12 at 15:17
Any reasonable model of set theory, anyway... (Even models of finite set theory can be undecidable – ZFC minus Infinity and Peano arithmetic are biinterpretable, for example.) – Zhen Lin Sep 15 '12 at 15:24
An arbitrary model could have nonstandard natural numbers and so the set of arithmetical formulas that is true in that model could be very different than the true theory of arithmetic. Naively, that set could even be computable. So it is not enough to note that the set of true arithmetic sentences is not computable. ... – Carl Mummert Sep 15 '12 at 20:03
However, the answer can be remedied via Tennenbaum's theorem that no nonstandard model of PA has a computable elementary diagram (neither addition nor multiplication can be computable). Because the theory of each model of ZFC computes the theory of a model of PA, if the model of ZFC is not an $\omega$-model this shows its theory cannot be computable. Or you could use the fact that the theory of the model of ZFC computes a completion of PA, and no such extension is computable (even if it is nonstandard). But it takes more than the uncomputablity of true arithmetic, in any case. – Carl Mummert Sep 15 '12 at 20:06

The viewpoint that is usually taken in the literature is to look at extensions of the original theory rather than models of it. A theory is said to be essentially incomplete if it has no decidable complete consistent extension. Essential incompleteness implies, in particular, that the theory cannot have a model whose elementary diagram is decidable.

A corollary of the incompleteness theorems is that many effective theories are essentially incomplete. For example, Peano arithmetic and ZFC are both essentially incomplete, so they cannot have models whose elementary diagrams are decidable.

On the other hand, the theory of groups is incomplete, because it cannot prove or disprove $(\exists x)(\exists y)(x \not = y)$, but it can be made complete by adding the axiom $(\forall x)(\forall y)(x = y)$, and the resulting theory (which is categorical) has a model whose elementary diagram is decidable.

share|cite|improve this answer

Your Answer


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.