The axiomatization of algebras of functions or partial functions under various operations has been studied by several authors. Menger [2] deals with the problem of axiomatizing the algebraic properties of 1-ary functions from the reals to the reals. He considers algebras with one of three binary operations corresponding to addition, multiplication or composition. This study is furthered by Schweizer and Sklar in [3]–[6]. In addition to the operations mentioned above they also introduce a partial ordering which corresponds to restriction of functions. In the second of these papers they give a set of axioms such that any system satisfying these axioms is order isomorphic to a concrete system of partial functions under composition and ordered by restriction. In [7] Schweizer and Sklar extend their work to the algebra of multiplace vector-valued functions. In [8] Whitlock studies abstract multiplaced function systems given by super-associative laws and shows that these systems are isomorphically embeddable in a concrete system of multiplaced functions where the operation on the functions is substitution of an m-ary function in an n-ary function.

In this paper we consider the set of functions from Uα, the set of α-sequences, to U where a is an infinite ordinal. As opposed to the composition operations studied in the above works, we consider the composition operations *κ, for κ < α, in a narrow sense—the substitution of one function in the κth place of another. The algebras studied have the form ‹A, *κ, Vκ› κ<α where Vκ are the projection (selector) functions on the κth place. In particular, the polynomials over an algebra form such an algebra called a polynomial substitution algebra. In §6 we show that a first-order axiom system and a condition of local finiteness, given by Pinter in a talk at Berkeley in 1972 to characterize term substitution abgebras, also characterize these polynomial substitution algebras.

The basic concept underlying probability theory and statistics is a function assigning numerical values (probabilities) to events. An “event” in this context is any conceivable state of affairs including the so-called “empty event”—an a priori impossible state. Informally, events are described in everyday language (e.g. “by playing this strategy I shall win $1000 before going broke”). But in the current mathematical framework (first proposed by Kolmogoroff [Ko 1]) they are identified with subsets of some all-inclusive set Q. The family of all events constitutes a field, or σ-field, and the logical connectives ‘and’, ‘or’ and ‘not’ are translated into the set-theoretical operations of intersection, union and complementation. The points of Q can be regarded as possible worlds and an event as the set of all worlds in which it takes place. The concept of a field of sets is wide enough to accommodate all cases and to allow for a general abstract foundation of the theory. On the other hand it does not reflect distinctions that arise out of the linguistic structure which goes into the description of our events. Since events are always described in some language they can be indentified with the sentences that describe them and the probability function can be regarded as an assignment of values to sentences. The extensive accumulated knowledge concerning formal languages makes such a project feasible. The study of probability functions defined over the sentences of a rich enough formal language yields interesting insights in more than one direction.

Our present approach is not an alternative to the accepted Kolmogoroff axiomatics. In fact, given some formal language L, we can consider a rich enough set, say Q, of models for L (called also in this work “worlds”) and we can associate with every sentence the set of all worlds in Q in which the sentence is true. Thus our probabilities can be considered also as measures over some field of sets. But the introduction of the language adds mathematical structure and makes for distinctions expressing basic intuitions that cannot be otherwise expressed. As an example we mention here the concept of a random sequence or, more generally, a random world, or a world which is typical to a certain probability distribution.

In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set W is exponential diophantine, i.e. can be represented in the form

Here P is a polynomial with integer coefficients and the variables range over positive integers.

In 1970 Ju. V. Matijasevič used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevič proved [11] that the exponential relation y = 2x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set Wcan be represented in the form

From this it follows that there does not exist an algorithm to decide solvability of diophantine equations. The nonexistence of such an algorithm follows immediately from the existence of r.e. nonrecursive sets.

Now it is well known that the recursively enumerable sets W1, W2, W3, … can be enumerated in such a way that the binary relation x ∈ Wv is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v,

One of the first results in model theory [12] asserts that a first-order sentence is preserved in extensions if and only if it is equivalent to an existential sentence.

In the first section of this paper, we analyze a natural program for extending this result to a class of languages extending first-order logic, notably including L(Q) and L(aa), respectively the languages with the quantifiers “there exist un-countably many” and “for almost all countable subsets”.

In the second section we answer a question of Bruce [3] by showing that this program cannot resolve the question for L(Q). We also consider whether the natural class of “generalized Σ-sentences” in L(Q) characterizes the class of sentences preserved in extensions, refuting the relativized version but leaving the unrestricted question open.

In the third section we show that the analogous class of L(aa)-sentences preserved in extensions does not include (up to elementary equivalence) all such sentences. This particular candidate class was nominated, rather tentatively, by Bruce [3].

In the fourth section we show that under rather general conditions, if L is a countably compact extension of first-order logic and T is an ℵ1-categorical first-order theory, then L is trivial relative to T.

If is a countable recursively saturated structure and T is a recursively axiomatizable theory that is consistent with Th(), then it is well known that can be expanded to a recursively saturated model of T [7, p. 186]. This is what has made recursively saturated models useful in model theory. Recursive saturation is the weakest notion of saturation for which this expandability result holds. In fact, if is a countable model of Pr = Th(ω, +), then can be expanded to a model of first order Peano arithmetic P just in case is recursively saturated (see [3]).

In this paper we investigate two natural sets of Turing degrees that tell a good deal about the expandability of a given structure. If is a recursively saturated structure, I() consists of the degrees of sets that are recursive in complete types realized in . The second set of degrees, D(), consists of the degrees of sets S such that is recursive in S-saturated. In general, I() ⊆ D(). Moreover, I() is obviously an “ideal” of degrees. For countable structures , D() is “closed” in the following sense: For any class C ⊆ 2ω, if C is co-r.e. in S for some set S such that , then there is some σ ∈ C such that . For uncountable structures , we do not know whether D() must be closed.

We show that every formula of Lω1P is equivalent to one which is a propositional combination of formulas with only one quantifier. It follows that the complete theory of a probability model is determined by the distribution of a family of random variables induced by the model. We characterize the class of distribution which can arise in such a way. We use these results together with a form of de Finetti’s theorem to prove an almost sure interpolation theorem for Lω1P.

We study reducts of Peano arithmetic for which conditions of saturation imply the corresponding conditions for the whole model. It is shown that very weak reducts (like pure order) have such a property for κ-saturation in every κ ≥ ω1. In contrast, other reducts do the job for ω and not for κ > ω1. This solves negatively a conjecture of Chang.

G is the system of propositional modal logic whose axioms are all tautologies and all sentences □(A → B) → (□A → □B) and □(□A → A) → □A and whose rules are modus ponens and necessitation. For the connections between G and provability in formal systems, see [3] and [2].

A letterless sentence is a modal sentence that contains no sentence letters at all. In [1] the author showed (in effect) the existence of simple normal forms in G for letterless sentences: every letterless sentence is equivalent in G to a truth-functional compound of sentences ⋄r ⊤ (⋄0B = B; ⋄r+1B = ⋄ ⋄r+1 B. ⊤ is the 0-ary connective that is always evaluated as true; we assume that the language contains ⊤ as a primitive.)

A family of sets {Hn}n∈ω of modal sentences that contain no sentence letters other than some fixed one (say p) was introduced by Solovay in [3]: H0 = the set of sentences equivalent in G to one of p, −p, ⊤, and ⊥; Hn+x = the set of sentences equivalent in G to a truth-functional combination of sentences ⋄rB, where r ∈ ω and B ∈ Hn. (This definition of the Hn's differs inessentially from the one given in [3].) Since r may = 0, Hn ⊆ Hn+1 and thus if m ≤ n, Hm ⊆ Hn; every modal sentence containing no letter other than p is in some Hn. It follows from the normal form theorem for letterless sentences that every letterless sentence is in H1.

In [3] Solovay stated without proof a result about the sets Hn: for every n, Hn ⊊ Hn+1; equivalently, for every n, there is a sentence containing no letter other than p not in Hn. Thus the existence of a normal form for letterless sentences is a very special feature of these sentences, for Solovay's result shows that normal forms like those obtainable for letterless sentences are not to be found in general. He takes this result to be one reason for regarding the Lindenbaum algebra in G of sentences containing no letter other than p as much more complicated than that of letterless sentences.

Si vous ne gardez du calcul des prédicats classique (que j'appellerai Lω) que les formules qui ne font intervenir, tant en occurences libres que liées, que les n premières variables, vous obtenez le langage Ln. Avant de poursuivre, et de façon un peu cavalière, je vous invite à résoudre l'exercice suivant:

Exercice 1. Dans le langage comprenant seulement un symbole de relation binaire, caractériser à isomorphisme près la chaîne à n éléments au moyen d'un seul énoncé de L2.

Vous avez vu que Ln a plus de possibilités d'expression que vous ne l'aviez d'abord pensé, qu'il est ennemi de la forme prénexe, que sa force au contraire réside dans l'utilisation d'une même variable en différentes places d'une formule.

Ces langages ont été étudiés par Léon Henkin dans [1]; il y remarque que L1 est très pauvre: c'est le “calcul des classes”, on y peut seulement exprimer que des combinaisons booléennes de formules atomiques sont vides ou non, et nous n'en parlerons plus; il montre ensuite que tout théorème de L2est prouvable par une suite de déductions (d'un système classique) qui ne fait intervenir que des énoncés de L3. Dans [2], Donald Monk construit pour tout n un théorème de L3 dont toute preuve utilise des énoncés avec au moins n variables. Dans [3], Dana Scott prouve que L2 est décidable; ce résultat est précisé par Michael Mortimer dans [4], qui montre que tout énoncé consistant f de L2 a un modèle fini, de cardinal borné effectivement en fonction de f. Pour n supérieur ou égal à 3, Ln n'est plus décidable car il a même pouvoir d'expression que Lω, comme il est montré dans l'exercice suivant.

For every κ ∈ ω, there is an infinite set Aκ ⊆ ω and a d(κ) ∈ ω such that for all Q0, Q1, ⊆ Aκ where ∣Q0∣ = ∣ Q1∣, or d(κ) < ∣Q0∣, Q1∣ < ℵ0, the structures ‹ω, +, Q0› and ‹ω, +, Q1› are indistinguishable by first-order sentences of quantifier depth κ whose atomic formulas are of the form u = v, u + v = w, and Q(u), where u, v, and w are variables.

Let ℒ be the first order language of field theory with an additional one place predicate symbol. In [B2] it was shown that the elementary theory T of the class of all pairs of real closed fields, i.e., ℒ-structures ‹K, L›, K a real closed field, L a real closed subfield of K, is undecidable.

The aim of this paper is to show that the elementary theory Ts of a nontrivial subclass of containing many naturally occurring pairs of real closed fields is decidable (Theorem 3, §5). This result was announced in [B2]. An explicit axiom system for Ts will be given later. At this point let us just mention that any model of Ts, is elementarily equivalent to a pair of power series fields ‹R0((TA)), R1((TB))› where R0 is the field of real numbers, R1 = R0 or the field of real algebraic numbers, and B ⊆ A are ordered divisible abelian groups. Conversely, all these pairs of power series fields are models of Ts.

Theorem 3 together with the undecidability result in [B2] answers some of the questions asked in Macintyre [M]. The proof of Theorem 3 uses the model theoretic techniques for valued fields introduced by Ax and Kochen [A-K] and Ershov [E] (see also [C-K]). The two main ingredients are

(i) the completeness of the elementary theory of real closed fields with a distinguished dense proper real closed subfield (due to Robinson [R]),

(ii) the decidability of the elementary theory of pairs of ordered divisible abelian groups (proved in §§1-4).

I would like to thank Angus Macintyre for fruitful discussions concerning the subject. The valuation theoretic method of classifying theories of pairs of real closed fields is taken from [M].

Let Bn, 0 ≤ n ≤ ω, be the equational classes of distributive p-algebras (precise definitions are given in §1). It has been known for some time that the elementary theories Tn of Bn possess model companions ; see, e.g., [6] and [14] and the references given there. However, no axiomatizations of were given, with the exception of n = 0 (Boolean case) and n= 1 (Stonian case). While the first case belongs to the folklore of the subject (see [6], also [11]), the second case presented considerable difficulties (see Schmitt [13]). Schmitt's use of methods characteristic for Stone algebras seems to prevent a ready adaptation of his results to the cases n ≥ 2.

The natural way to get a hold on is to determine the class E(Bn) of existentially complete members of Bn: Since exists, it equals the elementary theory of E(Bn). The present author succeeded [12] in solving the simpler problem of determining the classes A(Bn) of algebraically closed algebras in Bn (exact definitions of A(Bn) and E(Bn) are given in §1) for all 0 > n < ω. A(Bn) is easier to handle since it contains sufficiently many “small” algebras-viz. finite direct products of certain subdirectly irreducibles-in terms of which the members of A(Bn) may be analyzed (in contrast, all members of E(Bn) are infinite and ℵ-homogeneous). As it turns out, A(Bn) is finitely axiomatizable for all n, and comparing the theories of A(B0), A(B1) with the explicitly known theories of E(B0), E(B1)-viz. , , a reasonable conjecture for , 2 ≤ n ≤ ω, is immediate. The main part of this paper is concerned with verifying that the conditions formalized by suffice to describe the algebras in E(Bn) (necessity is easy). This verification rests on the same combinatorial techniques as used in [12] to describe the members of A(Bn).