Let ω be the set of natural numbers, i.e. {0,1,2,…}. A set A (≤ω) is called n-generic if it is Cohen-generic for n-quantifier arithmetic. As characterized by Jockusch [4], this is equivalent to saying that for every set of strings S, there is a σ < A such that σ ∈ S or ∀ν ≥ σ(ν ∉ S). When we say degree, we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. A nonrecursive degree a is called minimal if there is no nonrecursive degree b with b < a. Jockusch [4] exhibited various properties of generic degrees, and he showed that any 2-generic degree bounds no minimal degree. Chong and Jockusch [1] showed that any 1-generic degree below 0′ bounds no minimal degree. Haught [3] refuted one of the conjectures in [1] and showed that if a is a 1-generic degree and 0 < b < a < 0′ then b is also 1-generic. We show here that there is a 1-generic degree which bounds a minimal degree. This gives an affirmative answer to questions in [1] and [4], As any 1-generic degree below 0′ bounds no minimal degree, we see that our 1-generic degree which bounds a minimal degree is not below 0′, but can be constructed recursively in 0″. Furthermore we see that the initial segments below 1-generic degrees are not order isomorphic.

An important program in the study of the structure the lattice of r.e. sets modulo finite sets, is the classification of the orbits under Aut(), the automorphism group of , If Φ ∈ Aut() and Φ(We) =* Wh(e) for all e ∈ ω, then h is called a presentation of Φ. Define Autχ() to be the class of those elements of Aut() that have a presentation in the class of functions X, where for instance X might be the class of Δn functions for n ∈ ω. If Φ ∈ Autx() then we will say that Φ is an X-automorphism. Note that we only need to consider Δn- and Πn-orbits and automorphisms since if f is a Σn-presentation, then f is a total function and therefore Δn.

Definition. If X is a class of functions and ⊆ {Wi: i < ω}, then is an X-orbit iff is an orbit under Aut() and for all A, B ∈ there is a Φ ∈ Autx() satisfying Φ(A) =* B. (Here Φ: → .)

Harrington proved that the creative sets form a Δ0-orbit and Soare proved that the maximal sets form Δ3-orbit. We will show that there is no Boolean algebra such that {A: A is r.e. and ℒ*(A) ≈ ] forms a Δ2-orbit, where ℒ*(A) is the principal filter of A in ; ℒ*(A) = {B: B ⊆* A & B ∈ }. The idea behind the proof of this theorem is very similar to the proof by Soare that maximal sets do not form a Δ2-orbit (see Soare [1974] or Soare [1987]).

Church's simple theory of types is a system of higher-order logic in which functions are assumed to be total. We present in this paper a version of Church's system called PF in which functions may be partial. The semantics of PF, which is based on Henkin's general-models semantics, allows terms to be nondenoting but requires formulas to always denote a standard truth value. We prove that PF is complete with respect to its semantics. The reasoning mechanism in PF for partial functions corresponds closely to mathematical practice, and the formulation of PF adheres tightly to the framework of Church's system.

We define a rich model to be one which contains a proper elementary substructure isomorphic to itself. Existence, nonstructure, and categoricity theorems for rich models are proved. A theory T which has fewer than min(2λ, ℶ2) rich models of cardinality λ (λ > ∣T∣) is totally transcendental. We show that a countable theory with a unique rich model in some uncountable cardinal is categorical in ℵ1 and also has a unique countable rich model. We also consider a stronger notion of richness, and use it to characterize superstable theories.

We show that the modal propositional logic G, originally introduced to describe the modality “it is provable that”, is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □κ holds for all κ < ℵω; on the other hand, it is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation.

We consider IOpen, the subsystem of PA (Peano Arithmetic) with the induction scheme restricted to quantifier-free formulas.

We prove that each model of IOpen can be embedded in a model where the equation has a solution. The main lemma states that there is no polynomial f{x,y) with coefficients in a (nonstandard) DOR M such that ∣f(x,y) ∣ < 1 for every (x,y) Є C, where C is the curve defined on the real closure of M by C: x2 + y2 = a and a > 0 is a nonstandard element of M.

The aim of the present paper is to give some general conditions for constructions by finitely many workers. Constructions using infinitely many workers will not be considered here, although there are examples of such constructions. The original construction using the method of workers, due to Harrington [H], has a worker n for each n ∈ ω, as do the constructions in [K1] and [K2]. Marker [M] obtains a result using three workers. In [AJK], there are two constructions that use three workers. There are also two constructions that have, for an arbitrary recursive ordinal α, one worker for each β < α.

The main result here is a metatheorem, which is patterned after Proposition 1 of Ash [A]. As in [A], the object of the construction is to attach “labels” to the nodes in a highly nonrecursive path through a tree, while recursively enumerating neighborhoods of an “adherent” point in a metric space. There is a family of relations associated with the labels, and the metatheorem here and the one in [A] both say that the construction will succeed if these relations satisfy a list of properties. There are significant differences between the result here and that in [A]. One difference is that certain relations which in [A] were required to be r.e. need not be r.e. here. Another difference is that there are extra relations here, and as a result, the list of properties to be satisfied is longer and more horrible than that in [A].

V. Lifschitz defined in 1979 a variant of realizability which validates Church's thesis with uniqueness condition, but not the general form of Church's thesis. In this paper we describe an extension of intuitionistic arithmetic in which the soundness of Lifschitz' realizability can be proved, and we give an axiomatic characterization of the Lifschitz-realizable formulas relative to this extension. By a “q-variant” we obtain a new derived rule. We also show how to extend Lifschitz' realizability to second-order arithmetic. Finally we describe an analogous development for elementary analysis, with partial continuous application replacing partial recursive application.

It is consistent that, for every n ≥ 2, every stationary subset of ωn consisting of ordinals of cofinality ωκ, where κ = 0 or κ ≤ n − 3, reflects fully in the set of ordinals of cofinality ωn−1. We also show that this result is best possible.