Structure of The R.e. Turing Degrees
A degree is called r.e. (recursively enumerable) if it contains a recursively enumerable set. Every r.e. degree is less than or equal to 0′ but not every degree less than 0′ is an r.e. degree.
- (G. E. Sacks, 1964) The r.e degrees are dense; between any two r.e. degrees there is a third r.e degree.
- (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) There are two r.e. degrees with no greatest lower bound in the r.e. degrees.
- (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) There is a pair of nonzero r.e. degrees whose greatest lower bound is 0.
- (S. K. Thomason, 1971) Every finite distributive lattice can be embedded into the r.e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima.
- (A. H. Lachlan and R. I. Soare, 1980) Not all finite lattices can be embedded in the r.e. degrees (via an embedding that preserves suprema and infima). The following particular lattice cannot be embedded in the r.e. degrees:
- (A. H. Lachlan, 1966b) There is no pair of r.e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem.
- (L. A. Harrington and T. A. Slaman, see Nies, Shore, and Slaman (1998)) The first-order theory of the r.e. degrees in the language 〈 0, ≤, = 〉 is many-one equivalent to the theory of true first order arithmetic.
Read more about this topic: Turing Degree
Famous quotes containing the words structure of the, structure of, structure and/or degrees:
“In the extent and proper structure of the Union, therefore, we behold a republican remedy for the diseases most incident to republican government.”
—James Madison (1751–1836)
“... the structure of a page of good prose is, analyzed logically, not something frozen but the vibrating of a bridge, which changes with every step one takes on it.”
—Robert Musil (1880–1942)
“There is no such thing as a language, not if a language is anything like what many philosophers and linguists have supposed. There is therefore no such thing to be learned, mastered, or born with. We must give up the idea of a clearly defined shared structure which language-users acquire and then apply to cases.”
—Donald Davidson (b. 1917)
“The political truths declared in that solemn manner acquire by degrees the character of fundamental maxims of free Government, and as they become incorporated with national sentiment, counteract the impulses of interest and passion.”
—James Madison (1751–1836)