Siblings of an ℵ0-categorical relational structure

Authors

  • Claude Laflamme
  • Maurice Pouzet
  • Norbert Sauer
  • Robert Woodrow

Abstract

A sibling of a relational structure $R$ is any structure $S$ which can be embedded into $R$ and, vice versa, such that $R$ can be embedded into $S$. Let $\operatorname{sib}(R)$ be the number of siblings of $R$, these siblings being counted up to isomorphism. Thomassé conjectured that for countable relational structures made of at most countably many relations, $\operatorname{sib}(R)$ is either one, countably infinite, or the size of the continuum; but even showing the special case $\operatorname{sib}(R)1$ is one or infinite is unsettled when $R$ is a countable tree.

We prove that if $R$ is countable and $\aleph_{0}$-categorical, then indeed $\operatorname{sib}(R)$ is one or infinite. Furthermore, $\operatorname{sib}(R)$ is one if and only if $R$ is finitely partitionable in the sense of Hodkinson and Macpherson [14]. The key tools in our proof are the notion of monomorphic decomposition of a relational structure introduced in [35] and studied further in [23], [24], and a result of Frasnay [11].

Downloads

Published

2021-06-29

Issue

Section

Articles