In spite of the fact that true arithmetic reduces to the monadic second-order theory of the real line, Peano arithmetic cannot be interpreted in the monadic second-order theory of the real line.

Friedberg [3] showed that every degree of unsolvability above 0′ is the jump of some degree, and Sacks [9] showed that the degrees above 0′ which are recursively enumerable (r.e.) in 0′ are the jumps of the r.e. degrees.

In this paper we examine the extent to which the Sacks jump theorem can be combined with the minimal pair theorem of Lachlan [4] and Yates [13]. We prove below that there is a degree c > 0′ which is r.e. in 0′ but which is not the jump of half a minimal pair of r.e. degrees.

This extends Yates' result [13] proving the existence of noncappable degrees (that is, r.e. degrees a < 0′ for which there is no corresponding r.e. b > 0 with a ∩ b = 0).

It also throws more light on the class PS of promptly simple degrees. It was shown by Ambos-Spies, Jockusch, Shore and Soare [1] that PS coincides with the class NC of noncappable degrees, and with the class LC of all low-cuppable degrees, and (using earlier work of Maass, Shore and Stob [5]) that PS splits every class Hn or Ln, n ≥ 0, in the high-low hierarchy of r.e. degrees.

If c > 0′, with c r.e. in 0′, let

and call c−1 the jump class for c. It is easy to see that every jump class contains members of PS (= NC = LC). By Sacks [8] there exists a low a ∈ LC, where of course [a, 0′] (= {br.e. ∣a ≤ b ≤ 0′}) ⊆ LC = PS. But by Robinson [7] [a, 0′] intersects with every jump class.

When equational logic for partial functions is interpreted using Kleene equality as the predicate, the relation of logical consequence may be said to express what identities of partial functions follow from a given set of identities. In the analogous situation for total functions, there is a complete set of inference rules consisting of reflexivity, symmetry, transitivity, replacement, and substitution; in the case of partial functions, unrestricted substitution fails to be a valid inference rule, and there remains the question of how to obtain a complete set of rules. The first part of the present paper shows that completeness cannot be obtained by a mere restriction of the substitution rule, for a counterexample shows that even a rule allowing substitution in all consequentially valid instances fails, in conjunction with the other four rules, to yield a complete set of rules.

The second part of the paper defines a combined rule of transitivity-substitution which, in conjunction with reflexivity, symmetry, replacement, and substitution only of variables, yields a complete set of rules. The new rule is first stated in a form that allows an unbounded number of premises, and then is altered to a three-premise form. In both forms, the rule suffers from the shortcoming that in its formulation an auxiliary notion of conditional existence is involved, which is given by a recursive syntactic definition. As a result, the set of instantiations of the rule is recursively enumerable, but not (apparently) recursive (assuming a recursive set of premises).

In this paper we study the varieties of Stone algebras (S, ∧, ∨, *, 0, 1) and double Stone algebras (D, ∧, ∨, *, +, 0, 1). Our primary interest is to give a structural description of the algebraically and existentially closed members of both classes. Our technique is an application of the natural dualities of Davey [6] and Clark and Krauss [5]. This approach gives a description of the desired models as the algebras of all continuous structure-preserving maps from certain structured Boolean spaces into the generating algebra for the variety. In each case the resulting description can be converted in a natural way into a finite ∀∃-axiomatization for these models. For Stone algebras these axioms appeared earlier in Schmid [20], [21] and in Schmitt [22].

Since both cases we consider satisfy the amalgamation property, the existentially closed members form a model companion for the variety which is also its model completion. Moreover, it is also ℵ0 categorical and its countably infinite member is the unique countable homogeneous universal model for the variety. In the case of Stone algebras, explicit constructions for this model appear in Schmitt [22] and Weispfenning [23]. We give here an explicit construction for double Stone algebras of S. Hayes.

This work was motivated by a problem of Stanley Burris. In [4] Burris and Werner superseded many previous results by showing that for any finite algebra A, the universal Horn class ISP has a model companion. Weispfenning [24], [25] discovered that this model companion is always ℵ0 categorical and has a primitive recursive ∀∃-axiomatization. In spite of these very general theorems, there are few instances in which a structural description of the (any!) existentially closed members of ISP is available. Burris and Werner [4] solve this problem in a special setting.

Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X′, its Turing jump, is recursive in ∅′ and high if X′ computes ∅″. Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of A ⊕ W is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one.

Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turing functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that (W ⊕ A)′ is forced to disagree with Φ(−;A′). The conversion has some ambiguity; in particular, A cannot be found uniformly from W.

We also show that there is a “moderately” deep degree: There is a low nonzero degree whose join with any other low degree is not high.

No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional iff its theory has the independence property iff its theory has the multi-order property.

We show that the DA-uniflcation problem is undecidable. That is, given two binary function symbols ⊕ and ⊗, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following DA-axioms hold:

Two terms are DA-unifiable (i.e. an equation is solvable in DA) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory DA.

This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained.

The failure of a large and diverse body of work to settle some of the now-classical questions of computational complexity (notably P =? NP) suggests that they might not, in fact, be resolvable by established proof techniques.

Hartmanis and Hopcroft [HH] raised the issue of independent statements about computational complexity in 1976, constructing, for any consistent r.e. theory T capable of expressing statements about Turing machines, a Turing machine MT such that statements which intuitively express the computational complexity of MT are independent of T. Their technique involves a simple diagonalizing search over the theorems of T. In this paper we prove a constructive version of their independence result in the context of a generalization of a hierarchy of free variable logics defined by Rose [R1]. These logics are based on an axiomatized treatment of an extension by Löb and Wainer [LW] of Grzegorczyk's [G] hierarchy into the transfinite. Associated with each extended Grzegorczyk class (relative to an ordinal notation system S satisfying certain conditions) is the logic -arithmetic.

Free variable logics are interesting from the perspective of theoretical computer science. We may construe the equational definition of functions as a form of programming system. Each -arithmetic, then, has the nice property of containing both a programming system and a logic for stating and proving facts about programs.

The notion of ∀-recursiviness, introduced by Lacombe [1], is intended to describe the effectively definable functions and predicates in abstract structures with equality and denumerable domains. The fact that on every such structure ∀-recursiviness and search computability are equivalent is proved by Moschovakis in [2].

The definition of search computability [3] does not require the presence of the equality among the basic predicates of the structure. There exist abstract structures where the equality is not search-computable and even not semicomputable. On the other hand, in some structures the equality is not an “effective” predicate. Consider, for example, a structure whose domain consists of all partial recursive functions.

A notion of relative computability in abstract structures with denumerable domains, which we shall call here ∀-admissibility, was introduced by D. Skordev in 1977. The notion of ∀-admissibility is a generalization of Lacombe's ∀-recursiviness and does not require the presence of the equality among the basic predicates. In 1977 Skordev conjectured that, in every partial structure with denumerable domain, ∀-admissibility and search computability are equivalent.

Since 1977 some attempts have been made to establish Skordev's conjecture. It is proved in [4] for structures with total basic functions and without basic predicates, and in [5] for structures with finite domains. The proofs in [4] and [5] make use of the priority method and are very complicated.

It is consistent that for many cardinals λ there is a family of at least λ+ unbounded subsets of λ which have uniformization properties. In particular if it is consistent that a supercompact cardinal exists, then it is consistent that ℵω has such a family. We have applications to point set topology, Whitehead groups and reconstructing separable abelian p-groups from their socles.

In [GS] Gurevich and Shelah introduce a novel method for proving that every satisfiable formula in the Gödel class has a finite model (the Gödel class is the class of prenex formulas of pure quantification theory with prefixes ∀∀∃ … ∃). They dub their method “random models”: it proceeds by delineating, given any F in the Gödel class and any integer p, a set of structures for F with universe {1, …, p} that can be treated as a finite probability space S. They then show how to calculate an upper bound on the probability that a structure chosen at random from S makes F false; from this bound they are able to infer that if p is sufficiently large, that probability will be less than one, so that there will exist a structure in S that is a model for F. The Gurevich-Shelah proof is somewhat simpler than those known heretofore. In particular, there is no need for the combinatorial partitionings of finite universes that play a central role in the earlier proofs (see [G] and [DG, p. 86]). To be sure, Gurevich and Shelah obtain a larger bound on the size of the finite models, but this is relatively unimportant, since searching for finite models is not the most efficient method to decide satisfiability.

Gurevich and Shelah note that the random model method can be used to treat the Gödel class extended by initial existential quantifiers, that is, the prefix-class ∀…∀∃…∃; but they do not investigate further its range of applicability to syntactically specified classes.

We show that a cardinal κ is a (strongly) Mahlo cardinal if and only if there exists a nontrivial κ-complete κ-normal ideal on κ. Also we show that if κ is Mahlo and λ ≧ κ and λ<κ = λ then there is a nontrivial κ-complete κ-normal fine ideal on Pκ(λ). If κ is the successor of a cardinal, we consider weak κ-normality and prove that if κ = μ+ and μ is a regular cardinal then (1) μ< μ = μ if and only if there is a nontrivial κ-complete weakly κ-normal ideal on κ, and (2) if μ< μ = μ < λ<μ = λ then there is a nontrivial κ-complete weakly κ-normal fine ideal on Pκ(λ).

In [1] and [2] there is a development of a class theory, whose axioms were formulated by Bernays and based on a reflection principle. See [3]. These axioms are formulated in first order logic with ∈:

(A1) Extensionality.

(A2) Class specification. If ϕ is a formula and A is not free in ϕ, then

Note that “x is a set“ can be written as “∃u(x ∈ u)”.

(A3) Subsets.

Note also that “B ⊆ A” can be written as “∀x(x ∈ B → x ∈ A)”.

(A4) Reflection principle. If ϕ(x) is a formula, then

where “u is a transitive set” is the formula “∃v(u ∈ v) ∧ ∀x∀y(x ∈ y ∧ y ∈ u → x ∈ u)” and ϕPu is the formula ϕ relativized to subsets of u.

(A5) Foundation.

(A6) Choice for sets.

We denote by B1 the theory with axioms (A1) to (A6).

The existence of weakly compact and -indescribable cardinals for every n is established in B1 by the method of defining all metamathematical concepts for B1 in a weaker theory of classes where the natural numbers can be defined and using the reflection principle to reflect the satisfaction relation; see [1]. There is a proof of the consistency of B1 assuming the existence of a measurable cardinal; see [4] and [5]. In [6] several set and class theories with reflection principles are developed. In them, the existence of inaccessible cardinals and some kinds of indescribable cardinals can be proved; and also there is a generalization of indescribability for higher-order languages using only class parameters.

The purpose of this work is to develop higher order reflection principles, including higher order parameters, in order to obtain other large cardinals.

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.

Let K be a field of characteristic p. The map τ(X) = Xp − X is an additive endomorphism of K, with kernel Fp. The Galois extensions of K of order p are obtained by adjoining to K solutions to equations of the form Xp − X = a for some a in K. These extensions are called the Artin-Schreier extensions of K and have a cyclic Galois group.

The study of Artin-Schreier extensions is very important for studying fields of characteristic p, in particular for studying valued fields of the form K((t)). An attempt at getting quantifier elimination for those fields would necessitate the adjunction to the language of fields of a cross-section for the function τ, i.e. a function σ such that τ ∘ σ is the identity on the image of τ. When K = Fp, such a cross-section is in fact definable in K((t)): it associates to τ(x) the element of {x, x + 1, …, x + p – 1} whose constant term is 0 (see [2]). When K is infinite, such a cross-section is usually not definable.

The results presented in this paper originate from a question of L. van den Dries: is there a natural way of defining a cross-section σ for τ on F̃p, and is the theory of (F̃p, σ) decidable? (F̃p is the algebraic closure of Fp.)

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan (improving upon [Kle50] and [Kle52]) showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1 is speedable over another system S0 on a set of formulae A iff, for each recursive function h, there is a formula α in A such that the length of the shortest proof of α in S0 is larger than h of the shortest proof of α in S1. (Here we equate the length of a proof with something like the number of characters making it up, not its number of lines.) We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1 but unprovable in S0 from the collection A–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.

We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below, ϕ is an acceptable numbering of the partial recursive functions [Rog87] and Φ a (Blum) complexity measure associated with ϕ [Blu67], [DW83].

Following Soare [11] we say a recursively enumerable (r.e.) degree a has the anticupping (a.c.) property if there is a nonzero r.e. degree b < a such that for no r.e. c < a does a = b ∪ c.

Cooper [2] and Yates showed that 0′ has the a.c. property, while Harrington (see Miller [6]) proved that every high r.e. degree a has the a.c. property.

The recent paper by Ambos-Spies, Jockusch, Shore and Soare [1] describes a general theoretical framework for cupping and capping below 0′ which seems likely to be useful in a wider context.

Definition. (1) We say b is strongly noncuppable belowa if 0 < b < a and, for each d < a, b ∪ d ≠ a.

(2) We say an r.e. a has the strong anticupping property if there is an r.e. b which is strongly noncuppable below a.

The main results on cupping in (≤ 0′) are due to Epstein, Posner and Robinson. For instance it is known (Posner and Robinson [8]) that the s.a.c. property fails for 0′.

We prove below that r.e. degrees with the s.a.c. property do exist, hence obtaining a nonzero r.e. degree a such that (≤ a) ≢e(≤h) for any high r.e. degree h. This result, obtained by means of an infinite injury construction in (≤ 0′), extends Theorem 2 of [3], proved using a finite injury construction in (≤ 0′).

Our main source of notation and terminology is [3].

Several rather concrete propositions about Borel measurable functions of several variables on the Hilbert cube (countable sequences of reals in the unit interval) were formulated by Harvey Friedman [F1] and correlated with strong set-theoretic hypotheses. Most notably, he established that a “Borel diagonalization” proposition P is equivalent to: for any a ⊆ co and n ⊆ ω there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. In later work (see the expository Stanley [St] and Friedman [F2]), Friedman was to carry his investigations further into propositions about spaces of groups and the like, and finite propositions. He discovered and analyzed mathematical propositions which turned out to have remarkably strong consistency strength in terms of large cardinal hypotheses in set theory.

In this paper, we refine and extend Friedman's work on the Borel diagonalization proposition P. First, we provide more combinatorics about regressive partitions and n-Mahlo cardinals and extend the approach to the context of the Erdös cardinals In passing, a combinatorial proof of a well-known result of Silver about these cardinals is given. Incorporating this work and sharpening Friedman's proof, we then show that there is a level-by-level analysis of P which provides for each n ⊆ ω a proposition almost equivalent to: for any a ⊆ co there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. Finally, we use the combinatorics to bracket a natural generalization Sω of P between two large cardinal hypotheses.

In [1], Degtëv constructed a nonzero r.e. tt-degree containing a single r.e. m-degree. It is not difficult to construct an r.e. tt-degree containing infinitely many r.e. m-degrees (Fischer [6]); indeed, in [3], the author constructed an r.e. tt-degree with no greatest r.e. m-degree. Odifreddi [12, Problem 10] asked if every r.e. tt-degree contains either one or infinitely many r.e. m-degrees. The goal of this paper is to solve Odifreddi's question by showing:

Theorem. There exists a nonzero r.e. tt-degree containing exactly 3 r.e. m-degrees.

This theorem can be extended to show that there exist r.e. tt-degrees with arbitrarily large finite numbers of r.e. m-degrees.

We remark that save for the aforementioned results, very little is known about the structures that can be realized as the collection of r.e. m-degrees within an r.e. tt-degree. It seems conceivable that the methods of the present paper may be useful in, for example, embedding distributive (semi) lattices into such structures.

In part II of this paper [4], we continue our analysis of r.e. m- and tt-degrees. We define an r.e. tt-degree to be singular if it contains a single r.e. m-degree, and an r.e. T-degree a to be singular if a contains a singular r.e. tt-degree.

In [4] we study the distribution (in the r.e. T-degrees) of singular tt-degrees. We show that 0′T is singular (solving a question of Odifreddi [11]), and that the singular T-degrees are dense, but also we construct a nonsingular T-degree. The techniques used for the first results extend those of §2 of the present paper.