Reducts of the random partial order

Details Reducts of the random partial order Reducts of the random partial order

2011-11-30

arxiv.org/abs/1111.7109v1

Mathematics

Logic

15 pages

Scientific paper

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. 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.

Affiliated with

Also associated with

No associations

Rating

Reducts of the random partial order does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reducts of the random partial order, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducts of the random partial order will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7600