TL;DR

Trying to talk through the resolution of Skolems paradox (topic in First Order 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).

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}##.

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...

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.

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.

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.

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.

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.

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.

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.

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”).

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.

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}##"?

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}##"?

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.

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.

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.

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/

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.

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.

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.

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