We show that given ω many supercompact cardinals, there is a generic extension in which the tree property holds at ℵω2+ 1 and the SCH fails at ℵω2.

This paper studies several systems of the transfinite iteration and autonomous progression of self-applicable truth and determines their proof-theoretic strength.

Since the publication in 1967 of the two papers [1] and [2] by Manuel Blum, the techniques and results of “pure” recursion theory, particularly the recursion theorem and priority methods, have come to play an increasingly important role in studies of computational complexity. This paper gives a typical application of the recursion theorem with a fairly intricate diagonalization to answer a question raised by Blum in [3]. Roughly, we prove the existence of functions which have the property that if we are given any program for computing the function and want to pass to a program which computes the function much more efficiently, then we can only do so at the expense of obtaining a much larger program: the function which describes the necessary increase in the size of the more efficient program must grow more rapidly than any recursive function.

It has long been known that every free associative algebra can be embedded in a skew field [11]; in fact there are many different embeddings, all obtainable by specialization from the ‘universal field of fractions’ of the free algebra (cf. [5, Chapter 7]). This makes it reasonable to call the latter the free field; see §2 for precise definitions. The existence of this free field was first established by Amitsur [1], but his proof is rather indirect and does not provide anything like a normal form for the elements of the field. Actually one cannot expect to find such a normal form, since it does not even exist in the field of fractions of a commutative integral domain, but at least one can raise the word problem for free fields: Does there exist an algorithm for deciding whether a given expression for an element of the free field represents zero?

Now some recent work has revealed a more direct way of constructing free fields ([4], [5], [6]), and it is the object of this note to show how this method can be used to solve the word problem for free fields over infinite ground fields. In this connexion it is of interest to note that A. Macintyre [9] has shown that the word problem for skew fields is recursively unsolvable. Of course, every finitely generated commutative field has a solvable word problem (see e.g. [12]).

The construction of universal fields of fractions in terms of full matrices is briefly recalled in §2, and it is shown quite generally for a ring R with a field of fractions inverting all full matrices, that if the set of full matrices over R is recursive, then the universal field has a solvable word problem. This holds more generally if the precise set of matrices over R inverted over the field is recursive, but it seems difficult to exploit this more general statement.

A notion of an epistemic state is introduced as a generalization of common representations suggested for belief change. Based on it, a new kind of nonmonotonic inference relation corresponding to belief contractions is defined. A number of representation results is established that cover both traditional AGM contractions and contractions that do not satisfy recovery.

We analyze Zorn's Lemma and some of its consequences for Boolean algebras in a constructive setting. We show that Zorn's Lemma is persistent in the sense that, if it holds in the underlying set theory, in a properly stated form it continues to hold in all intuitionistic type theories of a certain natural kind. (Observe that the axiom of choice cannot be persistent in this sense since it implies the law of excluded middle.) We also establish the persistence of some familiar results in the theory of (complete) Boolean algebras—notably, the proposition that every complete Boolean algebra is an absolute subretract. This (almost) resolves a question of Banaschewski and Bhutani as to whether the Sikorski extension theorem for Boolean algebras is persistent.

The main purpose of this paper is to show that there exists a prime differentially closed extension over each differentially perfect field. We do this in a roundabout manner by first giving new and simple axioms for the theory of differentially closed fields (in the manner of Blum [1] for characteristic 0) and by proving that this theory is the model completion of the theory of differentially perfect fields. This paper can be read independently from [10], where we gave more complicated axioms for the same theory (in the manner of Robinson [6] for characteristic 0).

I am indebted to E. R. Kolchin for answering many questions and for making the manuscript of his forthcoming book [2] available to me.

Monadic (second-order) theories of well-orderings were first studied by Büchi [1], [2], [3] using concepts of automata theory. There it was shown that the monadic theory of ω, the monadic theory of any countable ordinal, and the monadic theory of ω1 are decidable. Expansions of the well-ordering (ω, <) by further relations were considered in [4], [5], [8] and [9], for example. Concerning such expansions, Buchi and Landweber [4] asked whether there is a set P ⊂ ω such that the weak monadic theory of (ω, <, P) is decidable and the (strong) monadic theory of (ω, <, P) is undecidable. In this note we give a negative answer by proving the following general theorem: If α is an ordinal and an n-tuple of subsets of α, then the monadic theory of (α, <, ) is decidable provided the monadic theory of (cf (α), <), i.e. of the cofinality of α, and the bounded monadic theory of (or, <, ) are decidable. (In the bounded monadic theory the second-order variables range only over bounded subsets of α.) Also we show that in the bounded and the (strong) monadic theory of a structure (α, <, ) the same classes of subsets of α are definable. For the proofs we use a result of Shelah [7] and a suitable version of a combinatorial argument which was introduced by Büchi [1] and McNaughton [6] into the study of monadic theories.

Definition. A cardinal κ is strong iff for every x there is an elementary embedding j:V → M with critical point κ such that x ∈ M.

κ is superstrong iff ∃j:V → M with critical point κ such that Vj(κ) ∈ M.

These definitions are natural weakenings of supercompactness and hugeness respectively and display some of the same relations. For example, if κ is superstrong then Vκ ⊨ “∃ proper class of strong cardinals”, but the smallest superstrong cardinal is less than the smallest strong cardinal (if both types exist). (See [SRK] and [Mo] for the arguments involving supercompact and huge, which translate routinely to strong and superstrong.)

Given any two types of large cardinals, a typical vague question which is often asked is “How large is the gap in consistency strength?” In one sense the gap might be considered relatively small, since the “higher degree” strong cardinals described below (a standard trick that is nearly always available) and the Shelah and Woodin hierarchies of cardinals (see [St] for a definition of these) seem to be (at least at this point in time) the only “natural” large cardinal properties lying between strong cardinals and superstrong cardinals in consistency strength.

A pointwise definable model is one in which every object is definable without parameters. In a model of set theory, this property strengthens V = HOD, but is not first-order expressible. Nevertheless, if ZFC is consistent, then there are continuum many pointwise definable models of ZFC. If there is a transitive model of ZFC, then there are continuum many pointwise definable transitive models of ZFC. What is more, every countable model of ZFC has a class forcing extension that is pointwise definable. Indeed, for the main contribution of this article, every countable model of Gödel-Bernays set theory has a pointwise definable extension, in which every set and class is first-order definable without parameters.

We prove that it is decidable of a finite algebra whether it has a near-unanimity term operation, which settles a ten-year-old problem. As a consequence, it is decidable of a finite algebra in a congruence distributive variety whether it admits a natural duality.

If T is a model complete theory with the strict order property, then the theory of the models of T with an automorphism has no model companion.

We prove that certain pairs of ordered structures are dependent. Among these structures are dense and tame pairs of o-minimal structures and further the real field with a multiplicative subgroup with the Mann property, regardless of whether it is dense or discrete.

It is consistent with ¬ CH that every universal theory of relational structures with the joint embedding property and amalgamation for -(3)-diagrams has a universal model of cardinality ℵ1. For classes with amalgamation for -(4)-diagrams it is consistent that and there is a universal model of cardinality ℵ2.

We show, first, that the normalization procedure for S4 modal logic presented by Dag Prawitz in [5] does not work. We then develop a new natural deduction system for S4 classical modal logic that is logically equivalent to that of Prawitz, and we show that every derivation in this new system can be transformed into a normal derivation.

The paper studies how the localic notion of sublocale transfers to formal topology. For any formal topology (not necessarily with positivity predicate) we define a sublocale to be a cover relation that includes that of the formal topology. The family of sublocales has set-indexed joins. For each set of base elements there are corresponding open and closed sublocales, boolean complements of each other. They generate a boolean algebra amongst the sublocales. In the case of an inductively generated formal topology, the collection of inductively generated sublocales has coframe structure.

Overt sublocales and weakly closed sublocales are described, and related via a new notion of “rest closed” sublocale to the binary positivity predicate. Overt, weakly closed sublocales of an inductively generated formal topology are in bijection with “lower powerpoints”, arising from the impredicative theory of the lower powerlocale.

Compact sublocales and fitted sublocales are described. Compact fitted sublocales of an inductively generated formal topology are in bijection with “upper powerpoints”, arising from the impredicative theory of the upper powerlocale.

We prove the existence of p-ideals that are nonmeagre subsets of (ω) under various set-theoretic assumptions.

A combinatorial criterium is given when a monadic quantifier is expressible by means of universe-independent monadic quantifiers of width n. It is proved that the corresponding hierarchy does not collapse. As an application, it is shown that the second resumption (or vectorization) of the Härtig quantifier is not definable by monadic quantifiers. The techniques rely on Ramsey theory.

At the source of what is now known as “geometric stability theory” was Zil'ber's intuition that the essential properties of an aleph-one-categorical theory were controlled by the geometries of its minimal types. (However, the situation is much more complex than was assumed in Zil'ber [1984], since the main conjecture of that paper has been disproved by Hrushovski.) This is not unnatural in this unidimensional case, where all these geometries have isomorphic contractions, but it was even realized later, in Cherlin, Harrington and Lachlan [1985] and Buechler [1986], that, for any superstable theory with finite ranks, a certain “local” property, i.e. a property satisfied by the geometry of each type of rank one (namely: to have a projective contraction), was equivalent to a “global” one (the theory is one-based, hence satisfies a coordinatization lemma). Then it was shown, in Pillay [1986], that this situation does not generalize to the infinite rank case, that, even for a theory of rank omega, the (local) assumption of projectivity for all the regular types of the theory does not have an exact global counterpart.

To clarify this kind of phenomena, I suggest here the elimination of their geometrical aspect, considering only the case where all of the geometries are degenerate. I will study various notions of triviality, which make sense in a stable context, and turn out to be equivalent in the finite rank case; some of them have a definite global flavour, others are of local character.