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