TransWikia.com

Examples of $aleph_0$-categorical nonhomogeneous structures

MathOverflow Asked on November 3, 2021

Macpherson in a survey of homogeneous structures, states that there are many $aleph_0$-categorical structures which are not homogeneous. I’d like to know more of such examples.

Edit: The homogeneity mentioned here is the ultrahomogeneity that is defined as every isomorphism between two finite substructures of a structure $M$ can be extended to an automorphism of $M$. There is another homogeneity known as $ℵ_0$-homogeneity that is defined as two $n$-tuples with the same type in $M^n$ must be on the same orbit of $rm Aut$$(M)$.

$aleph_0$-categorical structures need not be ultrahomogeneous, but are always $aleph_0$-homogeneous. So $aleph_0$-homogeneous is a weaker notation than ultrahomogeneous in general. These two types of homogeneity become equivalent if and only if $rm Th$$(M)$ has quantifier elimination.

2 Answers

Here is my favorite example.

Theorem. Fix $ngeq 1$. Then there is a unique (up to isometry) countable metric space $(M_n,d)$ satisfying the following properties:

  1. $d(x,y)in{0,1,2,ldots,n}$ for all $x,yin M_n$
  2. Any finite metric space with distances in ${0,1,2,ldots,n}$ embeds as a subspace of $M_n$.
  3. Any partial isometry between two finite subspaces of $M_n$ extends to a total isometry of $M_n$.

I don't really know who to attribute this to (perhaps Casanovas & Wagner, or Delhomme, Laflamme, Pouzet, Sauer). The point is that the class of finite metric spaces with distances in ${0,1,ldots,n}$ is a Fraisse class in an appropriate relational language, and so $M_n$ is the Fraisse limit. In particular, for all $kleq n$, add a binary relation $d_k(x,y)$ interpreted as "$d(x,y)leq k$". In this language, $M_n$ is homogeneous. But....

View $M_n$ as a graph under just the relation $d_1(x,y)$. Then $M_n$ is still $aleph_0$-categorical because the metric is "definable" from the graph language using existential quantifiers. (Specifically, the defining properties of $M_n$ force the metric $d$ to coincide with the "path metric" given by distance $1$. E.g, $d(x,y)leq 2$ iff $exists z(d_1(x,z)wedge d_1(z,y))$.) However, in the graph language, $M_n$ is homogeneous if and only if $n=1$ or $n=2$. Indeed, if $ngeq 3$ then we can find points $a,b,c,din M_n$ such that $d(a,b)=2$ and $d(c,d)=3$. In the graph language, the finite substructures ${a,b}$ and ${c,d}$ are isomorphic. But an automorphism of $M_n$ has to respect the metric, and so there is no automorphism sending $(a,b)$ to $(c,d)$.

The point, of course, is that by looking only at the distance $1$ relation, we lose quantifier elimination.

Note, on the other hand, $M_1$ is a countably infinite complete graph and $M_2$ is the countable Rado graph, both of which are homogeneous as graphs.

By the way, $M_n$ is an example of what is called a metrically homogeneous graph. For more on these, see Cherlin's work on the classification program for these graphs.

Answered by Gabe Conant on November 3, 2021

How about: dense linear order with endpoints.

It's $aleph_0$-categorical by the same proof as for the case without endpoints.

It's not homogeneous because of the endpoints.

Answered by Bjørn Kjos-Hanssen on November 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP