It is well known that the hypothesis that all real numbers are constructible in the sense of Gödel [1] implies the existence of a Σ21 well-ordering of the Baire space [1, p. 67]. We are concerned with the converse to this theorem. From the assumption of the existence of a Σ21 well-ordering with total domain, we derive various consequences which in the presence of a nonconstructible real seem highly pathological. However, while several of these consequences are obviously absurd, none have as yet been disproven. Indeed some of the stranger consistency proofs of Jensen seem to indicate that there is a possibility that they may be consistent. I am referring to such results as existence of a model for ZF set theory in which the degrees of constructibility form a sequence of type ω + 1 with the (ω + 1)st degree being the only one which contains a nonconstructible real, and that degree being the degree of a Δ31 nonconstructible real.

In what follows we shall use the small Greek letters α, β, γ to range over the Baire space NN where N is the set of natural numbers. We assume that the reader is familiar with the use of trees to encode closed subsets of this space. The class Σ21 is the collection of all those subsets of the Baire space which can be defined by a formula which is Σ21 in a constructible parameter. Correspondingly Π21 will be taken to mean Π11 in a constructible parameter. The proof of the first lemma is left as an exercise. It involves nothing more than coding perfect sets by trees and then counting quantifiers.

We introduce and discuss a concept of approximation of a topological algebraic system A by finite algebraic systems from a given class . If A is discrete, this concept agrees with the familiar notion of a local embedding of A in a class of algebraic systems. One characterization of this concept states that A is locally embedded in iff it is a subsystem of an ultraproduct of systems from . In this paper we obtain a similar characterization of approximability of a locally compact system A by systems from using the language of nonstandard analysis.

In the signature of A we introduce positive bounded formulas and their approximations; these are similar to those introduced by Henson [14] for Banach space structures (see also [15, 16]). We prove that a positive bounded formula φ holds in A if and only if all precise enough approximations of φ hold in all precise enough approximations of A.

We also prove that a locally compact field cannot be approximated arbitrarily closely by finite (associative) rings (even if the rings are allowed to be non-commutative). Finite approximations of the field ℝ can be considered as possible computer systems for real arithmetic. Thus, our results show that there do not exist arbitrarily accurate computer arithmetics for the reals that are associative rings.

This paper consists of two parts. In §1 we mention the first strongly compact cardinal. Magidor proved in [6] that it can be the first measurable and it can be also the first supercompact. In [2], Apter proved that Con(ZFC + there is a supercompact limit of supercompact cardinals) implies Con(ZFC + the first strongly compact cardinal κ is ϕ(κ)-supercompact + no α < κ is ϕ(α)-supercompact) for a formula ϕ which satisfies certain conditions.

We shall get almost the same conclusion as Apter's theorem assuming only one supercompact cardinal. Our notion of forcing is the same as in [2] and a trick makes it possible.

In §2 we study a kind of fine ultrafilter on Pκλ investigated by Menas in [7], where κ is a measurable limit of strongly compact cardinals. He showed that such an ultrafilter is not normal in some case (Theorems 2.21 and 2.22 in [7]). We shall show that it is not normal in any case (even if κ is supercompact). We also prove that it is weakly normal in some case.

We work in ZFC and much of our notation is standard. But we mention the following: the letters α,β,γ… denote ordinals, whereas κ,λ,μ,… are reserved for cardinals. R(α) is the collection of sets rank <α. φM denotes the realization of a formula φ to a class M. Except when it is necessary, we drop “M”. For example, M ⊩ “κ is φ(κ)-supercompact” means “κ is φM(κ)-supercompact in M”. If x is a set, |x| is its cardinality, Px is its power set, and . If also x ⊆ OR, denotes its order type in the natural ordering. The identity function with the domain appropriate to the context is denoted by id. For the notation concerning ultrapowers and elementary embeddings, see [11]. When we talk about forcing, “⊩” will mean “weakly forces” and “p < q” means “p is stronger than q”.

Craig's theorem is a result about the cardinality of a proper basis for the theory of combinators. Its proof given in [3] was shown to be incomplete by André Chauvin [2]. By using a different approach, we give a very short proof of this theorem. We use the notation of [1].

Definition 1. A combinator Q is proper if there exists a natural number n such that for arbitrary variables x1,…,xn we have the following contraction rule:

where C is a pure combination of the variables x1,…,xn. Q is to be understood as an abstract symbol, not as a combination of S and K's. Therefore Q comes with a contraction rule.

Definition 2. A set (Q1,…, Qm} of combinators is a basis for combinatory logic if for every finite set {x1,…, xk} of variables and every pure combination C of these variables, there exists a pure combination Q of Q1,…, Qm such that Qx1 … xk ↠ C.

Craig's Theorem. Every basis for combinatory logic containing only proper combinators contains at least two elements.

Proof. Let {Q} be a singleton basis for combinatory logic, and let us show that we cannot have combinatory completeness. This is an easy consequence of the next two lemmas.

Lemma 1. Q is a projection. That is, Qx1 … xn ↠ xj, for some j.

Proof. Let I be a proper combination of Q such that Ix ↠ x for a variable x, and let M be a term such that Ix ↠ M → x and M → x is a nontrivial contraction.

In [6], Nadel showed that if is a recursively saturated model of Pr = Th(ω, +) of power at most ℵ1, then there is a model such that ≡ ∞ω and can be expanded to a recursively saturated model of P. For a fixed completion T of P, can be chosen to have a recursively saturated expansion to a model of T just in case is recursive in T-saturated. (“Recursive in T-saturation” is defined just like recursive saturation except that the sets of formulas considered are those that are recursive in T.)

Nadel also showed in [6] that for a fixed completion T of P, a countable nonstandard model of Pr can be expanded to a model of T (not necessarily recursively saturated) iff satisfies a condition called “exp(T)-saturation.” This condition is stronger than recursive saturation but weaker than recursive in T-saturation. Nadel left open the problem of characterizing the models of Pr of power ℵ1 such that for some , ≣ ∞ω and can be expanded to a model of T. The present paper gives such a characterization. The condition on is that it is recursively saturated, and for each n ∈ ω, the set Tn of Πn-sentences of T is recursive in some type realized in .

This result can be interpreted in various ways, just as the results from [6] were interpreted in various ways in [4]. Friedman [2] introduced the notion of a “standard system.”

Given an admissible indexing φ of the countable atomless Boolean algebra ℬ, an automorphism F of ℬ is said to be recursively presented (relative to φ) if there exists a recursive function p ϵ Sym(ω) such that F ∘ φ = φ ∘ p. Our key result on recursiveness: Both the subset of Aut(ℬ) consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all “totally nonrecursive” automorphisms, are uncountable.

This arises as a consequence of the following combinatorial investigations: (1) A comparison of the cycle structures of ƒ and , where ƒ is a permutation of some free basis of ℬ and is the automorphism of ℬ induced by ƒ.(2) An explicit description of the permutations of ω whose conjugacy classes in Sym(ω) are (a) uncountable, (b) countably infinite, and (c) finite.

In Forcing and reducibilities, I [20] we reviewed various forcing techniques in the context of arithmetic. This second part deals with the same topics in the context of analysis. The numbering of sections is the continuation of the numbering of the first part. For the reader's convenience, we collect in an independent bibliography the papers which are referred to in this part.

We begin with some notes concerning the genesis of this paper. A preliminary version of it was written by the third author, who was moved by the desire to correct a mistake in Poizat [1987, p. 97], and to refresh some other minor results of the same book, concerning equations which are satisfied generically in a stable group. The book in question will be considered here as our basic reference on stable groups, and these other results will be discussed elsewhere.

This preliminary version contained §§1, 2 and 3 of the present paper, restricted to the context of groups of finite Morley rank. It was observed that a counterexample of finite rank to the above theorem would be an extreme refutation of a conjecture by Zil'ber and Cherlin (cyrillic alphabet order), that may be not so solid as was believed some time ago, which states that a simple group of finite rank should be an algebraic group. Additional motivation for the problem was seen in Reineke's theorem (Reineke [1975]), stating that a connected group of rank one is abelian—the cornerstone for the study of superstable groups—whose proof rests on the fact that a group with two conjugacy classes either has only two elements, or has infinite chains of centralizers (a property that violates stability).

Given a prime p, we exhibit a Horn sentence Hp which expresses “the cardinality is not p” and has size O(p5 log p).

Assuming determinacy, the model L[T2] does not depend on the choice of T2.