Abstract Feedback is oracle computability when the oracle consists exactly of the con- and divergence information about computability relative to that same oracle. Here we study two possible feedback hyperjumps and characterize each of them as the complete $\varSigma _1$ set relative to a level of Gödel’s constructible hierarchy $L$.

Abstract Feedback computability is computation with an oracle that contains the correct convergence/divergence information for all computations calling that same oracle. Here we study feedback Turing computability, as well as feedback for some smaller classes of computation. We also examine some versions of parallelization of these notions.

Abstract We show that several weakenings of the Cauchy condition are all equivalent under the assumption of countable choice, and investigate to what extent choice is necessary. We also show that the syntactically reminiscent notion of metastability allows similar variations, but is empty in terms of its constructive content.1

Abstract Varieties of the Fan Theorem have recently been developed in reverse constructive mathematics, corresponding to different continuity principles. They form a natural implicational hierarchy. Earlier work showed all of these implications to be strict. Here we reprove one of the strictness results, using very different arguments. The technique used is a mixture of realizability, forcing in the guise of Heyting-valued models, and Kripke models.

Abstract We separate many of the basic fragments of classical logic which are used in reverse constructive mathematics. A group of related Kripke and topological models is used to show that various fragments of the Weak Law of the Excluded Middle, the Limited Principle of Omniscience, and Markov’s Principle, including Weak Markov’s Principle, do not imply each other.

The notion of a feedback query is a natural generalization of choosing for an oracle the set of indices of halting computations. Notice that, in that setting, the computations being run are different from the computations in the oracle: the former can query an oracle, whereas the latter cannot. A feedback computation is one that can query an oracle, which itself contains the halting information about all feedback computations. Although this is self-referential, sense can be made of at least some such computations. This threatens, though, to obliterate the distinction between con- and divergence: before running a computation, a machine can ask the oracle whether that computation converges, and then run it if and only if the oracle says "yes." This would quickly lead to a diagonalization paradox, except that a new distinction is introduced, this time between freezing and non-freezing computations. The freezing computations are even more extreme than the divergent ones, in that they prevent the dovetailing on all computations into a single run. In this paper, we study feedback around Turing computability. In one direction, we examine feedback Turing machines, and show that they provide exactly hyper arithmetic computability. In the other direction, Turing computability is itself feedback primitive recursion (at least, one version thereof). We also examine parallel feedback. Several different notions of parallelism in this context are identified. We show that parallel feedback Turing machines are strictly stronger than sequential feedback TMs, while in contrast parallel feedback p.r. Is the same as sequential feedback p.r.

Abstract Varieties of the Fan Theorem have recently been developed in reverse constructive mathematics, corresponding to different continuity principles. They form a natural implicational hierarchy. Some of the implications have been shown to be strict, others strict in a weak context, and yet others not at all, using disparate techniques. Here we present a family of related Kripke models which separates all of the as yet identified fan theorems.

Abstract BD-N is a weak principle of constructive analysis. Several interesting principles implied by BD-N have already been identified, namely the closure of the anti-Specker spaces under product, the Riemann Permutation Theorem, and the Cauchyness of all partially Cauchy sequences. Here these are shown to be strictly weaker than BD-N, yet not provable in set theory alone under constructive logic.

Abstract We give the natural topological model for ¬BD-ℕ, and use it to show that the closure of spaces with the anti-Specker property under product does not imply BD-ℕ. Also, the natural topological model for ¬BD is presented. Finally, for some of the realizability models known indirectly to falsify BD-ℕ, it is brought out in detail how BD-ℕ fails.

There has been increasing interest in intuitionistic methods over the years. Still, there has been relatively little work on intuitionistic set theory, and most of that has been on intuitionistic ZF. This investigation is about intuitionistic admissibility and theories of similar strength. There are several more particular goals for this paper. One is just to get some more Kripke models of various set theories out there. Those papers that have dealt with IZF usually were more proof-theoretic in nature, and did not provide models. Furthermore, the inspirations for many of the constructions here are classical forcing arguments. Although the correspondence between the forcing and the Kripke constructions is not made tight, the relationship between these two methods is of interest (see [6] for instance) and some examples, even if only suggestive, should help us better understand the relationship between forcing and Kripke constructions. Along different lines, the subject of least and greatest fixed points of inductive definitions, while of interest to computer scientists, has yet to be studied constructively, and probably holds some surprises. Admissibility is of course the proper set-theoretic context for this study. Finally, while most of the classical material referred to here has long been standard, some of it has not been well codified and may even be unknown, so along the way we'll even fill in a gap in the classical literature. The next section develops the basics of IKP, including some remarks on fixed points of inductive definitions.

Inductive definability has been studied for some time already. Nonetheless, there are some simple questions that seem to have been overlooked. In particular, there is the problem of the expressibility of the μ-calculus. The μ-calculus originated with Scott and DeBakker [SD] and was developed by Hitchcock and Park [HP], Park [Pa], Kozen [K], and others. It is a language for including inductive definitions with first-order logic. One can think of a formula in first-order logic (with one free variable) as defining a subset of the universe, the set of elements that make it true. Then “and” corresponds to intersection, “or” to union, and “not” to complementation. Viewing the standard connectives as operations on sets, there is no reason not to include one more: least fixed point. There are certain features of the μ-calculus coming from its being a language that make it interesting. A natural class of inductive definitions are those that are monotone: if X ⊃ Y then Γ (X) ⊃ Γ (Y) (where Γ (X) is the result of one application of the operator Γ to the set X). When studying monotonic operations in the context of a language, one would need a syntactic guarantor of monotonicity. This is provided by the notion of positivity. An occurrence of a set variable S is positive if that occurrence is in the scopes of exactly an even number of negations (the antecedent of a conditional counting as a negation). S is positive in a formula ϕ if each occurrence of S is positive. Intuitively, the formula can ask whether x ∊ S, but not whether x ∉ S. Such a ϕ can be considered an inductive definition: Γ (X) = {x ∣ ϕ(x), where the variable S is interpreted as X}. Moreover, this induction is monotone: as X gets bigger, ϕ can become only more true, by the positivity of S in ϕ. So in the μ-calculus, a formula is well formed by definition only if all of its inductive definitions are positive, in order to guarantee that all inductive definitions are monotone.

The program of reverse mathematics has usually been to find which parts of set theory, often used as a base for other mathematics, are actually necessary for some particular mathematical theory. In recent years, Slaman, Groszek, et al, have given the approach a new twist. The priority arguments of recursion theory do not naturally or necessarily lead to a foundation involving any set theory; rather, Peano Arithmetic (PA) in the language of arithmetic suffices. From this point, the appropriate subsystems to consider are fragments of PA with limited induction. A theorem in this area would then have the form that certain induction axioms are independent of, necessary for, or even equivalent to a theorem about the Turing degrees. (See, for examples, [C], [GS], [M], [MS], and [SW].) As go the integers so go the ordinals. One motivation of α-recursion theory (recursion on admissible ordinals) is to generalize classical recursion theory. Since induction in arithmetic is meant to capture the well-foundedness of ω, the corresponding axiom in set theory is foundation. So reverse mathematics, even in the context of a set theory (admissibility), can be changed by the influence of reverse recursion theory. We ask not which set existence axioms, but which foundation axioms, are necessary for the theorems of α-recursion theory. When working in the theory KP – Foundation Schema (hereinafter called KP−), one should really not call it α-recursion theory, which refers implicitly to the full set of axioms KP. Just as the name β-recursion theory refers to what would be α-recursion theory only it includes also inadmissible ordinals, we call the subject of study here γ-recursion theory. This answers a question by Sacks and S. Friedman, “What is γ-recursion theory?”

The mu -calculus is a language consisting of standard first-order finitary logic with a least fixed-point operator applicable to positive inductive definitions. The main theorem of this study is a set-theoretic characterization of the sets of integers definable in the mu -calculus. Another theorem used but not proved is a prenex normal form theorem for the mu -calculus.>

Does every countable set of hyperdegrees have a minimal upper bound? This question remains unanswered. In this paper, we extend the known results. The standard way to construct minimal upper bounds for degrees is to force with pointed perfect trees. This works for hyperdegrees, in the right context. Sacks [Sa] showed that if an admissible set A satisfies Σ1 DC, then forcing with its uniformly hyperarithmetically pointed perfect trees yields a minimal upper bound for the degrees in A. A next question is whether Σ1DC is necessary. Abramson [A] built an admissible set such that Sacks forcing, or anything like it, would not produce a minimal upper bound. He left open the question, though, whether there is such a bound for his set. We answer this question affirmatively. In §II we summarize the previous relevant results, including Steel forcing. In §III we give a construction different from Abramson's of an admissible set for which Sacks forcing does not produce the desired bound. We present this alternative because it is different (although still based on Steel forcing), simpler than the original, and fully illustrates the technique of finding the bound, which applies equally well to the earlier example. §IV describes the construction of the bound. §V closes with questions. I thank Professor Sy Friedman for bringing this problem to my attention. This paper is dedicated to Professor Alexander Kechris on the occasion of his fortieth birthday, and to the Los Angeles VIGOL on its tenth anniversary.

In the paper mentioned in the title (this Journal, vol. 52 (1987), pp. 208–213), it is shown that if ⊨ “V = HC is recursively inaccessible” is ω-standard -nonstandard, then = s.p.( ) has at most four r. e. degrees. They are 0 = deg(∅), = deg{e ∣ We is a recursive well-ordering of ω}, = deg{R ∣ ⊨ “R codes a well-ordering”}, and ∨ . Furthermore, 0 < < ∨ and 0 < . Then it is claimed that < < ∨ and = ∨ if are each possible. In fact, < < ∨ always. The mistake in the argument is that the model ≤T is really a structure on a set, which we may as well take as ω: there is an R ⊆ ω × ω, R ≤T , and ‹ω, R› ≃ . So a copy of coded as a relation on ω is ≤ over . But there is no reason to think that the restriction of the isomorphism of and ‹ω, R› to is Σ1( ).

Abstract We combine two techniques of set theory relating to mininal degrees of constructibility. Jensen constructed a minimal real which is additionally a singleton. Groszek built an initial segment of order type 1 + α*, for any ordinal α. This paper shows how to force a singleton such that the c-degrees beneath it, all represented by reals, are of type 1 + α*, for many ordinals α. We also examine the definability α needs to be so represented by a real.

Constructions of minimal Turing degrees have been generalized to embed partial orders as initial segments.Lachlan [4], , Lerman [6,7], and Abraham-Shore [2] have been quite successful in getting positive results, the strongest formulation being that every col-sized locally countable upper semilattice is an ideal in the Turing degrees.Minimal degree proofs carry over almost verbatim to other contexts, such as hyperdegrees, A~-degrees, and c-degrees.In contrast, the differences among these notions express themselves when considering more complicated orders.For instance, Adamowicz [1] uses more complicated machinery to get only that a well-founded upper semi-lattice can be realized via forcing as the structure of the c-degrees.In this paper, we make the distinction among these notions of degree sharper by showing that a general class of partial orders cannot be so realized.Theorem.Suppose U is a countable lattice with a top element, and ~ ~ U. Then U is complete (closed under infinitary ^ and v ).Proof.As a warm-up, we start with some easy cases.Let U = to + to*.Suppose R realizes U. We build a real T which falls in the cut.Identify to with to x to recursively.Let R(0)= R. At stage n, choose the L[R(n)]-least representative of the nth degree and put it in T's nth slot.Let R(n + 1) be the L[R(n)]-least representative of the (n + 1)*th degree.We have coded a representative of each degree from the to-sequence into T, so Vn deg(T)>n.T<~cR(n) Vn since R(n) needs only the finitely many choices of the representatives for the kth degrees, k < n, to replicate the construction.This is a contradiction.Let U-1 + Q + 1.Let R realize U.The former proof won't work directly, since there is no canonical isomorphism between Q and the c-degrees.If we merely choose an (to + to*)-sequence around an irrational cut, there is no * Research supported by NSF grant DMS 84-14103.The author would like to thank Professor Richard Shore for his assistance in the formulation and solution of this problem.

Much of recursion theory centers on the structures of different kinds of degrees. Classically there are the Turing degrees and r. e. Turing degrees. More recently, people have studied α-degrees for α an ordinal, and degrees over E-closed sets and admissible sets. In most contexts, deg(0) is the bottom degree and there is a jump operator' such that d' is the largest degree r. e. in d and d' > d. Both the degrees and the r. e. degrees usually have a rich structure, including a relativization to the cone above a given degree. A natural exception to this pattern was discovered by S. Friedman [F], who showed that for certain admissible ordinals β the β-degrees ≥ 0′ are well-ordered, with successor provided by the jump. For r. e. degrees, natural counterexamples are harder to come by. This is because the constructions are priority arguments, which require only mild restrictions on the ground model. For instance, if an admissible set has a well-behaved pair of recursive well-orderings then the priority construction of an intermediate r. e. degree (i.e., 0 < d < 0′) goes through [S]. It is of interest to see just what priority proofs need by building (necessarily pathological) admissible sets with few r. e. degrees. Harrington [C] provides an admissible set with two r. e. degrees, via forcing. A limitation of his example is that it needs ω1 (more accurately, a local version thereof) as a parameter. In this paper, we find locally countable admissible sets, some with three r. e. degrees and some with four.

The Turing jump can easily be iterated any finite number of times. The challenge is posed by by transfinite iterations. a(ω) has an intuitively compelling definition: {‹m, n›: n ∈ a(m)}. Starting with Putnam et al. [1], [2], [9] and culminating in Jockusch-Simpson [8] and Hodes [6], recent work has justified this ω-jump and extended it through . Of great use are the master codes of Jensen [3], [7]. Briefly, a Δn(Lβ)-master code is a complete Δn(Lβ) set of ordinals, with supremum as small as possible. Connections with classical recursion theory are tight. When the Δn(Lβ) master codes are reals, they are Turing equivalent. If a is a Δn(Lβ) MC, then a′ is a Δn + 1(Lβ) MC. Intuitively satisfying transfinite jumps, such as the ω-jump above, produce a Turing jump hierarchy equal to an initial segment of the master codes. Hodes capitalized on these facts by defining 0α, α < , set-theoretically as the degree of the αth MC which is a real, and then proving the equivalence of a jump-theoretic definition of 0α. The successor codes are jumps of their predecessors, and for a limit λ, 0λ is the minimum of a set of degrees associated with {0α: α: < λ}.