**p500vax:white** (02/14/83)

The question about the Lowenheim-Skolem theorem and countability is called Skolem's paradox. It is concerned with the difference between the language we describe things in, and the things themselves. I can't find a book with the LST in it right now, but the seeds of the paradox are in the completeness theorem. The completeness theorem says that any consistent theory has a model whose cardinality is the max of the cardinality of the natural numbers and the cardinality of the set of formulas of the language. Modern proofs of it actually construct the model out of the constructible terms of the language. (As I remember, the proof of the LST uses the completeness theorem in exactly this way.) The paradox is that we can make first order axioms to deal with set theory in a finitely generated language, say for ZF, and inside of that theory, we can prove that there are an uncountable number of elements in the universe. The key here is that the proof is inside of the theory. Recall that a function is a set of ordered pairs which is single valued. Let S be a set. The claim that S is uncountably large is (roughly) equivalent to this sentence: (*) !((E f)(func(f) && dom(f)=S && cod(f)=N && inj(f))) Where func(f) means that f is a function, dom(f) is the domain of f, cod(f) is the codomain of f, and inj(f) means that f is injective (one- to-one). If p0 and p1 are the projections onto the first and second coordinates of a pair, (x) means "for each x", and f(x) denotes application of f, we can write these as: dom(f) = {y|Ex.(x in f) && (p0(x) = y)} cod(f) = {y|Ex.(x in f) && (p1(x) = y)} inj(f) = (x)(x')(y)((f(x) = y && f(x') = y) ==> x = x') ) (Of course we have to say what func(f) is, and specify that f is a set of pairs, but you get the general drift.) (*) is a sentence in a first order theory, ZF. (You'll have to take it on faith that N makes sense in this context.) We can certainly find sets S such that (*) is provable. (Let S = 2^N.) However, (*) is a sentence denying the existence of a certain thing. If we fix our model as the countable one that the completeness theorem says we must have, all the theorem says is that there aren't elements of the model which embed S into N. It doesn't say anything about our ability to construct them outside of the model, just that they aren't in the countable model. The situation is kind of similar to the existence of solutions to x^2=-1 in the real numbers. There aren't any solutions to that equation in the real numbers, though we can find one if we look in the complex plane. The really interesting thing here is that we can use this kind of argument to prove things about independence of axioms. To prove the independence of the axiom of choice, for example, we start with a universe where the axiom of choice is true, and construct a model of ZF where it fails. The failure of AC in the constructed model doesn't say anything about the trueness of falseness of AC in the real world, just that it's independent of the first few axioms of ZF. peace Bill White 477 Potrero Rd. Sunnyvale, Ca., 94086 lbl-csam!megatest!white Shasta!megatest!white