The reducts of the homogeneous binary branching C-relation

DOI10.1017/JSL.2016.37zbMATH Open1436.03181arXiv1408.2554OpenAlexW2963203731MaRDI QIDQ2976332FDOQ2976332

Authors: Manuel Bodirsky, Peter Jonsson, Trung van Pham 

Publication date: 28 April 2017

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• Title not available (Why is that?)
• Infinitely many reducts of homogeneous structures
• Constants and finite unary relations in qualitative constraint reasoning
• Title not available (Why is that?)
• The universal homogeneous binary tree
• Permutation groups with small orbit growth
• Title not available (Why is that?)
• The reducts of equality up to primitive positive interdefinability
• Title not available (Why is that?)
• Set‐homogeneous hypergraphs

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)