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:
“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)
“I’m a Sunday School teacher, and I’ve always known that the structure of law is founded on the Christian ethic that you shall love the Lord your God and your neighbor as yourself—a very high and perfect standard. We all know the fallibility of man, and the contentions in society, as described by Reinhold Niebuhr and many others, don’t permit us to achieve perfection.”
—Jimmy Carter (James Earl Carter, Jr.)
“How have I been able to live so long outside Nature without identifying myself with it? Everything lives, moves, everything corresponds; the magnetic rays, emanating either from myself or from others, cross the limitless chain of created things unimpeded; it is a transparent network that covers the world, and its slender threads communicate themselves by degrees to the planets and stars. Captive now upon earth, I commune with the chorus of the stars who share in my joys and sorrows.”
—Gérard De Nerval (1808–1855)