𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coding in the Partial Order of Enumerable Sets

✍ Scribed by Leo Harrington; André Nies

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
489 KB
Volume
133
Category
Article
ISSN
0001-8708

No coin nor oath required. For personal study only.

✦ Synopsis

We develop methods for coding with first-order formulas into the partial order E of enumerable sets under inclusion. First we use them to reprove and generalize the (unpublished) result of the first author that the elementary theory of E has the same computational complexity as the theory of the natural numbers. Relativized versions of the coding methods show that the p.o. of 7 0 p and 7 0 q sets are not elementarily equivalent for natural numbers p{q. As a further application, definability of the class of quasimaximal sets in E is obtained. On the other side, we prove theorems limiting coding and definability in E, thereby establishing a sharp contrast between E and other structures occurring in computability theory.

📜 SIMILAR VOLUMES

The Index Set of Injectively Enumerable
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5-Complete
✍ Stephan Wehner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 372 KB

## Abstract I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set __IE__ of injectively enumerable classes. It is easy to see that this set is ∑~5~ in the Arithmetical Hierarchy and I describe a proof for the ∑~5~‐hardness of

Flag Vectors of Eulerian Partially Order
Flag Vectors of Eulerian Partially Ordered Sets
✍ Margaret M. Bayer; Gábor Hetyei 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 244 KB

The closed cone of flag vectors of Eulerian partially ordered sets is studied. A new family of linear inequalities valid for Eulerian flag vectors is given. Half-Eulerian posets are defined. Certain limit posets of Billera and Hetyei are half-Eulerian; they give rise to extreme rays of the cone for