Reducts of the random partial order

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 there are precisely five such structures. 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 result lines up with previous similar classifications for the random graph and 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. In the proof we use the new technique of “canonical functions” originally invented in the context of theoretical computer science, which allows for a systematic Ramsey-theoretic analysis of functions acting on the random partial order. The technique identifies patterns in arbitrary functions on the random partial order, which makes them accessible to finite combinatorial arguments.