The Universal Homogenous Binary Tree

Bodirsky, Manuel, Bradley-Williams, David, Pinsker, Michael and Pongracz, Andras (2018) The Universal Homogenous Binary Tree. Journal of Logic and Computation, 28 (1). pp. 133-163. ISSN 0955-792X

[thumbnail of Author Accepted Manuscript]
PDF (Author Accepted Manuscript) - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.


Official URL:


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 (S 2 ;≤). We study the reducts of (S 2 ;≤), that is, the relational structures with domain S 2, all of whose relations are first-order definable in (S 2 ;≤)⁠. Our main result is a classification of the model-complete cores of the reducts of S 2. 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 S 2 that contain the automorphism group of (S 2 ;≤) and are closed with respect to the pointwise convergence topology.

Repository Staff Only: item control page