Skolem's Paradox (First Order Logic)

[Matterwave]

TL;DR

Trying to talk through the resolution of Skolems paradox (topic in First Order Logic)

I'm reading Leary and Kristiansen "Mathematical Logic".

This is problem 8 in section 3.4.1. exercise 8. It's not homework since I don't have homework anymore. But it was an interesting problem to think through. Not sure if I got it right though.

I'm paraphrasing the book since I don't want to literally copy paste, but let me know if I paraphrase in a way that introduces errors.

So basically, the following are theorems of Zermelo Frankel set theory:

1. There is a countably infinite set.
2. If a set $a$ exists then the set of all subsets of $a$ exists (we'll call it $\mathcal{P}(a)$).
3. If $a$ is countably infinite then $\mathcal{P}(a)$ is uncountable (Cantor's theorem).

By the Downward Lowenheim-Skolem Theorem, in a countable language $\mathcal{L}$, if $\mathfrak{B}$ is an $\mathcal{L}$-structure, then it has a countable elementary substructure.

This means there is a model of ZF set theory which is countable. Let's call it $\mathfrak{A}$ with universe $A$ where all 3 of the above sentences are true, and yet the model itself is countable. So let's say $a=\mathbb{N}$ (it exists by sentence 1), then $\mathcal{P}(\mathbb{N})$ exists (via sentence 2) in $A$. Every element of $\mathcal{P}(\mathbb{N})$ must also exist in $A$ or else the relation symbol $\in^{\mathfrak{A}}$ wouldn't work.

So how is it not a contradiction that $A$ is countable and yet every member of $\mathcal{P}(\mathbb{N})$ (which is itself an uncountable set by sentence 3) is in $A$?

The resolution as I understand it (this is the super sketchy part lol):

A few preliminaries

• The definition of an uncountable set is "there exists no bijective map from $\mathbb{N}$ to the set" (and countable is there does exist such a map).
• A bijective map is a map that is injective and surjective.
• An injective map from $\mathbb{N}$ to $\mathcal{P}(\mathbb{N})$ is simple in both $\mathfrak{A}$ and $\mathfrak{B}$ by just using the map $f(x) = x$.
• Because injection is easy, sentence 3 basically says there can't be a surjection $\mathbb{N}\rightarrow\mathcal{P}(\mathbb{N})$ on either $\mathfrak{A}$ or $\mathfrak{B}$.

So I guess the actual resolution is -- the definition of a map in $\mathfrak{A}$ and $\mathfrak{B}$ are different. A map is a tuple of input output pairs: $(x,y)$ represents the map that takes element $x$ and maps it to $y$ and this map must be encodable (as a set) into $A$ if we want to talk about "there exists a bijective map in $A$". Similarly, it has to be encodable into $B$ if we are talking "there exists a bijective map in $B$".

But the sets of $B$ and $A$ are obviously very different ($B$ is uncountably infinite while $A$ is only countably infinite).

Thus, even though $\mathcal{P}(\mathbb{N})^\mathfrak{A}$ (the power set of N in $A$) is "countably infinite" when "viewed from the outside", from "inside $\mathfrak{A}$" there is no surjective map $\mathbb{N}^\mathfrak{A}\rightarrow\mathcal{P}(\mathbb{N})^\mathfrak{A}$ since one can not encode $(x,y)$ pairs such that the second slots in those tuples hits every element of $\mathcal{P}(\mathbb{N})^\mathfrak{A}$. In other words, inside $\mathfrak{A}$ the power set is uncountable (because no such bijective function exists within $\mathfrak{A}$) even though if we were allowed to use maps in $\mathfrak{B}$ we could actually construct a bijection between $\mathbb{N}^\mathfrak{A}$ and $\mathcal{P}(\mathbb{N})^\mathfrak{A}$.

This kind of breaks my mind...

 

[Hornbein]

So how is it not a contradiction that N is countable and yet every member of P(N) (which is itself an uncountable set by sentence 3) is in N?

The elements of N are numbers while the elements of P(N) are sets. None of the elements of P(N) are elements of N. The intersection of N and P(N) is the empty set.

 

[Matterwave]

The elements of N are numbers while the elements of P(N) are sets.

This one trips me up all the time, but the elements of N must also be sets because everything in set theory are sets.

The natural numbers are just encodings of sets, e.g. (Von Neumann's):

$0 := \emptyset$
$1 := \{\emptyset\}$
$2 := \{\emptyset, \{\emptyset\}\}$
...

This is not the only possible encoding.

None of the elements of P(N) are elements of N.

This depends on the encoding. In the Von Neumann encoding, this is false. There are encodings where this is true.

The intersection of N and P(N) is the empty set.

See above comments. Try it out with the Von Neumann encoding.

However, even if we grant your statements, the cardinality of sets has to do with bijections and not intersections so I don't see the relevance.

 

[Matterwave]

there is no surjective map $\mathbb{N}^\mathfrak{A}\rightarrow\mathcal{P}(\mathbb{N})^\mathfrak{A}$ since one can not encode $(x,y)$ pairs such that the second slots in those tuples hits every element of $\mathcal{P}(\mathbb{N})^\mathfrak{A}$.

I think this is the weakest point of my argument. I have not shown this or proved it. It does feel like it has to be so in order to resolve the paradox and I can kind of "see in my head" why it might be so, but I have no proof.

My guess is that the elements of $\mathcal{P}(\mathbb{N})^\mathfrak{A}$ are for some reason not all in $A$ (even though the set is). But it's just a guess.

 

[Matterwave]

My guess is that the elements of $\mathcal{P}(\mathbb{N})^\mathfrak{A}$ are for some reason not all in $A$ (even though the set is). But it's just a guess.

On thinking about it more, I think this is wrong.

The thing I wasn't able to picture in my head is truly that $f$ must be a set in $A$ (or $B$ if we are talking about the usual model). In other words, $f$ is an element of $A$.

Hence, by Cantor's theorem there is no element of $A$ that represents such a bijective map. But in $B$ there is such an element. Since $A$ and $B$ are two different universes, there is no contradiction.

 

[WWGD]

Is the LS constructive , in the sense of telling you how to construct lower- cardinality models to satisfy a set satisfied by models of higher cardinality?

 

[Matterwave]

Is the LS constructive , in the sense of telling you how to construct lower- cardinality models to satisfy a set satisfied by models of higher cardinality?

Yes. You take a countable subset of the universe and you take its "Skolem completion" (the main content of the proof) and you get a countable elementary substructure.

 

[Demystifier]

That's one of many apparent paradoxes of first-order logic. In first-order logic you are not allowed to say things such as "there is a set ..." or "all sets ...", so you just can't specify what you really want to specify. In particular, the notion of a power set means "all subsets of a set", but you cannot even say that with first-order logic. So how do you talk about power set? Not really by talking about all subsets, but by talking about some explicitly specified subsets, which represent a model of a power set. In this way a model of a power set does not need to be a true power set, it is only something that satisfies all axioms of a power set, and axioms in first-order logic do not define objects completely. In this way, instead of talking about the power set of natural numbers, you really talk about a model of the power set of natural numbers, which may not have all the properties of the true power set of natural numbers. In particular, this model of the power set of natural numbers may in fact be countable, even though you cannot count it inside the model, so from inside it looks uncountable.

But how can we ever step outside of the model and see what it really is as seen from the outside? Clearly, we cannot do that with first-order logic. But we, the human mathematicians, are not restricted by first-order logic. We can use our intuition to see things which are not formalized by first-order logic. (If we want, we can even formalize it with higher second-order logic.) The first-order logic is just a formal tool that we may use, but this tool has its limitations, so to see the truth sometimes we have to use other tools as well.

 

[Matterwave]

That's one of many apparent paradoxes of first-order logic. In first-order logic you are not allowed to say things such as "there is a set ..." or "all sets ...", so you just can't specify what you really want to specify.

The "things" in set theory are sets. The elements of the universe are sets. And as such, when you say $\forall x\phi(x)$, the x ranges over sets of the universe.

In particular, the notion of a power set means "all subsets of a set", but you cannot even say that with first-order logic.

Pretty sure I can: $\forall x \exists y: \forall z (z\subseteq x \rightarrow z\in y)$ where I define $\subseteq$ as: $a\subseteq x :\leftrightarrow \forall y(y\in a\rightarrow y\in x)$. In the first sentence, $y$ is the power set of $x$.

What you can't do is quantify over subsets of $A$ (or $A^n$), that would be second order logic, but I don't need to quantify over subsets, I just need to quantify over elements.

So how do you talk about power set? Not really by talking about all subsets, but by talking about some explicitly specified subsets, which represent a model of a power set. In this way a model of a power set does not need to be a true power set, it is only something that satisfies all axioms of a power set, and axioms in first-order logic do not define objects completely.

Don't think I agree with this, see my comments above.

Also, a "model" is a bit of a reserved name in FoL for a structure for which some formulae/sentences (axioms) are satisfied -- $\mathfrak{A}\models \Sigma$ means $\mathfrak{A}$ is a model of $\Sigma$.

But I will say, I know almost nothing of second order logic. So I very much could be wrong, and I would take my own statements with large grains of salt.

In this way, instead of talking about the power set of natural numbers, you really talk about a model of the power set of natural numbers, which may not have all the properties of the true power set of natural numbers. In particular, this model of the power set of natural numbers may in fact be countable, even though you cannot count it inside the model, so from inside it looks uncountable.

Very roughly speaking, I think this was my original guess at the resolution to the paradox (mentioned in post #4), but I think actually post #5 should be the more correct argument. The fault seems to me to lie in what is the definition of a bijection in each model. But again, I could be wrong.

But how can we ever step outside of the model and see what it really is as seen from the outside? Clearly, we cannot do that with first-order logic. But we, the human mathematicians, are not restricted by first-order logic. We can use our intuition to see things which are not formalized by first-order logic. (If we want, we can even formalize it with higher second-order logic.) The first-order logic is just a formal tool that we may use, but this tool has its limitations, so to see the truth sometimes we have to use other tools as well.

I think this paradox should be resolvable in first order logic since the text I am reading (Leary) is a text in first order logic and makes no mention of second order logic. This paradox is an exercise, so it would be a little unfair if its resolution required second order logic.

 

[gentzen]

But we, the human mathematicians, are not restricted by first-order logic. We can use our intuition to see things which are not formalized by first-order logic. (If we want, we can even formalize it with higher second-order logic.)

https://scottaaronson.blog/?p=4974#comment-1863531

Let me defend the “standard semantics” or “full semantics” of second-order logic. […]

The “full semantics” allows “last word” specifications, and the second-order induction axiom is a prime example of a “last word” specification: The language might initially only contain successor and neither addition nor multiplication. But as soon as you define addition, multiplication, exponentiation, or any other operation, the induction axiom will immediately apply to any property you can define using such newly defined operations. And if you define a powerful set theory with unbelievably strong inaccessible cardinal axioms, the induction axiom will also immediately apply to any property you can define using such a powerful set theory.

On the other hand, the danger with “last word” specifications is that there can be only one “last word”. As soon as there happen to be two (or more) “last words” contradicting each other, there will be a problem (if it is unclear which “last word” should “win”).

 

[gentzen]

https://scottaaronson.blog/?p=4045#comment-1798127

On the other hand, maybe I should use your remark about arithmetical consequences as an opportunity to defend the use of second order arithmetic for reverse mathematics. Simply put, first order arithmetic is not expressive enough to state theorems like the model existence theorem or Ramsey’s theorems. While P vs. NP is equivalent to a Π_2^0 sentence, separation principles like Kőnig’s lemma must talk about (the existence of) classes, and hence are not equivalent to arithmetical sentences. And if a theorem is not equivalent to some arithmetical sentence, then mathematicians are normally interested in the theorem itself, and not just in its arithmetical consequences.

Note however that my comment talks about arithmetic, not set theory. First order set theory would be expressive enough, so it is the restriction to arithmetic which requires second order logic here to overcome limitations of expressiveness. And Henkin semantics is good enough here (and is what is actually used), no need to worry about “standard semantics” or “full semantics”.

 

[Demystifier]

To put my point in a stronger form, let me make it more compact, without specifying details in which someone could find inessential errors.
There is no Skolem paradox in second-order logic with full semantics.

 

[Demystifier]

Let me better explain how I see the Skolem "paradox", by emphasizing the logical order of the whole construction.

1. Write down the axioms of ZFC, in first-order logic.

2. Give a definition of the real numbers in the language of set theory. For example, define natural numbers, integers, rationals, and then real numbers as Dedekind cuts of rationals.

3. Prove within ZFC that the set $\mathbb{R}$ of reals so defined is uncountable.

So far everything is defined and proved syntactically, without any semantics, i.e., without a model. In particular, the uncountability of $\mathbb{R}$ is defined and proved internally, within ZFC.

4. Now consider a countable model $M$ of ZFC. But to see that a model is countable, one must step out from ZFC axioms and look at it externally. So the external countability is not the same thing as internal countability. The external countability, in a model, is a true countability, while the internal countability is only a formal syntactic countability.

5. The definition of the real numbers is now interpreted in $M$, producing the set denoted by $\mathbb{R}^M$. From outside, $\mathbb{R}^M$ is countable, because $M$ has only countably many objects. Yet $M$ satisfies the formal syntactic theorem that $\mathbb{R}^M$ is uncountable. This looks like a paradox because it seems that $\mathbb{R}^M$ is both countable and uncountable. Yet there is no true paradox, because we are dealing with two different notions of "countability". The $\mathbb{R}^M$ is "countable" in one sense and "uncountable" in another.

More philosophically, the set $\mathbb{R}^M$ is truly countable, while its "uncountability" is only a formal uncountability, not a true uncountability. The formal provability and the truth are not the same. To see the truth one must look at the specific model, but this determination of truth cannot be fully formalized, it requires also some intuition.

 

[Matterwave]

The step I'm not sure needs to be made is the step outside of first order logic into second order logic.

Already in first order logic you have both the standard model of ZF, namely $\mathfrak{B}$ in my post and also the countable model $\mathfrak{A}$. It feels like at least the spirit of your argument goes through if you just consider those two? Like what is $\mathbb{R}^\mathfrak{A}$ if we look at it "from $\mathfrak{B}$"?

 

[Demystifier]

The step I'm not sure needs to be made is the step outside of first order logic into second order logic.

Already in first order logic you have both the standard model of ZF, namely $\mathfrak{B}$ in my post and also the countable model $\mathfrak{A}$. It feels like at least the spirit of your argument goes through if you just consider those two? Like what is $\mathbb{R}^\mathfrak{A}$ if we look at it "from $\mathfrak{B}$"?

In this case $\mathbb{R}^\mathfrak{A}$ looks countable.

Second order logic is of course not necessary, but it has its advantages and disadvantages. Pure logicians more often emphasize its disadvantages, that's why they usually work with first order logic. But ordinary mathematicians use intuition (rather than formal logic and set theory) that in spirit is more similar to second-order logic than to the first-order one. So if one wants to formalize how most mathematicians really think, then second-order logic is a much better choice.

 

[Matterwave]

But ordinary mathematicians use intuition (rather than formal logic and set theory) that in spirit is more similar to second-order logic than to the first-order one. So if one wants to formalize how most mathematicians really think, then second-order logic is a much better choice.

Ok, after I get through the Gödel incompleteness theorems in FoL (assuming I can lol) I will take a look into SoL.

 

[Demystifier]

Ok, after I get through the Gödel incompleteness theorems in FoL (assuming I can lol) I will take a look into SoL.

What kind of logic is lol?
Note that Godel incompleteness theorems are valid in both FoL and SoL. Which should not be confused with Godel completeness theorem, which refers only to FoL.

 

[Demystifier]

Since @Matterwave and @gentzen who write here are also interested in quantum foundations, let me give one metaphorical analogy. Theorems derived from a first-order axiomatic theory are somewhat like shut-up-and-calculate results in QM. Different models of the axiomatic theory are like different interpretations of QM. The standard Copenhagen interpretation of QM is analogous to the standard/intended model of the first-order axiomatic theory. The Skolem paradox is somewhat analogous to the result that QM is local due to the no-signaling theorem (derived from QM axioms) and nonlocal in some interpretations (typically, realist interpretations). To remove the ambiguities of quantum interpretations, perhaps we would need to formulate QM differently from the very start, by using some general principle analogous to second-order logic. It's not clear what this principle could be (but it's definitely not second quantization, if you ask). My conjecture is that it could be some principle that allows a formalization of metaphysical/ontological statements, which usual physical theories do not allow, in analogy with the fact that first-order theories do not allow quantification over sets. Someone may object that such a theory would not be physics, just like Quine objected that second-order logic is not logic (but set theory in disguise).

 

[gentzen]

Ok, after I get through the Gödel incompleteness theorems in FoL (assuming I can lol) I will take a look into SoL.

Well, in the typical mathematical logic textbook, you have to read many pages before you come to the incompleteness theorems. So maybe they should remain mysterious for the uninitialized, in order not to spoil the motivation to work through all those pages.

But in the end, it boils down to the fact that a proof must have a finite number of steps, in order to be a valid proof. And the formalization of „finite number“ is given by the natural numbers. Turing‘s proof of the undecidability of the halting problem (and the Entscheidungsproblem) shows that „finite number of steps“ cannot be formalized beyond that reduction to the natural numbers. Hence, the „natural numbers“ cannot be „perfectly“ formalized.

Note that Godel incompleteness theorems are valid in both FoL and SoL. Which should not be confused with Godel completeness theorem, which refers only to FoL.

The second order induction axiom formalizes the natural numbers in SoL with „full semantics“. And for „Henkin semantics“, the completeness theorem also applies to SoL. But I agree that the completeness theorem establishes that „syntactic provability“ and „semantic validity“ are equivalent for „Henkin semantics“, and hence gives the incompleteness theorems their force and mystery.

With respect to „full semantics“ vs „Henkin semantics“, this difference already occurs in simpler settings than SoL. I vividly remember the discussions (and confusion) about the meaning of pairs/cartesian product we had while reading and discussing
https://act-munich.github.io/

2025-09-25	Roy L. Crole, Categories for Types, Chapter 4: "Functional Type Theory".
2025-08-14	Roy L. Crole, Categories for Types, Chapter 4: "Functional Type Theory".
2025-07-10	Roy L. Crole, Categories for Types, Chapter 4: "Functional Type Theory".
2025-06-12	Roy L. Crole, Categories for Types, Chapter 3: "Algebraic Type Theory".
2025-05-08	Roy L. Crole, Categories for Types, Chapter 3: "Algebraic Type Theory".
2025-04-10	Roy L. Crole, Categories for Types, Chapter 3: "Algebraic Type Theory".

Because neither of you wants to dive into this just for appreciating the difference between „full semantics“ vs „Henkin semantics“, let me mention that the simplest instance of this difference already occurs with the formalization of equality. If the „equality sign“ is not part of your FoL, but gets emulated by an „equality predicate“ together with a suitable axiom scheme, then a model is not required to implement that „equality predicate“ by actual equality in the model. „Henkin semantics“ accepts this as a perfectly valid model, while „full semantics“ insists on the intuitive meaning of the „equality sign“.

 

[gentzen]

Very roughly speaking, I think this was my original guess at the resolution to the paradox (mentioned in post #4), but I think actually post #5 should be the more correct argument. The fault seems to me to lie in what is the definition of a bijection in each model. But again, I could be wrong.

Both contain a part of the explanation, and you will certainly work this out and understand it in the end.

Also, a "model" is a bit of a reserved name in FoL for a structure for which some formulae/sentences (axioms) are satisfied -- A⊨Σ means A is a model of Σ.

But I will say, I know almost nothing of second order logic.

You are spot on by focusing on the meaning of „model“ in FoL.

On the one hand, there is a large degree of freedom in what one allows as a „model“. On the other hand, one should provide enough freedom for the allowed „models“ to make the completeness theorem true. That is the problem with „full semantics“ in SoL, namely that the allowed models are „too restricted“, and hence the completeness theorem no longer holds.

On the other hand, this „freedom“ which allows the completeness theorem to hold is also what is responsible for Skolem‘s paradox. I guess this freedom was also the initial disagreement between Frege and Hilbert. Frege basically insisted on „full semantics“, and also tried to explain the difference to „Henkin semantics“ (basically Hilbert‘s formalist position). Hilbert on the other hand wanted to have „Henkin semantics“, because he wanted to secure „Cantor‘s paradise“ by allowing talk about infinite sets to be interpreted in a totally different „finitistic“ context/model. Both lost in a certain sense in the end, but Frege fully understood that he lost, while Hilbert didn‘t manage that stunning feat. Maybe Frege would have died happier if Hilbert‘s gift of not fully understanding had been granted to him.

 

[Matterwave]

Do y'all think the difference in the definition of a bijective/ surjective $f$ w.r.t. $\mathfrak{A}$ vs $\mathfrak{B}$ is the root resolution of the paradox as suggested in post #5?



Basically I'm saying $f$ is a set (of sets) where each element is an input output pair (still a set though). And there is no element of $\mathfrak{A}$ with the required input output pairs such that there is a bijection $f\in A$ between $\mathbb{N}^\mathfrak{A}$ and $\mathcal{P}(\mathbb{N})^\mathfrak{A}$ (I.e. there is no bijection). But if you looked at the object $\mathcal{P}(\mathbb{N})^\mathfrak{A}$ from the lenses of $\mathfrak{B}$ such a bijection $f\in B$ would exist.

 

[Matterwave]

Since @Matterwave and @gentzen who write here are also interested in quantum foundations, let me give one metaphorical analogy.

It's an interesting analogy~

To remove the ambiguities of quantum interpretations, perhaps we would need to formulate QM differently from the very start, by using some general principle analogous to second-order logic.

We do have some no-go theorems to guide us when it comes to foundations of QM. But ultimately I think few people work in the topic

Unless you count quantum gravity or its adjacencies as foundations of QM.

It's not clear what this principle could be (but it's definitely not second quantization, if you ask).

I don't think the human species knows, so I won't begrudge you for not knowing.

Someone may object that such a theory would not be physics, just like Quine objected that second-order logic is not logic (but set theory in disguise).

I would not object as long as it still had some connection to empiricism in the sense that even if we could not test the theory today, we could at least conceive of how it could possibly be tested (even if it required one to go into a black hole or something lol). Otherwise I might call it applied math and/or philosophy.

 

[Matterwave]

On the one hand, there is a large degree of freedom in what one allows as a „model“. On the other hand, one should provide enough freedom for the allowed „models“ to make the completeness theorem true. That is the problem with „full semantics“ in SoL, namely that the allowed models are „too restricted“, and hence the completeness theorem no longer holds.

This is insightful, thanks~

I guess this freedom was also the initial disagreement between Frege and Hilbert. Frege basically insisted on „full semantics“, and also tried to explain the difference to „Henkin semantics“ (basically Hilbert‘s formalist position). Hilbert on the other hand wanted to have „Henkin semantics“, because he wanted to secure „Cantor‘s paradise“ by allowing talk about infinite sets to be interpreted in a totally different „finitistic“ context/model. Both lost in a certain sense in the end, but Frege fully understood that he lost, while Hilbert didn‘t manage that stunning feat. Maybe Frege would have died happier if Hilbert‘s gift of not fully understanding had been granted to him.

I was not aware of this part of the history. But I will look into it because it seems interesting~