The universal homogeneous binary tree

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Manuel Bodirsky - , Institute of Algebra, TUD Dresden University of Technology (Author)
  • David Bradley-Williams - , Heinrich Heine University Düsseldorf (Author)
  • Michael Pinsker - , Charles University Prague (Author)
  • András Pongrácz - , University of Debrecen (Author)

Abstract

A partial order is called semilinear if the upper bounds of each element are linearly ordered and any two elements have a common upper bound. There exists, up to isomorphism, a unique countable existentially closed semilinear order, which we denote by (S2;≤). We study the reducts of (S2;≤), i.e. the relational structures with domain S2, all of whose relations are first-order definable in (S2;≤). Our main result is a classification of the model-complete cores of the reducts of S2. From this, we also obtain a classification of reducts up to first-order interdefinability, which is equivalent to a classification of all subgroups of the full symmetric group on S2 that contain the automorphism group of (S2;≤) and are closed with respect to the pointwise convergence topology.

Details

Original languageEnglish
Article number043
Pages (from-to)133-164
Number of pages32
JournalJournal of logic and computation
Volume28
Issue number1
Publication statusPublished - 1 Feb 2018
Peer-reviewedYes

External IDs

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

Keywords

Keywords

  • constraint satisfaction problem, endomorphism monoid, model companion, model-complete core, permutation group, reduct, Semilinear order