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 (mc-core) if every embedding of into 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 be an -categorical structure. The following conditions are equivalent.
- is an mc-core,
- Every fo formula is equivalent in to an ep formula,
- has a homogeneous expansion by relations , where is the equality, such that for , both the relation and its complement are ep definable in ,
- , 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.
- The structure is an mc-core, since it is homogeneous, and the complement of the relation is ep-definable.
- The structure is not an mc-core. Its mc-core is a singleton with a self-loop.
- The mc-core of the disjoint union of infinitely many 2-cliques is the 2-clique.
- The mc-core of the random graph is the infinite clique.
- 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).
- 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.
- 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,
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.