In the paper Mathematics of infinity, Martin-Löf extends his intuitionistic type theory with fixed “choice sequences”. The simplest, and most important instance, is given by adding the axioms

to the type of natural numbers. Martin-Löf's type theory can be regarded as an extension of Heyting arithmetic (HA). In this note we state and prove Martin-Löf's main result for this choice sequence, in the simpler setting of HA and other arithmetical theories based on intuitionistic logic (Theorem A). We also record some remarkable properties of the resulting systems; in general, these lack the disjunction property and may or may not have the explicit definability property. Moreover, they represent all recursive functions by terms.

We build models where all -sets of reals are measurable and (or) have the property of Baire and (or) are Ramsey. We will show that there is no implication between any of these properties for -sets of reals.

The aim of this paper is to introduce a formal system STW of self-referential truth, which extends the classical first-order theory of pure combinators with a truth predicate and certain approximation axioms. STW naturally embodies the mechanisms of general predicate application/abstractionon a par with function application/abstraction; in addition, it allows non-trivial constructions, inspired by generalized recursion theory. As a consequence, STW provides a smooth inner model for Myhill's systems with levels of implication.

In this paper we extend the models for the “logic of categories” to a wider class of categories than is usually considered. We consider two kinds of logic, a restricted first-order logic and the full higher-order logic of elementary topoi.

The restricted first-order logic has as its only logical symbols ∧, ∃, Τ, and =. We interpret this logic in a category with finite limits equipped with a factorization system (in the sense of [4]). We require to satisfy two additional conditions: ⊆ Monos, and any pullback of an arrow in is again in . A category with a factorization system satisfying these conditions will be called an EM-category.

The interpretation of the restricted logic in EM-categories is given in §1. In §2 we give an axiomatization for the logic, and in §§3 and 5 we give two completeness proofs for this axiomatization. The first completeness proof constructs an EM-category out of the logic, in the spirit of Makkai and Reyes [8], though the construction used here differs from theirs. The second uses Boolean-valued models and shows that the restricted logic is exactly the ∧, ∃-fragment of classical first-order logic (adapted to categories). Some examples of EM-categories are given in §4.

The restricted logic is powerful enough to handle relations, and in §6 we assign to each EM-category a bicategory of relations Rel() and a category of “functional relations” fr. fr is shown to be a regular category, and it turns out that Rel( and Rel(fr) are biequivalent bicategories. In §7 we study complete objects in an EM-category where an object of is called complete if every functional relation into is yielded by a unique morphism into . We write c for the full subcategory of consisting of the complete objects. Complete objects have some, but not all, of the properties that sheaves have in a category of presheaves.

Let be an admissible set. A sentence of the form is a sentence if φ ∈ (φ is ∨ Φ where Φ is an -r.e. set of sentences from ). A sentence of the form is an , sentence if φ is a sentence. A class of structures is, for example, a ∀1 class if it is the class of models of a ∀1() sentence. Thus ∀1() is a class of classes of structures, and so forth.

Let i, be the structure 〈i, <〉, for i > 0. Let Γ be a class of classes of structures. We say that a sequence J1, …, Ji,…, i < ω, of classes of structures is a Γ sequence if Ji ∈ Γ, i < ω, and there is I ∈ Γ such that ∈ Ji, if and only if [],i, where [,] is the disjoint sum. A class Γ of classes of structures has the easy uniformization property if for every Γ sequence J1,…, Ji,…, i < ω, there is a Γ sequence J′t, …, J′i, …, i < ω, such that J′i ⊆ Ji, i < ω, ⋃J′i = ⋃Ji, and the J′i are pairwise disjoint. The easy uniformization property is an effective version of Kuratowski's generalized reduction property that is closely related to Moschovakis's (topological) easy uniformization property.

We show over countable structures that ∀1() and ∃2() have the easy uniformization property if is a countable admissible set with an infinite member, that and have the easy uniformization property if α is countable, admissible, and not weakly stable, and that and have the easy uniformization properly. The results proved are more general. The result for answers a question of Vaught(1980).

We present a Kripke model for Girard's Linear Logic (without exponentials) in a conservative fashion where the logical functors beyond the basic lattice operations may be added one by one without recourse to such things as negation. You can either have some logical functors or not as you choose. Commutativity and associativity are isolated in such a way that the base Kripke model is a model for noncommutative, nonassociative Linear Logic. We also extend the logic by adding a coimplication operator, similar to Curry's subtraction operator, which is residuated with Linear Logic's cotensor product. And we can add contraction to get nondistributive Relevance Logic. The model rests heavily on Urquhart's representation of nondistributive lattices and also on Dunn's Gaggle Theory. Indeed, the paper may be viewed as an investigation into nondistributive Gaggle Theory restricted to binary operations. The valuations on the Kripke model are three valued: true, false, and indifferent. The lattice representation theorem of Urquhart has the nice feature of yielding Priestley's representation theorem for distributive lattices if the original lattice happens to be distributive. Hence the representation is consistent with Stone's representation of distributive and Boolean lattices, and our semantics is consistent with the Lemmon-Scott representation of modal algebras and the Routley-Meyer semantics for Relevance Logic.

In this paper, assuming large cardinals, we prove the consistency of the following:

Let n ∈ ω and k1, k2 ≤ n. Let f: ω → {k1, k2} be such that for all n1 < n2 ∈ f−1{k1},n2 − n1 ≥ 4. Then the set

is stationary in

The above is equivalent to the statement that for any structure on on ℵω, there is ≺ A such that ∣∣ = ωn and for all m > n, cf( ∩ ωm) = ωf(m).

Let X be a standard Borel space (i.e., a Polish space with the associated Borel structure), and let E be a countable Borel equivalence relation on X, i.e., a Borel equivalence relation E for which every equivalence class [x]E is countable. By a result of Feldman-Moore [FM], E is induced by the orbits of a Borel action of a countable group G on X.

The structure of general countable Borel equivalence relations is very little understood. However, a lot is known for the particularly important subclass consisting of hyperfinite relations. A countable Borel equivalence relation is called hyperfinite if it is induced by a Borel ℤ-action, i.e., by the orbits of a single Borel automorphism. Such relations are studied and classified in [DJK] (see also the references contained therein). It is shown in Ornstein-Weiss [OW] and Connes-Feldman-Weiss [CFW] that for every Borel equivalence relation E induced by a Borel action of a countable amenable group G on X and for every (Borel) probability measure μ on X, there is a Borel invariant set Y ⊆ X with μ(Y) = 1 such that E ↾ Y (= the restriction of E to Y) is hyperfinite. (Recall that a countable group G is amenable if it carries a finitely additive translation invariant probability measure defined on all its subsets.) Motivated by this result, Weiss [W2] raised the question of whether every E induced by a Borel action of a countable amenable group is hyperfinite. Later on Weiss (personal communication) showed that this is true for G = ℤn. However, the problem is still open even for abelian G. Our main purpose here is to provide a weaker affirmative answer for general amenable G (and more—see below). We need a definition first. Given two standard Borel spaces X, Y, a universally measurable isomorphism between X and Y is a bijection ƒ: X → Y such that both ƒ, ƒ-1 are universally measurable. (As usual, a map g : Z → W, with Z and W standard Borel spaces, is called universally measurable if it is μ-measurable for every probability measure μ on Z.) Notice now that to assert that a countable Borel equivalence relation on X is hyperfinite is trivially equivalent to saying that there is a standard Borel space Y and a hyperfinite Borel equivalence relation F on Y, which is Borel isomorphic to E, i.e., there is a Borel bijection ƒ: X → Y with xEy ⇔ ƒ(x)F ƒ(y). We have the following theorem.

We establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, complete f-rings are “boundedly algebraically compact” in the language (+, −, ·, ∧, ∨, ≤), and the positive cone of a complete l-group with infinity adjoined is algebraically compact in the language (+, ∨, ≤). We also give an example with any first-order language. The proofs can be translated into “naive set theory” in a uniform way.

A Skolem class is a class of formulas of pure quantification theory in Skolem normal form: closed, prenex formulas with prefixes ∀…∀∃…∃. (Pure quantification theory contains quantifiers, truth-functions, and predicate letters, but neither the identity sign nor function letters.) The Gödel Class, in which the number of universal quantifiers is limited to two, was shown effectively solvable (for satisfiability) sixty years ago [G1]. Various solvable Skolem classes that extend the Gödel Class can be obtained by allowing more universal quantifiers but restricting the combinations of variables that may occur together in atomic subformulas [DG, Chapter 2]. The Gödel Class and these extensions are also finitely controllable, that is, every satisfiable formula in them has a finite model. In this paper we isolate a model-theoretic property that connects the usual solvability proofs for these classes and their finite controllability. For formulas in the solvable Skolem classes, the property is necessary and sufficient for satisfiability. The solvability proofs implicitly relied on this fact. Moreover, for any formula in Skolem normal form, the property implies the existence of a finite model.

The proof of the latter implication uses the random models technique introduced in [GS] for the Gödel Class and modified and applied in [Go] to the Maslov Class. The proof thus substantiates the claim made in [Go] that random models can be adapted to the Skolem classes of [DG, Chapter 2]. As a whole, the results of this paper provide a more general, systematic approach to finite controllability than previous methods.

We shall present two novel ways of deriving simply typed combinatory models. These are of interest in a constructive setting. First we look at extension models, which are certain subalgebras of full function space models. Then we shall show how the space of singletons of a combinatory model can itself be made into one. The two and the algebras in between will have many common features. We use these two constructions in proving:

We know quite a lot about the general structure of ω-stable solvable centerless groups of finite Morley rank. Abelian groups of finite Morley rank are also well-understood. By comparison, nonabelian nilpotent groups are a mystery except for the following general results:

• An ω1-categorical torsion-free nonabelian nilpotent group is an algebraic group over an algebraically closed field of characteristic 0 [Z3].

• A nilpotent group of finite Morley rank is the central product of a definable subgroup of finite exponent and of a definable divisible subgroup [N3].

• A divisible nilpotent group of finite Morley rank is the direct product of its torsion part (which is central) and of a torsion-free subgroup [N3].

However, we do not understand nilpotent groups of bounded exponent. It seems that the classification of nilpotent (but nonabelian) p-groups of finite Morley rank is impossible. Even the nilpotent groups of Morley rank 2 contain insurmountable difficulties [C], [T] . At first glance, this may seem to be an obstacle to proving the Cherlin-Zil'ber conjecture (“simple groups of finite Morley rank are algebraic groups”). Our purpose in this article is to show that if such a group is a definable subgroup of a nonnilpotent group, then it is possible to obtain a classification within the boundaries of our present knowledge. In this respect, our article may be considered as a relief to those who are trying to classify simple groups of finite Morley rank.

Before explicitly stating our result, we need the following definition.

The study of recursion categories was introduced in [DH] to carry out an algebraic and intrinsic investigation of structures and phenomena which arise in the classical recursion theory. In this paper a recursion categorical arrangement is proposed for some of the concepts of reduction and relativization which are commonplace in studying classical recursive functions and operators. Indeed, this introduction can be done in a natural way, using categorical concepts already defined, without resorting to special structures. In developing the subject outlined one also has the opportunity of discussing the concept of uniform proof in the context of the recursion categories.

In well-known papers ([A-K1], [A-K2], and [E]) J. Ax, S. Kochen, and J. Ershov prove a transfer theorem for henselian valued fields. Here we prove an analogue for henselian valued and ordered fields. The orders for which this result apply are the usual orders and also the higher level orders introduced by E. Becker in [Bl] and [B2]. With certain restrictions, two henselian valued and ordered fields are elementarily equivalent if and only if their value groups (with a little bit more structure) and their residually ordered residue fields (a henselian valued and ordered field induces in a natural way an order in its residue field) are elementarily equivalent. Similar results are proved for elementary embeddings and ∀-extensions (extensions where the structure is existentially closed).

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call and , and , show that suffices to prove B.C.T.II. Some model theory of and its importance in view of Hilbert's program is discussed, as well as applications of our results to functional analysis.

Suppose κ is a supercompact cardinal and λ > κ. We study the relationship between the partition properly and the weak partition properly for normal ultrafilters on Pκλ. On the one hand, we show that the following statement is consistent, given an appropriate large cardinal assumption: The partition property and the weak partition properly are equivalent, there are many normal ultrafilters that satisfy these properties, and there are many normal ultrafilters that do not satisfy these properties. On the other hand, we consider the assumption that, for some λ > κ, there exists a normal ultrafilter U on Pκλ such that U satisfies the weak partition property but does not satisfy the partition property. We show that this assumption is implied by the assertion that there exists a cardinal γ > κ such that γ is γ+-supercompact, and, assuming the GCH, it implies the assertion that there exists a cardinal γ > κ such that γ is a measurable cardinal with a normal ultrafilter concentrating on measurable cardinals.

It is shown to be consistent that the reals are covered by ℵ1, meagre sets yet there is a Baire class 1 function which cannot be covered by fewer than ℵ2, continuous functions. A new cardinal invariant is introduced which corresponds to the least number of continuous functions required to cover a given function. This is characterized combinatorially. A forcing notion similar to, but not equivalent to, superperfect forcing is introduced.

Let E ⊲ F iff E and F are extenders and E ∈ Ult(V, F). Intuitively, E ⊲ F implies that E is weaker—embodies less reflection—than F. The relation ⊲ was first considered by W. Mitchell in [M74], where it arises naturally in connection with inner models and coherent sequences. Mitchell showed in [M74] that the restriction of ⊲ to normal ultrafilters is well-founded.

The relation ⊲ is now known as the Mitchell order, although it is not actually an order. It is irreflexive, and its restriction to normal ultrafilters is transitive, but under mild large cardinal hypotheses, it is not transitive on all extenders. Here is a counterexample. Let κ be (λ + 2)-strong, where λ > κ and λ is measurable. Let E be an extender with critical point κ and let U be a normal ultrafilter with critical point λ such that U ∈ Ult(V, E). Let i: V → Ult(V, U) be the canonical embedding. Then i(E) ⊲ U and U ⊲ E, but by 3.11 of [MS2], it is not the case that i(E) ⊲ E. (The referee pointed out the following elementary proof of this fact. Notice that i ↾ Vλ+2 ∈ Ult(V, E) and X ∈ Ea ⇔ X ∈ i(E)i(a). Moreover, we may assume without loss of generality that = support(E). Thus, if i(E) ∈ Ult(V, E), then E ∈ Ult(V, E), a contradiction.)

By going to much stronger extenders, one can show the Mitchell order is not well-founded. The following example is well known. Let j: V → M be elementary, with Vλ ⊆ M for λ = joω(crit(j)). (By Kunen, Vλ+1 ∉ M.) Let E0 be the (crit(j), λ) extender derived from j, and let En+1 = i(En), where i: V → Ult(V, En) is the canonical embedding. One can show inductively that En is an extender over V, and thereby, that En+1 ⊲ En for all n < ω. (There is a little work in showing that Ult(V, En+1) is well-founded.)

We consider the existence of coherent families of finite-to-one functions on countable subsets of an uncountable cardinal κ. The existence of such families for κ implies the existence of a winning 2-tactic for player TWO in the countable-finite game on κ. We prove that coherent families exist on κ = ωn, where n ∈ ω, and that they consistently exist for every cardinal κ. We also prove that iterations of Axiom A forcings with countable supports are Axiom A.

Frege's development of the theory of arithmetic in his Grundgesetze der Arithmetik has long been ignored, since the formal theory of the Grundgesetze is inconsistent. His derivations of the axioms of arithmetic from what is known as Hume's Principle do not, however, depend upon that axiom of the system—Axiom V—which is responsible for the inconsistency. On the contrary, Frege's proofs constitute a derivation of axioms for arithmetic from Hume's Principle, in (axiomatic) second-order logic. Moreover, though Frege does prove each of the now standard Dedekind-Peano axioms, his proofs are devoted primarily to the derivation of his own axioms for arithmetic, which are somewhat different (though of course equivalent). These axioms, which may be yet more intuitive than the Dedekind-Peano axioms, may be taken to be “The Basic Laws of Cardinal Number”, as Frege understood them.

Though the axioms of arithmetic have been known to be derivable from Hume's Principle for about ten years now, it has not been widely recognized that Frege himself showed them so to be; nor has it been known that Frege made use of any axiomatization for arithmetic whatsoever. Grundgesetze is thus a work of much greater significance than has often been thought. First, Frege's use of the inconsistent Axiom V may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establish may invalidate certain of his claims regarding the philosophical significance of his work (viz., the establishment of Logicism), but it should not be allowed to obscure his mathematical accomplishments and his contribution to our understanding of arithmetic. Second, Frege's knowledge that arithmetic is derivable from Hume's Principle raises important sorts of questions about his philosophy of arithmetic. For example, “Why did Frege not simply abandon Axiom V and take Hume's Principle as an axiom?”