I'm new to everything involving languages and I'm having trouble proving properties with quantifier elimination. In particular what's below.

Suppose we know the following:

$Lemma$ (L1): Let $N \leq M$ be a substructure. Then for every quantifier-free $L$- formula ($L$ the language in this context) $\phi$ there is: $\phi$ holds in $N$ $\iff$ $\phi$ holds in $M$

Theorem (to prove): Let $L$ be a language, $T$ an $L$-theory, $M$ a model of $T$ and $A$ a substructure of $M$. Assume the theory admits quantifier elimination.

  1. Show that for every $L_A$-sentence $\phi$ there is an $L_A$-sentence $\psi$ such that: $\phi$ holds in $M$ $\iff$ $\psi$ holds in $A$.
  2. Suppose $M_1$ and $M_2$ are models of $T$, and $A$ is a substructure of both models. Show that $M_1$ and $M_2$ satisfy the same $L_A$-sentences.

I've tried proving 1. as follows:

Suppose $\phi$ holds in $M$, then there is a qf equivalent $\psi$ that holds in $M$. Becuase of (L1) $\psi$ holds in $M$ $\iff$ $\psi$ holds in $A$. $\blacksquare$

I'm not sure wether this is entirely correct, I feel like I'm missing something.

For 2. I've done (so far):

Take $\psi$ that holds in $A$, then:

there is $\phi$ that holds in $M_1$ because of (1); there is $\chi$ that holds in $M_2$ because of(1). and because of (1) if we take every $L_A$-sentence that holds in $A$ we can find every $L_A$-sentence that holds in $M_1$ and also every $L_A$-sentence that holds in $M_2$. So there are as many $L_A$-sentences in both models. I don't know how to prove they are the same though...

In general: I've never been the best at logics, so correct me if I do important things wrong and if I skip important steps because I 'assume' something is known.


Your answer to $(1)$ is essentially right (I would only suggest to pay more attention to the fact that the formula $\phi$ is in $L_A$ and not in $L$).

Your answer to $(2)$ need some reworking, in my opinion. You can proceed as follows: let $\phi$ be an $L_A$-formula that holds in $M_1$, then by $(1)$ there is an equivalent $\psi$ without quantifiers. Then you can use $L1$ to say that $\psi$ holds true in $M_2$, and since $M_2\models T$ you can conclude that $M_2\models \phi$. This proves that $M_1\models \phi$ implies $M_2\models\phi$. Then, in an entirely similar way, you can go the other way around: take a formula $\phi$ true in $M_2$ and show that it is true in $M_1$.


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.