Henle, Mathias, and Woodin proved in [21] that, provided that ${\omega }{\rightarrow }({\omega })^{{\omega }}$ holds in a model M of ZF, then forcing with $([{\omega }]^{{\omega }},{\subseteq }^*)$ over M adds no new sets of ordinals, thus earning the name a “barren” extension. Moreover, under an additional assumption, they proved that this generic extension preserves all strong partition cardinals. This forcing thus produces a model $M[\mathcal {U}]$ , where $\mathcal {U}$ is a Ramsey ultrafilter, with many properties of the original model M. This begged the question of how important the Ramseyness of $\mathcal {U}$ is for these results. In this paper, we show that several classes of $\sigma $ -closed forcings which generate non-Ramsey ultrafilters have the same properties. Such ultrafilters include Milliken–Taylor ultrafilters, a class of rapid p-points of Laflamme, k-arrow p-points of Baumgartner and Taylor, and extensions to a class of ultrafilters constructed by Dobrinen, Mijares, and Trujillo. Furthermore, the class of Boolean algebras $\mathcal {P}({\omega }^{{\alpha }})/{\mathrm {Fin}}^{\otimes {\alpha }}$ , $2\le {\alpha }<{\omega }_1$ , forcing non-p-points also produce barren extensions.

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.

The concept of a topos as a system, or world in which mathematics could be defined and interpreted, was developed by F. W. Lawvere and M. Tierney. Much of their work is embodied in the lecture notes Elementary toposes by A. Kock and G. C. Wraith [6].

In an early paper Lawvere set forth a set of axioms for approximately such a system [8]. The topos constructed there is a set-like category that includes among its axioms an axiom of infinity and an axiom of choice.

In its final form an elementary topos is freed from any such axioms.

The most prominent example of an elementary topos is a set theory with the usual Zermelo-Fraenkel or Godel-Bernays set of axioms.

In this paper I have tried to determine what, if any, is the effect of an axiom of choice introduced in a topos, and how are some of the set-theoretic equivalents of such an axiom related in topos theory.

Since the set-theoretic membership relation ∈, the notions of an “empty” set and a “power” set are definable in topos theory, it makes sense to talk about a “choice map” that picks a single element out of every nonempty object, provided that these objects can be somehow collected into a single object or “family.” In other words, an analogue of the usual choice axiom can be formulated in elementary topos language; this is axiom AC2 of the text.

Models of normal open induction (NOI) are those discretely ordered rings, integrally closed in their fraction field whose nonnegative part satisfy Peano's induction axioms for open formulas in the language of ordered semirings.

Here we study the problem of representability of an element a of a model M of NOI (in some extension of M) by a quadratic form of the type X2 + b Y2 where b is a nonzero integer. Using either a trigonometric or a hyperbolic parametrization we prove that except in some trivial cases, M[x, y] with x2 + by2 = a can be embedded in a model of NOI.

We also study quadratic extensions of a model M of NOI; we first prove some properties of the ring of Gaussian integers of M. Then we study the group of solutions of a Pell equation in NOI; we construct a model in which the quotient group by the squares has size continuum.

A basic concept of the theory of models is that of elementary equivalence of similar relational systems: two such systems are said to be elementarily equivalent if they satisfy the same first-order statements or, in other words, if they have the same (first-order) complete theory. It is possible to reformulate this notion of elementary equivalence of systems within the framework of algebraic logic by replacing theories by algebraic structures derived from them or more directly from the systems which are models of these theories. To any such theory T (or model of it), is indeed associated a locally finite polyadic algebra with equality, the underlying Boolean algebra of which is simply the well-known Tarski-Lindenbaum algebra of the theory. It is not hard to prove (see Section 6.1) that two systems are elementarily equivalent iff (i.e. if and only if) they have isomorphic polyadic. algebras. The possibility of replacing theories by algebraic structures and of reducing the purely logical concept of elementary equivalence to the algebraic one of isomorphism can be exploited to give a purely algebraic treatment of model-theoretic problems and suggests natural questions concerning these structures. The present paper illustrates that possibility.

Suppose T is superstable. Let ≤ denote the fundamental order on complete types, [p] the class of the bound of p, and U(—) Lascar's foundation rank (see [LP]). We prove

Theorem 1. If q < p and there is no r such that q < r < p, then U(q) + 1 = U(p).

Theorem 2. Suppose U(p) < ω and ξ1 < … < ξk is a maximal descending chain in the fundamental order with ξk = [p]. Then k = U(p).

That the finiteness of U(p) in Theorem 2 is necessary follows from

Theorem 3. There is an ω-stable theory with a type p ϵ S 1(ϕ) such that

(1) U(p) = ω + 1, and

(2) there is a maximal descending chain of proper extensions of [p] which has order type ω.

Un prolongement de l'étude d'une théorie T, dans le langage , consiste à s'intéresser à la théorie T* des paires de modèles de T, c'est-à-dire les structures de la forme (K ⊊ L) où K ⊨ T, L ⊨ T, K ≺ L, dans le langage où E est un prédicat pour la sous-structure. Les propriétés de la théorie T ne se transmettent pas toujours à T*, particulièrement en ce qui concerne la complétude et la décidabilité. On trouve des illustrations de cas opposés dans les théories de corps:

—si T est la théorie des corps algébriquement clos de caractéristique fixée, T* est complète et décidable;

—si T est la théorie des corps réels clos, T est complète et décidable, mais T* est indécidable, et admet complétions différentes.

Nous allons nous intéresser ici aux paires de corps valués henseliens, et plus particulièrement au cas de caractéristique résiduelle nulle, de la forme (K ⊊ L, υ) où (K, υ) n'est pas nécessairement une sous-structure élémentaire de (L, υ). Ax, Kochen et Ershov ont montré que la théorie d'un corps valué henselien de caractéristique résiduelle nulle est entièrement déterminée par la théorie de son corps de restes et par la théorie de son groupe de valuation; par ailleurs, de résultats analogues existent pour certains corps de caractéristique résiduelle non nulle.

Our results concern the existence of a countable extension of the countable atomless Boolean algebra such that is a “nonconstructive” extension of . It is known that for any fixed admissible indexing φ of there is a countable nonconstructive extension of (relative to φ). The main theorem here shows that there exists an extension of such that for any admissible indexing φ of , is nonconstructive (relative to φ).Thus, in this sense a countable totally nonconstructive extension of .

We investigate amalgamation properties of relational type algebras. Besides purely algebraic interest, amalgamation in a class of algebras is important because it leads to interpolation results for the logic corresponding to that class (cf. [15]). The multi-modal logic corresponding to relational type algebras became known under the name of “arrow logic” (cf. [18, 17]), and has been studied rather extensively lately (cf. [10]). Our research was inspired by the following result of Andréka et al. [1].

Let K be a class of relational type algebras such that

(i) composition is associative,

(ii) K is a class of boolean algebras with operators, and

(iii) K contains the representable relation algebras RRA.

Then the equational theory of K is undecidable.

On the other hand, there are several classes of relational type algebras (e.g., NA, WA denned below) whose equational (even universal) theories are decidable (cf. [13]). Composition is not associative in these classes. Theorem 5 indicates that also with respect to amalgamation (a very weak form of) associativity forms a borderline. We first recall the relevant definitions.

Quoi qu'en pensent certains, la déviation de Saharon Shelah n'est pas qu'une construction technique servant à un résultat plus technique encore, le théorème de classification; c'est la notion de dépendance la plus générale qui soit apparue dans un contexte mathématique, si bien que toute propriété qu'on pourra attribuer à cette déviation sera, dans le fond, une propriété de la notion même de corrélation.

L'auteur de ces lignes a trouvé la vie beaucoup plus plaisante quand il a pu lire la déviation, associée à une théorie stable T, dans un ordre qu'il était facile de définir sur les types complets au-dessus des modèles de T; s'il a qualifié cet ordre de “fondamental”, ce n'est pas pour donner une emphase hors de propos à sa modeste contribution au démélage de l'échevau shelahien, mais parce que le rang U de Lascar n'était autre que le rang de fondation de l'ordre fondamental.

L'ordre fondamental condense l'essentiel de la déviation, sous une forme pour ainsi dire graphique; certes, tout ne peut s'y retrouver, et en particulier des théories peuvent avoir des ordres fondamentaux semblables si on se limite aux 1-types, et fort différents si on regarde aussi les bitypes; mais il est clair que dès qu'apparait l'ordre fondamental se pose de façon urgente le problème de décrire tous les ordres qui peuvent être ordre fondamental d'une théorie stable: tant que ce programme n'est pas rempli, il reste des propriétés cachées de la déviation.

An attempt to answer the following question gave rise to the results of the present paper. Let be an arbitrary model of set theory. Does there exist an elementary extension of satisfying the two requirements: (1) contains an ordinal exceeding all the ordinals of ; (2) does not enlarge any (hyper) integer of ? Note that a trivial application of the ordinary compactness theorem produces a model satisfying condition (1); and an internal ultrapower modulo an internal ultrafilter produces a model satisfying condition (2) (but not (1), because of the axiom of replacement). Also, such a satisfying both conditions (1) and (2) exists if the external cofinality of the ordinals of is countable, since by [KM], would then have an elementary end extension.

Using a class of models constructed by M. Rubin using in [RS], and already employed in [E1], we prove that our question in general has a negative answer (see Theorem 2.3). This result generalizes the results of M. Kaufmann and the author (appearing respectively in [Ka] and [E1]) concerning models of set theory with no elementary end extensions.

In the course of the proof it was necessary to establish that all conservative extensions (see Definition 2.1) of models of ZF must be cofinal. This is in direct contrast with the case of Peano arithmetic where all conservative extensions are end extensional (as observed by Phillips in [Ph1]). This led the author to introduce two useful weakenings of the notion of a conservative end extension which, as shown by the “completeness” theorems in §3, can exist.

Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, A formalization of set theory without variables, a monograph written in collaboration with S. Givant [8−m]. An account of the Warsaw seminar can be found in Vaught [1986].

Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.

We will say that a set of elementary sentences is a theory provided it is closed with respect to logical consequence and we will say that a theory is decidable or undecidable depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an equational theory is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.

Definition 1 (Kurepa [3, p. 99]). Let E be a partially ordered set. Then σE denotes the set of all bounded well-ordered subsets of E. We consider σE as a partially ordered set with ordering defined as follows: st if and only if s is an initial segment of t.

Then σE is a tree, i.e., {s ∈ σ E∣ st} is well-ordered for every t ∈ σE. The trees of the form αE were extensively studied by Kurepa in [3]–[10]. For example, in [4], he used σQ and σR to construct various sorts of Aronszajn trees. (Here Q and R denote the rationals and reals, respectively.) While considering monotone mapping between some kind of ordered sets, he came to the following two questions several times:

P.1. Does there exist a strictly increasing rational function on σQ? (See [4, Problème 2], [5, p. 1033], [6, p. 841], [7, Problem 23.3.3].)

P.2. Let T be a tree in which every chain is countable and every level has cardinality <2ℵ0. Does there exist a strictly increasing real function on T? (See [6, p. 246] and [7].)

It is known today that Problem 2 is independent of the usual axioms of set theory (see [1]). Concerning Problem 1 we have the following.