We say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀x∃yψ(x, y), where ψ(x, y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field.

It is known (see [1, 3.1.5]) that the order type of the nonstandard natural number system *N has the form ω + (ω* + ω) θ, where θ is a dense order type without first or last element and ω is the order type of N. Concerning this, Zakon [2] examined *N more closely and investigated the nonstandard real number system *R, as an ordered set, as an additive group and as a uniform space. He raised five questions which remained unsolved. These questions are concerned with the cofinality and coinitiality of θ (which depend on the underlying nonstandard universe *U). In this paper, we shall treat nonstandard models where the cofinality and coinitiality of θ coincide with some appropriated cardinals. Using these nonstandard models, we shall give answers to three of these questions and partial answers to the other to questions in [2].

The continuous or countable functionals were independently denned by Kleene [9] and Kreisel [10]. They were intended as a suitable basis for constructive mathematics, and thus it is interesting to investigate various notions of recursion on the countable functionals.

There have been two main streams in this investigation, the study of countable recursion and the study of computability or Kleene-recursion.

Countable recursion is the theory of recursion on the associates. Gandy and Hyland [3] and Hyland [7] are good sources for the recent development of countable recursion.

This paper will mostly be concerned with Kleene-recursion on the countable functionals as denned in Kleene [8] and [9]. We assume some familiarity with the countable functionals and associates, as presented in Kleene [9], Bergstra [1] or any other paper on the subject.

Pioneering work with recursion in nonnormal objects was done by Grilliot [4], who proved that a functional F of type 2 is normal if and only if its 1-section (that is the set of functions recursive in F) is closed under ordinary jump, and if and only if F is continuous on 1-section (F).

Hinman [6] constructed a countable functional that is not recursively equivalent to a function, and thereby showed that recursion in nonnormal functionals is an extension of ordinary recursion in functions.

In [6], Hinman asked if there are functionals with topless 1-sections, i.e. with no maximal elements in the semi-lattice of degrees. This was answered in the affirmative by Bergstra [1], using a spoiling construction. Thus the class of 1-sections of functionals extends the class of 1-sections of functions.

The celebrated theorem of Löwenheim and Skolem tells us that every consistent set S of quantificational schemata (i.e., every set of well-formed formulas of the lower predicate calculus admitting of a true interpretation in some non-empty universe) admits of a true numerical interpretation (i.e., an interpretation of predicate letters such that all schemata of S come out true when the variables of quantification are construed as ranging over just the positive integers).

Later literature goes farther, and shows how, given S, actually to produce a numerical interpretation which will fit S in case S is consistent. The general case is covered by Kleene (see Bibliography). The special case where S contains just one schema (or any finite number, since we can form their conjunction) had been dealt with by Hilbert and Bernays. Certain extensions, along lines not to be embarked on here, have been made by Kleene, Kreisel, Hasenjäger, and Wang.

My present purpose is expository: to make the construction of the numerical interpretation, and the proof of its adequacy, more easily intelligible than they hitherto have been. The reasoning is mainly Kleene's, though closer in some ways to earlier reasoning of Gödel.

Nach Gödel ist der Prädikatenkalkül der ersten Stufe vollständig in dem Sinne, daβ alle identischen Ausdrücke dieses Kalküls ableitbar sind. Für den einstelligen Prädikatenkalkül gilt darüber hinaus, daβ zwei Ausdrücke deduktionsgleich (HB I, p. 149) sind, wenn sie für dieselben Individuenbereiche identisch bzw. nicht identisch sind. Solche Ausdrücke mögen identitätsverbunden heiβen. Daβ umgekehrt deduktionsgleiche Ausdrücke identitätsverbunden sind, gilt auch für den vollen Prädikatenkalkül. Dagegen gibt es dort Ausdrücke, die identitätsverbunden, aber nicht deduktionsgleich sind. Solche Ausdrücke sind die in HB I, p. 123, 124 angegebenen und , die beide genau im Endlichen identisch, also identitätsverbunden sind. Die Frage der gegenseitigen Ableitbarkeit bleibt dort allerdings noch unentschieden. Ich werde im Folgenden die gegenseitige Nichtableitbarkeit von und im Prädikatenkalkül der ersten Stufe beweisen. Daraus folgt dann, daβ für den vollen Prädikatenkalkül die Bernayssche Deduktionsgleichheit nicht mit der Identitätsverbundenheit zusammenfällt. Es sei erwähnt, daβ die Identitätsverbundenheit sich zwar in der “Protosyntax” (d.h. metasprachliches “Alle” und “Es gibt” beschränkt auf Zeichenreihen) definieren läβt. Trotzdem kann man nicht von einer verschärften Vollständigkeit des Prädikatenkalküls sprechen; denn es läβt sich zeigen, daβ die Identitätsverbundenheit keine Beziehung vom Typ der Beweisbarkeit ist.

In Chapter X of his book on The structure of appearance, Goodman [1] studies the concept of linear order in finite linear arrays in terms of a two-place symmetrical predicate M, M(x, y) being read as x matches y. Although arising in the development of a nominalistic philosophical system, many problems relating to the properties of M are essentially of a mathematical and not of a philosophical nature. Some were considered by Fine in [2]. In the terminology of [1] and [2], the main result of this paper is that there is an effective method for embedding a weakly mapped array (consistently) in a uniform array. This carries with it the result that it is possible to obtain effectively a minimal uniform extension of the original array, that is, a uniform extension with minimum span for such an extension and with the minimum number of elements possible for a uniform extension with this span.

We formulate and prove a combinatorial property assuming AD + V = L(ℝ). As a consequence, we show that every regular κ which is either a Suslin cardinal or the successor of a Suslin cardinal is -supercompact. In particular, all the projective ordinals are -supercompact.

We prove results about nonstandard formulas in models of Peano arithmetic which complement those of Kotlarski, Krajewski, and Lachlan in [KKL] and [L]. This enables us to characterize both recursive saturation and resplendency in terms of statements about nonstandard sentences. Specifically, a model of PA is recursively saturated iff is nonstandard and -logic is consistent. is resplendent iff is nonstandard, -logic is consistent, and every sentence φ which is consistent in -logic is contained in a full satisfaction class for . Thus, for models of PA, recursive saturation can be expressed by a (standard) -sentence and resplendency by a -sentence.

Let $\kappa $ be a regular uncountable cardinal, and a cardinal greater than or equal to $\kappa $ . Revisiting a celebrated result of Shelah, we show that if is close to $\kappa $ and (= the least size of a cofinal subset of ) is greater than , then can be represented (in the sense of pcf theory) as a pseudopower. This can be used to obtain optimal results concerning the splitting problem. For example we show that if and , then no $\kappa $ -complete ideal on is weakly -saturated.

We define a nontrivial variety of boolean algebras with operators such that every member of the variety is atomless. This shows that not every variety of boolean algebras with operators is generated by its atomic members, and thus establishes a strong incompleteness result in (multi-)modal logic.

Suppose that I is a precipitous ideal over a cardinal κ and j is a generic embedding of I. What is the nature of j? If we assume the existence of a supercompact cardinal then, by Foreman, Magidor and Shelah [FMS], it is quite unclear where some of such j's are coming from. On the other hand, if ¬∃κ0(κ) = κ++, then, by Mitchell [Mi], the restriction of j to the core model is its iterated ultrapower by measures of it. A natural question arising here is if each iterated ultrapower of can be obtained as the restriction of a generic embedding of a precipitous ideal. Notice that there are obvious limitations. Thus the ultrapower of by a measure over λ cannot be obtained as a generic embedding by a precipitous ideal over κ ≠ λ. But if we fix κ and use iterated ultrapowers of which are based on κ, then the answer is positive. Namely a stronger statement is true:

Theorem. Let τ be an ordinal and κ a measurable cardinal. There exists a generic extension V* of V so that NSℵ1 (the nonstationary ideal on ℵ1) is precipitous and, for every iterated ultrapower i of V of length ≤ τ by measures of V based on κ, there exists a stationary set forcing “the generic ultrapower restricted to V is i”.

Our aim will be to prove this theorem. We assume that the reader is familiar with the paper [JMMiP] by Jech, Magidor, Mitchell and Prikry. We shall use the method of that paper for constructing precipitous ideals. Ideas of Levinski [L] for blowing up 2ℵ1 preserving precipitousness and of our own earlier paper [Gi] for linking together indiscernibles will be used also.

We generalize the result of Mekler and Shelah [3] that the existence of a canary tree is independent of ZFC + GCH to uncountable regular cardinals. We also correct an error from the original proof.

Let be the class of atomic models of a countable first order theory. We prove that if is excellent and categorical in some uncountable cardinal, then each model is prime and minimal over the basis of a definable pregeometry given by a quasiminimal set. This implies that is categorical in all uncountable cardinals. We also introduce a U-rank to measure the complexity of complete types over models. We prove that the U-rank has the usual additivity properties, that quasiminimal types have U-rank 1, and that the U-rank of any type is finite in the uncountably categorical, excellent case. However, in contrast to the first order case, the supremum of the U-rank over all types may be ω (and is not achieved). We illustrate the theory with the example of free groups, and Zilber's pseudo analytic structures.

The semantical account that Meyer and Lambert give in [7] of their quantificational calculus FQ can be considerably simplified, and—supposing as the authors do at the close of their paper that ‘ = ’ counts as a primitive sign—so can their axiom system for FQ.

(1) As the authors remark, axiom schema 102 can be simplified to read : A ⊃ (∀Χ)A, where Χ does not occur free in A. Following Tarski's [9], it can be further simplified: A ⊃ (∀Χ)A, where Χ does not occur in A.

The shift map σ on ω* is the continuous self-map of ω* induced by the function n ↦ n + 1 on ω. Given a compact Hausdorff space X and a continuous function f : X → X, we say that (X, f) is a quotient of (ω*, σ) whenever there is a continuous surjection Q : ω*→ X such that Q ○ σ = σ ○ f.

Our main theorem states that if the weight of X is at most ℵ1, then (X, f) is a quotient of (ω*, σ), if and only if f is weakly incompressible (which means that no nontrivial open U ⊆ X has $f\left( {\bar{U}} \right) \subseteq U$). Under CH, this gives a complete characterization of the quotients of (ω*, σ) and implies, for example, that (ω*, σ−1) is a quotient of (ω*, σ).

In the language of topological dynamics, our theorem states that a dynamical system of weight ℵ1 is an abstract ω-limit set if and only if it is weakly incompressible.

We complement these results by proving (1) our main theorem remains true when ℵ1 is replaced by any κ < p, (2) consistently, the theorem becomes false if we replace ℵ1 by ℵ2, and (3) OCA + MA implies that (ω*, σ−1) is not a quotient of (ω*, σ).

Answering a special case of a question of Chernikov and Simon, we show that any non-dividing formula over a model M in a distal NIP theory is a member of a consistent definable family, definable over M.

Let ε stand for the set of nonnegative integers (numbers), V for the class of all subcollections of ε (sets), Λ for the set of isols, and for the set of mappings from a subset of ε into ε (functions). I f is a function we write δf and ρf for its domain and range respectively. The relation of inclusion is denoted by ⊂ and that of proper inclusion by ⊊. The sets α and β are recursively equivalent [written: α ≃ β], if δf = α and ρf = β for some function f with a one-to-one partial recursive extension f. We denote the recursive equivalence type of α, {σ ∈ V ∣ ≃ α}, by Req(α). Also R stands for Req(ε), while ΛR denotes the collection of all regressive isols. The reader is assumed to be familiar with the contents of [1] and [6].

We define an ℜ-group to be a stable group with the property that a generic element (for any definable transitive group action) can only be algebraic over a generic. We then derive some corollaries for ℜ-groups and fields, and prove a decomposition theorem and a field theorem. As a nonsuperstable example, we prove that small stable groups are ℜ-groups.

The category of enumerations over P1 is investigated. Objects are the enumerations of the set of partial recursive functions in one variable φ: N → P1 where φ is a total effective function from the natural numbers N onto P1.

To each a ∈ P1 we call φ−1(a) the set of all indices for a, the fibre over a.

Morphisms from one enumeration φ to another one ψ are (partial) recursive functions f, for which φ(n) = ψ(f(n)) holds for all n where f is denned, i.e. f is fibrepreserving. They are also called translators if f is total. The existence of a translator induces a partial ordering on the enumerations:

Let φ ≤ ψ, iff there exists a translator f with φ = ψ·f; φ ≡ ψ iff φ ≤ ψ and ψ ≤ φ. Two enumerations are called incomparable iff φ ≰,ψ and ψ ≰ φ.

Given a recursively enumerable family of enumerations {φi}i∈ω then their direct sum = π is defined by a bijective recursive pairing function g(i, n) (e.g. g(i, n) = (i + n)(i + n + 1)/2 + i) summing up the φi by φi(n) = = πg(i, n) into π. We also say π decomposes into .

Direct sums satisfy the universal property of sums in categories.

We want to operate decompositiontheory on special kinds of objects in our category, the Gödelnumberings and the Friedbergnumberings.

A Gödelnumbering φ is defined by (a) enumeration theorem (i.e. φ is object of our category) and (b) -theorem, which means that each m + n-place p.r. function can be effectively replaced by an enumeration of n-place p.r. functions given by means of the total -function (see Rogers [3]).