To what extent can mathematical thought be analyzed in formal terms? Gödel's theorems show the inadequacy of single formal systems for this purpose, except in relatively restricted parts of mathematics. However at the same time they point to the possibility of systematically generating larger and larger systems whose acceptability is implicit in acceptance of the starting theory. The engines for that purpose are what have come to be called reflection principles. These may be iterated into the constructive transfinite, leading to what are called recursive progressions of theories. A number of informative technical results have been obtained about such progressions (cf. Feferman [1962], [1964], [1968] and Kreisel [1958], [1970]). However, for some years I had hoped to give a more realistic and perspicuous finite generation procedure. This was first done in a rather special way in Feferman [1979] for the characterization of predicativity, which may be regarded as that part of mathematical thought implicit in our acceptance of elementary number theory. What is presented here is a new and simple notion of the reflective closure of a schematic theory which can be applied quite generally.

Two examples of schematic theories in the sense used here are versions of Peano arithmetic and Zermelo set theory.

In this paper we will study four forcing notions, two of them giving a minimal degree of constructibility. These constructions give answers to questions in [Ih].

We present a survey of proof theory in the USSR beginning with the paper by Kolmogorov [1925] and ending (mostly) in 1969; the last two sections deal with work done by A. A. Markov and N. A. Shanin in the early seventies, providing a kind of effective interpretation of negative arithmetic formulas. The material is arranged in chronological order and subdivided according to topics of investigation. The exposition is more detailed when the work is little known in the West or the original presentation can be improved using notions or results which appeared later. This includes such topics as Novikov's cut-elimination method (regular formulas) and Maslov's inverse method for the predicate logic.

A fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Härtig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted by LI, is in some sense very natural and has in consequence special interest. Properties of LI are studied in many papers. In [BF, Chapter VI] there is a short survey of some known results about LI. We feel that a more extensive exposition of these results is needed.

The aim of this paper is to give an overview of the present knowledge about the language LI and list a selection of open problems concerning it.

After the Introduction (§1), in §§2 and 3 we give the fundamental results about LI. In §4 the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories in LI. In §6 the spectra of sentences of LI are discussed, and §7 is devoted to properties of LI which depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Härtig quantifier.

Contents. §1. Introduction. §2. Preliminaries. §3. Basic results. §4. Model-theoretic properties of LI. §5. Decidability of theories with I. §6. Spectra of LI-sentences. §7. Independence results. §8. What is not yet known about LI. Bibliography.

The purpose of this paper is to give structural results on graphs lying in the product of two hyperfinite sets X and Y, whose Y-sections are either all internal sets or all of “small” cardinality with respect to the saturation assumption imposed on our nonstandard universe. These results generalize those of [KKML] and [HeRo]. In [KKML] Keisler, Kunen, Miller and Leth proved, among other results, that any countably determined function in the product of two internal sets X and Y can be covered by countably many internal functions provided that the nonstandard universe is at least ℵ-saturated. This shows that any countably determined function can be represented as a union of countably many restrictions of internal functions to countably determined sets. On the other hand, Henson and Ross use in [HeRo] Choquet's capacitability theorem to prove that any Souslin function in the product of two internal sets X and Y is a.e. equal to an internal function. (Here “a.e.” refers to an arbitrary but fixed bounded Loeb measure.) Therefore, in our terminology, every Souslin function possesses an internal a.e. lifting.

After the introductory §0, where all the necessary terminology is introduced, we continue by presenting the structural result for graphs all of whose Y-sections are of cardinality ≤κ (provided that the nonstandard universe is ≤κ+-saturated) in §1. We show that, under the above saturation assumption, a κ-determined graph with all of the Y-sections of cardinality ≤κ is covered by κ-many internal functions. Therefore, any such graph is a union of κ-many κ-determined functions. In particular if the graph in question is Borel, Souslin, κ-Borel or κ-Souslin (or a member of one of the Borel, κ-Borel or projective hierarchies) then the corresponding constituting functions are of the same “complexity”. Thus, any Borel graph all of whose Y-sections are at most countable is a union of countably many Borel functions and, consequently, has Borel domain. In the setting of Polish topological spaces this was proved by Novikov (see [De]).

An error has been found in the cited paper; namely, Theorem 3.1 is false.

Let D be a strongly minimal set in the language L, and D′ ⊃ D an elementary extension with infinite dimension over D. Add to L a unary predicate symbol D and let T′ be the theory of the structure (D′, D), where D interprets the predicate D. It is known that T′ is ω-stable. We prove

Theorem A. If D is not locally modular, then T′ has Morley rank ω.

We say that a strongly minimal set D is pseudoprojective if it is nontrivial and there is a k < ω such that, for all a, b ∈ D and closed X ⊂ D, a ∈ cl(Xb) ⇒ there is a Y ⊂ X with a ∈ cl(Yb) and ∣Y∣ ≤ k. Using Theorem A, we prove

Theorem B. If a strongly minimal set D is pseudoprojective, then D is locally projective.

The following result of Hrushovski's (proved in §4) plays a part in the proof of Theorem B.

Theorem C. Suppose that D is strongly minimal, and there is some proper elementary extension D1 of D such that the theory of the pair (D1, D) is ω1-categorical. Then D is locally modular.

We study function fields over p-adically closed fields in the first-order language of fields. Using ideas of Duret [D], we show that the field of constants is definable, and that the genus is an elementary property.

We consider the following properties of uncountable-dimensional quadratic spaces (E, Φ):

(*) For all subspaces U ⊆ E of infinite dimension: dim U˔ < dim E.

(**) For all subspaces U ⊆ E of infinite dimension: dim U˔ < ℵ0.

Spaces of countable dimension are the orthogonal sum of straight lines and planes, so they cannot have (*), but (**) is trivially satisfied.

These properties have been considered first in [G/O] in the process of investigating the orthogonal group of quadratic spaces. It has been shown there (in ZFC) that over arbitrary uncountable fields (**)-spaces of uncountable dimension exist.

In [B/G], (**)-spaces of dimension ℵ1 (so (*) = (**)) have been constructed over arbitrary finite or countable fields. But this could be done only under the assumption that the continuum hypothesis (CH) holds in the underlying set theory.

We assume that the reader is familiar with the program of “reverse mathematics” and the development of countable algebra in subsystems of second order arithmetic. The subsystems we are using in this paper are RCA0, WKL0 and ACA0. (The reader who wants to learn about them should study [1].) In [1] it was shown that the statement “Every countable commutative ring has a prime ideal” is equivalent to Weak Konig's Lemma over RCA0, while the statement “Every countable commutative ring has a maximal ideal” is equivalent to Arithmetic Comprehension over RCA0. Our main result in this paper is that the statement “Every countable commutative ring has a minimal prime ideal” is equivalent to Arithmetic Comprehension over RCA0. Minimal prime ideals play an important role in the study of countable commutative rings; see [2, pp. 1–7].

In the paper [S1] I introduced a game, denoted by MG(J) (where J is a free ideal on some infinite set S) and called “the meager nowhere dense game for J”. The special case when J is the collection of finite subsets of the set S is called the countable-finite game on S. It proceeds as follows.

First player ONE picks a countable set C 1, then player TWO picks a finite set F 1. Then in the second inning ONE picks a countable set C 2 with C 1 ⊂ C 2 (unless explicitly indicated otherwise, “⊂” means “is a proper subset of”) and TWO responds with a finite set F 2, and so on. The players construct a sequence (C1,F1,C2,F2,…,Ck,Fk,…) where for each positive integer k

(i) Ck denotes ONE's countable set picked during the kth inning,

(ii) Fk denotes TWO's finite set picked during the kth inning, and

(iii) Ck ⊂ Ck + 1.

Such a sequence is a play of the countable-finite game on S, and TWO wins this play if is contained in . The notion of a winning perfect information strategy is defined as usual (see, for example, [S1]). Zermelo-Fraenkel set theory together with the axiom of choice (denoted by ZFC; for a statement of the axioms see pp. xv–xvi of [K]) is a strong enough theory to build a winning perfect information strategy for player TWO in this game.

Does TWO have a winning strategy requiring less than perfect information? Fix a positive integer k. A strategy of TWO which requires knowledge of only at the most the k most recent moves of ONE is said to be a k-tactic. For the countable-finite game on an infinite set S the following facts about the existence of winning k-tactics for TWO are proved in [S1]:

1) TWO does not have a winning 1-tactic (Theorem 1 of [S1]).

2) If the cardinality of S is less than ℵ2 then TWO has a winning 2-tactic (Corollary 4 of [S1]).

3) If TWO has a winning k-tactic in the countable-finite game on an infinite set S, then TWO has a winning 3-tactic (Proposition 15 of [SI]).

In [9] and [10] P. Kolaitis and M. Vardi proved that the 0-1 law holds for the second-order existential sentences whose first-order parts are formulas of Bernays-Schonfinkel or Ackermann prefix classes. They also provided several examples of second-order formulas for which the 0-1 law does not hold, and noticed that the classification of second-order sentences for which the 0-1 law holds resembles the classification of decidable cases of first-order prenex sentences. The only cases they have not settled are the cases of Gödel classes with and without equality.

In this paper we confirm the conjecture of Kolaitis and Vardi that the 0-1 law does not hold for the existential second-order sentences whose first-order part is in Gödel prenex form with equality. The proof we give is based on a modification of the example employed by W. Goldfarb [5] in his proof that, contrary to the Gödel claim [6], the class of Gödel prenex formulas with equality is undecidable.

In this paper we study notions of a “meager subset” of a hyper-finite set. We work within an ω-saturated nonstandard universe and fix a hyperfinite natural number Є *N∖N. We shall consider subsets of the set = {1, 2, …,H}.

By analogy with the meager subsets of the real interval [0, 1], a notion of meager subset of should have the following properties.

1. Finite sets, countable unions of meager sets, subsets of meager sets, and translates of meager sets should be meager.

2. The Baire Category Theorem should hold; that is, should not be meager.

3. The internal analogue of the Cantor set should be meager.

4. The notion of a meager set should be with respect to a natural topology on .

5. There should exist meager subsets of of Loeb measure one.

6. Sierpiński and Lusin sets should have hyperfinite counterparts with properties similar to the classical case.

Property 5 is desirable so that, as with Lebesgue measure and Baire category on [0, 1], the topological and measure-theoretic notions of “large” and “small” sets are incomparable.

Property 6, while not as necessary as the other five, is desirable because of the strong interplay between measure and category in the classical results about Lusin and Sierpinski sets. Our objective is to find notions of meager set which have a relationship to Loeb measure similar to the classical relationship between meager sets and Lebesgue measure.

For a complete theory of Boolean algebras T, let MT denote the class of countable models of T. For B1, B2 ∈ MT, let B1 ≤ B2 mean that B2 is elementarily embeddable in B2. Theorem 1. For every complete theory of Boolean algebras T, if T ≠ Tω, then ‹MT, ≤› is well-quasi-ordered. ∎ We define Tω. For a Boolean algebra B, let I(B) be the ideal of all elements of the form a + s such that B ↾ a is an atomic Boolean algebra and B ↾ s is an atomless Boolean algebra. The Tarski derivative of B is defined as follows: B(0) = B and B(n + 1) = B(n)/I(B(n)). Define Tω to be the theory of all Boolean algebras such that for every n ∈ ω, B(n) ≠ {0}. By Tarski [1949], Tω is complete. Recall that ‹A, < › is partial well-quasi-ordering, it is a partial quasi-ordering and for every {ai, ⃒ i ∈ ω} ⊆ A, there are i < j < ω such that ai ≤ aj. Theorem 2. contains a subset M such that the partial orderings ‹M, ≤ ↾ M› and are isomorphic. ∎ Let M′0 denote the class of all countable Boolean algebras. For B1, B2 ∈ M′0, let B1 ≤′ B2 mean that B1 is embeddable in B2. Remark. ‹M′0, ≤′› is well-quasi-ordered. ∎ This follows from Laver's theorem [1971] that the class of countable linear orderings with the embeddability relation is well-quasi-ordered and the fact that every countable Boolean algebra is isomorphic to a Boolean algebra of a linear ordering.

Indescribability is closely related to the reflection principles of Zermelo-Fränkel set theory. In this axiomatic setting the universe of all sets stratifies into a natural cumulative hierarchy (Vα: α ϵ On) such that any formula of the language for set theory that holds in the universe already holds in the restricted universe of all sets obtained by some stage.

The axioms of ZF prove the existence of many ordinals α such that this reflection scheme holds in the world Vα. Hanf and Scott noticed that one arrives at a large cardinal notion if the reflecting formulas are allowed to contain second order free variables to which one assigns subsets of Vα. For a given collection Ω of formulas in the ϵ language of set theory with higher type variables and a unary predicate symbol they define an ordinal α to be Ω indescribable if for all sentences Φ in Ω and A ⊆ Vα

Since a sufficient coding apparatus is available, this definition is (for the classes of formulas that we are going to consider) equivalent to the one that one obtains by allowing finite sequences of relations over Vα, some of which are possibly k-ary. We will be interested mainly in certain standardized classes of formulas: Let (, respectively) denote the class of all formulas in the language introduced above whose prenex normal form has n alternating blocks of quantifiers of type m (i.e. (m + 1)th order) starting with ∃ (∀, respectively) and no quantifiers of type greater than m. In Hanf and Scott [1961] it is shown that in ZFC, indescribability is equivalent to inaccessibility and indescribability coincides with weak compactness.

We prove that in many situations it is consistent with ZFC that part of the invariants involved in Cichoń's diagram are equal to κ while the others are equal to λ, where κ < λ are both arbitrary regular uncountable cardinals. We extend some of these results to the case when λ is singular. We also show that cf is consistent with ZFC.

We generalize Specker's theorem on typical ambiguity, that NF and TST + Ambiguity have the same stratified consequences, to the subschemes Amb(Γ) of ambiguity restricted to classes of sentences Γ with certain natural closure conditions.

The axiom of infinity can be expressed by stating the existence of sets satisfying a formula which involves restricted universal quantifiers only, even if the axiom of foundation is not assumed.

We investigate the cofinality of the partial order κ of functions from a regular cardinal κ into the ideal of Lebesgue measure zero subsets of R. We show that when add () = κ and the covering lemma holds with respect to an inner model of GCH, then cf (κ) = max{cf(κκ), cf([cf()]κ)}. We also give an example to show that the covering assumption cannot be removed.