It is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there are recursive sets with no optimal order of enumeration.

The axiomatization of algebras of functions or partial functions under various operations has been studied by several authors. Menger [2] deals with the problem of axiomatizing the algebraic properties of 1-ary functions from the reals to the reals. He considers algebras with one of three binary operations corresponding to addition, multiplication or composition. This study is furthered by Schweizer and Sklar in [3]–[6]. In addition to the operations mentioned above they also introduce a partial ordering which corresponds to restriction of functions. In the second of these papers they give a set of axioms such that any system satisfying these axioms is order isomorphic to a concrete system of partial functions under composition and ordered by restriction. In [7] Schweizer and Sklar extend their work to the algebra of multiplace vector-valued functions. In [8] Whitlock studies abstract multiplaced function systems given by super-associative laws and shows that these systems are isomorphically embeddable in a concrete system of multiplaced functions where the operation on the functions is substitution of an m-ary function in an n-ary function.

In this paper we consider the set of functions from Uα, the set of α-sequences, to U where a is an infinite ordinal. As opposed to the composition operations studied in the above works, we consider the composition operations *κ, for κ < α, in a narrow sense—the substitution of one function in the κth place of another. The algebras studied have the form ‹A, *κ, Vκ› κ<α where Vκ are the projection (selector) functions on the κth place. In particular, the polynomials over an algebra form such an algebra called a polynomial substitution algebra. In §6 we show that a first-order axiom system and a condition of local finiteness, given by Pinter in a talk at Berkeley in 1972 to characterize term substitution abgebras, also characterize these polynomial substitution algebras.

The ω-rule,

with the meaning “if the formula A(n) is provable for all n, then the formula ∀xA(x) is provable”, has a certain formal similarity with a uniform reflection principle saying “if A(n) is provable for all n, then ∀xA(x) is true”. There are indeed some hints in the literature that uniform reflection has sometimes been understood as a “formalized ω-rule” (cf. for example S. Feferman [1], G. Kreisel [3], G. H. Müller [7]). This similarity has even another aspect: replacing the induction rule or scheme in Peano arithmetic PA by the ω-rule leads to a complete and sound system PA∞, where each true arithmetical statement is provable. In [2] Feferman showed that an equivalent system can be obtained by erecting on PA a transfinite progression of formal systems PAα based on iterations of the uniform reflection principle according to the following scheme:

Then T = (∪dЄ, PAd, being Kleene's system of ordinal notations, is equivalent to PA∞. Of course, T cannot be an axiomatizable theory.

The characterization of classes of r.e. sets by their index sets has proved valuable in producing new results about the r.e. sets and degrees. The classic example is Yates' proof [5, Theorem 7] of Sacks' density theorem for r.e. degrees using his classification of {e: We ≤TD) as Σ3(D) whenever D is r.e. Theorem 1 of this paper is a refinement of this index set theorem of Yates which has already proved to have interesting consequences about the r.e. degrees. This theorem was originally announced by Kallibekov [1, Theorem 1]. Kallibekov there proposed a new and ingenious method for doing priority arguments which has also since been used by Kinber [2]. Unfortunately his proof to this particular theorem contains an error. We have a totally different proof using standard techniques which is of independent interest.

The proof to Theorem 1 is an infinite injury priority argument. In §1 therefore we give a short summary of the infinite injury priority method. We draw heavily on the exposition of Soare [4] where a complete description of the method is given along with many examples. In §2 we prove the main theorem and also give what we think are the most interesting corollaries to this theorem announced by Kallibekov. In §3 we prove a theorem about Σ3 sets of indices of r.e. sets. This theorem is a strengthening of a theorem of Kinber [2, Theorem 1] which was proved using a modification of Kallibekov's technique. As application, we use our theorem to show that an r.e. set A has supersets of every r.e. degree iff A is not simple.

In this note we show that taking a scalar extension of two elementarily equivalent finite-dimensional algebras over the same field preserves elementary equivalence. The general question of whether or not tensor product preserves elementary equivalence was originally raised in [4]. In [3] Feferman relates an example of Ersov which answers the question negatively. Eklof and Olin [7] also provide a counterexample to the general question in the context of two-sorted structures. Thus the result proved below is a partial positive answer to a general question whose status has been resolved negatively. From the viewpoint of applied model theory it seems desirable to find contexts in which positive statements of preservation can be obtained. Our result does have an application; a corollary to it increases our understanding of what it means for two division algebras to be elementarily equivalent.

All algebras are finite-dimensional algebras over fields. All algebras contain an identity element, but are not necessarily associative.

Recall that the center of a not necessarily associative algebra A is the set of elements which commute and “associate” with all elements of A. The notion of a scalar extension is an important one in algebra. If A is an algebra over F and G is an extension field of F, then the scalar extension of A by G is the algebra A ⊗F G.

Let T be a countable complete theory and C(T) the category whose objects are the models of T and morphisms are the elementary maps. The main object of this paper will be the study of C(T). The idea that a better understanding of the category may give us model theoretic information about T is quite natural: The (semi) group of automorphisms (endomorphisms) of a given structure is often a powerful tool for studying this structure. But certainly, one of the very first questions to be answered is: “to what extent does this category C(T) determine T?”

There is some obvious limitation: for example let T0 be the theory of infinite sets (in a language containing only =) and T1 the theory, in the language ( =, U(ν0),f(ν0)) stating that:

(1) U is infinite.

(2)f is a bijective map from U onto its complement.

It is quite easy to see that C(T0) is equivalent to C(T1). But, in this case, T0 andT1 can be “interpreted” each in the other. To make this notion of interpretation precise, we shall associate with each theory T a category, loosely denoted by T, defined as follows:

(1) The objects are the formulas in the given language.

(2) The morphisms from into are the formulas such that

(i.e. f defines a map from ϕ into ϕ; two morphisms defining the same map in all models of T should be identified).

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).

The basic concept underlying probability theory and statistics is a function assigning numerical values (probabilities) to events. An “event” in this context is any conceivable state of affairs including the so-called “empty event”—an a priori impossible state. Informally, events are described in everyday language (e.g. “by playing this strategy I shall win $1000 before going broke”). But in the current mathematical framework (first proposed by Kolmogoroff [Ko 1]) they are identified with subsets of some all-inclusive set Q. The family of all events constitutes a field, or σ-field, and the logical connectives ‘and’, ‘or’ and ‘not’ are translated into the set-theoretical operations of intersection, union and complementation. The points of Q can be regarded as possible worlds and an event as the set of all worlds in which it takes place. The concept of a field of sets is wide enough to accommodate all cases and to allow for a general abstract foundation of the theory. On the other hand it does not reflect distinctions that arise out of the linguistic structure which goes into the description of our events. Since events are always described in some language they can be indentified with the sentences that describe them and the probability function can be regarded as an assignment of values to sentences. The extensive accumulated knowledge concerning formal languages makes such a project feasible. The study of probability functions defined over the sentences of a rich enough formal language yields interesting insights in more than one direction.

Our present approach is not an alternative to the accepted Kolmogoroff axiomatics. In fact, given some formal language L, we can consider a rich enough set, say Q, of models for L (called also in this work “worlds”) and we can associate with every sentence the set of all worlds in Q in which the sentence is true. Thus our probabilities can be considered also as measures over some field of sets. But the introduction of the language adds mathematical structure and makes for distinctions expressing basic intuitions that cannot be otherwise expressed. As an example we mention here the concept of a random sequence or, more generally, a random world, or a world which is typical to a certain probability distribution.

The category of enumerations over P1 is investigated. Objects are the enumerations of the set of partial recursive functions in one variable φ: N → P1 where φ is a total effective function from the natural numbers N onto P1.

To each a ∈ P1 we call φ−1(a) the set of all indices for a, the fibre over a.

Morphisms from one enumeration φ to another one ψ are (partial) recursive functions f, for which φ(n) = ψ(f(n)) holds for all n where f is denned, i.e. f is fibrepreserving. They are also called translators if f is total. The existence of a translator induces a partial ordering on the enumerations:

Let φ ≤ ψ, iff there exists a translator f with φ = ψ·f; φ ≡ ψ iff φ ≤ ψ and ψ ≤ φ. Two enumerations are called incomparable iff φ ≰,ψ and ψ ≰ φ.

Given a recursively enumerable family of enumerations {φi}i∈ω then their direct sum = π is defined by a bijective recursive pairing function g(i, n) (e.g. g(i, n) = (i + n)(i + n + 1)/2 + i) summing up the φi by φi(n) = = πg(i, n) into π. We also say π decomposes into .

Direct sums satisfy the universal property of sums in categories.

We want to operate decompositiontheory on special kinds of objects in our category, the Gödelnumberings and the Friedbergnumberings.

A Gödelnumbering φ is defined by (a) enumeration theorem (i.e. φ is object of our category) and (b) -theorem, which means that each m + n-place p.r. function can be effectively replaced by an enumeration of n-place p.r. functions given by means of the total -function (see Rogers [3]).

This paper is devoted to the proof of the following theorem.

Theorem. Let M be a countable standard transitive model of ZF + V = L, and let ℒ Є M be a wellfounded lattice in M, with top and bottom. Let ∣ℒ∣M = λ, and suppose κ ≥ λ is a regular cardinal in M. Then there is a generic extension N of M such that

(i) N and M have the same cardinals, and κN ⊂ M;

(ii) the c-degrees of sets of ordinals of N form a pattern isomorphic to ℒ;

(iii) if A ⊂ On and A Є N, there is B Є P(κ+)N such that L(A) = L(B).

The proof proceeds by forcing with Souslin trees, and relies heavily on techniques developed by Jech. In [5] he uses these techniques to construct simple Boolean algebras in L, and in [6] he uses them to construct a model of set theory whose c-degrees have orderlype 1 + ω*.

The proof also draws on ideas of Adamovicz. In [1]–[3] she obtains consistency results concerning the possible patterns of c-degrees of sets of ordinals using perfect set forcing and symmetric models. These methods have the advantage of yielding real degrees, but involve greater combinatorial complexity, in particular the use of ‘sequential representations’ of lattices.

The advantage of the approach using Souslin trees is twofold: first, we can make use of ready-made combinatorial principles which hold in L, and secondly, the notion of genericity over a Souslin tree is particularly simple.

In [4] Gordon Plotkin considers the problem of characterizing the λ-definable functionals in full type structures. A plausible, but, as we shall see, quite false, conjecture is that a functional is λ-definable ⇔ it is invariant in the sense of Fraenkel and Mostowski. A better guess might be that the set of λ-definable functionals of type σ has a uniform (in σ) definition in type theory over all full type structures (Plotkin explicitly considers a certain sort of definition by means of “logical relations”). More or less generally, one may ask if the following question is decidable.

Given: a functional F in a full type structure over a finite ground domain.

Question: is Fλ-definable?

We call the statement that this question is decidable Plotkin's λ-definability conjecture. We do not know if Plotkin's conjecture is true.

In this note we consider several questions which quickly arise from Plotkin's conjecture. In §1, we ask which type structures satisfy λ-definability = invariance. We construct for each consistent set of equations a model satisfying this equality. From consideration of these models we obtain a number of syntactic corollaries including a reduction of βη-conversion to βη-conversion at a single type (Theorem 3), an “ω-rule” for βη-conversion (Proposition 6) and consistency with βη-conversion (Proposition 8), definability and indefinability results for versions of Kronecker's δ (Propositions 10 and 11), and a decidability result for the problem of inter-definability among combinators.

Let ε stand for the set of nonnegative integers (numbers), V for the class of all subcollections of ε(sets), Λ for the set of isols, ΛR for the set of regressive isols, and for the set of mappings from a subset of ε into ε (functions). If ƒ is a function we write δƒ and ρƒ for its domain and range, respectively. We denote the inclusion relation by ⊃ and proper inclusion by ⊊. The sets α and β are recursively equivalent [written: α ≃ β], if δƒ = α and ρƒ = β for some function ƒ with a one-to-one partial recursive extension. We denote the recursive equivalence type of a set α, {σ ∈ V ∣ σ ≃ α} by Req(α). The reader is assumed to be familiar with the contents of [1], [2], [3], and [6].

The concept of an ω-group was introduced in [6], and that of an ω-homomorphism in [1]. However, except for a few examples, very little is known about the structure of ω-groups. If G is an ω-group and Π is an ω-homomorphism, then it follows that K = Ker Π and H = Π(G) are ω-groups. The question arises that if we know the structure of K and H, then what can we say about the structure of G? In this paper we will begin the study of ω-extensions, which will give us a partial answer to this question.

We prove that the statement “For every pair A, B, stationary subsets of ω2, composed of points of cofinality ω, there exists an ordinal α such that both A ∩ α and B ∩ α are stationary subsets of α is equiconsistent with the existence of weakly compact cardinal. (This completes results of Baumgartner and Harrington and Shelah.)

We also prove, assuming the existence of infinitely many supercompact cardinals, the statement “Every stationary subset of ωω+1 has a stationary initial segment.”

In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set W is exponential diophantine, i.e. can be represented in the form

Here P is a polynomial with integer coefficients and the variables range over positive integers.

In 1970 Ju. V. Matijasevič used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevič proved [11] that the exponential relation y = 2x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set Wcan be represented in the form

From this it follows that there does not exist an algorithm to decide solvability of diophantine equations. The nonexistence of such an algorithm follows immediately from the existence of r.e. nonrecursive sets.

Now it is well known that the recursively enumerable sets W1, W2, W3, … can be enumerated in such a way that the binary relation x ∈ Wv is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v,

Let κB be the least cardinal for which the Baire category theorem fails for the real line R. Thus κB is the least κ such that the real line can be covered by κ many nowhere dense sets. It is shown that κB cannot have countable cofinality. On the other hand it is consistent that the corresponding cardinal for 2ω1 be ℵω. Similar questions are considered for the ideal of measure zero sets, other ω1, saturated ideals, and the ideal of zero-dimensional subsets of Rω1.

Two real-valued deduction schemes are introduced, which agree on ⊢ ⊿ but not on Γ ⊢ ⊿, where Γ and ⊢ are finite sets of formulae. Using the first scheme we axiomatize real-valued equality so that it induces metrics on the domains of appropriate structures. We use the second scheme to reduce substitutivity of equals to uniform continuity, with respect to the metric equality, of interpretations of predicates in structures. This continuity extends from predicates to arbitrary formulae and the appropriate models have completions resembling analytic completions of metric spaces. We provide inference rules for the two deductions and discuss definability of each of them by means of the other.

One of the first results in model theory [12] asserts that a first-order sentence is preserved in extensions if and only if it is equivalent to an existential sentence.

In the first section of this paper, we analyze a natural program for extending this result to a class of languages extending first-order logic, notably including L(Q) and L(aa), respectively the languages with the quantifiers “there exist un-countably many” and “for almost all countable subsets”.

In the second section we answer a question of Bruce [3] by showing that this program cannot resolve the question for L(Q). We also consider whether the natural class of “generalized Σ-sentences” in L(Q) characterizes the class of sentences preserved in extensions, refuting the relativized version but leaving the unrestricted question open.

In the third section we show that the analogous class of L(aa)-sentences preserved in extensions does not include (up to elementary equivalence) all such sentences. This particular candidate class was nominated, rather tentatively, by Bruce [3].

In the fourth section we show that under rather general conditions, if L is a countably compact extension of first-order logic and T is an ℵ1-categorical first-order theory, then L is trivial relative to T.

Frege's conception of reference has been interpreted as calling for a completely extensional language, on the grounds that according to it the reference of a complex expression is a function of the references of its parts. To meet this demand and still allow for oblique contexts, one uses Frege's idea that in an oblique context an expression has as reference what is ordinarily its sense.

A purely extensional formalized intensional logic was constructed in the 1940s by Alonzo Church: his logic of sense and denotation [2], [3]. The ambiguity of the “direct” and “oblique” reference of an expression is avoided. For each denoting expression A there is an expression A denoting its sense, which then replaces A in “oblique” contexts. A consequence of this approach is that for each natural number n, in a context with n-fold embedding of intensional operators A is paraphrased by the result of iterating the operation à n times, so that A is treated as if it were infinitely ambiguous. Church's underlying logic is a simple theory of types, in fact just an expansion of the extensional typed λ-calculus so as to contain ωth-order predicate logic.

In this paper we study a variant of Church's logic that admits a possible-worlds semantics, i.e. a version of Church's Alternative (2) [3, pp. 4–5], [4]. This type of logic has been perspicuously formulated by David Kaplan [11], [12], and we follow his version.

In §1 we formulate Kaplan's logic L-Church-O with two alterations: the typed λ-calculus is replaced by combinators, and unlike Kaplan (but like Church) we allow concepts (that is, senses) that are not concepts of anything.

The class of stable posets is defined and investigated. We give a forcing construction of a universe of set theory which satisfies a weak form of Martin's Axiom and 2ℵ0 > ℵ1 and yet some propositions which follow from CH hold in this universe.