The universal homogeneous binary tree
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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 language | English |
---|---|
Article number | 043 |
Pages (from-to) | 133-164 |
Number of pages | 32 |
Journal | Journal of logic and computation |
Volume | 28 |
Issue number | 1 |
Publication status | Published - 1 Feb 2018 |
Peer-reviewed | Yes |
External IDs
ORCID | /0000-0001-8228-3611/work/142241091 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- constraint satisfaction problem, endomorphism monoid, model companion, model-complete core, permutation group, reduct, Semilinear order