The universal homogeneous binary tree

Bodirsky, Manuel and Bradley-Williams, David and Pinsker, Michael and Pongrácz, András (2018) The universal homogeneous binary tree. Journal of Logic and Computation, 28 (1). pp. 133-163. ISSN 0955-792X, ESSN: 1465-363X

Preview

Text 1409.2170.pdf Download (578kB) | Preview

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

Actions (login required)

Edit Item