3
$\begingroup$

Let $T$ be the theory of dense linear orders without endpoints in the language $\{ < \}$. I need to show that if $\mathcal{A}$, $\mathcal{B}$ are two models of $T$ with $\mathcal{A} \leqslant \mathcal{B}$ then $\mathcal{A} \preccurlyeq \mathcal{B}$. I can do this by showing $T$ has quantifier elimination but the question suggests using the downward Lowenheim-Skolem theorem.

In the proof of the downward LS theorem, we take a subset of a structure and close it under Skolem functions, and then use this as the domain of the elementary substructure. But if we could show $\mathcal{A}$ is closed under Skolem functions then we'd have that it's an elementary substructure already by the Tarski-Vaught criterion.

How else can this be done?

$\endgroup$
1
  • 2
    $\begingroup$ The idea of choosing Skolem functions under which $\mathcal A$ is closed runs into the problem that you need Skolem functions for all formulas, of arbitrary quantifier complexity. I don't see how to handle those without first reducing the quantifier complexity, i.e., without first proving quantifier elimination. But that would defeat your purpose here. $\endgroup$ May 17, 2020 at 16:47

1 Answer 1

5
$\begingroup$

We use Lowenheim-Skolem to reduce the general case to the countable case. Specifically:

If there are $\mathcal{A,B}\models DLOWOE$ with $\mathcal{A}\le\mathcal{B}$ but $\mathcal{A}\not\preccurlyeq\mathcal{B}$ then there are countable such $\mathcal{A},\mathcal{B}$.

Proof idea: Fix a tuple $\overline{a}\in\mathcal{A}$ witnessing the failure of elementarity and consider a countable elementary substructure of the expansion of $\mathcal{B}$ by a predicate naming $\mathcal{A}$ and constants naming $\overline{a}$.

Note that this is true for any theory - nothing special about $DLOWOE$ is being used here.


We now handle the countable case directly, via homogeneity:

If $\mathcal{A}\le\mathcal{B}$ are countable DLOWOEs, then for every $\overline{a},b$ in $\mathcal{B}$ with $b\not\in\overline{a}$ there is some automorphism $\eta\in Aut(\mathcal{B})$ which fixes $\overline{a}$ pointwise and has $\eta(b)\in\mathcal{A}$.

Proof idea: Back-and-forth.

This lets us apply Tarski-Vaught: if $\overline{a}\in\mathcal{A}$ such that $\mathcal{B}\models\exists y(\varphi(\overline{a}, y))$, pick some $b\in\mathcal{B}$ with $\mathcal{B}\models\varphi(\overline{a},b)$ and apply the result above.

$\endgroup$
2
  • 2
    $\begingroup$ DLOWE isn't really less ambiguous than DLO, is it? The W could stand for "with" or "without"! :0) $\endgroup$ May 17, 2020 at 20:28
  • 3
    $\begingroup$ @AlexKruckman ... That's a real DLO woe right there. $\endgroup$ May 17, 2020 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.