Ultrahomogeneity and ω \omega -categoricity of monounary algebras

Thomas Quinn-Gregson · 2026

Read Ultrahomogeneity and ω \omega -categoricity of monounary algebras by Thomas Quinn-Gregson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26616.txt.

Introduction

Quinn-Gregson gives a clear account of ultrahomogeneous monounary algebras of any size. A structure is ultrahomogeneous when any map between its small generated parts that keeps the single operation extends to a full symmetry of the whole. Monounary algebras carry just one unary operation, which keeps the setting spare. He shows such an algebra meets the full test exactly when it meets the weaker one based on single elements. He then sets the results beside kindred notions like homogeneity and transitivity, and sorts how they relate.

Catalog record

CREATORThomas Quinn-Gregson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79013
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26616

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ultrahomogeneity and ω \omega -categoricity of monounary algebras Thomas Quinn-Gregson Abstract Ultrahomogeneity and ω \omega -categoricity are two central concepts arising from model theory, with strong connections with oligomorphic permutation groups and quantifier elimination. In particular, both are conditions on the automorphism group of a structure. The aim of this paper is to describe both the ω \omega -categorical monounary algebras and the ultrahomogeneous monounary algebras of arbitrary cardinalities. We show that a monounary algebra is ω \omega -categorical [ultrahomogeneous] if and only if every element has finite height and Aut ⁡ ( 𝒜 ) \Aut(\mathcal{A}) has only finitely many 1-orbits [ 𝒜 \mathcal{A} is 1-ultrahomogeneous]. Our classification of ultrahomogeneous monounary algebras is then viewed in the context of previously studied variants of ultrahomogeneity, including (partial)-homogeneity and transitivity. Keywords: Monounary algebra, ultrahomogeneity, homogeneity, partial homogeneity, \omega -categoricity Subject Classification 2020: 08A60, 03C35, 03C10 1 Introduction A monounary algebra is a set together with a single unary function. Their transparent structure has allowed for a complete description of those monounary algebras which satisfy certain properties which arise in model theory. Examples include transitivity [ 18 ] , homomorphism-homogeneity [ 21 ] , and polymorphism-homogeneity [ 12 ] ; these are conditions on the automorphism group, the endomorphism monoid, and the polymorphism clone of a monounary algebra, respectively. Such a complete picture is rare amongst structures, and indeed no such classifications exist even for classical structures such as graphs, groups, or partially ordered sets. Spurred by this, we consider two of the most widely studied model theoretic properties of this form; ultrahomogeneity and \omega -categoricity. A (first order) structure \mathcal{M} is called n - ultrahomogeneous if every isomorphism between n -generated substructures of \mathcal{M} extends to an automorphism of \mathcal{M} , and is ultrahomogeneous 1 1 1 This is also known as being homogenous . if it is n -ultrahomogeneous for each n\in\mathbb{N} . For several key classes of relational structures, ultrahomogeneity proves to be a strong enough condition to allow for classifications, albeit often only in the countable case. These include graphs [ 22 ] , digraphs [ 6 ] , and partially ordered sets [ 31 ] . For algebras the problem appears far more difficult in general, and indeed Saracino and Wood [ 30 ] showed the existence of 2^{\omega} ultrahomogeneous countable groups. Despite this, ultrahomogeneous abelian groups (of arbitrary cardinality) have been described in [ 7 ] , and ultrahomogeneous finite groups in [ 8 ] . Progress has also been made for rings and non-abelian groups (see, e.g., [ 7 , 9 ] ) and for semilattices and semigroups (see, e.g., [ 11 , 25 , 26 ] ). Our second fundamental property is \omega -categoricity, where a countable structure \mathcal{M} is called \omega -categorical if it can be defined uniquely, up to isomorphism, by its first order properties. The much celebrated Ryll-Nardzewski Theorem states that \omega -categoricity is equivalent to the purely algebraic condition that the automorphism group \Aut(\mathcal{M}) is oligomorphic . That is, for each n\geq 1 the coordinate-wise action of \Aut(\mathcal{M}) on M^{n} has only finitely many orbits. However, \omega -categoricity is often too weak to allow for classifications, with the exception of more simplistic structures such as abelian groups [ 29 ] and linear orders [ 28 ] . For non-abelian groups, it follows from the work in [ 30 ] that there exists 2^{\omega} \omega -categorical groups, and a meaningful classification of \omega -categorical groups thus seems unlikely. Nevertheless, advances in the \omega -categoricity of algebras such as groups, rings, and semigroups continue to be made (see, e.g., [ 1 , 2 , 27 ] ). The main results of this article is a classification of both the ultrahomogeneous and the \omega -categorical monounary algebras. The former result answers in far greater generality the first half of Problem 1 in [ 32 ] , which asks for all countable locally finite ultrahomogeneous monounary algebras (here stated in the language of Fraïssé limits). We will show that much of what determines whether a monounary algebra \mathcal{A} is ultrahomogeneous or \omega -categorical is whether it has the corresponding pointwise property, i.e., is 1-ultrahomogeneous or \Aut(\mathcal{A}) has finitely many orbits on M , respectively. Our results on ultrahomogeneity will allow for further classifications of other similar conditions on the automorphism group of a monounary algebra. Namely, we describe all [partial] homogeneous monounary algebras, that is, ones in which isomorphisms between finite [partial] subalgebras extend to an automorphisms. Moreover, we show the following pleasing connection in greater generality in Theorem 4.15 : Corollary . For the class of monounary algebras we have Transitive automorphism group \displaystyle\Rightarrow\text{partial homogeneous}\Rightarrow\text{ultrahomogeneous} \displaystyle\Rightarrow\text{homogeneous}. This paper is ordered as follows. In Sections 2 and 3 we give a self-contained introduction to model theory and monounary algebras, respectively. In Section 4 we produce a classification of ultrahomogeneous monounary algebras of arbitrary cardinalities. In the context of monounary algebras, a strong link is then shown between ultrahomogeneity and similar conditions on an automorphism group, namely n -partial homogeneity, n -homogeneity, and transitivity. This is then used to classify the ultrahomogeneity of directed pseudoforests. We begin Section 5 by considering locally finite and uniformly locally finite (ULF) monounary algebras. By the Ryll-Nardzewski Theorem these properties are weaker than that of \omega -categoricity. By forming induced semilinear orders from a monounary algebra, where \omega -categoricity is known, we are then able to describe all \omega -categorical monounary algebras. Recent results on monadic stability are then used to show that there exists only countably many \omega -categorical (mono)unary algebras. In Section 6 we discuss the limits of generalizing our results to unary algebras. Throughout, we let \mathbb{N}=\{1,2,\dots\} and \omega=\mathbb{N}\cup\{0\} . 2 Model theory preliminaries In this section we give an introduction to the required model theoretic notions, and refer the reader to [ 16 ] for a detailed study. 2.1 First order structures A signature \tau is a set of relation symbols and function symbols, where each symbol is associated with a natural number, called its arity . A \tau -structure \mathcal{M} is a tuple (M;(X^{\mathcal{M}})_{X\in\tau}) where M is a set (call the domain ) and X^{\mathcal{M}}\subseteq M^{n} if X is a relation symbol of arity n , and X^{\mathcal{M}}\colon M^{n}\rightarrow M if X is a function of arity n ; in the latter case we allow n=0 to model constant symbols. When no confusion may arise we use the same symbol for a relation and its relation symbol, and likewise for functions. Unless stated otherwise, we will assume that the structures \mathcal{A,B,C},\dots have domains A,B,C,\dots . Definition 2.1 . Let \mathcal{M} and \mathcal{N} be a pair of \tau -structures. A bijection g\colon M\rightarrow N is called an isomorphism if • (x_{1},\dots,x_{n})\in R^{\mathcal{M}}\Leftrightarrow(g(x_{1}),\dots,g(x_{n}))\in R^{\mathcal{N}} for every relation symbol R\in\tau , and • g(f^{\mathcal{M}}(x_{1},\dots,x_{n}))=f^{\mathcal{N}}(g(x_{1}),\dots,g(x_{n})) for every function symbol f\in\tau . If, further, \mathcal{M}=\mathcal{N} then g is called an automorphism . The group of automorphisms of \mathcal{M} is denoted by \Aut(\mathcal{M}) . A (binary) relational structure is one in which its signature has only (binary) relation symbols. 2.2 Permutation groups and orbit growth For a set X , we write Sym (X) for the group of all permutations of X . Let G be a permutation group on a

Read the complete text