A common-sense analogue of Skolem paradox?

[Demystifier]

I am a non-mathematician who was reading about Skolem paradox. Since I am not sure that I understood it correctly, I would like to see a simple non-technical common-sense explanation of it. Unfortunately, I have not yet seen such an explanation that would completely satisfy me, so here I present my own attempt to explain the main idea of Skolem paradox in elementary terms. Of course, my explanation will be very very far from rigorous, but I would be happy if someone could tell me if my explanation, at least, correctly captures the main idea.

Instead of using abstract logic, model theory, and axiomatic set theory, I will only use standard English language and a little bit of naive set theory at a high-school level.

By the well known diagonal trick, Cantor has shown that the set or real numbers is not countable. But he has proven it by using only English language (actually German, but that's irrelevant here) enlarged with a few basic mathematical symbols. Such a language (or more precisely, the set of all sentences expressible in that language) is certainly countable. So by expressing set theory in a countable language, and therefore by using only countable sets, he has proven that there is an uncountable set. But that's a paradox, for how can a smaller countable set prove the existence of a larger uncountable set?

Is the paradox above at least a good analogue of the Skolem paradox? If not, then why not? Can you make a better simple analogue of Skolem paradox?

 

[gopher_p]

Your analogy is kinda close, I guess. Here's how I see see it;

So we're these omnipotent gods, and we've made all of these various worlds to play with. In all of those worlds are beings which can tell us things about their worlds, and we take them at their word. Now one of those worlds is known by us to be purple, and everything in that world is purple. However the people in that world think that there are some things that aren't purple.

So the paradox is that we know that everything is purple, and yet we have to take the word of our little friends that not everything is purple. The resolution to the paradox is that we are gods and have access to information that our little friends don't have access to. For what ever reason, they think that "purple and shiny" is not purple. But we still take them at there word and know that, if we were in there with them, we would agree that there are things that are not purple.

 

[Demystifier]

Thanks for the answer. I am also little confused about a difference between a theory and a model (or if you like, between gods and beings created by gods). Can one theory be viewed as a model for an even more general theory? And similarly, can a model be viewed as a theory containing finer sub-models?

For example, consider group theory. A model for group theory is, for instance, group SO(3). (This is a continuous Lie group, so it represents an uncountable model for group theory.) But group SO(3) contains many representations, differing by the dimension of the vector space on which the group is represented. Can we think of each representation as a different model for the group SO(3)?

 

[gopher_p]

In model theory, a theory in a particular formal language is basically just a set of consistent sentences in that language. Think of it kind of like a blueprint. For instance, the language of groups is $\mathcal{L}=\{+,-,0\}$ along with all of the the logical symbols. The theory of groups would be all of the sentences built using that language that are true for all groups.

Note that the "theory" used colloquially in the term "model theory" (as well as your use in "group theory") is different than the theory defined and used in that field of study. One way to think about it is that people studying "group theory" are examining the things that are true about specific groups whereas a person studying the theory of groups in model theory is examining the things that are true about group theory.

A model of a theory is basically just a set along with the right kinds of functions and relations "satisfying" all of the sentences in the theory. If the theory is the blueprint, then the model is a building that meets all the requirements of the blueprint. For instance, a model of our theory of groups would be a set $G$ along with a binary function $+_G:G\times G\rightarrow G$,a unary function $-_G:G\rightarrow G$, and a distinguished member $0_G$.

Model theory doesn't really care about representations. It's in the same boat with a lot of other math disciplines in that it really only talks about what is true "up to isomorphism" most of the time.

 

[Demystifier]

Thanks, but I still don't understand why the theory of group SO(3) cannot be viewed as an axiomatic theory in a particular formal language, and why different representations of that theory cannot be viewed as different models of the theory. :(

 

[gopher_p]

Thanks, but I still don't understand why the theory of group SO(3) cannot be viewed as an axiomatic theory in a particular formal language, and why different representations of that theory cannot be viewed as different models of the theory. :(

Can you propose a language and a set of axioms for the "theory of SO(3)"? Can you explain what you mean by "representation"? Can you explain why you think different representations of a thing should count a different models of the "theory of thing"? It would be infinitely easier for me to explain to you why a specific idea will or will not work than it would be to figure out how you think it should work and try to explain why all of the things don't work that way.

 

[Demystifier]

Can you propose a language and a set of axioms for the "theory of SO(3)"? Can you explain what you mean by "representation"? Can you explain why you think different representations of a thing should count a different models of the "theory of thing"? It would be infinitely easier for me to explain to you why a specific idea will or will not work than it would be to figure out how you think it should work and try to explain why all of the things don't work that way.

I guess my problem is that I think informally, rather than formally. So for me, "theory of SO(3)" is just the group SO(3) defined as usual, as e.g. in
http://en.wikipedia.org/wiki/Rotation_group_SO(3)
where the "language" is nothing but the language used at that wiki page. I guess you will object that this language is not sufficiently formal, but my reply would be that the language used for the general theory of groups in
http://en.wikipedia.org/wiki/Group_(mathematics)
is also not very formal, which does not stop group theory to be a theory.

So I guess I would need to see a more formal definition of the group theory, presented in such a form that it is obvious that "the theory of SO(3)" cannot be presented in a similar form. Can you help me in that direction? Unfortunately, the texts on mathematical logic and model theory usually consider examples from set theory, but not from more "concrete" theories such as group theory.

 

[Demystifier]

Concerning my original question, I would like to add that now I better understand the meaning of Skolem paradox.

Instead of considering abstract set theory, let me consider something more concrete: group theory. Continuos groups certainly exist (e.g. SO(3)), so there are uncountable models of group theory. The existence (construction) of an uncountable model is a proof that axioms of group theory imply the existence of uncountable models. This can be expressed as a theorem saying

T1: There is an uncountable group.

For reasons that will become clear soon, let me express it in a different (but equivalent) form as

T1': A group is uncountable.

But there also countable groups, so in a similar way one can also express a theorem

T2': A group is countable.

There is nothing contradictory between T1' and T2'. However, a contradiction arises when one ignores the word "A", leading to

T1'': Group is uncountable.
T2'': Group is countable.

which one might interpret as

T1''': The group is uncountable.
T2''': The group is countable.

Clearly, T1''' and T2''' are in contradiction with each other, which represents a paradox. The paradox arises from a naive assumption that "A" is the same as "The", i.e. that there is only one thing called "group" which satisfies the axioms of group theory. The resolution of the paradox is nothing but a conclusion that this naive assumption is wrong. In other words, the resolution is the conclusion that the group theory is not categorical.

Essentially the same can be said about set theory. The creators of set theory initially assumed that the theory should be categorical, and Skolem paradox is nothing but an observation that this assumption was wrong.

 

[gopher_p]

http://en.wikipedia.org/wiki/List_of_first-order_theories#Groups

Note that they decided to go with a multiplicative language (they're calling it a signature). Also, the notation $x^2$, $x^3$, $x^n$ is not part of the formal syntax (unlike $x^{-1}$). It's just shorthand for $xx$, $xxx$, $xx\ldots x$.

There are also some first-order properties that a group might have there. "$G$ is finite" is not one of them. I think that's one of the things that you're going to need to begin to consider; there are some statements that we might consider very basic that certain logics are not capable of making.

 

[gopher_p]

I'm not trying to be rude, but I think you are doing yourself a great disservice in your attempt to wrap your head around one of the more interesting and nuanced results of model theory without first understanding its basic definitions and ideas. At the end of the day, Skolem's paradox is about the existence of countable models of set theory. To understand (a) why it looks like there is a paradox and (b) why it's not really a paradox, you absolutely must understand the basics of FOL and model theory.

 

[atyy]

hurkyl had this explanation, which is similar to the idea in the OP: https://www.physicsforums.com/threads/is-this-a-good-way-to-explain-skolems-paradox.609139/#post-3929647.

 

[Demystifier]

I'm not trying to be rude, but I think you are doing yourself a great disservice in your attempt to wrap your head around one of the more interesting and nuanced results of model theory without first understanding its basic definitions and ideas. At the end of the day, Skolem's paradox is about the existence of countable models of set theory. To understand (a) why it looks like there is a paradox and (b) why it's not really a paradox, you absolutely must understand the basics of FOL and model theory.

I understand your critique, and I thank you for that. My problem is that I would like to understand these things intuitively, informally, and without all the details, before trying to understand them formally and in detail. Eventually it may turn out to be impossible, but you cannot blame me for a try.

Perhaps you can suggest me a good gentle introduction to this stuff, which is written for general readers and as such is neither too technical nor too casual?

 

[Demystifier]

hurkyl had this explanation, which is similar to the idea in the OP: https://www.physicsforums.com/threads/is-this-a-good-way-to-explain-skolems-paradox.609139/#post-3929647.

I've seen that, but I was not completely satisfied with it.

 

[atyy]

I've seen that, but I was not completely satisfied with it.

I too am not a mathematician, as you know. But my intuitive understanding is that a theory is a formal set of meaningless symbols, with rules about how they can be arranged, somewhat like a branch of combinatorics. An example of such meaningless symbols are the Peano axioms. To give the symbols meaning, we can say the symbols represent "real objects" like the intuitive natural numbers. To be more formal, we can construct the natural numbers using ZFC, and consider these our "real objects". (We have many levels. At every level the top level is "intuitive", and the bottom level is "formal".) A model is an assignment of meaning to meaningless symbols by associating them with "real objects" from set theory. However, if we use only the first order version of Peano axioms, there can be more than one valid way to assign meaning to the meaningless symbols. Apart from the "standard natural numbers", we can also imagine "nonstandard natural numbers", and both are valid interpretations of the meaningless symbols of Peano axioms.

Skolem's paradox is another case of meaningless symbols having more than one valid meaning, except that the meaningless symbols are a particular formalization of set theory.

Here is a nice friendly write-up about nonstandard natural numbers by Victoria Gitman: http://boolesrings.org/victoriagitman/2012/01/18/an-iphone-app-for-a-nonstandard-model-of-number-theory/.

Here is an article by Haim Gaifman about the more general idea of nonstandard models that mentions Skolem's paradox, as well as the nonstandard natural numbers: http://www.columbia.edu/~hg17/nonstandard-02-16-04-cls.pdf.

 

[Demystifier]

For a theoretical physicist (which I happen to be one), a much more interesting example of a non-standard model is the case of non-standard analysis. Why? Because it justifies the usual intuitive way of thinking in terms of infinitesimal quantities, which physicists practice every day. Both mathematicians and physicists are usually taught that infinitesimal quantities are not well defined objects and that the proper way to do analysis is with epsilon and delta. And yet, for practical purposes the infinitesimal way of thinking turns out to be much more efficient. How can something which is not well defined be so efficient?

In 1960 Robinson has shown that infinitesimal quantities can be well defined, as a non-standard model of the field of real numbers. But the actual work of Robinson is a work in abstract logic and model theory, which, as such, is very hard to understand for a practical physicist, and even for most mathematicians.

Nevertheless, for practical purposes, there is a very simple and intuitive way to present the ideas of non-standard analysis, at a level at which practical mathematicians, physicists, and even engineers can easily understand. For that purpose I recommend the book
https://www.amazon.com/dp/0871509113/?tag=pfamazon01-20
There is also a free version of the book
https://www.math.wisc.edu/~keisler/calc.html
and even some information on the book at wikipedia
http://en.wikipedia.org/wiki/Elementary_Calculus:_An_Infinitesimal_Approach

Why am I saying all that? Because it demonstrates that some abstract ideas in logic and model theory can be understood at a non-formal intuitive level. Perhaps it does not imply that they all can be understood at such a level, but it certainly gives some justification for a hope that they might.

 

[SteveL27]

Here is a down-to-earth way to understand what's going on.

When Cantor proves that the real numbers are uncountable, we must be more specific about what has been proved. If you study the diagonal proof you'll see that what's been shown is that there is no bijection between $\mathbb{N}$, the set of natural numbers, and $\mathbb{R}$, the set of real numbers.

The key observation is that the problem with $\mathbb{R}$ is that there are not enough bijections.

Suppose you are a clever set theorist. You start with model of the axioms of Zermelo-Fraenkel set theory (ZF), and you create some countable set X. In other words X has a bijection (in your model of set theory) to $\mathbb{N}$.

Now, here's the clever bit. You take your model of ZF and you start removing some sets in such a way that you still have a model of set theory. If you can manage to do two things:

a) Remove all of the sets that are bijections between $\mathbb{N}$ and X; and

b) Still ensure that the remaining sets are a model of the axioms of set theory;

then you now have a model of set theory in which X has no bijection to $\mathbb{N}$. So X is uncountable in your model. But (as seen from above) X is "really" countable in some larger model that includes the needed bijection.

This is my understanding of the English-language version of Skolem's paradox.

Now this brings up a question. When we say that the reals are uncountable, is there some higher level in which it's countable? If we just had more bijections, would the reals be countable? This Stackexchange thread provides additional insight.

Note the first comment from Arturo Magidin: The Lowenheim-Skolem Theorem guarantees the existence of a countable model, where of course R will be countable. However, R will not be countable-within-the-model. R always has cardinality 2^ℵ0 (within the model).

Note (this is me again, not the far more knowledgeable Prof. Magidin) that, by Skolem, we have a countable set which is a model of the reals. But (since Cantor's proof is a theorem of ZF) the reals look uncountable from the point of view of this model.

Hope this is helpful. This is how I understand this matter. I'd be glad for any technical corrections in my understanding.

 

[Demystifier]

Does the Lowenheim-Skolem theorem depend on the axiom of choice? I guess not, so does it mean that a countable model of set theory (ZF without AC) can be explicitly constructed?

 

[Demystifier]

I have found a great non-technical explanation of all this stuff:
http://lesswrong.com/lw/93q/completeness_incompleteness_and_what_it_all_means/

 

[Demystifier]

I have just found (and started reading) a semi-technical book on this stuff:
https://www.amazon.com/dp/1107678668/?tag=pfamazon01-20