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 if every embedding of $\str A$ into $\str A$ 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 $\str A$ be an $\omega$ -categorical structure. The following conditions are equivalent.

$\str A$ is an mc-core,
Every fo formula is equivalent in $\str A$ to an ep formula,
$\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$ ,
$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.

The structure $(\mathbb Q,<)$ is an mc-core, since it is homogeneous, and the complement of the relation $<$ is ep-definable.
The structure $(\mathbb Q,\le)$ 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 $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).
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.
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 $(\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.

Atompress

Definability of model-complete cores

Leave a Reply Cancel reply

Computation with atoms