Equivalence between regular and “positive” model completeness

Question

Take the classical notion of model completeness as introduced in Tent, Ziegler:

A theory $T$ is model complete if for any two models $M,N$ of $T$: $$M\subseteq N\implies M\preceq N,$$ meaning that every extension is elementary, or in other words that every embedding between models of $T$ is elementary. More precisely, if $U_M$ and $U_N$ are the universes of $M$ and $N$ respectively, $f:U_M\longrightarrow U_N$ an embedding and $$M\models\phi(\bar a)\iff N\models\phi(f(\bar a))$$ for every tuple $\bar a$ of elements of $U_A$ and every atomic formula $\phi$, then $$M\models\psi(\bar a)\iff N\models\psi(\bar a)$$ for every formula $\psi$.

Next, consider the "positive" model completeness as introduced by Belkasmi in this article (page 4):

An $h$-inductive theory $T$ is model complete if every model of $T$ is positively closed in the class of models of $T$. Making this precise, if $M$ and $N$ are models of $T$ and $g:U_M\longrightarrow U_N$ a homomorphism, then $g$ is an immersion. This in turn means that if $$M\models\phi(\bar a)\implies N\models\phi(g(\bar a))$$ for all atomic formulas $\phi$, then $$M\models\psi(\bar a)\iff N\models\psi(g(\bar a))$$ for every positive formula $\psi$.

Some additional notes:

A theory is $h$-inductive if it is formed by finite conjunctions of sentences of the form $\forall\bar x(\Phi(\bar x)\rightarrow\Psi(\bar x))$, where $\Phi$ and $\Psi$ are positive formulas, which in turn are formulas of the form $\exists\bar x\theta(\bar x,\bar y)$ with free variables $\bar y$. Positive formulas are the formulas obtained from atomic formulas by the use of $\wedge,\vee$ and $\exists$.

This is the way I interpret everything up until now.

My question is: are these notions of "model completeness" equivalent, taking into account that in the positive case we consider $h$-inductive theories, while in the "classical" definition we consider extensions? If they are equivalent, why? I fail to see this equivalence, but it would make a lot of sense if they were.

Answer 1

I just want to add a few things to Mark Kamsma's thorough answer.

The classical notion of model-completeness is closely tied to the notion of inductive theory.

Let $T$ be a first-order theory. The following are equivalent:

1. $T$ is equivalent to a set of $\forall\exists$ (inductive) sentences.
2. The class of models of $T$ is closed (in the category of $L$-structures) under directed colimits along chains of embeddings.
3. The class of models of $T$ is closed (in the category of $L$-structures) under all directed colimits along diagrams of embeddings.

If these conditions hold, we say $T$ is inductive.

Now if $T$ is an inductive theory, then the following are equivalent:

1. Every embedding between models of $T$ is an elementary embedding.
2. Every model of $T$ is existentially closed: Let $M$ and $N$ be models of $T$, $f\colon M\to N$ an embedding, and $\varphi(x)$ an existential formula. If $N\models \varphi(f(a))$, then $M\models \varphi(a)$.
3. Every first-order formula is equivalent to an existential formula.

If these conditions hold, we say $T$ is model-complete.

---

Now the basic idea of positive model theory is to refocus our attention on homomorphisms instead of embeddings.

Let $T$ be a first-order theory. The following are equivalent:

1. $T$ is equivalent to a set of h-inductive sentences.
2. The class of models of $T$ is closed (in the category of $L$-structures) under directed colimits along chains (of homomorphisms).
3. The class of models of $T$ is closed (in the category of $L$-structures) under all directed colimits (along diagrams of homomorphisms).

If these conditions hold, we say $T$ is h-inductive.

Now if $T$ is an h-inductive theory, then the following are equivalent:

1. Every homomorphism between models of $T$ is an elementary embedding.
2. Every model of $T$ is positively closed: Let $M$ and $N$ be models of $T$, $f\colon M\to N$ a homomorphism, and $\varphi(x)$ a positive formula. If $N\models \varphi(f(a))$, then $M\models \varphi(a)$.
3. Every first-order formula is equivalent to a positive formula.

If these conditions hold, we say $T$ is positive model-complete.

The point is that we've just replaced the word "embedding" with "homomorphism" everywhere, and made the necessary adjustments on the syntax side (replacing "existential" by "positive" and "inductive" by "h-inductive"). Since every embedding is a homomorphism, positive model-complete is a strictly stronger condition than model-complete (on h-inductive theories). And you should not expect model-completeness and positive model-completeness to be equivalent except in situations where every homomorphism is an embedding (like for Morleyized theories as in Mark's answer).

But in any context where we're strictly doing positive model theory (i.e. where we don't even consider any theories that aren't h-inductive), positive model-completeness is clearly the right notion of model-completeness to consider, so there's not really a chance for confusion if we just call it "model-completeness", dropping the word "positive".

Answer 2

I can think of two ways to make this question precise, and they have different answers. I think it is actually interesting and insightful to see these different ways and why their answers may be different. It should also shed light on why the name in the positive setting is justified. So I will work out both.

---

First an important technique is that of Morleyisation. This is a way of sneaking in some negation in positive formulas. We start with an $h$-inductive theory $T$. For every positive existential formula $\phi(\bar{x})$ we introduce a new relation symbol $N_\phi(\bar{x})$. We then extend $T$ to $T_1$ by adding the $h$-inductive sentences $$ \forall \bar{x}(\phi(\bar{x}) \wedge N_\phi(\bar{x}) \to \bot) \quad\text{and}\quad \forall \bar{x}(\phi(\bar{x}) \vee N_\phi(\bar{x})). $$ That is, $T_1$ expresses that $N_\phi(\bar{x})$ is equivalent to $\neg \phi(\bar{x})$. We iterate this process to build $T = T_0 \subseteq T_1 \subseteq T_2 \subseteq \ldots$, and we let $T' = \bigcup_{n < \omega} T_n$. Then $T'$ has the property that every positive existential formula has a negation. Let's make up a name for this.

Definition. Let $T$ be an $h$-inductive theory, such that for every positive existential formula $\phi(\bar{x})$ there is a positive existential formula $\psi(\bar{x})$ with $$T \models \forall \bar{x}(\neg \phi(\bar{x}) \leftrightarrow \psi(\bar{x})).$$ Then we call $T$ fully negated.

Lemma 1. In a fully negated theory, every first-order formula is equivalent to a positive existential formula.

Proof. First we replace all occurrences of $\forall$ and $\to$ by positive connectives, negation and the existential quantifier. Then the argument easily follows by induction on the complexity of the formula, using the fully negated hypothesis for the negation step. QED.

The point of this is that we can express any first-order theory as an $h$-inductive theory, but in a bigger signature. This process is harmless, because the models do not really change. So in this sense positive logic is a strictly more general setting than first-order logic.

There is already a direct link with positive model completeness.

Proposition 2. For a fully negated $h$-inductive theory $T$ every homomorphism is an elementary embedding. Hence every model is positively closed, so $T$ is positively model complete.

Proof. Let $f: M \to N$ be a homomorphism of models of $T$ and let $\phi(\bar{x})$ be a first-order formula. Then by lemma 1 there is positive existential $\psi(\bar{x})$ that is equivalent (modulo $T$) to $\phi(\bar{x})$. So for $\bar{a} \in M$ we have that $M \models \phi(\bar{a})$ iff $M \models \psi(\bar{a})$, which implies $N \models \psi(f(\bar{a}))$ hence $N \models \phi(f(\bar{a}))$. So $f$ is an elementary embedding. QED.

---

This gives the first interpretation of the question and its answer. If we consider a first-order theory $T$ as an $h$-inductive theory by Morleyising it then we end up with a fully negated theory. So by proposition 2 such a theory is always positively model complete. In other words: if we view positive logic as a generalisation of first-order logic, then this way of defining positive model completeness does not generalise the original notion of model completeness.

---

The name is still justified, and there is a reasonable scenario where the notions do coincide. First let's prove the converse of Proposition 2.

Proposition 3. Let $T$ be an $h$-inductive theory and let $\phi(\bar{x})$ be a first-order formula, such that for any homomorphism $f: M \to N$ of models of $T$ we have that $M \models \phi(\bar{a})$ implies $N \models \phi(f(\bar{a}))$. Then $\phi(\bar{x})$ is equivalent to a positive existential formula $\psi(\bar{x})$ modulo $T$.

Proof. This is just a very slight generalisation of a classical result and the proof is really the same. See e.g. here (Theorem 5) for a proof. The proof actually goes through word for word, if you replace "diagram" by "positive diagram" and "existential formula" by "positive existential formula". QED.

Corollary 4. The following are equivalent for an $h$-inductive theory $T$:

1. $T$ is positively model complete;
2. $T$ is fully negated;
3. every homomorphism between models of $T$ is an elementary embedding.

Proof. The implication (2) $\implies$ (3) is Proposition 2, and (3) $\implies$ (1) is trivial. The remaining (1) $\implies$ (2) follows from Proposition 3. Truth of negations of positive existential formulas is preserved upwards by immersions. Since every homomorphism is an immersion, we conclude that indeed every negation of a positive existential formula must be equivalent to a positive existential formula. QED.

Now back to the technique of Morleyisation: we can also partially Morleyise a theory, by just adding a negation for each relation symbol. So for every relation symbol $R$ we add $N_R$ and let our $h$-inductive theory express that $N_R$ is equivalent to $\neg R$. This way homomorphisms of models of $T$ are just the usual embeddings. For such a theory, the $h$-inductive sentences are the same as $\forall \exists$-formulas. So we can again view every $\forall \exists$-theory as an $h$-inductive theory.

Corollary 5. A $\forall \exists$-theory $T$, considered as $h$-inductive theory, is positively model complete if and only if it is model complete in the classical sense.

Proof. Homomorphisms are precisely embeddings. So such a theory is model complete in the classical sense if and only if every homomorphism is an elementary embedding, which by corollary 4 is equivalent to being positively model complete. QED.