Definability of model-complete cores

These are some short notes concerning model-complete cores, based on an exposition of Manuel Bodirsky. In particular, he proved that every \omega-categorical structure has a unique (up to isomorphism) model-complete core. We pose the question whether the model-complete core of a definable structure (say, over the equality atoms) is again definable.

Definition. A structure \str A is
a core if every endomorphism of \str A is an embedding, i.e., every homomorphism from \str A to \str A is injective and preserves the relations of \str A and their complements.

Definition. A structure \str A is model-complete (mc-core) if every embedding of \str A into \str A is elementary, i.e., preserves all first-order definable relations.

An existential positive formula (ep formula) is a formula formed by using conjunctions, disjunctions and existential quantification and atomic formulas.

Theorem. Let \str A be an \omega-categorical structure. The following conditions are equivalent.

  1. \str A is an mc-core,
  2. Every fo formula is equivalent in \str A to an ep formula,
  3. \str A has a homogeneous expansion by relations R_0,R_1,R_2,\ldots, where R_0 is the equality, such that for i=0,1,2,\ldots, both the relation R_i and its complement are ep definable in \str A,
  4. end(\str A)=\overline{aut}(\str A), with respect to the topology of pointwise convergence.

Remark. (some) people from Prague take the fourth condition as the definition of a core.

Proof.
(1→2) Let R be an fo-definable relation on \str A; in particular, R is preserved by all elementary maps from \str A to \str A. Since \str A is an mc-core, it follows R that R preserved by all endomorphism from \str A to \str A. Applying an appropriate homomorphism-preservation result, we get that R is ep-definable.

(2→3) We expand \str A by all fo-definable relations. By \omega-categoricity, the resulting structure is homogeneous. Each relation (and its complement) is ep-definable by assumption.

(3→4) Let f:\str A\to \str A be an endomorphism, and let X\subset \str A be a finite subset. Then f preserves every relation R_i and its complement. In particular f induces a partial automorphism g from the substructure of (\str A,R_1,R_2,\ldots) induced by X to the substructure induced by f(X). Since (\str A,R_1,R_2,\ldots) is homogeneous, it follows that g can be extended to an automorphism. The automorphism g is in particular an automorphism of \str A, which agrees with f on X.

(4→1) Assume that \textrm{end}(\str A)\subseteq\overline{\textrm{aut}}(\str A). Then \str A is a core, since each mapping in \overline{\textrm{aut}}(\str A) is elementary.
\square

Theorem (Bodirsky ’06, ’12). Every \omega-categorical structure is homomorphically equivalent to an mc-core, which is moreover unique, up to isomorphism.

Examples.

  1. The structure (\mathbb Q,<) is an mc-core, since it is homogeneous, and the complement of the relation < is ep-definable.
  2. The structure (\mathbb Q,\le) is not an mc-core. Its mc-core is a singleton with a self-loop.
  3. The mc-core of the disjoint union of infinitely many 2-cliques is the 2-clique.
  4. The mc-core of the random graph is the infinite clique.
  5. Let J=(V,E) be the Johnson graph defined as the line graph of the infinite clique. Its mc-core is the infinite clique, since J contains an induced infinite clique (as the line graph of an infinite star).
  6. Let J' be the Johnson graph J=(V,E) expanded additionally by the relation R(x,y)=(x\neq y)\land \neg E(x,y). Then J' is an mc-core. To prove this, we show (1) the relation T(x,y,z), expressing that x,y,z can be extended to a 4-clique in J, and the complement of the relation T, are both ep-definable in (V,E,R), and (2) the structure (V,E,R,T) is homogeneous.
  7. Here is an example of a core (in the sense that endomorphisms are injective) which is not an mc-core: (\str Q^+,<) — the non-negative rationals with the linear order <. The mc-core of this structure is (\str Q,<). This also shows that the mc-core of a structure \str A does not necessarily need to be a surjective image of \str A.
    \squareFrom these examples we see that the mc-core of a structure \str A is often a simpler structure than \str A. The following properties are preserved by taking the mc-core: being a homogeneous structure over a finite relational signature, being a Ramsey structure.Open questions. Are the following properties preserved by taking the mc-core (for \omega-categorical structures):

    • Being interpretable in (\str N,=) (or some other structure),
    • Being an fo-reduct of a homogeneous structure over a finite relational signature,
    • Being (\omega-)stable,
    • Being finitely bounded,
    • etc.

    Some of these questions would be implied by a positive answer to the following question.

    Question.
    Does the mc-core of an \omega-categorical structure \str A interpret in \str A?

    The current construction of the mc-core is non-finitistic.

    Update. The answer to the last question seems to be negative: the mc-core of the universal homogeneous poset (P,\subsetneq) is (\mathbb Q,<), which seems not to interpret in (P,\subsetneq): in this post  we show that there is no 0-interpretation.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>