The theory of computational complexity deals with those functions which can be computed subject to certain restrictions on the resources (for instance, time or memory) available for computation. Blum [5] gave an axiomatic characterization of some of the properties which should be possessed by a measure of computational complexity and established the existence of speed-upable functions—computable functions which fail to possess optimal programs in a particularly strong sense. Recursion theorists tend to like such functions, and people concerned with the specifics of real computing tend to consider such functions somewhat pathological. In Theorem 2 we show that such pathology is rampant: there is a great diversity of behavior among the collections of “run-times” of different functions which do not possess optimal programs, where such diversity is gauged by certain algebraic criteria which have computational significance. Roughly speaking, these algebraic criteria concern the ways in which various functions can be intermixed to satisfy requirements that certain functions can or cannot be computed more easily than certain other functions. (More detailed motivation for the relevance of these algebraic notions is given later.) Specifically, in Theorem 2 we generalize the embeddability theorem of McCreight and Meyer [12] (discussed below) by making speed-upable functions responsible for the embedding.

In mathematics, when we want to introduce classes which fulfill certain conditions, we usually prove beforehand that classes fulfilling such conditions do exist, and that such classes are uniquely determined by the conditions. The statements which state such unicity and existence of classes are in mathematical logic consequences of the principles of extensionality and class existence. In order to illustrate how these principles enable us to introduce classes into systems of mathematical logic, let us consider the manner in which Gödel introduces classes in his book on set theory.

For instance, before introducing the definition of the non-ordered pair of two classes

Gödel puts down as its justification the following two axioms:

By A4, for every two classes y and z there exists at least one non-ordered pair w of them; and by A3, w is uniquely determined in A4.

Validity in recursive structures was investigated by several authors. Kreisel [10] has shown that there exists a consistent sentence of classical predicate calculus (CPC) that does not possess a recursive model. The sentence is a conjunction of the axioms of a variant of Bernays set theory, including the axiom of infinity. The language contains additional constants besides ϵ. Later Kreisel [2] and Mostowski [3] presented a sentence (not possessing recursive models) which was a conjunction of axioms of a variant of Bernays set theory without the axiom of infinity but still with additional constants besides ϵ. Later Mostowski [4] improved the result by giving a sentence which can be demonstrated in Heyting arithmetic to be consistent and to have no recursive models. Rabin [6] obtained a simple proof that some sentence of set theory with the single nonlogical constant ϵ does not have any recursively enumerable models.

More generally, Mostowski [5] has shown that the set of all sentences valid in all RE models is not arithmetical and Vaught [1] improved this result by showing that it holds for a language of one binary relation. In fact, Vaught gives· a way of translating n-place relations to 2-place ones that preserves the RE characteristic of the model. For further results pertaining to recursive models see Vaught [1].

It is shown that a stable division ring with positive characteristic has finite dimension over its centre. This is then extended to simple division rings.

We prove that infinite definably simple locally finite groups of finite centraliser dimension are simple groups of Lie type over locally finite fields. Then, we identify conditions on automorphisms of a stable group that make it resemble the Frobenius maps, and allow us to classify definably simple stable groups in the specific case when they admit such automorphisms.

The theory of ranked partial structures allows a reinterpretation of several of the standard results of model theory and first-order logic and is intended to provide a proof-theoretic method which allows for the intuitions of model theory. A version of the downward Löwenheim-Skolem theorem is central to our development. In this paper we will present the basic theory of ranked partial structures and their logic including an appropriate version of the completeness theorem.

Let ${\cal M}$ be ternary, homogeneous and simple. We prove that if ${\cal M}$ is finitely constrained, then it is supersimple with finite SU-rank and dependence is k-trivial for some k < ω and for finite sets of real elements. Now suppose that, in addition, ${\cal M}$ is supersimple with SU-rank 1. If ${\cal M}$ is finitely constrained then algebraic closure in ${\cal M}$ is trivial. We also find connections between the nature of the constraints of ${\cal M}$, the nature of the amalgamations allowed by the age of ${\cal M}$, and the nature of definable equivalence relations. A key method of proof is to “extract” constraints (of ${\cal M}$) from instances of dividing and from definable equivalence relations. Finally, we give new examples, including an uncountable family, of ternary homogeneous supersimple structures of SU-rank 1.

We prove the Decomposability Conjecture for functions of Baire class $2$ from a Polish space to a separable metrizable space. This partially answers an important open problem in descriptive set theory.