# Further background information on Richard Kaye's research

Here is some more details on my research, including some background and an attempt to give the flavour of the sort of research I do. These are taken topic-by-topic, although all the topics mentioned here are very much related.

## Models of arithmetic

The theory of Peano Arithmetic or PA is the first-order theory true for the natural numbers with addition and multiplication, and has the full induction scheme in this language. The theory of Presburger Arithmetic is essentially the same, but the language is restricted so that it only contains symbols for +, <, 0, 1, and the usual logical symbols.

Much of my work and the work of research students associated with me concentrates on investigating the stuctural properties of models of Peano Arithmetic (PA) and Presburger Arithmetic (Pres). The natural numbers forms one such model, but there are many others, all with "infinite" natural numbers, called nonstandard numbers.

The fine structure theory of such models is in many ways analogous to Galois theory, and the automorphism groups of recursively saturated models of PA and Pres are studied as well. However, some of the interesting questions have little to do with groups---for example, there are plenty of interesting questions concerning the order type of such models.

## Diophantine problems and Hilbert's tenth problem.

Hilbert's tenth problem (posed in 1900) asks for an algorithm to decide which diophantine equations (polynomial equations of the form p(x1,...,xn)=0 in several variables but with integer coefficients) can be solved in the integers. The final solution in 1970 by Yuri Matyasevich says there is no such algorithm. There are many important and interesting problems still left over in this area, however. For example, an algorithm can be given to decide whether diophantine equations in a single variable are soluble, but noone knows what the status of the question for equations in two variables is.

Matiyasevich's theorem on Hilbert's tenth problem also has important applications to the fine structure of models of arithmetic, especially weak fragments of PA. A typical sort of application shows that the addition and/or multiplication in a nonstandard model cannot be computable.

A third aspect of Matiyasevich's theorem is that we do not know how strong a system of arithmetic T is required to prove it. T=PA suffices, but the status of Matiyasevich's theorem in much weaker theories is unknown. A typical problem here which I am particularly interested in and which has much scope for interesting postgraduate work is the following question for a theory T: is there an algorithm which will tell you is a diophantine equation p(x1,...,xn)=0 in several variables has a solution in some model of T. One object of this research is to find theories T for which there is no such algorithm.

## Recursive saturation.

Recursively saturated models are `rich' or resplendent models, and they often arise in the context of models of arithmetic, but do not have to. I am interested especially in countable recursively saturated models. This area of my work is rather pure "model theory", and relates more closely to model theory done elsewhere. It is also, I believe, an important tool in the study of infinite permutation groups.

To study recursive saturation it is not really necessary to have any deep background knowledge of recursion theory (i.e., computability), but there are of course many interesting links.

## Automorphism groups of first-order stuctures.

The automorphism group of a structure is a typically infinite group acting on an infinite set (the domain of the structure), i.e., is a permutation group. Therefore it is no surprise to find that permutation group theory and model theory have close connections. These close connections have been best exploited in the context of Oligomorphic permutation groups---equivalently aleph-0 categorical structures. It seems, however, that the connections are just as important (and somewhat more general) in the context of recursive saturation. The main object of my research here is to identify these connections and find applications both of permutation group theory to model theory and the other way round.

Automorphism groups can also be considered as topological groups, and the study of such topological groups is equally facinating.

## Satisfaction classes.

Satisfaction classes provide a formal theory of truth over a model of arithmetic, and also provide a way to study recursively saturated models of arithmetic. A satisfaction class is an extra predicate on can sometime put on a model of PA which provides a definition of truth for the arithmetical notions in the model. (It is necessary that a satisfaction class is a new predicate since it cannot itself be definable in the original model by Tarski's theorem on the undefinability of truth.)

In fact, not every model of PA can have a satisfaction class added to it, but many can. It turns out that a countable model M of PA has a satisfaction class S (indeed, many such classes) if and only if M is recursively saturated. The details are technical, but quite fascinating with applications ranging from philosophy (theories of truth, and what can and cannot be made "true" in some satisfaction class) through models of arithmetic (important structural properties are proved using satisfaction classes) to model theory in general.