Skolem’s paradox
#notes on this
As a consequence of Cantor’s theorem, there exists a set of uncountable cardinality
Löwenheim-Skolem theorem: if a first-order theory has an infinite model, then it has a countable model
Seems to be a paradox!
Let TT denote some standard axiomatization of set theory
Assuming TT has a model, Löwenheim-Skolem theorem asserts existence of some countable model M\mathbf M for TT
Let Ω(x)\Omega(x) be the assertion, expressed using first-order logic, that xx is uncountable
By Cantor’s theorem we have that Tm Ω(m)T \vdash \exists m\ \Omega(m) and so there is a mMm \in \mathbf M where MΩ(m)\mathbf M \vDash \Omega(m)
But since M\mathbf M is countable then there are only countably many nMn \in \mathbf M such that nmn \in m!
Contradiction?
Resolution
When evaluating the semantics of a first-order sentence such as Ω(m)\Omega(m), we must recognize that the meaning of first-order language is relative to the model in which we interpret it
For instance, \forall- and \exists- bindings quantify exactly over the domain of M\mathbf M rather than any other domain that we had in mind. Likewise, the inclusion relation \in need not represent “genuine” inclusion but need only be some binary relation between elements of M\mathbf M which satisfies the appropriate properties
Though we have some intention for what first-order sentences “ought” to mean, M\mathbf M has no mandate to respect that intention.
As humans, we have a certain sense and intuition around what it means for a set to be uncountable. Guided by that sense and intuition, we write the definition of Ω\Omega as a first-order expression of uncountability
But this definition was predicated on a certain understanding of first-order logic which M\mathbf M need not follow
As such, the fact that MΩ(m)\mathbf M \vDash \Omega(m) may have a meaning far differing from mm being uncountable.
(For what it’s worth, I think the article does a better job explaining this than me. Go read it! §2.2)
Details on how M\mathbf M has “strange interpretations”
Transitive models
A model X\mathbf X is called transitive if (1) every member of X\mathbf X is a set and any every member of a member of X\mathbf X is also a member of X\mathbf X; and (2) the relation \in in X\mathbf X is the same as \in in the language being used to describe X\mathbf X
Stronger, if X\mathbf X is a transitive model and if f,mXf, m \in \mathbf X then Xf:ωm is bijective"\mathbf X \vDash ``f : \omega \to m \text{ is bijective}" if and only if ff is a bijection in the metalanguage
Conceptually, in a transitive model the interpretations of membership and bijectivity are “correct” (relative to the metalanguage)
An example of how a transitive model can “misinterpret” axioms
Take Z\mathbf Z a transitive model of ZFC
Powerset axiom is x y zzxzy\forall x\ \exists y\ \forall z \mid z \subseteq x \leftrightarrow z \in y
But \forall only quantifies over members of Z\mathbf Z
So for a given xx its powerset yy only contains sets zz where zxzZz \subseteq x \land z \in \mathbf Z
If Z\mathbf Z is countable, then xx contains at most a countable number of sets
(In §2.4¶4 they say that the source Resnik 1966 follows “this phenomenon through the case of the real numbers”. Seems interesting! #onwards)
In non-transitive models we get even more ways to misinterpret!
Assuming is M\mathbf M is transitive, where can it differ from the metalanguage for Skolem’s paradox to arise?
M\mathbf M can differ on \exists
The form of Ω\Omega is Ω(m)=¬f:ωm bijective\Omega(m) = \neg \exists f : \omega \to m \text{ bijective}
Since they agree on “bijective”, then they must differ on "\exists"
This is exactly the case. Since M\mathbf M is countable, then m={nMnm}m = \{ n \mid \mathbf M \vDash n \in m \} is countable, so there exists at least one bijection f~:ωm\tilde f : \omega \to m. But any such bijection is not a member of M\mathbf M, so M\mathbf M considers mm to be uncountable. That is, whereas \exists in the metalanguage can “see” f~\tilde f, \exists in M\mathbf M cannot.
Skolem’s paradox is intimately tied to first-order logic
Does not arise in second-order settings
Standard proofs fail in constructivist settings
Personally, it seems that this situation suggests that the semantics of first-order logic are not strong enough. If we are confident that we know what uncountability means, and we are confident that Ω\Omega is a proper expression of uncountability in first-order logic, then it seems that any appropriately-faithful interpretation of Ω\Omega would demand an uncountable model.
The source also includes some discussion of philosophical consequences of Skolem’s paradox (§3) which I chose to skip/skim for now (#onwards?)



Referenced by: