The reducts of the homogeneous binary branching C-relation

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Manuel Bodirsky - , Institute of Algebra, TUD Dresden University of Technology (Author)
  • Peter Jonsson - , Linköping University (Author)
  • Trung Van Pham - , Vienna University of Technology (Author)

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.

Details

Original languageEnglish
Pages (from-to)1255-1297
Number of pages43
JournalJournal of Symbolic Logic
Volume81
Issue number4
Publication statusPublished - 1 Dec 2016
Peer-reviewedYes

External IDs

ORCID /0000-0001-8228-3611/work/142241098

Keywords

ASJC Scopus subject areas

Keywords

  • C-relation, Endomorphism monoids, First-order reducts, Homogeneous structures, Model-completeness, Omega-categoricity, Tree-like structures