The reducts of the homogeneous binary branching C-relation

DOI10.1017/JSL.2016.37MaRDI QIDQ2976332zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Peter Jonsson, Trung van Pham

Publication date 28 April 2017

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2554

zbMATH Keywords

homogeneous structuresmodel-completenessendomorphism monoidstree-like structuresomega-categoricity\(C\)-relationfirst-order reducts

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Automorphisms and endomorphisms of algebraic structures (08A35) Equational classes, universal algebra in model theory (03C05) Basic properties of first-order languages and structures (03C07) Infinite automorphism groups (20B27) Applications of model theory (03C98)

Abstract: Let (L;C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of (L;C), i.e., the structures with domain L that are first-order definable in (L;C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of (L;C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.

Recommendations

• The 116 reducts of (ℚ, <, a)
• Infinitely many reducts of homogeneous structures
• The reducts of equality up to primitive positive interdefinability
• The universal homogeneous binary tree
• Reducts of the generic digraph

Cites work

• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• A Ramsey theorem for trees
• A generalization of Ramsey's theorem for regular trees
• A survey of homogeneous structures
• Cell decompositions of C-minimal structures
• Extension operations on sets of leaf-labelled trees
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Minimal functions on the random graph
• Notes on infinite permutation groups
• On variants of \(o\)-minimality
• Quelques problèmes combinatoires concernant les ordres totaux et les rélations monomorphes
• Ramsey Classes and Homogeneous Structures
• Reducts of the random partial order
• Relations related to betweenness: their structure and automorphisms
• SOME TREELIKE OBJECTS
• The 42 reducts of the random ordered graph
• The complexity of reconstructing trees from qualitative characters and subtrees
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
• Transitivity of permutation groups on unordered sets

Cited in

(10)

• Set‐homogeneous hypergraphs
• scientific article; zbMATH DE number 5596976 (Why is no real title available?)
• Infinitely many reducts of homogeneous structures
• Constants and finite unary relations in qualitative constraint reasoning
• Permutation groups with small orbit growth
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• The universal homogeneous binary tree
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• The reducts of equality up to primitive positive interdefinability
• scientific article; zbMATH DE number 1404138 (Why is no real title available?)

This page was built for publication: The reducts of the homogeneous binary branching \(C\)-relation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976332)