Re: looking for a good reference on Turing degrees and hyperdegrees

From: Robert E. Beaudoin (rbeaudoin_at_comcast.net)
Date: 02/24/05

  • Next message: Robert E. Beaudoin: "Re: Union of Uncountable Totally Imperfect Sets" 
    Date: Thu, 24 Feb 2005 02:00:07 +0000 (UTC)

    Ali Enayat wrote:
    > On Wed, 23 Feb 2005 16:00:13 +0000 (UTC), David Madore wrote:
    >
    >>Hi.
    >>
    >>I'm looking for a good reference book (or possibly article) which
    >>would explain clearly and synthetically various known facts about
    >>Turing degrees and hyperdegrees.
    >>
    >
    >
    >
    > Here are two recommendations:
    >
    > 1. Higher Recursion Theory, by Gerlad Sacks:
    >
    > http://www.aslonline.org/books-perspectives-list.html
    >
    > 2. Classical Recursion Theory, by Piergorgio Odifreddi:
    >
    > http://www.elsevier.com/wps/find/bookdescription.cws_home/502130/description#description
    >
    > I can also answer one of your questions. You asked:
    >
    >
    >>If A is a subset of N, we can define the smallest countable ordinal
    >>CK(A)which is not the order type of a well-ordering of N computable
    >
    >>from A (so CK(0) is the usual Church-Kleene omega_1): what can be
    >
    >>said about the range of the CK?
    >
    >
    > The answer is: the range of the CK operation is precisely the
    > admissible ordinals [an ordinal alpha is admissible if the
    > constructible universe up to alpha satisfies a decent fragment of ZF
    > set theory, known as KP (for Kripke-Platek)].
    >
    > One direction of this result is easy (that every CK(X) is admissible),
    > but the other direction is deep, and was proved by Gerald Sacks in the
    > 1960's using forcing. Shortly thereafter, the joint work of
    > Friedman-Jensen derived Sacks' result as a corollary of the "Barwise
    > Compactness Theorem".
    >
    > Later, Jensen proved the following remarkable extension of Sacks'
    > theorem:
    >
    > If alpha_1 < alpha_2 < ...< alpha_n < ...
    >
    > is an increasing sequence of admissible countable ordinals, then there
    > is a subset X of natural numbers such that
    >
    > alpha_n = the n-th iterate of the CK operator applied to X.
    >
    >
    > Regards,
    >
    > Ali Enayat
    >

    You might also be interested in:

    Recursive Aspects of Descriptive Set Theory (Oxford Logic Guides, #11),
    Richard Mansfield and Galen Weitkamp, OUP/Clarendon Press, 1985.

    This slim volume packs an impressive amount of recursion- and set-
    theoretic goodness into about 150 pages. The emphasis is more on
    descriptive set theory (and related topics) than recursion theory,
    but there is an introduction to hyperarithmetic sets, and to
    admissible ordinals (e.g. a proof of the above characterization of
    them as Church-Kleene ordinals). Unfortunately its out of print, but
    your local library may have a copy.

    Hope this helps,

    Bob Beaudoin

  • Next message: Robert E. Beaudoin: "Re: Union of Uncountable Totally Imperfect Sets"