1
$\begingroup$

A formula is called positive if is is built from atomic formulas using only $\land, \lor, \exists$ and $\forall$. A homomorphism $f : M \to N$ is positive if $$ M \models \varphi(m_1, \cdots, m_n) \Rightarrow N \models \varphi(f(m_1), \cdots, f(m_n)) $$ for all positive $\varphi(x_1, \cdots, x_n)$ and all $m_1, \cdots, m_n \in M$. Let $T$ be a satisfiable $L$-theory and $$ T_0 = \{\varphi : \varphi \text{ is positive and } T \models \varphi \} \, . $$

Prove that for any model $A \models T_0$ there is a model $C$ such that there exists 1) a model $B \models T$ and a positive homomorphism $g : B \to C$; and 2) an elementary embedding $h : A \to C$ with $\text{Im}(h) \subset \text{Im}(g)$. [Where $\text{Im}(\cdot)$ stands for "image"]

I really don't know how to approach such a problem. The best I can think of is to prove that there is a model for $\text{ElDiag}(A) \cup \{\varphi : B \models \varphi \text{ and } \varphi \text{ is positive}\}$ for some model $B \models T$ to which we have added all the constants of $L_A$ ($L_A$ is $L$ with all the elements in $A$ added as constants; $\text{ElDiag}$ = elementary diagram). Maybe we can use compactness to prove the existence, utilising that we know $A \models T_0$ and we have freedom to choose $B \models T$?

Could you provide a hint? I have been at this exercise for several days, but am completely stuck; I have no strategy to approach it.

$\endgroup$
  • 2
    $\begingroup$ What are the $>\to$ and $>\Rightarrow$ supposed to mean? And the $>$ in the definition of $T_0$? $\endgroup$ – tomasz Mar 11 '19 at 19:51
  • $\begingroup$ @tomasz Nothing. I fixed it now; apparently the blockquote tool does not handle LaTeX well. $\endgroup$ – Joachim Mar 12 '19 at 10:12
1
$\begingroup$

Your idea to solve the problem by the method of diagrams and compactness is the right one. But the first thing you should ask yourself is: What is $B$, and what is its relationship to $A$? Can we take any model $B\models T$?

Well, no, we can't in general... Since we must have $\text{Im}(h)\subseteq \text{Im}(g)$, for all $a\in A$ there must be some $a'\in B$ such that it is consistent that $g(a') = h(a)$, where $h$ is some elementary embedding $A\to C$ and $g$ is some positive homomorphism $B\to C$. What does this consistency amount to? Suppose $\varphi(x)$ is a positive formula such that $B\models \varphi(a')$, where $h(a) = g(a')$. Then $C\models \varphi(g(a'))$, so $C\models \varphi(h(a))$, and $A\models \varphi(a)$. This is a constraint on $B$: If $A\models \lnot \varphi(a)$, then we must have $B\models \lnot \varphi(a')$.

So let's define a negative formula to be the negation of a positive formula, and consider the $L_A$-theory: $$T\cup \text{Diag}^-(A)\text{, where }\text{Diag}^-(A) = \{\psi(a)\mid \psi(x)\text{ is negative, and }A\models \psi(a)\}.$$

You can show by compactness that this theory is consistent, using our assumption that $A\models T_0$.

So $B$ be a model. $B$ is an $L_A$-structure, so when we form the language $L_B$, we reuse the constants naming the elements of $A$, i.e. $L_A\subseteq L_B$. Now consider the $L_B$-theory: $$\text{ElDiag}(A)\cup \text{Diag}^+(B)\text{, where }\text{Diag}^+(B) = \{\varphi(b)\mid \varphi(x)\text{ is positive, and }B\models \psi(b)\}.$$

It remains to show that this theory is consistent, using compactness and the fact that $B\models \text{Diag}^-(A)$.

$\endgroup$
  • $\begingroup$ Thank-you, Alex. I knew I was not that far off. This was a very good tip. I have found the solution now, but it was still not quite trivial to me (especially how to deal with the constants). You left me enough work to learn something :) . Can I interpret your second paragraph as to how you (or someone in general) might have come to this solution? $\endgroup$ – Joachim Mar 11 '19 at 13:54
  • 1
    $\begingroup$ @Joachim Yes, I had to think through the reasoning in the second paragraph to see which theory to write down when finding $B$. $\endgroup$ – Alex Kruckman Mar 11 '19 at 14:09

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.