This paper presents an analysis of definitions and decidability for exponential functions on various matrix algebras. The main idea is to show that, generically, the entries of the exponential (or logarithm) of a matrix are Pfaffian functions of the entries of the matrix.

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog neural networks with the sigmoid activation function o(y) = 1/1 + e-y to be bounded by a quadratic polynomial in the number of programmable parameters.O

The brilliant work of Ax-Kochen [1], [2], [3] and Ersov [6], and later work by Kochen [7] have made clear very striking resemblances between real closed fields and p-adically closed fields, from the model-theoretical point of view. Cohen [5], from a standpoint less model-theoretic, also contributed much to this analogy. In this paper we shall point out a feature of all the above treatments which obscures one important resemblance between real and p-adic fields. We shall outline a new treatment of the p-adic case (not far removed from the classical treatments cited above), and establish an new analogy between real closed and p-adically closed fields. We want to describe the definable subsets of p-adically closed fields. Tarski [9] in his pioneering work described the first-order definable subsets of real closed fields. Namely, if K is a real-closed field and X is a subset of K first-order definable on K using parameters from K then X is a finite union of nonoverlapping intervals (open, closed, half-open, empty or all of K). In particular, if X is infinite, X has nonempty interior. Now, there is an analogous question for p-adically closed fields. If K is p-adically closed, what are the definable subsets of K? To the best of our knowledge, this question has not been answered until now. What is the difference between the two cases? Tarski's analysis rests on elimination of quantifiers for real closed fields. Elimination of quantifiers for p-adically closed fields has been achieved [3], but only when we take a cross-section π as part of our basic data. The problem is that in the presence of π it becomes very difficult to figure out what sort of set is definable by a quantifier free formula. We shall see later that use of the cross-section increases the class of definable sets.

In this paper we prove that the word problem for division rings is recursively unsolvable. Our proof relies on the corresponding result for groups [7], [28], and makes essential use of P. M. Cohn's recent work [11], [13], [15], [16] on division rings. The word problem for groups is usually formulated in terms of group presentations or finitely presented groups, as in [7], [24], [28], [30]. An equivalent formulation, in terms of the universal Horn sentences of group theory, is mentioned in [32]. This formulation makes sense for arbitrary first-order theories, and it is with respect to this formulation that we show that the word problem for division rings has degree 0′.

The central result of this paper was proved in order to settle a problem arising from B. H. Neumann's paper [10]. In [10] Neumann proved that if a finitely generated group H is recursively absolutely presentable then H is embeddable in all nontrivial algebraically-closed groups. Harry Simmons [14] clarified this by showing that a finitely generated group H is recursively absolutely presentable if and only if H can be recursively presented with solvable word-problem. Therefore, if a finitely generated group H can be recursively presented with solvable word-problem then H is embeddable in all nontrivial algebraically-closed groups. The problem arises of characterizing those finitely generated groups which are embeddable in all nontrivial algebraically-closed groups. In this paper we prove, by a forcing argument, that if a finitely generated group H is embeddable in all non-trivial algebraically-closed groups then H can be recursively presented with solvable word-problem. Thus Neumann's result is sharp. Our results are obtained by the method of forcing in model-theory, as developed in [1], [12]. Our method of proof has nothing to do with group-theory. We prove general results, Theorems 1 and 2 below, about constructing generic structures without certain isomorphism-types of finitely generated substructures. The formulation of these results requires the notion of Turing degree. As an application of the central result we prove Theorem 3 which gives information about the number of countable K-generic structures. We gratefully acknowledge many helpful conversations with Harry Simmons.