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, structure and/or degrees:
“... 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)
“What is the structure of government that will best guard against the precipitate counsels and factious combinations for unjust purposes, without a sacrifice of the fundamental principle of republicanism?”
—James Madison (1751–1836)
“No sooner met but they looked; no sooner looked but they loved; no sooner loved but they sighed; no sooner sighed but they asked one another the reason; no sooner knew the reason but they sought the remedy; and in these degrees have they made a pair of stairs to marriage, which they will climb incontinent, or else be incontinent before marriage.”
—William Shakespeare (1564–1616)