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 -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 is a core if every endomorphism of is an embedding, i.e., every homomorphism from to is injective and preserves the relations of and their complements.

Definition. A structure is model-complete if every embedding of into is elementary, i.e., preserves all first-order definable relations.

An mc-core is a model-complete core, i.e., a structure in which every endomorphism is elementary.

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

Theorem. Let be an -categorical structure. The following conditions are equivalent.

  1. is an mc-core,
  2. Every fo formula is equivalent in to an ep formula,
  3. has a homogeneous expansion by relations , where is the equality, such that for , both the relation and its complement are ep definable in ,
  4. , with respect to the topology of pointwise convergence.

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

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

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

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

(4→1) Assume that . Then is a core, since each mapping in is elementary.

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


  1. The structure is an mc-core, since it is homogeneous, and the complement of the relation is ep-definable.
  2. The structure 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 be the Johnson graph defined as the line graph of the infinite clique. Its mc-core is the infinite clique, since contains an induced infinite clique (as the line graph of an infinite star).
  6. Let be the Johnson graph expanded additionally by the relation . Then is an mc-core. To prove this, we show (1) the relation , expressing that can be extended to a 4-clique in , and the complement of the relation , are both ep-definable in , and (2) the structure is homogeneous.
  7. Here is an example of a core (in the sense that endomorphisms are injective) which is not an mc-core: — the non-negative rationals with the linear order . The mc-core of this structure is . This also shows that the mc-core of a structure does not necessarily need to be a surjective image of .
    From these examples we see that the mc-core of a structure is often a simpler structure than . 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 -categorical structures):

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

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

    Does the mc-core of an -categorical structure interpret in ?

    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 is , which seems not to interpret in : 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>