Help with Skolem's Paradox and Model Theory
I'm studying Skolem's Paradox. Cantor's Theorem: for any (arbitrary) set S, no mapping surjects S onto its power set P(S). Consequently, there exist uncountable sets. Skolem's Theorem: if some collection of first-order sentences has any infinite model, then it has a countable model. The paradox: how can (e.g.) ZFC, a first-order theory, have a countable model and imply that there uncountable sets? I understand Cantor's Theorem, but not so much Skolem's Theorem.
Timothy Bays spells it out (my paraphrase):
Let T be ZFC. Let M be a model of ZFC. Since T ⊢ ∃x x is uncountable, there must be some m ∈ M such that M ⊨ m is uncountable. But, as M itself is only countable, there are only countably many m ∈ M such that M ⊨ m ∈ m. Thus there seems to be a contradiction.
(1) what is "m^" and what does it mean to say "m ∈ M"? -- I ask this because I understand what x is such that x ∈ T: it is a first-order sentence (e.g. one of the axioms in ZFC), but I guess I don't understand models. What does it mean to say "a model with a countable domain?"
(2) Can someone explain in plain English what the relevant Skolem (-Lowenheim) Theorem is saying?
(3) General comments?
Thanks! Feel free to be thorough (though clear), I'd appreciate it.
Re: Help with Skolem's Paradox and Model Theory
i'm not an expert in this area. but my take on it is this:
what "uncountable" means in a standard model of ZFC, and what it means in a "countable model" are two different things. in the former, when we say there is no surjection from S to P(S), we mean there is no such function at all. period. what we mean in the latter, is that there may indeed be some surjection, but it is not an element of our model (since we define functions as sets, and sets in a countable model must be countable). or, equivalently: the power set P(S) means something different than what we're used to (in a standard model) in a countable model, it doesn't include "all" sub-collections, but only countably many of them (in particular, those sub-collections which are already in our countable model).
a somewhat conventional response, is to say that Skolem's Paradox points out that first-order logic doesn't define an invariant property of "countability". which sets we can "count" depends on which functions can be described as sets (in our model) so that we can make the necessary bijection (as a set in our model). uncountable in T, and uncountable in M may be two different concepts, and just because a set S is in both, doesn't mean that S has to be countable in both. there is something of an unspoken agreement that second-order logic is the proper realm for discussing "large" sets, as then cantor's argument always has its desired conclusion. some people have objections to second-order logic, and for these people, construction of sets such as the real numbers (or the completion of a metric space, in general) has always been looked on with some suspicion.
personally, i feel that the trouble is with ZFC itself. note that downward Lowenheim-Skolem starts with "if there is a model of ZFC....". the trouble is, i don't think anyone has ever found a model for ZFC. it appears likely that we never will. the problem is, that the class of all sets is not a set itself, so it cannot serve as a model for ZFC. we act "as if" there was a model, which boils down to accepting that ZFC is logically consistent "on faith". there are good reasons for doing so, taking the axioms of ZFC "as sound", allows us to re-cast most of mathematics in its language, and the general consensus is that this allows for relatively unambiguous communication within this framework.
that is, ZFC allows us to prove things we feel are "actually true" (such as 2+2 = 4 with the usual interpretation of these as integers), and hasn't led to proofs of things we feel "aren't true at all" (such as 2+2 = 5).
i think the "bigger picture" question is: what do we want to be in our "universe of mathematical discourse"? we can CHOOSE these items, logic itself doesn't "set them in stone". different choices (different axioms, and the models that might satisfy these axioms), give us different things to talk about. we can define "truth" narrowly, or expansively...there are pros and cons to each approach. perhaps this is more of a pressing issue for a platonist, who believes "ultimate mathematical structure" is "out there", waiting to be discovered. but i believe, as the great mathematician clint eastwood said: "a man's got to know his limitations". finding an over-arching all-encompassing structure that consistently accounts for "all" mathematics, is, in my opinion, a pipe dream.