4
$\begingroup$

Setting

Definition(1). $\mathcal{M} \models T$ is an existentially closed (e.c.) model of $T$ if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists \bar{v} \phi(\bar{v},\bar{a})$, where $\bar{a} \in M$ and $\phi$ is a quantifier free formula, then $\mathcal{M} \models \exists \bar{v} \phi(\bar{v},\bar{a})$.

Definition(2). Let $T$ be a theory. A theory $T^*$ is called the model companion of $T$ if $$\mathcal{M}\models T^* \text{ iff } \mathcal{M} \text{ is an e.c. model of } T$$

So $T^*= \bigcap_{\mathcal{M} \text{ is e.c.} } Th(\mathcal{M})$, where $Th(\mathcal{M})$ is the full theory of $\mathcal{M}$.

Case of study

Let $T$ be the theory of bowtie-free graphs (i.e. $T$ is the theory of graphs plus the axiom that expresses every five points does not form a bowtie), and $mod(T)$ be the class of all models of $T$.

Question(1). Is $mod(T)$ closed under the union of chain? (equivalently we may ask, does $T$ have $\forall\exists$-axiomatization?)

If the answer of the first question is positive, we can ask the following questions.

Question(2). What are the $e.c.$ models of $T$?

Question(3). Does $T$ have model-companion?

$\endgroup$
  • 1
    $\begingroup$ The answer for 1) is easy : if there's a bowtie in the union, then it appears in some finite stage; so it is closed under chain unions. $\endgroup$ – Max Jun 8 at 22:06
  • $\begingroup$ @Max Yes, you're right. I was actually thinking about the third question. I just broke it down into 3 steps to make more sense! $\endgroup$ – user6232017 Jun 8 at 22:19
  • $\begingroup$ Doesn't $T$ have $\forall$-axiomatization? Isn't the class of bowtie-free graphs closed under passage to substructures? $\endgroup$ – bof Jun 13 at 16:20
1
$\begingroup$

The answer to question (3) is yes. This is a theorem of Cherlin, Shelah and Shi in the paper Universal graphs with forbidden subgraphs and algebraic closure. More generally, they prove (Theorem 1) that for any finite set $\mathcal{F}$ of finite graphs, the theory of $\mathcal{F}$-free graphs has a model companion.

The proof of Theorem 1 is fairly constructive, so you can extract an axiomatization of the model companion from the proof. This axiomatization will answer question (2), but maybe not in a way you find satisfying. The best you can hope for in an answer to question (2) is a reduction of the general definition of existentially closed to a more concrete set of instances of existential closure, in the form of "extension axioms".

$\endgroup$
  • $\begingroup$ I'm confused by Example 4.7 of onlinelibrary.wiley.com/doi/pdf/10.1002/malq.201400019 Do we need any assumption on $\mathcal{F}$, the finite set of finite graphs, such that the theory of $\mathcal{F}$-free graphs has a model companion? (It seems that Corollary 4.5 is a direct consequence of Theorem 1 of Cherlin, Shelah and Shi. Am I right?) $\endgroup$ – Mostafa Mirabi Jul 5 at 23:25
  • $\begingroup$ Hi @MostafaMirabi. It is strange that the paper you link to by Takeuchi, Tanaka, and Tsuboi (TTT) does not cite the paper by Cherlin, Shelah, and Shi (CSS). It seems to me that Corollary 4.5 of TTT is exactly the same statement as Theorem 1 of CSS. The confusion you're having with Example 4.7 is probably due to an unfortunate ambiguity in terminology: Does $K$-free mean have no induced subgraphs in $K$, or no (possibly non-induced) subgraphs in $K$? The former is what $K$-free means in TTT (and it's more natural for model theorists), while the latter is what $K$-free means in CSS ... $\endgroup$ – Alex Kruckman Jul 6 at 2:06
  • $\begingroup$ ... and it seems to be the more common usage in graph theory. This is why Corollary 4.5 of TTT speaks of a class $K$ of graphs closed under adding edges. If you take an arbitrary class $K$ and form a new class $K'$ by closing under adding edges, then $K$-free in the CSS sense is equivalent to $K'$-free in the TTT sense. $\endgroup$ – Alex Kruckman Jul 6 at 2:08
  • $\begingroup$ Hi @AlexKruckman. Thank you! Right! In TTT, $K$-free means have no induced subgraph (actually no sub-structure in model theory sense) in $K$, and in CSS it means have no usual subgraph in $K$. Also, in CSS they define a universal graph as a graph that every graph embeds into it as an induced subgraph. So, Theorem 1 of CSS does not hold in the case that we consider induced subgraphs, right? $\endgroup$ – Mostafa Mirabi Jul 6 at 17:41
  • $\begingroup$ @MostafaMirabi That's my understanding, and I guess Example 4.7 of TTT provides a counterexample (but I haven't checked the counterexample myself). $\endgroup$ – Alex Kruckman Jul 6 at 17:49

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.