Introduction. One of the most important objects in the study of the recursive functions is the universal computable function, which makes it possible to compute the values of those functions in a uniform and algorithmic way. That is, if is an acceptable system of indices (see [3]) for the unary partial computable functions, then the function

is also computable.

Hence, it is interesting to study its properties, including its symmetry. The usual way to accomplish this is to study the automorphisms, isomorphic embeddings and homomorphisms of the object (see [1] for the definitions). In this case we will study the corresponding functions for the graph of ϕ. We will denote this predicate by P, so

for all natural numbers e, x and y.

A permutation f of the natural numbers will be an automorphism [1] of this predicate if

for all natural numbers e, x and y; that is, if

for all natural numbers e, x and y.

Thus, these automorphisms are changes of coordinates with respect to which the computations of the recursive functions are performed in exactly the same way as in the original model. In other words, these are the symmetric transformations which take into account the way the computable functions are actually computed.

Another interesting predicate closely related to P is the one that expresses membership of an element to an r.e. set. Since r.e. sets are exactly the domains of the unary partial computable functions (see, for instance, [4]), if we define (as usual)

the new predicate, which we will denote by W, will have the form

for x, y natural numbers.

Introduction.

Motivating Question:Which functions are explicitly definable in the arithmetic Structures

Here iq (“integer quotient”) and rem (“remainder”) describe

integer division with remainder,

that is, iq : and rem : are the functions such that for all we have, with.

We nowspecifywhatwe mean by explicitly definable. Let be an L-structure with distinct marked elements 0,. A function is said to be explicitly definable in M if there are L-terms t1(x), …, tn(x) with x = (x1, …, xm), such that each set

is definable inMby a quantifier-free L-formula, and these sets together cover Mm. (Throughout this paper, m and n range over

An n-ary relation is said to be explicitly definable in M if its characteristic function is explicitly definable inM.

Remarks on explicit definability.

1. (1) Connection to computation: The recursive programs on M from [7, 8] have the property that explicit definability in M is equivalent to computability by a recursive program on M in a uniformly bounded number of steps, as measured by a certain cost function. A precise statement to this effect can be found in [8].

Introduction and preliminaries.If (K, ∂) is a differentially closed field of characteristic 0, an algebraic D-variety over K is an algebraic variety over K together with an extension of the derivation ∂ to a derivation of the structure sheaf of X. Welet D denote the category of algebraic D-varieties and G the full subcategory whose objects are algebraic D-groups. D and G were essentially introduced by Buium and G was exhaustively studied in [2]. The category D is closely related but not identical to the class of sets of finite Morley rank definable in the structure (K,+, ・, ∂) (which is essentially the class of “finitedimensional differential algebraic varieties”). However an object ofD can also be considered as a first order structure in its own right by adjoining predicates for algebraic D-subvarieties of Cartesian powers. In a similar fashion D can be considered as a many-sorted first order structure. In [5] it was shown that the many-sorted “reduct” G has quantifier-elimination. We point out in this paper an easy example showing:

PROPOSITION 1.1. D does not have quantifier-elimination.

The notion of a “complete variety” in algebraic geometry is fundamental. Over C these are precisely the varieties which are compact as complex spaces. Kolchin [4] introduced completeness in the context of differential algebraic geometry. This was continued by Pong [12] who obtained some interesting results and examples. We will give a natural definition of completeness for algebraic D-varieties. The exact relationship to the notion studied by Kolchin and Pong is unclear: in particular I do not know whether any of the examples of new “complete” ∂-closed sets in [12] correspond to complete algebraic D varieties in our sense.

Introduction.This paper is to some extent a continuation of my introductive and programmatic paper [Ku3]. In that paper I pointed out that the ramification theoretical defect of finite extensions of valued fields is responsible for the problems we have when we deal with the model theory of valued fields, or try to prove local uniformization in positive characteristic.

In the present paper I will discuss the connection between the defect and additive polynomials. I will state and prove basic facts about additive polynomials and then treat several instances where they enter the theory of valued fields in an essential way that is particularly interesting for model theorists and algebraic geometers. I will show that non-commutative structures (skew polynomial rings) play an essential role in the structure theory of valued fields in positive characteristic. Further, I will state the main open questions. I will also include some exercises.

In the next section, I will give an introduction to additive polynomials and describe the reasons for their importance in the model theory of valued fields. For the convenience of the reader, I outline the characterizations of additive polynomials in Section 3 and the basic properties of rings of additive polynomials in Section 4. For more information on additive polynomials, the reader may consult [Go], cf. also [O1], [O2], [Wh1], [Wh2], [Ku4], [Dr–Ku]. The remaining sections of this paper will then be devoted to the proofs of some of the main theorems stated in Section 2.