[FOM] Equivalence of Downward Löwenheim-Skolem theorem and the Axiom of Dependent Choice

[Christian Espindola]

Dear all,

It is known that the Axiom of Dependent Choice (DC) is enough to derive in
ZF the following form of the (downward) Löwenheim-Skolem theorem (LS):
Every model M of a first order theory T with countable signature has an
elementary submodel N which is at most countable. But the standard
reference (Consequences of the axiom of choice by Howard and Rubin) does
not contain any mention of the reverse implication (neither the book nor
the website).

I believe that DC and LS are equivalent over ZF, according to the following
argument:

That DC implies LS is standard. Perhaps the shortest proof adapts Henkin's
construction in the following way: Let T be a first order theory with
countable signature with a model M. Use Dependent Choice to extend M to a
model M' of the Henkinized theory T' (this is necessary because the
interpretation of the constants added in each level depends on that of the
constants of previous levels). Finally, an elementary submodel N which is
at most countable can be constructed by taking as its underlying universe X
the interpretation in M' of all constants of T' and restricting to X the
interpretation in M of the symbols of T (the restriction of functions is
well defined because T' is a Henkin theory). Note that this amounts to
repeat Henkin's proof of the completeness theorem except that we use Th(M')
(the theory of the model M') as the maximal consistent extension of T'.

That LS implies DC could be seen in this way: Let S be a set with a binary
relation R such that for every x in S, the set of y's in S such that xRy is
nonempty. Consider the theory T over the language {R} that contains a
binary relation symbol, and whose only non logical axiom is $\forall x
\exists y R(x, y)$. Then S is a model of T with the obvious interpretation
of R. By LS, it has a submodel N whose underlying set is in bijection with
either some finite ordinal or the natural numbers. Hence, a sequence x_n
such that x_nRx_{n+1} can be defined by recursion taking at each step the
minimum element (according to the bijection) of the nonempty set of
elements of N which are related to x_n.

My question: is this equivalence known (if it's correct?). If so, where can
I find a reference?

Many thanks,

Christian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120330/b76494e9/attachment-0001.html>