In an article named 'Skolem’s Paradox' on SEP, there is a description of the Paradox I'm asking about here:

Skolem's Paradox arises when we notice that the standard axioms of set theory can themselves be formulated as (countable) collection of first-order sentences. If these axioms have a model at all, therefore, then the Löwenheim-Skolem theorem ensures that they have a model with a countable domain. But this seems quite puzzling. How can the very axioms which prove Cantor's theorem on the existence of uncountable sets be satisfied by a model which is itself only countable? How can a countable model satisfy the first-order sentence which “says that” there are uncountably many things?

I wonder if anyone really has constructed a countable model of set theory that falls in the trap of the Skolem's Paradox. That is, they constructed a countable model of the usual first-order set theory, and proved that in that very model, there is an element x such that the existence of an injective function from x to the set of natural numbers N in the model can be denied in that theory (and hence, x is uncountable). Of course, how they verified that the x above is really an uncountable 'set' seen from the theory/model may be done differently (, different from the way I describe above).

Some may suggest that one can use the method in the proof of the skolem theorem to generate such a model. But that method is not really 'constructive' enough-- we don't know how the elements in the model behave. So, in the spirit of being 'constructive', such a model is more preferred:

  1. its universe is computably enumerable (or at least decidable);
  2. the relations (as sets) in this model are also computably enumerable (or at least decidable);
  3. the collection of the relations in this model is also computably enumerable (or at least decidable).

If all 3 of the above conditions can't be met in one single model, then a model satisfying as many of them as possible is preferred.

  • I don't think it works like that. If S is a statement in set theory that we normally interpret as saying there is an uncountable set, then S will be satisfied by the countable model; there will be an element x in the model that makes S true. But if we are using the countable model then we can no longer interpret S as saying there is an uncountable set. S loses that interpretation because we are not using the standard model.
    – causative
    Sep 20, 2022 at 12:51
  • @causative Of course it would be weird if the model turns out to 'have' the usual 'interpretation'. But the sentences can "have" the usual 'interpretation'.
    – Michael
    Sep 20, 2022 at 13:17
  • The model is how you interpret the sentences in the theory. The model is what the variables named in the sentences refer to. If you change the model, you change the interpretation.
    – causative
    Sep 20, 2022 at 16:36
  • 5
    Skolem's paradox is not a real antimony like Russell's paradox, it simply shows that countability and uncountability are not absolute properties in first-order logic and Skolem used this argument as one of his many other arguments to critique set theory as a proper and categorical math foundation. To constructive a model as you wished one usually need its nice properties such as pointwise (countable) definability and transitivity. Countable set models are very useful in forcing extensions and you may refer to Joel Hamkins et al's paper "Pointwise Definable Models of Set Theory"... Sep 21, 2022 at 6:08
  • 1
    @JustSomeOldMan see van Dalen, Dirk; Ebbinghaus, Heinz-Dieter (Jun 2000). "Zermelo and the Skolem Paradox". The Bulletin of Symbolic Logic. 6 (2): 145–161: I believed that it was so clear that axiomatisation in terms of sets was not a satisfactory ultimate foundation of mathematics that mathematicians would, for the most part, not be very much concerned with it. But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come for a critique... Sep 22, 2022 at 2:59

1 Answer 1


Countable models of ZFC are extremely far away from being computable. To see this, consider any Turing degree whose existence is provable in ZFC, by which I mean that we have a ZFC definition of a representative of that Turing degree. For example, the Halting problem is one (but there are far, far more complicated ones).

Our countable model of ZFC (which we externally view as being coded over natural numbers) contains an element it considers the natural numbers, and it contains an element it considers to be the representative mentioned above (eg the Halting problem). If we can enumerate the elements of the model, and decide the membership-predicate of the model, these two elements let us decide which natural numbers belong to our non-computable set.

So that attempt to get a more hands-on understanding of how a countable model can consider stuff to uncountable is doomed to failure. However, you can look at weaker theories than ZFC. One example would be the subsystem RCA_0 of second order arithmetic. This system is strong enough to state and prove Cantor's diagonalization argument for the real numbers. However, taking all natural numbers as first-order part together with all computable sets of natural numbers as second-order part gives us a concrete countable model of RCA_0.

What is going on here that is that what this model tells us when it says "The reals are uncountable." is from our external perspective just "There is no computable enumeration of all computable real numbers.".

  • +1, but I think it's important to note that countable models of ZFC don't need to be that far away from computable: since ZFC is itself a computable theory, it has countable models which are low (in particular, much simpler than the halting problem). Of course this doesn't contradict anything in your answer, I just think it's worth pointing out since it's a common stumbling block. Things do get worse if we look at "reasonably correct" models - e.g. no $\omega$-model is hyperarithmetic, and well-founded models are even worse - but if all we want is a model of ZFC it's not that bad. Sep 21, 2022 at 17:06
  • To the OP, the crucial point re: the apparent tension between the second paragraph of this answer vs. my above comment is that (for M a countable model of ZFC) while (the standard part of) M's halting problem might not actually be the real halting problem, it will have to be non-computable in reality. Sep 21, 2022 at 17:11

Not the answer you're looking for? Browse other questions tagged .