Reducts of the random partial order
From MaRDI portal
Abstract: We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that these structures fall into precisely five equivalence classes. We achieve this result by showing that there exist exactly five closed permutation groups which contain the automorphism group of the random partial order, and thus expose all symmetries of this structure. Our classification lines up with previous similar classifications, such as the structures definable in the random graph or the order of the rationals; it also provides further evidence for a conjecture due to Simon Thomas which states that the number of structures definable in a homogeneous structure in a finite relational language is, up to first-order interdefinability, always finite. The method we employ is based on a Ramsey-theoretic analysis of functions acting on the random partial order, which allows us to find patterns in such functions and make them accessible to finite combinatorial arguments.
Recommendations
Cites work
- scientific article; zbMATH DE number 1007358 (Why is no real title available?)
- scientific article; zbMATH DE number 1943960 (Why is no real title available?)
- A new operation on partially ordered sets.
- A survey of homogeneous structures
- Decidability of definability
- Minimal functions on the random graph
- Reducts of Ramsey structures
- Reducts of random hypergraphs
- Reducts of the random graph
- The 116 reducts of (ℚ, <, a)
- The complexity of temporal constraint satisfaction problems
- The reducts of equality up to primitive positive interdefinability
- Transitivity of permutation groups on unordered sets
Cited in
(20)- Reducts of Ramsey structures
- Permutations on the random permutation
- The Behavior of Random Reduced Bases
- \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
- The 42 reducts of the random ordered graph
- Ramsey degrees: big v. small
- Permutation groups with small orbit growth
- A new operation on partially ordered sets.
- Functional reducts of the countable atomless Boolean algebra
- Reducts of structures and maximal-closed permutation groups
- On methods for generating random partial orders
- An algebraic view on p-admissible concrete domains for lightweight description logics
- Reducts of the generic digraph
- Linear extensions of a random partial order
- Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
- The reducts of the homogeneous binary branching \(C\)-relation
- scientific article; zbMATH DE number 7406819 (Why is no real title available?)
- Using model theory to find decidable and tractable description logics with concrete domains
- Partial ordering of degrees of alternative m-reducibility
- Infinitely many reducts of homogeneous structures
This page was built for publication: Reducts of the random partial order
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462283)
