We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free structures, and (...) the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics. (shrink)

Let $\Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $\Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $\operatorname {Aut}(\Gamma)^{\ast}$ , where $\operatorname {Aut}(\Gamma)^{\ast}$ is the group of all isomorphisms and anti-isomorphisms of $\Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nešetřil and Rödl and a strong (...) finite submodel property for $\Gamma$. (shrink)

Disjoint n-amalgamation is a condition on a complete first-order theory specifying that certain locally consistent families of types are also globally consistent. In this article, we show that if a countably categorical theory T admits an expansion with disjoint n-amalgamation for all n, then T is pseudofinite. All theories which admit an expansion with disjoint n-amalgamation for all n are simple, but the method can be extended, using filtrations of Fraïssé classes, to show that certain nonsimple theories are pseudofinite. As (...) case studies, we examine two generic theories of equivalence relations, Tfeq∗ and TCPZ, and show that both are pseudofinite. The theories Tfeq∗ and TCPZ are not simple, but they have NSOP1. This is established here for TCPZ for the first time. (shrink)

This article aims to classify those reducts of expansions of (Q, <) by unary predicates which eliminate quantifiers, and in particular to show that, up to interdefinability, there are only finitely many for a given language. Equivalently, we wish to classify the closed subgroups of Sym(Q) containing the group of all automorphisms of (Q, <) fixing setwise certain subsets. This goal is achieved for expansions by convex predicates, yielding expansions by constants as a special case, and for the expansion by (...) a dense, co-dense predicate. Partial results are obtained in the general setting of several dense predicates. (shrink)

From a logical point of view, Stone duality for Boolean algebras relates theories in classical propositional logic and their collections of models. The theories can be seen as presentations of Boolean algebras, and the collections of models can be topologized in such a way that the theory can be recovered from its space of models. The situation can be cast as a formal duality relating two categories of syntax and semantics, mediated by homming into a common dualizing object, in this (...) case 2.In the present work, we generalize the entire arrangement from propositional to first-order logic, using a representation result of Butz and Moerdijk. Boolean algebras are replaced by Boolean categories presented by theories in first-order logic, and spaces of models are replaced by topological groupoids of models and their isomorphisms. A duality between the resulting categories of syntax and semantics, expressed primarily in the form of a contravariant adjunction, is established by homming into a common dualizing object, now Sets, regarded once as a boolean category, and once as a groupoid equipped with an intrinsic topology.The overall framework of our investigation is provided by topos theory. Direct proofs of the main results are given, but the specialist will recognize toposophical ideas in the background. Indeed, the duality between syntax and semantics is really a manifestation of that between algebra and geometry in the two directions of the geometric morphisms that lurk behind our formal theory. Along the way, we give an elementary proof of Butz and Moerdijkʼs result in logical terms. (shrink)

Given two structures${\cal M}$and${\cal N}$on the same domain, we say that${\cal N}$is a reduct of${\cal M}$if all$\emptyset$-definable relations of${\cal N}$are$\emptyset$-definable in${\cal M}$. In this article the reducts of the Henson digraphs are classified. Henson digraphs are homogeneous countable digraphs that omit some set of finite tournaments. As the Henson digraphs are${\aleph _0}$-categorical, determining their reducts is equivalent to determining the closed supergroupsG≤ Sym of their automorphism groups.A consequence of the classification is that there are${2^{{\aleph _0}}}$pairwise noninterdefinable Henson digraphs which have (...) no proper nontrivial reducts. Taking their automorphisms groups gives a positive answer to a question of Macpherson that asked if there are${2^{{\aleph _0}}}$pairwise nonconjugate maximal-closed subgroups of Sym. By the reconstruction results of Rubin, these groups are also nonisomorphic as abstract groups. (shrink)