$A \models \Sigma_1(T)$ iff there is some $T$-model whose every finite substructure is embeddable in $A$?

Question

Given a theory $T$, let $\Sigma_1(T)$ be the set of $T$-provable existential sentences and let $\Pi_1(T)$ be the set of $T$-provable universal sentences. Then for any structure $A$, we have $A \models \Pi_1(T)$ if and only if $A$ is embeddable in a $T$-model. It can be generalized to any $\Pi_n$. The Łoś–Tarski theorem is a consequence of it, as well as the Chang-Łoś–Susko theorem.

So we can ask if something similar is true for $\Sigma_1(T)$ instead of $\Pi_1(T)$. We see that if $B$ is a submodel of $A$ and $B \models T$, then $A \models \Sigma_1(T)$. But the converse is not true. Is the following true?

$A \models \Sigma_1(T)$ if and only if there exists $B \models T$ such that for any finite substructure $F \subseteq B$, there is an embedding $F \subseteq A$.

I also read this statement in a comment under this question:

$A \models \Sigma_1(T)$ if and only if there exists $B \models T$ and $C$ such that $B⊆C$ and $C \equiv A$.

How can one prove that?

Answer 1

Let me handle your second question first.

$A \models \Sigma_1(T)$ if and only if there exists $B \models T$ and $C$ such that $B\subseteq C$ and $C \equiv A$. How can one prove that?

Suppose there exists $B\models T$ and $C$ such that $B\subseteq C$ and $C\equiv A$. For every $\varphi\in \Sigma_1(T)$, we have $B\models \varphi$. Since $\varphi$ is existential, $C\models \varphi$. Since $C\equiv A$, $A\models \varphi$. So $A\models \Sigma_1(T)$.

Conversely, suppose $A\models \Sigma_1(T)$. Let $T' = \text{Th}(A)$. It suffices to show that $\Pi_1(T')\cup T$ is consistent: If $B\models \Pi_1(T')\cup T$, then $B\models T$, $B$ is a substructure of some $C\models T'$, and $C\equiv A$ since $T' = \text{Th}(A)$.

So suppose for contradiction that $\Pi_1(T')\cup T$ is inconsistent. By compactness, there is a universal sentence $\varphi$ such that $T'\models \varphi$ and $T\cup \{\varphi\}$ is inconsistent, so $T\models \lnot \varphi$. But $\lnot\varphi$ is existential, so $\lnot \varphi\in \Sigma_1(T)$. Thus $A\models \varphi$ and $A\models \lnot \varphi$, contradiction.

Ok, now for your first question.

Is the following true? $A \models \Sigma_1(T)$ if and only if there exists $B \models T$ such that for any finite substructure $F \subseteq B$, there is an embedding $F \subseteq A$.

No. Here's a trivial counterexample: Let $B = (\mathbb{N};s)$, where $s$ is the successor function, let $T = \text{Th}(B)$, and let $A = (\{*\};*)$ where $s(*) = *$. Then $A\not\models \Sigma_1(T)$, since $T\models \exists x\, s(x)\neq x$, but every finite substructure of $B$ embeds in $A$ (since the empty structure is the only finite substructure of $B$).

Ok, the obvious thing to try here is to replace "finite" by "finitely generated". Now it's true that if every finitely generated substructure of $B$ embeds in $A$, then $A\models \Sigma_1(T)$. Why? If $\exists x_1\dots x_n\, \psi\in \Sigma_1(T)$, and $B\models T$, then picking witnesses $b_1,\dots,b_n\in B$ for the existential quantifiers, and letting $F = \langle b_1,\dots,b_n\rangle$, we have $F\models \psi(b_1,\dots,b_n)$ since $\psi$ is quantifier-free, and if $f\colon F\to A$ is an embedding, then $A\models \psi(f(b_1),\dots,f(b_n))$, so $A\models \exists x_1\dots x_n\, \psi$.

But the converse is still not true. For example, if we take again $B = (\mathbb{N};s)$ and $T = \text{Th}(B)$, and we let $A$ be the disjoint union of one $s$-cycle of length $n$ for each natural number $n$, then $B$ itself is finitely generated and does not embed in $A$, but $A\models \Sigma_1(T)$. Why? By compactness, there exists a structure $C\equiv A$ with an element $c\in C$ such that $s^n(c)\neq c$ for all $n\in \mathbb{N}$. Then $B$ embeds in $C$ by $n\mapsto s^n(c)$, and we can use the criterion proved above.

On the other hand, if $L$ is a finite relational language (and in particular every finitely generated substructure is finite), then the statement is true. Suppose $A\models \Sigma_1(T)$. Let $T' = \text{Th}(A)$. By the argument above, $\Pi_1(T')\cup T$ is consistent. Let $B\models \Pi_1(T')\cup T$. Now for any finite substructure $F = \{b_1,\dots,b_n\}\subseteq B$, there is a quantifier-free formula $\varphi_F(x_1,\dots,x_n)$ which describes the isomorphism type of $F$ (take the conjunction of all atomic and negated atomic formulas true in $F$). If $A\models \exists x_1\dots x_n\, \varphi_F$, then $F$ embeds in $A$. If not, then $A\models \forall x_1\dots x_n\, \lnot\varphi_F$, so $\forall x_1\dots x_n\, \lnot\varphi_F\in \Pi_1(T')$, and $B\models \forall x_1\dots x_n\, \lnot\varphi_F\in \Pi_1(T')$, contradiction.