In [2] Bachmann showed how a hierarchy of normal functions on the countable ordinals Ω can be constructed using certain uncountable ordinals together with appropriate fundamental sequences for limit ordinals, as indexing ordinals for the hierarchy. This method, explained in more detail in §1 below, has been generalized by Pfeiffer [6] and Isles [4] to produce larger hierarchies. Using the hierarchies constructed in this way it is possible, as an immediate consequence of the definitions, to assign ω-sequences 〈αn〉n∈ω to limit ordinals α in an initial segment I of Ω such that . Indeed this was the motivation for Bachmann's original construction. However the initial segments I constructed in this way are of interest even without the fundamental sequences because they occur naturally as the proof-theoretic ordinals associated with particular formal theories. The fundamental sequences necessary for the Bachmann method are not intrinsically of interest proof-theoretically and only serve to obscure the definitions of the associated initial segments. Feferman and Weyhrauch [9] suggested an alternative definition for a sequence of functions on the countable ordinals. This definition was generalized by Aczel [1] who showed how the new functions corresponded to those in Bachmann's hierarchy. (Independently, Weyhrauch established the same results for an initial segment of the sequence of Bachmann functions, i.e. those functions indexed by α < εΩ+1.)

It is known that a countable $\omega $ -categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.

In the thirty years since its invention by Abraham Robinson, nonstandard analysis has become a useful tool for research in many areas of mathematics. It seems fair to say, however, that the search for practically satisfactory foundations for the subject is not yet completed. New proposals, intended to remedy various shortcomings of older approaches, continue to be put forward. The objective of this paper is to show that nonstandard concepts have a natural place in the usual (more or less “standard”) set theory, and to argue that this approach improves upon various aspects of hitherto considered systems, while retaining most of their attractive features. We do this by working in Zermelo-Fraenkel set theory with non-well-founded sets. It has always been clear that the axiom of regularity may fail for external sets. The previous approaches either avoid non-well-foundedness by considering only that fragment of nonstandard set theory that is well-founded (over individuals; enlargements of Robinson and Zakon [17]) or reluctantly live with it (various axiomatic nonstandard set theories). Ballard and Davidon [2] were the first to propose constructive use for non-well-foundedness in the foundations of nonstandard analysis. In the present paper we adopt a very strong anti-foundation axiom. In the resulting more or less “usual” set theory, the (to the “standard” mathematician) unfamiliar concepts of standard, external and internal sets can be defined and their requisite properties proved (rather than postulated, as is the case in axiomatic nonstandard set theories).

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity.

We also consider Low(ℳ, Kurtz), the class of degrees a such that every element of ℳ is a-Kurtz random. These are characterised when ℳ is the class of Martin-Löf random, computably random, or Schnorr random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees.

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable degree, but not 0. Since our argument requires the technique of permitting below a set, we include a detailed explantion of the mechanics and intuition behind this type of permitting.

Nominal logic is a variant of first-order logic in which abstract syntax with names and binding is formalized in terms of two basic operations: name-swapping andfreshness. It relies on two important principles: equivariance (validity is preserved by name-swapping), and fresh name generation (“new” or fresh names can always be chosen). It is inspired by a particular class of models for abstract syntax trees involving names and binding, drawing on ideas from Fraenkel-Mostowski set theory: finite-support models in which each value can depend on only finitely many names.

Although nominal logic is sound with respect to such models, it is not complete. In this paper we review nominal logic and show why finite-support models are insufficient both in theory and practice. We then identify (up to isomorphism) the class of models with respect to which nominal logic is complete: ideal-supported models in which the supports of values are elements of a proper ideal on the set of names.

We also investigate an appropriate generalization of Herbrand models to nominal logic. After adjusting the syntax of nominal logic to include constants denoting names, we generalize universal theories to nominal-universal theories and prove that each such theory has an Herbrand model.

In the early days of the development of Kripke-style semantics for modal logic a great deal of effort was devoted to showing that particular axiom systems were characterised by a class of models describable by a first-order condition on a binary relation. For a time the approach seemed all encompassing, but recent work by Thomason [6] and Fine [2] has shown it to be somewhat limited—there are logics not determined by any class of Kripke models at all. In fact it now seems that modal logic is basically second-order in nature, in that any system may be analysed in terms of structures having a nominated class of second-order individuals (subsets) that serve as interpretations of propositional variables (cf. [7]). The question has thus arisen as to how much of modal logic can be handled in a first-order way, and precisely which modal sentences are determined by first-order conditions on their models. In this paper we present a model-theoretic characterisation of this class of sentences, and show that it does not include the much discussed LMp → MLp.

Definition 1. A modal frame ℱ = 〈W, R〉 consists of a set W on which a binary relation R is defined. A valuation V on ℱ is a function that associates with each propositional variable p a subset V(p) of W (the set of points at which p is “true”).

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.

Relativization—the principle that says one can carry over proofs and theorems about partial recursive functions and Turing degrees to functions partial recursive in any given set A and the Turing degrees of sets in which A is recursive—is a pervasive phenomenon in recursion theory. It led H. Rogers, Jr. [15] to ask if, for every degree d, (≥ d), the partial ordering of Turing degrees above d, is isomorphic to all the degrees . We showed in Shore [17] that this homogeneity conjecture is false. More specifically we proved that if, for some n, the degree of Kleene's (the complete set) is recursive in d(n) then ≇ (≤ d). The key ingredient of the proof was a new version of a result from Nerode and Shore [13] (hereafter NS I) that any isomorphism φ: → (≥ d) must be the identity on some cone, i.e., there is an a called the base of the cone such that b ≥ a ⇒ φ(b) = b. This result was combined with information about minimal covers from Jockusch and Soare [8] and Harrington and Kechris [3] to derive a contradiction from the existence of such an isomorphism if deg() ≤ d(n).

We determine the exact bounds for the length of an arbitrary reduction sequence of a term in the typed λ-calculus with β-, ξ- and η-conversion. There will be two essentially different classifications, one depending on the height and the degree of the term and the other depending on the length and the degree of the term.

One of the major problems of model theory is the spectrum problem, i.e. the development of structure theorems for the spectrum of models of a given theory. I hope that this paper will make a (small) contribution to the solution of this problem.

Broadly speaking, in this paper we take a fixed (but arbitrary) theory T and consider a particular class ℰ of models of T. The structures in ℰ (which are known as existentially closed structures) are connected with the model complete extensions of T. These structures have already appeared several times in the literature.

In §1 we survey the notation and terminology that we use, as well as the well known facts that we require. We also consider several concepts which are not new here but which may not be well known.

In §2 we define, and give the basic results concerning existentially closed structures. For most theories, T, the class ℰ is not elementary and hence is not directly amenable to a model theoretic study. Because of this we consider a smaller class of structures—the uniformly existentially closed structures. These are discussed in §3.

In §4 we look at model complete theories via existentially closed structures. This section is essentially a refinement of parts of [6].

In §5 we look at model companions of theories via existentially closed structures.

Finally, in §6 we make some remarks on the relevance of existentially closed structures to the spectrum problem.

The concepts of ω-consistency and ω-completeness are closely related. The former concept has been generalized to notions of Γ-consistency and strong Γ-consistency, which are applicable not only to formal systems of number theory, but to all functional calculi containing individual constants; and in this general setting the semantical significance of these concepts has been studied. In the present work we carry out an analogous generalization for the concept of ω-completeness.

Suppose, then, that F is an applied functional calculus, and that Γ is a non-empty set of individual constants of F. We say that F is Γ-complete if, whenever B(x) is a formula (containing the single free individual variable x) such that ⊦ B(α) for every α in Γ, then also ⊦ (x)B(x). In the paper “Γ-con” a sequence of increasingly strong concepts, Γ-consistency, n = 1,2, 3,…, was introduced; and it is possible in a formal way to define corresponding concepts of Γn-completeness, as follows. We say that F is Γn-complete if, whenever B(x1,…, xn) is a formula (containing exactly n distinct free variables, namely x1…, xn) such that ⊦ B(α1,…,αn) for all α1,…,αn in Γ, then also ⊦ (X1)…(xn)B(x1,…,xn). However, unlike the situation encountered in the paper “Γ-con”, these definitions are not of interest – for the simple reason that F is Γn-complete if and only if it is Γ-complete, as one easily sees.

Ramsey's theorem [5] asserts that every infinite set X has the following partition property (RP): For every partition of the set [X]2 of two-element subsets of X into two pieces, there is an infinite subset Y of X such that [Y]2 is included in one of the pieces. Ramsey explicitly indicated that his proof of this theorem used the axiom of choice. Kleinberg [3] showed that every proof of Ramsey's theorem must use the axiom of choice, although rather weak forms of this axiom suffice. J. Dawson has raised the question of the position of Ramsey's theorem in the hierarchy of weak axioms of choice.

In this paper, we prove or refute the provability of each of the possible implications between Ramsey's theorem and the weak axioms of choice mentioned in Appendix A.3 of Jech's book [2]. Our results, along with some known facts which we include for completeness, may be summarized as follows (the notation being as in [2]):

A. The following principles do not (even jointly) imply Ramsey's theorem, nor does Ramsey's theorem imply any of them:

the Boolean prime ideal theorem,

the selection principle,

the order extension principle,

the ordering principle,

choice from wellordered sets (ACW),

choice from finite sets,

choice from pairs (C2).

B. Each of the following principles implies Ramsey's theorem, but none of them follows from Ramsey's theorem:

the axiom of choice,

wellordered choice (∀kACk),

dependent choice of any infinite length k (DCk),

countable choice (ACN0),

nonexistence of infinite Dedekind-finite sets (WN0).

Let We be the eth recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that We = W f(e). In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets.

Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper.

Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete (i.e. A has degree 0′) iff there is a function f recursive in A with no fixed point.

I falsely claimed, as an aside remark in [8] and also implicitly in the abstract [9], that the slow-growing hierarchy

“catches up” with the fast-growing hierarchy

at level Γ0, i.e. that, for all x > 0,

where x′ is some simple (even linear) function of x.

Girard [4] gave the first correct analysis of the deep relationship which exists between G and F, based on his extensive category-theoretic framework for -logic. This analysis indicates that the first point at which G catches up with F is the ordinal of the theory ID<ω(0 of arbitrary finite iterations of an inductive definition. This is very far beyond Γ0! In particular, in order to capture F at level ∣IDn∣ the slow-growing hierarchy must be generated up to ∣IDn+1∣, i.e. one extra iteration of an inductive definition is needed in order to generate sufficient new ordinals.

If S is a finite set, let ∣S∣ be the cardinality of S. We show that if m ∈ ω, A ⊆ ω, B ⊆ ω, and ∣i: ≤ i ≤ 2m & xi ∈ A}∣ can be computed by an algorithm which, for all x1, …, x2m, makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.

In the theory of conversion it is important to have a formally defined function which assigns to any positive integer n the least integer not less than n which has a given property. The definition of such a formula is somewhat involved: I propose to give the corresponding formula in λ-K-conversion, which will (naturally) be much simpler. I shall in fact find a formula þ such that if T be a formula for which T(n) is convertible to a formula representing a natural number, whenever n represents a natural number, then þ(T, r) is convertible to the formula q representing the least natural number q, not less than r, for which T(q) conv 0.2 The method depends on finding a formula Θ with the property that Θ conv λu·u(Θ(u)), and consequently if M→Θ(V) then M conv V(M). A formula with this property is,

The formula þ will have the required property if þ(T, r) conv r when T(r) conv 0, and þ(T, r) conv þ(T, S(r)) otherwise. These conditions will be satisfied if þ(T, r) conv T(r, λx·þ(T, S(r)), r), i.e. if þ conv {λptr·t(r, λx·p(t, S(r)), r)}(þ). We therefore put,

This enables us to define also a formula,

such that (T, n) is convertible to the formula representing the nth positive integer q for which T(q) conv 0.

The theory of relations was discussed, along with the theory of classes, by Peirce and Schröder. While the calculus of classes has subsequently been presented (by Couturat, and by Huntington) as an abstract mathematical system, no similar formulation has been published of the calculus of relations. Professor Alfred Tarski has proposed to me, the problem of developing a similar formulation for the theory of relations. In this paper I present a set of postulates for the calculus of relations.

The postulates have been chosen so as to enable us to prove Theorem A, below, which asserts a kind of completeness of the system. A set of postulates is called semi-categorical, if every two realizations which involve the same number of elements are isomorphic. From Theorem A one can easily prove that my postulates are semi-categorical, if one assumes the following theorem from Mengenlehre: if α and β are cardinal numbers such that , then α=β. This theorem has not been proved, however, except on the assumption of the axiom of choice and the generalized continuum hypothesis, and is not assumed in the present paper.

It should be pointed out, that the sort of completeness I have chosen is not the only sort, or even necessarily the most interesting sort, of completeness which a set of postulates for the calculus of relations could possess. For example, the question arises, whether it would be possible to find a set of postulates from which all true equations (involving free variables and the operations used by Schröder) could be derived, and which was the weakest possible such set. The present work should therefore be regarded only as a first step in the investigation of the axiomatization of the calculus of relations.

The paper is a continuation of [The SCH revisited], In § 1 we define a forcing with countably many nice systems. It is used, for example, to construct a model “GCH below κ, c f κ = ℵ0, and 2κ > κ+ω” from 0(κ) = κ+ω. In §2 we define a triangle iteration and use it to construct a model satisfying “{μ ≤ λ∣c f μ = ℵ0 and pp(μ) > λ} is countable for some λ”. The question of whether this is possible was asked by S. Shelah. In §3 a forcing for blowing the power of a singular cardinal without collapsing cardinals or adding new bounded subsets is presented. Answering a question of H. Woodin, we show that it is consistent to have “c f κ = ℵ0. GCH below κ, 2κ > κ+, and ”. In §4 a variation of the forcing of [The SCH revisited, §1] is defined. It behaves nicely in iteration processes. As an application, we sketch a construction of a model satisfying:

“κ is a measurable and 2κ ≥ κ+α for some α, κ < c f α < α” starting with 0(κ) = κ+α. This answers the question from Gitik's On measurable cardinals violating the continuum hypothesis.