10
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

Here is my favorite example.

Theorem. Fix $n\geq 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,y\in 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 $k\leq 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 $n\geq 3$ then we can find points $a,b,c,d\in 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Macpherson states that for $ℵ_0$-categorical structures, they are homogeneous iff they have quantifier elimination. Why is that? Intuitively, $ℵ_0$-categorical structures along can have quantifier elimination. $\endgroup$
    – Eugene Zhang
    Commented Jul 15, 2020 at 20:09
  • 3
    $\begingroup$ @hermes When Macpherson says a countable structure $M$ in a relational language is homogeneous, he means that every isomorphism between finite substructures extends to an automorphism of $M$. It is easy to see that this is equivalent to the following condition: if $\overline{a}$ and $\overline{b}$ are finite tuples with the same quantifier-free type, then there is an automorphism $\sigma\in \mathrm{Aut}(M)$ such that $\sigma(\overline{a}) = \overline{b}$. In other sources (e.g. Hodges), this condition is sometimes called "ultrahomogeneity". $\endgroup$
    – Alex Kruckman
    Commented Jul 15, 2020 at 20:19
  • 3
    $\begingroup$ It is also a theorem that every $\aleph_0$-categorical structure $M$ is $\aleph_0$-homogeneous, which means that if $\overline{a}$ and $\overline{b}$ are finite tuples with the same type, then there is an automorphism $\sigma\in \mathrm{Aut}(M)$ such that $\sigma(\overline{a}) = \overline{b}$ (this holds because $M$ is atomic, and also because $M$ is saturated). These two conditions, ultahomogeneity and $\aleph_0$-homogeneity, are equivalent if and only if the quantifier-free type of a tuple determines its type, i.e. exactly when $\text{Th}(M)$ has quantifier elimination. $\endgroup$
    – Alex Kruckman
    Commented Jul 15, 2020 at 20:21
  • 3
    $\begingroup$ @hermes No. To reiterate Alex's main points: for Macpherson, "homogeneous" means "ultrahomogeneous" and $\aleph_0$-categorical structures need not be ultrahomogeneous. $\aleph_0$-categorical structures are always $\aleph_0$-homogeneous, which is a weaker notation than ultrahomogeneous in general. They become equivalent in the presence of QE. $\endgroup$
    – Gabe Conant
    Commented Jul 16, 2020 at 11:38
13
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Looks like one can do something similar from any $\aleph_0$-categorical theory by adding finitely many constants. $\endgroup$
    – YCor
    Commented Jul 16, 2020 at 21:41
  • $\begingroup$ @YCor well, in my example it's important that the endpoints are not named by constants, so I'm not sure about that $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jul 16, 2020 at 21:46
  • $\begingroup$ In which way is it important for the question? one could consider an poset with two constants in which the order is total and dense without endpoints outside the constants, and the constants are incomparable to the other elements. $\endgroup$
    – YCor
    Commented Jul 16, 2020 at 21:50
  • 1
    $\begingroup$ @YCor ah okay, yes I think that works. Only these would not be "constants" in the usual sense; they will not be interpretations of constant symbols in the first-order language. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jul 16, 2020 at 21:54
  • 2
    $\begingroup$ @hermes it's the back and forth argument + the observation that endpoints are sent to endpoints by isomorphism $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jul 19, 2020 at 4:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .