Although there is no smallest ω model [6], Putnam and Gandy independently proved about 1963 that the class of ramified analytical sets, as defined by Cohen [3], form the smallest β model of analysis [2], [8]. This paper will consider other restricted classes of models, namely the βn models for integers n > 1 [10], and prove under appropriate assumptions the existence of minimum such models. In fact we shall construct the minimum βn model in a fashion similar to the procedure yielding the class of ramified analytical sets, but adding at each stage a segment of the sets in those already obtained (for n a fixed integer > 1).

Roughly speaking a βn model is an ω model absolute for n-set-quantifier assertions about its subsets of natural numbers. A β model is simply a β1 model. See Enderton and Friedman [4] for a further investigation of βn models.

Classical Ramsey theory (at least in its simplest form) is concerned with problems of the following kind: given a set X and a colouring of the set [X]n of unordered n-tuples from X, find a subset Y ⊆ X such that all elements of [Y]n get the same colour. Subsets with this property are called monochromatic or homogeneous, and a typical positive result in Ramsey theory has the form that when X is large enough and the number of colours is small enough we can expect to find reasonably large monochromatic sets.

Polychromatic Ramsey theory is concerned with a “dual” problem, in which we are given a colouring of [X]n and are looking for subsets Y ⊆ X such that any two distinct elements of [Y]n get different colours. Subsets with this property are called polychromatic or rainbow. Naturally if we are looking for rainbow subsets then our task becomes easier when there are many colours. In particular given an integer k we say that a colouring is k-bounded when each colour is used for at most k many n-tuples.

At this point it will be convenient to introduce a compact notation for stating results in polychromatic Ramsey theory. We recall that in classical Ramsey theory we write to mean “every colouring of [κ]n in k colours has a monochromatic set of order type α”. We will write to mean “every k-bounded colouring of [κ]n has a polychromatic set of order type α”. We note that when κ is infinite and k is finite a k-bounded colouring will use exactly κ colours, so we may as well assume that κ is the set of colours used.

Let μ be singular of uncountable cofinality. If μ > 2cf(μ), we prove that in ℙ = ([μ]μ, ⊇) as a forcing notion we have a natural complete embedding of Levy(ℵ0, μ+) (so ℙ collapses μ+ to ℵ0) and even Levy (). The “natural” means that the forcing ({p ∈ [μ] : p closed}, ⊇) is naturally embedded and is equivalent to the Levy algebra. Also if ℙ fails the χ-c.c. then it collapses χ to ℵ0 (and the parallel results for the case μ > ℵ0 is regular or of countable cofinality). Moreover we prove: for regular uncountable κ, there is a family P of κ partitions Ā = ⟨Aα : α < κ⟩ of κ such that for any A ∈ [κ]κ for some ⟨Aα : α < κ⟩ ∈ P we have α < κ ⇒ ∣Aα ∩ A∣ = κ.

As is well known, NF is a first-order theory whose language coincides with that of ZF. The nonlogical axioms of the theory are: Extensionality. (x)(y)[(z)(z ∈ x ↔ z ∈ y) → x = y].

Comprehension. (Ex)(y)(y ∈ x ↔ ψ) for every stratified ψ in which x does not occur free (a formula of NF is said to be stratified if it can be turned into a formula of the simple theory of types by adding type indices (natural numbers ≥ 0) to its variables).

Before stating our result, a few preliminaries are in order. Let T be the simple theory of types. If ψ is a formula of T, we denote by ψ+ the formula obtained from ψ by raising all type indices by 1. T* is the result of adding to T every axiom of the form ψ ↔ ψ+. A formula of T is n-stratified (n > 0) if it does not contain any type index ≥ n. A formula of NF is n-stratified if it can be turned into an n-stratified formula of T by adding type indices to its variables. (In practice, we shall allow ourselves to confuse an n-stratified formula of T with the corresponding n-stratified formula of NF). For n > 0, Tn (resp. ) is the subtheory of T (resp. T*) containing only n-stratified formulae. For n > 0, NFn is the subtheory of NF generated by those axioms of NF which are n-stratified. Let = 〈M0, M1,…,=, ∈〉 be a model of T.

Galois theory states that if L is a certain algebraic extension (called a Galois extension) of a field K, then there is a one-to-one correspondence (called a Galois correspondence) between subfields M, K ⊂ M ⊂ L and subgroups of the automorphism groups of L fixing the elements in K.

A subfield of a field L can be considered as a substructure of L in general model theory. However, a substructure is a subset closed under functions which are interpretations of function symbols in a given language, so the notion of substructure may change if we expand the language by adding definable notions. On the other hand a definably closed substructure is a subset which is closed under all definable functions, and it does not change by such expansions. If we are interested in subfields of an algebraically closed field of characteristic 0, these two notions are the same. But in a field of prime characteristic they are not equal. Speaking roughly, a Galois extension of a field K is an extension whose subfields are relatively definably closed. Poizat [4] showed that if a structure M has elimination of imaginaries there is a kind of Galois correspondence between definably closed substructures and subgroups of bijective elementary mappings of M.

In this paper, using Poizat's result we study algebraic types. As is well known, one motivation for developing the Galois theory was to show the unsolvability of equations with degree ≥ 5. We want to take this unsolvability as a special case of general phenomena. For this purpose, we introduce several notions which are stronger than mere algebraicity and study relations between these notions and groups of bijective elementary mappings. (See Theorems 3.7 and 3.9.)

An infinitary characterisation of the first-order sentences true in all substructures of a structure M is used to obtain partial reduction of the decision problem for such sentences to that for Th(M). For the relational structure 〈R, ≤, + 〉 this gives a decision procedure for the ∃x∀y-part of the theory of all substructures, yet we show that the ∃x1x2∀y-part, and the entire theory, is Π11-complete. The theory of all ordered subsemigroups of 〈R, ≤, + 〉 is also shown Π11-complete. Applications in the philosophy of science are mentioned.

Let Ω ≔ ℵ1. For any α< εΩ + 1 ≔ min {ξ > Ω: ξ = ωξ} let EΩ(α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let α* ≔ max(EΩ(α) ∪ {0}). A function f: εΩ + 1 → Ω is called essentially increasing, if for any α < εΩ + 1; f(α) ≥ α*: f is called essentially monotonic, if for any α, β<εΩ + 1;

Let be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions:

(a)

(b)

Let be the Howard-Bachmann ordinal, which is, for example, defined in [3]. The following theorem is shown: If f: εΩ + 1 → Ω is essentially monotonic and essentially increasing, then the order type of is less than or equal to .

A major theme in arithmetic combinatorics is proving multiple recurrence results on semigroups (such as Szemerédi’s theorem) and this can often be done using methods of ergodic Ramsey theory. What usually lies at the heart of such proofs is that, for actions of semigroups, a certain kind of one recurrence (mixing along a filter) amplifies itself to multiple recurrence. This amplification is proved using a so-called van der Corput difference lemma for a suitable filter on the semigroup. Particular instances of this lemma (for concrete filters) have been proven before (by Furstenberg, Bergelson–McCutcheon, and others), with a somewhat different proof in each case. We define a notion of differentiation for subsets of semigroups and isolate the class of filters that respect this notion. The filters in this class (call them ∂-filters) include all those for which the van der Corput lemma was known, and our main result is a van der Corput lemma for ∂-filters, which thus generalizes all its previous instances. This is done via proving a Ramsey theorem for graphs on the semigroup with edges between the semigroup elements labeled by their ratios.

We prove a variety of theorems about stationary set reflection and concepts related to internal approachability. We prove that an implication of Fuchino–Usuba relating stationary reflection to a version of Strong Chang’s Conjecture cannot be reversed; strengthen and simplify some results of Krueger about forcing axioms and approachability; and prove that some other related results of Krueger are sharp. We also adapt some ideas of Woodin to simplify and unify many arguments in the literature involving preservation of forcing axioms.

Regular groups and fields are common generalizations of minimal and quasi-minimal groups and fields, so the conjectures that minimal or quasi-minimal fields are algebraically closed have their common generalization to the conjecture that each regular field is algebraically closed. Standard arguments show that a generically stable regular field is algebraically closed. Let K be a regular field which is not generically stable and let p be its global generic type. We observe that if K has a finite extension L of degree n, then P(n) has unbounded orbit under the action of the multiplicative group of L.

Known to be true in the minimal context, it remains wide open whether regular, or even quasi-minimal, groups are abelian. We show that if it is not the case, then there is a counter-example with a unique nontrivial conjugacy class, and we notice that a classical group with one nontrivial conjugacy class is not quasi-minimal, because the centralizers of all elements are uncountable. Then, we construct a group of cardinality ω1 with only one nontrivial conjugacy class and such that the centralizers of all nontrivial elements are countable.

It follows constructively from weak versions of Markov's principle (MP) and of Church's thesis (WCT) that logical validity for single sentences is not arithmetically definable. This is a direct consequence of the constructive model-theoretic fact that, using MP and WCT, one can prove the categoricity of first-order Heyting arithmetic. By a straightforward refinement of this proof, we then obtain generalizations of the incompleteness theorem of Kreisel [K 2] as presented by van Dalen [Da] and improved by Leivant [L 1]. An analogous result for classical validity in r.e. models appears in [V].

Our methods of proof are new in that they rely not upon variants of the ideas of [K2] but upon a constructive proof idea inspired by the classical result of Tennenbaum ([Te], [E&K], [S]) on recursive models of arithmetic. This line of reasoning was suggested by the applications of readability to recursive mathematics described in [McC1], [McC2] and [McC3].

In his Mathematical logic, Quine adopts as axioms of quantification all statements specified by the first five of the six metatheorems listed below. The sixth serves as a rule of inference, and is the only primitive rule of inference used. The metatheorems in question are as follows:

The theme of the present paper is that *101 may be eliminated by means of an otherwise trivial shift in the meanings of *100, *102, *103, and *104.

In the statement of the above metatheorems and throughout the paper as a whole, we deviate from Quine's notational conventions only in using double quotes rather than corners and in using English letters rather than Greek ones as syntactical variables. Accordingly, ‘a’, ‘b’, and ‘d’ ambiguously denote variables ‘x’, ‘y’, ‘z’, and so on. The letters ‘p’ and ‘q’ ambiguously denote formulae, i.e. statements, and expressions which become statements when their contained free variables are supplanted by constants. Since we replace Quine's corners with double quotes, “(a)p” (for instance) is not the result of prefixing a parenthesized occurrence of the first letter of the alphabet to an occurrence of the sixteenth: “(a)p” is rather the result of prefixing any parenthesized variable a to any formula p.

Following Quine, we define the closure of p as p itself when p is a statement and as “(a1)(a2)…(an)p” where a1, a2, …, an are the sole variables free in p and where each ai is alphabetically prior to the corresponding ai+1.

There are inequalities between cardinal characteristics of the continuum that are true in any model of ZFC, but without a Borel morphism proving the inequality. We answer some questions from Blass [1].

In this sequel to [7] the method of the consistency proof presented there is extended to provide a proof of the ω-consistency of the systems of number theory which were there shown consistent. This proof yields sharp bounds on the ordinal recursions required to establish the κ-consistency of these systems. The main technical innovation of this proof is the extension of what are essentially the methods of Ackermann [1] for handling finite sets of critical formulae of the first and second kinds to apply as well to sets of critical formulae in which the rank ordering is transfinite. The notation, definitions, and results of [7] will be presupposed throughout; we suggest the reader keep a copy of that paper at hand.

Let ${\cal F}$ =(F; +, .,0, 1, D) be a differentially closed field. We consider the question of definability of the derivation D in reducts of ${\cal F}$ of the form ${\cal F}$R = (F; +, .,0, 1, P)P ε R where R is some collection of definable sets in ${\cal F}$. We give examples and nonexamples and establish some criteria for definability of D. Finally, using the tools developed in the article, we prove that under the assumption of inductiveness of Th (${\cal F}$R) model completeness is a necessary condition for definability of D. This can be seen as part of a broader project where one is interested in finding Ax-Schanuel type inequalities (or predimension inequalities) for differential equations.

We show that for any infinite cardinal κ, every strongly (κ + 1 )-strategically closed poset is strongly κ+-strategically closed if and only if APκ (the approachability property) holds, answering the question asked in [5]. We also give a complete classification of strengths of strategic closure properties and that of strong strategic closure properties respectively.

We prove that every countable jump upper semilattice can be embedded in , where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, and is the jusl of Turing degrees. As a corollary we get that the existential theory of 〈D, ≤T, ∨, ′〉 is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier free 1-type of jusl with 0 is realized in . On the other hand, we show that every quantifier free 1-type of jump partial ordering (jpo) with 0 is realized in . Moreover, we show that if every quantifier free type, p(x1,…, xn), of jpo with 0, which contains the formula x1 ≤ 0(m) & … & xn ≤ 0(m) for some m, is realized in , then every quantifier free type of jpo with 0 is realized in .

We also study the question of whether every jusl with the c.p.p. and size is embeddable in . We show that for the answer is no, and that for κ = ℵ1 it is independent of ZFC. (It is true if MA(κ) holds.)

For n < ω, expand the structure (n, S, I, F) (with S the successor relation, I, F as the initial and final element) by forming graphs with edge probability n−α for irrational α, with 0 < α < 1. The sentences in the expanded language, which have limit probability 1, form a complete and stable theory.

In the author's Relative lawlessness in intuitionistic analysis [this Journal, vol. 52 (1987), pp. 68–88] and An intuitionistic theory of lawlike, choice and lawless sequences [Logic Colloquium ’90, Springer-Verlag, Berlin, 1993, pp. 191–209] a notion of lawlessness relative to a countable information base was developed for classical and intuitionistic analysis. Here we simplify the predictability property characterizing relatively lawless sequences and derive it from the new axiom of closed data (classically equivalent to open data) together with a natural principle of invariance under finite translation. We characterize relative lawlessness in terms of a notion of forcing. Finally, we study relative lawlessness on an arbitrary fan and show that the collection of lawless binary sequences (which is comeager in the sense of Baire) has probability measure zero. The reasoning is predominantly constructive.

In this paper we give a new proof of the characterization of the closed fragment of the provability logic of Heyting's Arithmetic. We also provide a characterization of the closed fragment of the provability logic of Heyting's Arithmetic plus Markov's Principle and Heyting's Arithmetic plus Primitive Recursive Markov's Principle.