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:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“... the structure of our public morality crashed to earth. Above its grave a tombstone read, “Be tolerant—even of evil.” Logically the next step would be to say to our commonwealth’s criminals, “I disagree that it’s all right to rob and murder, but naturally I respect your opinion.” Tolerance is only complacence when it makes no distinction between right and wrong.”
—Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 2, ch. 2 (1962)
“A special feature of the structure of our book is the monstrous but perfectly organic part that eavesdropping plays in it.”
—Vladimir Nabokov (1899–1977)
“The most durable thing in writing is style, and style is the most valuable investment a writer can make with his time. It pays off slowly, your agent will sneer at it, your publisher will misunderstand it, and it will take people you have never heard of to convince them by slow degrees that the writer who puts his individual mark on the way he writes will always pay off.”
—Raymond Chandler (1888–1959)