There are human beings whose intellectual power exceeds that of ordinary men. In my life, in my personal experience, there were three such men, and one of them was Andrei Nikolaevich Kolmogorov. I was lucky enough to be his immediate pupil. He invited me to be his pupil at the third year of my being student at the Moscow University. This talk is my tribute, my homage to my great teacher.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903. He graduated from Moscow University in 1925, finished his post-graduate education at the same University in 1929, and since then without any interruption worked at Moscow University till his death on October 20, 1987, at the age 84½.

Kolmogorov was not only one of the greatest mathematicians of the twentieth century. By the width of his scientific interests and results he reminds one of the titans of the Renaissance. Indeed, he made prominent contributions to various fields from the theory of shooting to the theory of versification, from hydrodynamics to set theory. In this talk I should like to expound his contributions to mathematical logic.

Here the term “mathematical logic” is understood in a broad sense. In this sense it, like Gallia in Caesarian times, is divided into three parts:

(1) mathematical logic in the strict sense, i.e. the theory of formalized languages including deduction theory,

(2) the foundations of mathematics, and

(3) the theory of algorithms.

During the 1989 European ASL Summer Meeting in Berlin, the authors gave a series of eight lectures (short course) on the topic of the title. This survey article consists basically of the lecture notes for that course distributed to the participants of that conference. We have purposely tried in this printed version to preserve the informal style of the original notes.

Let us say first a few things aboui the content of these lectures. Our aim has been to present some recent work in descriptive set theory and its applications to an area of harmonic analysis. Typical uses of descriptive set theory in analysis are most often through regularity properties of definable sets, like measurability, the property of Baire, capacitability, etc., which are used to show that certain problems have solutions that behave nicely. In the theory we will present, definability itself, in fact the precise analysis of the “definable complexity” of certain sets, will be the main concern. It will be through such knowledge that we will be able to infer important structural properties of various objects which will then be used to solve analysis problems.

The first lecture provides a short historical introduction to the subject of uniqueness for trigonometric series, which is the area of harmonic analysis whose problems are the origin of this work. As is well known, it was Cantor who proved the first major result in this subject in 1870, and it was his subsequent work here that led him to the creation of set theory.

We prove that if ℵα is uncountable and regular, then the Beth-closure of ℒωω(Qα) is not a sublogic of ℒαω(Qn), where Qn is the class of all n-ary generalized quantifiers. In particular, B(ℒωω(Qα)) is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set Q of Lindström quantifiers such that B(ℒωω(Qα)) ≤ ℒωω(Q).

Let be the ring of all entire functions of one complex variable, and let DA be the subring of those entire functions that are differentially algebraic (DA); that is, they satisfy a nontrivial algebraic differential equation.

where P is a non-identically-zero polynomial in its n + 2 variables. It seems not to be known whether DA is elementarily equivalent to . This would mean that DA and have exactly the same true statements about them, in the first-order language of rings. (Roughly speaking, a sentence about a ring R is first-order if it has finite length and quantifies only over elements (i.e., not subsets or functions or relations) of R.) It follows from [NAN] that DA and are not isomorphic as rings, but this does not answer the question of elementary equivalence.

We give a sufficient condition for a countable model M of PA to be expandable to an ω-model of AST with absolute Ω-orderings. The condition is in terms of saturation schemes or, equivalently, in terms of the ability of the model to code sequences which have some kind of definition in (M, ω). We also show that a weaker scheme of saturation leads to the existence of wellorderings of the model with nice properties. Finally, we answer affirmatively the question of whether the intersection of all β-expansions of a β-expandable model M is the set RA(M, ω)—the ramified analytical hierarchy over (M, ω).

The results are based on forcing constructions.

Suppose that U and U′ are normal ultrafilters associated with some supercompact cardinal. How may we compare U and U′? In what ways are they similar, and in what ways are they different? Partial answers are given in [1], [2], [3], [5], [6], and [7]. In this paper, we continue this study.

In [6], Menas introduced a combinatorial principle χ(U) of normal ultrafilters U associated with supercompact cardinals, and showed that normal ultrafilters satisfying this property also satisfy a partition property. In [5], Kunen and Pelletier showed that this partition property for U does not imply χ(U). Using results from [3], we present a different method of finding such normal ultrafilters which satisfy the partition property but do not satisfy χ(U). Our method yields a large collection of such normal ultrafilters.

This note deals with a proof-theoretic characterisation of certain complexity classes of functions in fragments of intuitionistic bounded arithmetic. In this Introduction we survey the background and state our main result.

We follow Buss [B1] and consider a language for arithmetic whose nonlogical symbols are 0, S (the successor operation Sx = x + 1), +, ·, ∣ ∣ (∣x∣ being the number of digits in the binary notation for x), rounded down to the nearest integer), # (x#y = 2∣x∣∣y∣) and ≤. We define 1 = S0, 2 = S1, s0x = 2x and s1x = 2x + 1. In Buss's approach the functions s0 and s1 play a special role. Notice that six is the number obtained from x by suffixing the digit i to its binary representation, and thus the natural numbers are generated from 0 by repeated applications of the operations s0 and s1. This means that they satisfy the induction scheme

Using the fact that is x with its last binary digit deleted, this can be stated more compactly in the following form, called by Buss the polynomial induction or PIND schema:

Buss defined a theory S2 consisting of a finite set BASIC of open axioms and the PIND-schema restricted to bounded formulas ϕ. The topic of bounded arithmetic is concerned with S2 and its fragments.

Let be an admissible structure. A cPCd() class is the class of all models of a sentence of the form , where is an -r.e. set of relation symbols and Φ is an -r.e. set of formulas of ℒ∞,ω that are in . The main theorem is a generalization of the following: Let be a pure countable resolvable admissible structure such that is not Σ-elementarily embedded in HYP(). Then a class K of countable structures whose universes are sets of urelements is a cPCd() class if and only if for some Σ formula σ (with parameters from ), is in K if and only if is a countable structure with universe a set of urelements and σ, where , the smallest admissible set above relative to , is a generalization of HYP to structures with similarity type Σ over that is defined in this article. Here we just note that when Lα is admissible, HYPLα() is Lβ() for the least β ≥ α such that Lβ() is admissible, and so, in particular, that is just HYP() in the usual sense when has a finite similarity type.

The definition of is most naturally formulated using Adamson's notion of a +-admissible structure (1978). We prove a generalization from admissible to +-admissible structures of the well-known truncation lemma. That generalization is a key theorem applied in the proof of the generalized Spector-Gandy theorem.

Our purpose in this note is to study countable ℵ0-categorical structures whose theories are tree-decomposable in the sense of Baldwin and Shelah. The permutation group corresponding to such a structure can be decomposed in a canonical manner into simpler permutation groups in the same class. As an application of the analysis we show that these structures are finitely homogeneous.

We generalize to theories of modules (complete or not) a result of U. Felgner stating that a complete theory of abelian groups is a Horn theory if and only if it is closed under products. To prove this we show that a reduced product of modules ΠFMi (i ϵ I) is elementarily equivalent to a direct product of ultraproducts of the modules Mi(i ϵ I).

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperinlegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y, x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. U is called a good cut if there exists a U-meager subset of of Loeb measure one. Otherwise U is bad. In this paper we discuss the questions of Keisler and Leth about the existence of bad cuts and related cuts. We show that assuming b > ω1, every hyperfinite time line has a cut with both cofinality and coinitiality uncountable. We construct bad cuts in a nonstandard universe under ZFC. We also give two results about the existence of other kinds of cuts.

In an ω-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y,x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. A subset B of is called a U-Lusin set in if B is uncountable and for any Loeb-Borel U-meager subset X of , B ⋂ X is countable. Here a Loeb-Borel set is an element of the σ-algebra generated by all internal subsets of : In this paper we answer some questions of Keisler and Leth about the existence of U-Lusin sets by proving the following facts. (1) If U = x/N = {y ϵ : ∀n ϵ ℕ(y < x/n)} for some x ϵ , then there exists a U-Lusin set of power κ if and only if there exists a Lusin set of the reals of power κ. (2) If U ≠ x/N but the coinitiality of U is ω, then there are no U-Lusin sets if CH fails. (3) Under ZFC there exists a nonstandard universe in which U-Lusin sets exist for every cut U with uncountable cofinality and coinitiality. (4) In any ω2-saturated nonstandard universe there are no U-Lusin sets for all cuts U except U = x/N.

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y, x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. The U-monad topology of is the quotient topology of the U-topological space modulo U. In this paper we answer a question of Keisler and Leth about the U-monad topologies by showing that when is κ-saturated and has cardinality κ,(1) if the coinitiality of U1, is uncountable, then the U1,-monad topology and the U2-monad topology are homcomorphic iff both U1, and U2 have the same coinitiality; and (2) can produce exactly three different U-monad topologies (up to homeomorphism) for those U's with countable coinitiality. As a corollary can produce exactly four different U-monad topologies if the cardinality of is ω1.

Let B be the random real forcing. Miller [Mi] asked if there are ZFC models M ⊆ N such that forcing with BM over N adds a dominating real. A YES answer was provided by Judah and Shelah in [JS], where in a long and sophisticated construction they built such models. In this paper we prove that forcing with BV over VI, where I is the infinitely often equal real forcing of [Mi], adds a dominating real over VI. This greatly simplifies the YES answer to Miller's question. Moreover it turns out that B may be replaced here by E, the eventually different real forcing of [Mi]. This answers the second part of Miller's question. We also prove that both side by side products I × B and I × E add a Hechler dominating real over V.

In this section we establish the main result of the paper; namely, we prove that forcing over VI with either of the posets BV or EV adds a dominating real over VI.

First we recall the definitions of I and E from [Mi]. The infinitely often equal real forcing is the set

ordered by extension. Miller [Mi] proves that I is ωω bounding.

We prove that a stable solvable group G which satisfies xn = 1 generically is of finite exponent dividing some power of n. Furthermore, G is nilpotent-by-finile.

A second result is that in a stable group of finite exponent, involutions either have big centralisers, or invert a subgroup of finite index (which hence has to be abelian).

On any reasonable definition of functions, neither the category of sets nor the category of small categories is cartesian closed in New Foundations (NF). The latter category is sometimes proposed as a foundation for category theory since it is among its own objects. Our result shows it is a poor one.

In NF, as in other set theories, a "function" f from a set A to a set B is defined to be a set f of ordered pairs 〈x, y〉 with x in A and y in B, such that (a) if 〈x, y〉 ∈ f and 〈x, y′〉 ∈ f then y = y′, and (b) for every x in A there is some y in B with 〈x, y〉 ∈ f. But in NF different definitions of ordered pairs give significantly different functions. I say a reasonable definition must give:

1. The formula z = 〈x, y〉 is stratifiable.

2. For every set S there is a set {〈x, x〉 ∣ x ∈ S}.

3. If f is a function from A to B, and g one from B to C, there is a set {〈x, z〉∣(∃y)〈x, y〉∈ f & 〈y, z〉∈ g}.

Principles 2 and 3 are needed for identity functions and composites. By principle 1, any sets A and B have a set A × B of all ordered pairs 〈x, y〉 with x in A and y in B, but it does not follow that functions exist making A × B a categorical product of A and B.

The purpose of this paper is an axiomatic study of the interrelations between certain continuity properties. We deal with principles which are equivalent to the statements “every mapping is sequentially nondiscontinuous”, “every sequentially nondiscontinuous mapping is sequentially continuous”, and “every sequentially continuous mapping is continuous”. As corollaries, we show that every mapping of a complete separable space is continuous in constructive recursive mathematics (the Kreisel-Lacombe-Schoenfield-Tsejtin theorem) and in intuitionism.

We consider some modal languages with a modal operator D whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

In this paper it is shown that the meet-inaccessible degrees are dense in R. The construction uses an 0′-priority argument. As a consequence, the meet-inaccessible degrees and the meet-accessible degrees give a partition of R into two sets, either of which is a nontrivial dense subset of R and generates R − {0} under joins (thus an automorphism base of R).

Under a sharp version of the assumption I∆0 ⊢ ¬ ∆0H we characterize models of I∆0 + BΣ1 having a proper end extension to a model of I∆0.

In [WP] Wilkie and Paris study the relationship between the existence of a proper end extension of a model and its “fullness”, which is related to a certain weak overspill principle (we recall the definition of fullness in §3). Let M be a countable nonstandard model of I∆0 + BΣ1. Under the hypothesis I∆0 ⊢ ¬ ∆0H they prove the following (Corollaries 7 and 8):

The following are equivalent:

1. 1) M has a proper end extension to a model of I∆0 + BΣ1.

2. 2) M is (I∆0 + BΣ1)-full.

Moreover, assuming that there is no t ∈ M such that for v ∈ M, 2[t/v]exists if and only if v < N, the following are equivalent:

1. 1) M has a proper end extension to a model of I∆0.

2. 2) M is I∆0-full.

Wilkie and Paris ask whether the assumption on the structure of the model can be eliminated from the second equivalence.

We eliminate it, but we sharpen the assumption I∆0 ⊢ ¬ ∆0H. So we partially answer their question.