Though many working mathematicians embrace a rough and ready form of Platonism, that venerable position has suffered a checkered philosophical career. Indeed the three schools of thought with which most of us began our official philosophizing about mathematics—Intuitionism, Formalism, and Logicism—all stand in fundamental disagreement with Platonism. Nevertheless, various versions of Platonistic thinking survive in contemporary philosophical circles. The aim of this paper is to describe these views, and, as my title suggests, to trace their roots.

I'll begin with some preliminary remarks about the big three schools. This seems a reasonable approach to the issues both because most observers are familiar, at least in a general way, with the tenets of Intuitionism, Formalism, and Logicism, and because it is in reaction to these that contemporary Platonism has taken shape.

The purpose of this paper is to extend the coding method (see Beller, Jensen and Welch [82]) into the context of large cardinals.

Theorem. Suppose μ is a normal measure on κ in V and 〈 V, A〉 ⊨ ZFC. Then there is a 〈V, A〉-definable forcing for producing a real R such that:

(a) V[R] ⊨ ZFC and A is V[R]-definable with parameter R.

(b) V[R] = L[μ*, R], where μ* is a normal measure on κ in V[R] extending μ.

(c) V ⊨ GCH → is cardinal and cofinality preserving.

Corollary. It is consistent that μ is a normal measure, R ⊆ ω is not set-generic over L[μ] and 0+ ∉ L[μ, R].

Some other corollaries will be discussed in §4 of the paper.

The main difficulty in L[μ]-coding lies in the problem of “stationary restraint”.

As in all coding constructions, conditions will be of the form belonging to an initial segment of the cardinals, where p(γ) is a condition for almost disjoint coding into a subset of γ +. In addition for limit cardinals γ in Domain(p), 〈p γ′∣γ′ < γ〉 serves to code pγ .

An important restriction in coding arguments is that for inaccessible for only a nonstationary set of γ′ < γ. The reason is that otherwise there are conflicts between the restraint imposed by the different and the need to code extensions of pγ below γ.

As Dekker [3] suggested, certain fragments of the isols can exhibit an arithmetic rather more resembling that of the natural numbers than the general isols do. One such natural fragment is Barback's “tame models” (cf. [2], [6] and [7]), whose roots go back to Nerode [8]. In this paper we study another variety of such fragments: the hyper-torre isols introduced by Ellentuck [4]. Let Y denote an infinite isol with D(Y) the collection of all isols A ≤ f∧(Y) for some recursive and combinational unary function f. (Here, as usual, f ∧ is the Myhill-Nerode extension of f to the isols).

The separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.

For the reader's convenience, we begin Part II by restating the rules for constructing Sq derivations given in §2:

We let R be the set of 14 rules for Sq, R* the set of pure *-rules in R, R≃ the set of pure ≃-rules in R, and R− the set R ∩ − {Exs≃}. The closure of any F ⊆ Sq under R will be denoted by csR F, and the direct image of F under Cut*, for example, by Cut*(F).

This is the first of a sequence of papers in which we will develop a foundation for the theory of computation based on a precise, mathematical notion of abstract algorithm. To understand the aim of this program, one should keep in mind clearly the distinction between an algorithm and the object (typically a function) computed by that algorithm. The theory of computable functions (on the integers and on abstract structures) is obviously relevant to this work, but we will focus on making rigorous and identifying the mathematical properties of the finer (intensional) notion of algorithm.

It is characteristic of this approach that we take recursion to be a fundamental (primitive) process for constructing algorithms, not a derived notion which must be reduced to others—e.g. iteration or application and abstraction, as in the classical λ-calculus. We will model algorithms by recursors, the set-theoretic objects one would naturally choose to represent (syntactically described) recursive definitions. Explicit and iterative algorithms are modelled by (appropriately degenerate) recursors.

The main technical tool we will use is the formal language of recursion, FLR, a language of terms with two kinds of semantics: on each suitable structure, the denotation of a term t of FLR is a function, while the intension of t is a recursor (i.e. an algorithm) which computes the denotation of t. FLR is meant to be intensionally complete, in the sense that every (intuitively understood) “algorithm” should “be” (faithfully modelled, in all its essential properties by) the intension of some term of FLR on a suitably chosen structure.

Using coding devices based on a theorem due to Zsigmondy, Birkhoff and Vandiver, we first define in terms of successor S and coprimeness predicate ⊥ a full arithmetic over the set of powers of some fixed prime, then we define in the same terms a restriction of the exponentiation. Hence we prove the main result insuring that all arithmetical relations and functions over prime powers and their opposite are {S, ⊥}-definable over Z. Applications to definability over Z and N are stated as corollaries of the main theorem.

Let We be the eth recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that We = W f(e). In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets.

Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper.

Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete (i.e. A has degree 0′) iff there is a function f recursive in A with no fixed point.

A function is recursive (in given operations) if its values are computed explicitly and uniformly in terms of other “previously computed” values of itself and (perhaps) other “simultaneously computed” recursive functions. Here, “explicitly” includes definition by cases.

We investigate those recursive functions on the structure N = 〈ω, 0, succ, pred〉 that are computed in terms of themselves only, without other simultaneously computed recursive functions.

In the 1960's, it was conjectured that a complete first order theory in a countable language would have a nondecreasing spectrum on uncountable cardinals. This conjecture became known as Morley's conjecture. Shelah has proved this in [10]. The intent of this paper is to give a different proof which resembles a more naive way of approaching this theorem.

Let I(T, λ) = the number of nonisomorphic models of T in cardinality λ. We prove:

Theorem 0.1. If T is a complete countable first order theory then for ℵ0 < κ < λ, I(T,K) ≤ I(T, λ).

In some sense, one can view Shelah's work on the classification of first order theories as an attack on Morley's conjecture. Over the years, he has shown that certain assumptions on a first order theory would lead to its having maximal spectrum in powers larger than the cardinality of its language (see §6 for precise references). At some point it must have seemed that Morley's conjecture would be a corollary to an exact calculation of all possible spectrums. In the end, this did not occur and, in fact, the exact spectrum functions are still not known (see [10]). Let us consider a naive approach to the proof.

If we have two nonisomorphic models of the same cardinality and their cardinality is “large enough” then there should be some reason, irrespective of their cardinalities, which causes this nonisomorphism. If we could isolate this property and extend these models to a larger cardinality preserving this property, then the larger models would also be nonisomorphic. The notion of extendibility introduced in §2 is such a property which allows a version of this naive proof to work. Let us preview the sections.

In [9] and [12], Shelah defined a certain type of Scott sentence which he called excellent. He proved, among other things, that if a Scott sentence is excellent and categorical in some uncountable power then it is categorical in all uncountable powers: the analog of the Morley categoricity theorem. Proving such an analog is often the starting point in the classification of a family of classes. Before beginning this classification in the case of excellent Scott sentences, let us say a few words about what this paper is and what it is not.

It is not the beginning of a classification theory for complete sentences in where is countable. Although excellence arises in the study of the model theory of Scott sentences, it is not a dividing line in a classification of them. In particular, the assumption of nonexcellence does not yield much information. In fact, in [3] there is an example of a nonexcellent Scott sentence, categorical in ℵ1 which is. not fully categorical. It seems to the second author that a classification of sentences analogous to the classification of first order theories is a long way off and may not be accomplishable in ZFC.

This is not to say that the study of excellent Scott sentences (or the class of models of such which we will call excellent classes) is unproductive. Besides its extreme usefulness in [12], Mekler and Shelah have shown that excellence plays a decisive role in the study of almost free algebras (see [7]). Moreover, as the class of ω-saturated models of an ω-stable theory is an example of an excellent class, the study of excellent classes is at least as difficult as the study of first order ω-stable theories.

The motivation for the results presented here comes from the following two known theorems which concern countable, recursively saturated models of Peano arithmetic.

(1) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ. (See Theorem 10 of [1].)

(2) if is a countable, recursively saturated model of PA, then is generated by a set of indiscernibles. (See [4].)

It will be shown here that (1) and (2) can be amalgamated into a common generalization.

(3) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ and which is generated by a set of indiscernibles.

By way of contrast we will also get recursively saturated models of PA which fail to be resplendent and yet are generated by indiscernibles.

(4) if is a countable, recursively saturated model of PA, then for each uncountable cardinal κ there is a κ-like recursively saturated generated by a set of indiscernibles.

None of (1), (2) or (3) is stated in its most general form. We will make some comments concerning their generalizations. From now on let us fix a finite language L; all structures considered are infinite L-structures unless otherwise indicated.

We present a critical discussion of the claim (most forcefully propounded by Chaitin) that algorithmic information theory sheds new light on Gödel's first incompleteness theorem.

Since Gilmore showed that some theory with a positive comprehension scheme is consistent when the axiom of extensionality is dropped and inconsistent with it (see [1] and [2]), the problem of the consistency of various positive comprehension schemes has been investigated. We give here a short classification, which shows clearly the importance of the axiom of extensionality and of the abstraction operator in these consistency problems. The most difficult problem was to show the consistency of the comprehension scheme for positive formulas, with extensionality but without abstraction operator. In his unpublished thesis, Set theory in which the axiom of foundation fails [3], Malitz solved partially this problem but he needed to assume the existence of some unusual kind of large cardinal; as his original construction is very interesting and his thesis is unpublished, we give a short summary of it. M. Forti solved the problem completely by working in ZF with a free-construction principle (sometimes called an anti-foundation axiom), instead of ZF with the axiom of foundation, as Malitz did.

This permits one to obtain the consistency of this positive theory, relative to ZF. In his general investigations about “topological set theories” (to be published), E. Weydert has independently proved the same result. The authors are grateful to the Mathematisches Forshungsinstitut Oberwolfach for giving them the opportunity of discussing these subjects and meeting E. Weydert during the meeting “New Foundations”, March 1–7, 1987.

We show in this paper that all fragments of intuitionistic propositional logic based on a subset of the connectives ∧, ∨, →, ¬ satisfy interpolation. Fragments containing ↔ or ¬¬ are briefly considered.

We get consistency results on I(λ, T, T) under the assumption that D(T) has cardinality > ∣T∣. We get positive results and consistency results on IE(λ, T 1, T).

The interest is model-theoretic, but the content is mostly set-theoretic: in Theorems 1–3, combinatorial; in Theorems 4–7 and 11(2), to prove consistency of counterexamples we concentrate on forcing arguments; and in Theorems 8–10 and 11(1), combinatorics for counterexamples; the rest are discussion and problems. In particular:

(A) By Theorems 1 and 2, if T ⊆ T 1 are first order countable, T complete stable but ℵ0-unstable, λ > ℵ0, and ∣D(T)∣ > ℵ0, then IE(λ, T 1, T) > Min{2 λ , ℶ2}.

(B) By Theorems 4,5,6 of this paper, if e.g. V = L, then in some generic extension of V not collapsing cardinals, for some first order T ⊆ T 1, ∣T∣ = ℵ0, ∣T 1∣ = ℵ1, ∣D(T)∣ = ℵ2 and IE(ℵ2, T1, T) = 1.

This paper (specifically the ZFC results) is continued in the very interesting work of Baldwin on diversity classes [Bl]. Some more advances can be found in the new version of [Sh300] (see Chapter III, mainly §7); they confirm 0.1, 0.2 and 14(1), 14(2).

In a modal system of arithmetic, a theory S has the modal disjunction property if whenever S ⊢ □φ ∨ □ψ, either S ⊢ □φ or S ⊢ □ψ. S has the modal numerical existence property if whenever S ⊢ ∃x □φ(x), there is some natural number n such that S ⊢ □φ(n). Under certain broadly applicable assumptions, these two properties are equivalent.

The problem of the nonequivalent modalities available in certain systems is a classical problem of modal logic. In this paper we deal with this problem without referring to particular logics, but considering the whole class of normal propositional logics. Given a logic L let P(L) (the m-partition generated by L) denote the set of the classes of L-equivalent modalities. Obviously, different logics may generate the same m-partition; the first problem arising from this general point of view is therefore to determine the cardinality of the set of all m-partitions. Since, as is well known, there exist normal logics, and since one immediately realizes that there are infinitely many m-partitions, the problem consists in choosing (assuming the continuum hypothesis) between ℵ0 and . In Theorem 1.2 we show that there are m-partitions, as many as the logics.

The next problem which naturally arises consists in determining, given an m-partition P(L), the number of logics generating P(L) (in symbols, μ(P(L))). In Theorem 2.1(ii) we show that ∣{P(L): μ(P(L)) = }∣ = . Now, the set {L′) = P(L)} has a natural minimal element; that is, the logic L* axiomatized by K ∪ {φ(p) ↔ ψ(p): φ, ψ are L-equivalent modalities}; P(L) and L* can be, in some sense, identified, thus making the set of m-partitions a subset of the set of logics.