CODING IN THE PARTIAL ORDER OF ENUMERABLE SETS

We develop methods for coding with first-order formulas into the parti al order E of enumerable sets under inclusion. First we use them to re prove and generalize the (unpublished) result of the first author that the elementary theory of E has the same computational complexity as t he theory of the natural numbers. Relativized versions of the coding m ethods show that the p.o. of Sigma(p)(0) and Sigma(q)(0) sets are not elementarily equivalent for natural numbers p not equal q. As a furthe r application, definability of the class of quasimaximal sets in E is obtained. On the other side, we prove theorems limiting coding and def inability in E, thereby establishing a sharp contrast between E and ot her structures occurring in computability theory. (C) 1998 Academic Pr ess.