We refine results of Gannon [6, Theorem 4.7] and Simon [22, Lemma 2.8] on convergence of Morley sequences. We then introduce the notion of eventual$NIP$, as a property of a model, and prove a variant of [15, Corollary 2.2]. Finally, we give new characterizations of generically stable types (for countable theories) and reinforce the main result of Pillay [17] on the model-theoretic meaning of Grothendieck’s double limit theorem.

We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel quotient of the reals reduces to it.

Let α be a limit ordinal with the property that any “recursive” function whose domain is a proper initial segment of α has its range bounded by α. α is then called admissible (in a sense to be made precise later) and a recursion theory can be developed on it (α-recursion theory) by providing the generalized notions of α-recursively enumerable, α-recursive and α-finite. Takeuti [12] was the first to study recursive functions of ordinals, the subject owing its further development to Kripke [7], Platek [8], Kreisel [6], and Sacks [9].

Infinitary logic on the other hand (i.e., the study of languages which allow expressions of infinite length) was quite extensively studied by Scott [11], Tarski, Kreisel, Karp [5] and others. Kreisel suggested in the late '50's that these languages (even which allows countable expressions but only finite quantification) were too large and that one should only allow expressions which are, in some generalized sense, finite. This made the application of generalized recursion theory to the logic of infinitary languages appear natural. In 1967 Barwise [1] was the first to present a complete formalization of the restriction of to an admissible fragment (A a countable admissible set) and to prove that completeness and compactness hold for it. [2] is an excellent reference for a detailed exposition of admissible languages.

It is well known that in prepositional logic not every propositional connective is definable in terms of equivalence nor indeed in terms of equivalence together with negation. It is the purpose of this note to show that in a certain sense this is, however, possible within predicate logic.

Let F1 be the class of predicate logical formulae containing only the logical connectives ¬ (not), ∨ (or), E (exists), and F2 the class of predicate logical formulae containing only the logical connectives ≡ (if and only if) and E.

Our object will be to find a method for reducing any formulae ϕ of F1 to a formula ψ of F2 such that ϕ is valid if and only if ψ is valid.

Note first that for every domain D containing at least two individuals we can for every n-place relation R defined over D find an n + 1-place relation S defined over D such that for all x1, …, xn ∈ D,

holds. For instance, let S(y, x1, …, xn) be the relation y = x1 & R(x1, …, xn).

Now let ϕ be an arbitrary formula of F1 and A1, …, A3 a complete list of predicate letters occurring in ϕ of degree g1, …, gi, respectively. Let ϕ′ be the formula obtained from ϕ by replacing every prime formula Ai(x1, …, xgi) by

Then it follows immediately from the previous observation that (a) ϕ is satisfiable in D if and only if ϕ′ is satisfiable in D.

A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i.e. one whose Turing jump is truth-table reducible to the halting problem ∅′. A negative answer to this question is provided by giving an explicit construction of a promptly simple set that is not superlow cuppable. This problem relates to effective randomness and various lowness notions.

We consider the effect on decidability of adding, to the decidable theory of algebraically closed fields of characteristic zero, relation symbols for algebraic independence or function symbols for differentiation. Our results show that the corresponding theories are usually undeeidable.

Let k and K be algebraically closed fields of characteristic zero. Let K be an extension of k of transcendence degree n over k. Since k has characteristic 0, we may assume that the rational field, Q, is a subfield of k.

Let Indn be the n-ary relation on K which holds for exactly those n-tuples from K which are algebraically independent over k.

Let x1, …, xn be a transcendence base for K over k. For i = 1, 2, …, n, let Di: K → K be the partial differentiation function with respect to xi and this base.

Let KnInd = (K, +, ·, Indn), n ≤ 1 and let KnDiff = (K, +, ·, D1, …, Dn), n ≤ 1 where K has transcendence degree n over k.

We show that the theories of these structures are independent of k when k has infinite transcendence degree over Q, that KnDiff has undeeidable theory for n ≤ 1 and that KnInd has undeeidable theory for n ≤ 2. The theory of K1Ind is decidable.

One long-range objective of logic is to find models of arithmetic with noteworthy properties, perhaps properties that imply some long-standing number theoretic conjectures. In areas of mathematics such as algebra or set theory, new models are often made by extending old models, that is, by adjoining new elements to already existing models. Usually the extension retains most of the characteristics of the old model with at least one exception that makes the new model interesting. However, such a scheme is difficult in the area of arithmetic. Many interesting properties of the fine structure of arithmetic are diophantine and hence unchangeable in extensions. For instance, one cannot change a prime number into a composite one by adjoining new elements.

One could possibly get around this diophantine difficulty in one of two ways. One way is to change the usual language of addition and multiplication to an equivalent language that does not transmit so much information to extensions. For instance, multiplication is definable from the squaring function, as one sees from the identity 2xy = (x + y)2 − x2 − y2, and the squaring function in turn is definable either from the unary square predicate (as one sees from the fact that n = m2 if n and n + 2m + 1 are successive squares) or from the divisor relation (as one sees from the fact that n = m2 if n is the smallest number such that m divides n and m + 1 divides n + m). Either of these two alternatives to multiplication might make for interesting extensions.