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.

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.

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.

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

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.

Quine has shown that set theory may be based on inclusion and abstraction [1937], [1953]. He quantifies over (or abstracts upon) sets of all kinds, of course, including sets of sets. Here I confine Quine's approach to quantification over (abstraction upon) individuals alone, or at any rate their unit classes. Forsaking quantification over sets undercuts Quine's definition of negation, however. Smullyan sketches a first-order restriction of Quine's approach with no bound class variables for which inclusion and abstraction alone are adequate logical primitives [1957, n. 10]. However, the definition of negation requires more than one element in the universe of discourse. This requirement is met for Smullyan because he is doing arithmetic. Here, on the other hand, I presuppose only that the universe is nonempty. Accordingly, I assume a third primitive notion, the empty class. I will show that this threefold basis suffices both for classical first-order logic and for a version of “free” many-sorted logic. The monadic fragment, which I call Boolean logic with abstraction, is intermediate in strength between Boolean class logic and Lesniewski's Ontology. It affords a novel perspective on descriptions, particularly in their generic use.

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0′. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice ℰ of recursively enumerable sets with inclusion. We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions.

Ever since Craig-Beth and Addison-Kleene proved their versions of the Lusin-Suslin theorem, work in model theory and recursion theory has demonstrated the value of classical descriptive set theory as a source of ideas and inspirations. During the sixties in particular, J.W. Addison refined the technique of “conjecture by analogy” and used it to generate a substantial number of results in both model theory and recursion theory (see, e.g., Addison [1], [2], [3]).

During the past 15 years, techniques and results from recursion theory and model theory have played an important role in the development of descriptive set theory. (Moschovakis's book [6] is an excellent reference, particularly for the use of recursion-theoretic tools.) The use of “conjecture by analogy” as a means of transferring ideas from model theory and recursion theory to descriptive set theory has developed more slowly. Some notable recent examples of this phenomenon are in Vaught [9], where some results in invariant descriptive set theory reflecting and extending model-theoretic results are obtained and others are left as conjectures (including a version of the well-known conjecture on the number of countable models) and in Hrbacek and Simpson [4], where a notion analogous to that of Turing reducibility is used to study Borel isomorphism types. Moschovakis [6] describes in detail an effective descriptive set theory based in large part on classical recursion theory.

A set J of Turing degrees is called an ideal if (1) J ≠ ∅, (2) for any pair of degrees ã, , if ã, ϵ J, then ã ⋃ ϵJ, and (3) for any ⋃ ϵ J and any , if < ⋃, then ϵ J. A set J of degrees is said to be closed if for any theory T with a set of axioms of degree in J, T has a completion of degree in J.

Closed ideals of degrees arise naturally in the following way. If is a recursively saturated structure, let I() = { for some ā ϵ }. Let D() = {: is recursive in d-saturated}. (Recursive in d-saturation is defined like recursive saturation except that the sets of formulas considered are recursive in d.) These two sets of degrees were investigated in [2]. It was shown that if is a recursively saturated model of P, Pr = Th(ω, +), or Pr′ = Th(Z, +, 1), then I() = D(), and this set is a closed ideal. Any closed ideal J can be represented as I() = D() for some recursively saturated model of Pr′. For sets J of power at most ℵ1, Pr′ can be replaced by P.

Assuming CH, all closed ideals have power at most ℵ1, but if CH fails, there are closed ideals of power greater than ℵ1, and it is not known whether these can be represented as I() = D() for a recursively saturated model of P.

In the present paper, it will first be shown that information about representation of closed ideals provides new information about an old problem of MacDowell and Specker [6] and extends an old result of Scott [8] in a natural way. It will also be shown that the representation results from [2] answer a problem of Friedman [1]. This part of the paper is aimed at convincing the reader that representation problems are worth investigating.

Les arbres sont les ordres partiels qui vérifient l'axiome supplémental ∀x∀y∀z(y ≤x ∧z ≤ x → y ≤ z ∨ z ≤ y), i.e. l'ensemble des minorants de chaque élément est totalement ordonné.

Le principal résultat de cet article concerne l'instabilité des arbres: nous prouvons (§2) qu'aucune théorie d'arbre n'a la propriété d'indépendance, ce qui généralise un theoreme de Poizat [3] sur les ordres totaux. II s'en suit au moyen d'un resultat d'interprétation [4] qu'aucune théorie de structure arborescente n'a la propriété d'indépendance; en particulier ceci vaut pour les arbres colorés.

Le §3 est consacré aux arbres stables. II est prouvé qu'un arbre est stable ssi il est superstable ssi il est de hauteur bornée. Sous l'hypothèse de stabilité, les arbres premiers, minimaux, et strictement minimaux sont caractérisés en termes d'al-gébricité.

A notion of relative reducibility for partial functions, which coincides with Turing reducibility on the total functions, was first given by S.C. Kleene in Introduction to metamathematics [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., Theory of recursive functions and effective computability [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the enumeration degrees, were derived. The question of density of this proper extension of the degrees of unsolvability was left open, although Medvedev's result [6] that there are quasi-minimal partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved.

In 1971, Sasso [9] introduced a finer notion of partial degree, which also contained the Turing degrees as a proper substructure (intuitively, Sasso's notion of reducibility between partial functions differed from Rogers' in that computations terminated when the oracle was asked for an undefined value, whereas a Rogers computation could be thought of as proceeding simultaneously along a number of different branches of a ‘consistent’ computation tree—cf. Sasso [10]). His construction of minimal ‘partial degrees’ [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.

For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.

Anderson and Belnap asked in §8.11 of their treatise Entailment [1] whether a certain pure implicational calculus, which we will call P − W, is minimal in the sense that no two distinct formulas coentail each other in this calculus. We provide a positive solution to this question, variously known as The P − W problem, or Belnap's conjecture.

We will be concerned with two systems of pure implication, formulated in a language constructed in the usual way from a set of propositional variables, with a single binary connective →. We use A, B,…, A1, B1, …, as variables ranging over formulas. Formulas are written using the bracketing conventions of Church [3].

The first system, which we call S (in honour of its evident incorporation of syllogistic principles of reasoning), has as axioms all instances of

The second system, P − W, has in addition to the axioms and rules of S the axiom scheme

We write ⊢SA (⊣SA) to mean that A is (resp. is not) a theorem of S, and similarly for P − W.

We consider various strengthenings of the combinatorial principle ◊+ which are provable from V = L, and give applications in set theory.