Let T be a set of axioms for a classical theory TC (e.g. abelian groups, linear order, unary function, algebraically closed fields, etc.). Suppose we regard T as a set of axioms for an intuitionistic theory TH (more precisely, we regard T as axioms in Heyting's predicate calculus HPC).

Question. Is TH decidable (or, more generally, if X is any intermediate logic, is TX decidable)? In [1] we gave sufficient conditions for the undecidability of TH. These conditions depend on the formulas of T (different axiomatization of the same TC may give rise to different TH) and on the classical model theoretic properties of TC (the method did not work for model complete theories, e.g. those of the title of the paper). For details see [1]. In [2] we gave some decidability results for some theories: The problem of the decidability of theories TH for a classically model complete TC remained open. An undecidability result in this direction, for dense linear order was obtained by Smorynski [4]. The cases of algebraically closed fields and real closed fields and divisible abelian groups are treated in this paper. Other various decidability results of the intuitionistic theories were obtained by several authors, see [1], [2], [4] for details.

One more remark before we start. There are several possible formulations for an intuitionistic theory of, e.g. fields, that correspond to several possible axiomatizations of the classical theory. Other formulations may be given in terms of the apartness relation, such as the one for fields given by Heyting [5]. The formulations that we consider here are of interest as these systems occur in intuitionistic mathematics. We hope that the present methods could be extended to the (more interesting) case of Heyting's systems [5].

In this paper we prove that if L is a set of modal propositional formulas then FR(L) (the class of all frames in which every formula of L holds) is elementary, Δ-elementary or not ΣΔ-elementary. For single modal formulas the second of these cases does not occur.

The model theoretic terminology and results used here are from [1]. (The underlying first order language contains only one, binary, predicate letter in addition to the identity symbol.) We presuppose familiarity with the usual notions and notations of propositional modal logic. A structure for our first order language is called a frame. (So a frame is an ordered couple 〈W, R〉 with domain W and R a binary predicate on W, i.e. a subset of W × W.) A valuation V on F is a function from the set of proposition letters to the power set of W. Using the well-known Kripke truth definition V can be extended to a function from the set of all modal propositional formulas to the power set of W. A modal propositional formula φ holds in a frame F (= 〈W, R〉) if, for all V on F, V(φ) = W. Notation: FR(φ) for the class of all frames in which φ holds. For a set L of modal propositional formulas we define FR(L) as ⋂φ∈L FR(φ). Obviously both FR(L) and cFR(L) (the complement of FR(L)) are closed under isomorphisms.

The aim of this paper is to introduce a formal system STW of self-referential truth, which extends the classical first-order theory of pure combinators with a truth predicate and certain approximation axioms. STW naturally embodies the mechanisms of general predicate application/abstractionon a par with function application/abstraction; in addition, it allows non-trivial constructions, inspired by generalized recursion theory. As a consequence, STW provides a smooth inner model for Myhill's systems with levels of implication.

One of the most fundamental results of higher-type recursion theory was first proved by Thomas Grilliot [3]. He showed that the functional embodying number quantification, 2E, is computable from a type-2 object F if and only if F has an effective discontinuity. For the background to this work we recommend Normann's book [9] or his summary [10], and for an example of its many applications Normann-Wainer [11].

The purpose of §1 of this paper is to give an effective proof of the “only if” part of this result: i.e. a construction of a discontinuity of F from the information 2E = {e}F. This contrasts with Grilliot's argument which is topological and nonconstructive, and shows that “Grilliot's trick” for computing 2E from a discontinuity of F is essentially the only method.

We then apply the method to two more general situations in which it gives new results. In §2 we treat type-3 objects in which 3E is computable (assuming AC and CH), and obtain a strengthening of the result of Hartley [5, §5]. In §3 we consider the superjump and characterise it as the least among a class of functionals with a particular sort of family of discontinuities.

The most basic construction of an r.e. nonrecursive set—e.g. of the halting problem—proceeds by taking the diagonal of a recursive enumeration of all r.e. sets. We will answer the question of which r.e. sets can be constructed in this manner.

If ψ is a computable numbering of some class of partial recursive functions, we define the diagonal of ψ to be the set K ψ ≔ {i ∈ ω ∣ ψi (i)↓}- It is well known that K φ is creative if φ is a Gödelnumbering, and that for each creative set K there exists a Gödelnumbering φ such that K = K φ. That is to say, the class of diagonals of Gödelnumberings is characterized as the class of creative sets. This class was shown to be elementary lattice theoretic (e.l.t.) by Harrington (see [So87, XV. 1.1]).

We give a characterization of diagonals of arbitrary computable numberings of the class P 1 of all partial recursive functions. To this end we introduce the notion of a semihyperhypersimple (shhs) set, which generalizes the notion of hyperhypersimplicity to nonsimple sets. It is shown that the diagonals of numberings of P 1 are exactly the non-shhs sets. Then, properties of shhs sets are discussed. For example, for each nonrecursive r.e. set A there exists a nonrecursive shhs set B ≤T A, but not every r.e. T-degree contains a shhs set. These results build upon previous work by Downey and Stob [DSta].

The question whether the property “shhs” is (elementary) lattice theoretic remains open. A positive answer would give both an analog of Harrington's result mentioned above, and a generalization of the well-known fact, due to Lachlan [La68], that hyperhypersimplicity is e.l.t. Therefore, we suspect that shhs sets turn out to be useful in the study of the lattice of r.e. sets.

Previously, for several constructions from recursion theory the role of the underlying numbering of P 1 was investigated; see Martin ([Ma66a] or [So87, V.4.1]) and Lachlan ([La75] or [Od89, III.9.2]) for Post's simple set, and Jockusch and Soare ([JS73]; cf. also [So87, XII.3.6, 3.7]) for Post's hypersimple set. However, only Gödelnumberings were considered. An explanation for the greater variety which arises when arbitrary numberings of P 1 are admitted is provided by the fact that the index set of Gödelnumberings is less complex than the index set of all numberings of P 1. The former is Σ1-complete; the latter is Π4-complete.

A many-one degree is functional if it contains the index set of some class of partial recursive functions but does not contain an index set of a class of r.e. sets. We give a natural embedding of the r.e. m-degrees into the functional degrees of 0′. There are many functional degrees in 0′ in the sense that every partial-order can be embedded. By generalizing, we show there are many functional degrees in every complete Turing degree.

There is a natural tie between the studies of index sets and partial-many-one reducibility. Every partial-many-one degree contains one or two index sets.

We prove that if μ is a regular cardinal and ℙ is a μ-centered forcing poset, then ℙ forces that (I[μ++[)V generates I[μ++] modulo clubs. Using this result, we construct models in which the approachability property fails at the successor of a singular cardinal. We also construct models in which the properties of being internally club and internally approachable are distinct for sets of size the successor of a singular cardinal.

A significant portion of the study of large cardinals in set theory centers around the concept of “partition relation”. To best capture the basic idea here, we introduce the following notation: for x and y sets, κ an infinite cardinal, and γ an ordinal less than κ, we let [x]γ denote the collection of subsets of x of order-type γ and abbreviate with the partition relation for each function F frominto y there exists a subset C of κ of cardinality κ such that (such that for each α < γ) the range of F on [С]γ ([С]α) has cardinality 1. Now although each infinite cardinal κ satisfies the relation for each n and m in ω (F. P. Ramsey [8]), a connection with large cardinals arises when one asks, “For which uncountable κ do we have κ → (κ)2?” Indeed, any uncountable cardinal κ which satisfies κ → (κ)2 is strongly inaccessible and weakly compact (see [9]). As another example one can look at the improvements of Scott's original result to the effect that if there exists a measurable cardinal then there exists a nonconstructible set. Indeed, if κ is a measurable cardinal then κ → (κ)< ω, and as Solovay [11] has shown, if there exists a cardinal κ such that κ → (κ)< ω3 (κ → (ℵ1)< ω, even) then there exists a nonconstructible set of integers.

This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and complementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.

We consider ωn-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ωn for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω2-automatic (resp. ωn-automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for ωn-automatic boolean algebras, n ≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a -set nor a -set. We obtain that there exist infinitely many ωn-automatic, hence also ω-tree-automatic, atomless boolean algebras , which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14].

We prove that each Σ20 set which is hypersimple relative to ∅′ is noncuppable in the structure of the Σ20 enumeration degrees. This gives a connection between properties of Σ20 sets under inclusion and and the Σ20 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to ∅′.

Using properties of ${\cal K}$-pairs of sets, we show that every nonzero enumeration degree a bounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump as a. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low enumeration degree can be capped by degrees of any possible local jump (i.e., any jump that can be realized by enumeration degrees of the local structure); every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degree a can be capped below a.

A. N. Prior in [9] has suggested an approach towards a second order logic of existence where, following medieval logicians, we distinguish “between predicates (like ‘is red’, ‘is hard’, etc.) which entail existence, and predicates (like ‘is thought to be red’, ‘is thought of’, etc.) which do not.”2 Let us refer to attributes (including relational attributes) which are designated by the former kind of predicate as existence attributes, or for brevity, e-attributes.

The degree spectrum of a countable structure is the set of all Turing degrees of presentations of that structure. We show that every nonlow Turing degree lies in the spectrum of some differentially closed field (of characteristic 0, with a single derivation) whose spectrum does not contain the computable degree 0. Indeed, this is an equivalence, for we also show that if this spectrum contained a low degree, then it would contain the degree 0. From these results we conclude that the spectra of differentially closed fields of characteristic 0 are exactly the jump-preimages of spectra of automorphically nontrivial graphs.

A fundamental problem of symbolic logic is to define logical calculi sufficient to comprise important parts of mathematics, and to develop systematic methods of calculation therein.

The possibility of progress in this direction has been severely limited by Gödel's proof that a consistent system sufficient to comprise arithmetic must contain propositions whose truth-value cannot be decided within the system, and by Church's extension of Gödel's method to the result that even in the first order logical function calculus the general decision problem cannot be solved.

We analyze combinatorial properties of open covers of sets of real numbers by using filters on the natural numbers. In fact, the goal of this paper is to characterize known properties related to ω-covers of the space in terms of combinatorial properties of filters associated with these ω-covers. As an example, we show that all finite powers of a set of real numbers have the covering property of Menger if, and only if, each filter on ω associated with its countable ω-cover is a P+ filter.

We develop an elimination theory for addition and the Frobenius map over rings of polynomials. As a consequence we show that if F is a countable, recursive and perfect field of positive characteristic p, with decidable theory, then the structure of addition, the Frobenius map x → xp and the property ‘x ∈ F1, over the ring of polynomials F[T], has a decidable theory.

In this paper, we use algebra-valued models to study cardinal numbers in a class of non-classical set theories. The algebra-valued models of these non-classical set theories validate the Axiom of Choice, if the ground model validates it. Though the models are non-classical, the foundations of cardinal numbers in these models are similar to those in classical set theory. For example, we show that mathematical induction, Cantor’s theorem, and the Schröder–Bernstein theorem hold in these models. We also study a few basic properties of cardinal arithmetic. In addition, the generalized continuum hypothesis is proved to be independent of these non-classical set theories.

Finitely axiomatizable ℵ1 categorical theories are locally modular.