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)$. Here, $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.