All reducts of the random graph are model-complete

Details All reducts of the random graph are model-complete All reducts of the random graph are model-complete

2009-03-14

arxiv.org/abs/0903.2553v3

Mathematics

Logic

Technical report not intended for publication in a journal. Subsumed by the more recent article 1003.4030. Length 14 pages.

Scientific paper

We study locally closed transformation monoids which contain the automorphism group of the random graph. We show that such a transformation monoid is locally generated by the permutations in the monoid, or contains a constant operation, or contains an operation that maps the random graph injectively to an induced subgraph which is a clique or an independent set. As a corollary, our techniques yield a new proof of Simon Thomas' classification of the five closed supergroups of the automorphism group of the random graph; our proof uses different Ramsey-theoretic tools than the one given by Thomas, and is perhaps more straightforward. Since the monoids under consideration are endomorphism monoids of relational structures definable in the random graph, we are able to draw several model-theoretic corollaries: One consequence of our result is that all structures with a first-order definition in the random graph are model-complete. Moreover, we obtain a classification of these structures up to existential interdefinability.

Affiliated with

Also associated with

No associations

Rating

All reducts of the random graph are model-complete 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 All reducts of the random graph are model-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and All reducts of the random graph are model-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236026