nLab Skolem's paradox

Idea

According to the Löwenheim-Skolem theorem, for a first-order theory with a countable alphabet if there is an infinite model, then there is a countable model. Let us consider the language of some form of set theory and a model satisfying the axiom of infinity. Then Cantor’s diagonal argument can be carried out internally within the model and provides internally uncountable “sets” in the countable model.

The resolution of this apparent paradox is that, while this conclusion is true internally, it is not true externally: namely any two infinite sets are countable externally in that model, hence there is a $1$–$1$ function between any two of them including for a model of some uncountable set $X$ and of its power set $P(X)$. However, that function (or its graph) is not in the model! One can enlarge the model by adding the function (and more). But this extended model will necessary have $P(X)$ uncountable externally and there is no $1$–$1$ function from $X$ to $P(X)$ externally any more.

Remark

The paradox highlights a general feature of first-order logic namely that it cannot discern between countable and uncountable models. In fact, Skolem cast set theory as a first-order theory precisely to display the deficiency of axiomatizations of the uncountable, a move that was not accepted by Zermelo.

It is somewhat ironic that Skolem effectively helped consolidating what is today called Zermelo-Fraenkel set theory and inaugurating first-order model theory in what was basically an attempt to discredit set-theoretic foundations and the axiomatic method in general.

Related entries

• Lindström's theorem

• second-order logic

References

• Thoralf Skolem, Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre, Mathematikerkongressen i Helsingfor 4-7 Juli 1922. English transl. pp.290-301 of van Heijenoort (ed.), From Frege to Gödel , Harvard UP 1967.

• D. van Dalen, H.-D. Ebbinghaus, Zermelo and the Skolem paradox , Bull. Symbolic Logic 6 (2000) pp.145–161.

• C. McCarty, N. Tennant, Skolem’s Paradox and Constructivism , J. Phil. Logic 16 (1987) pp.165-202. (draft)