The universal homogeneous binary tree

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Manuel Bodirsky - , Institut für Algebra, Technische Universität Dresden (Autor:in)
  • David Bradley-Williams - , Heinrich Heine Universität Düsseldorf (Autor:in)
  • Michael Pinsker - , Karlsuniversität Prag (Autor:in)
  • András Pongrácz - , University of Debrecen (Autor:in)

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

OriginalspracheEnglisch
Aufsatznummer043
Seiten (von - bis)133-164
Seitenumfang32
FachzeitschriftJournal of logic and computation
Jahrgang28
Ausgabenummer1
PublikationsstatusVeröffentlicht - 1 Feb. 2018
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Schlagwörter

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