Christopher John Ash was born on 5 January 1945 at Gorleston, a seaside town adjoining Great Yarmouth, Norfolk, England. He was an only child. His father, Kenneth William Ash, was the middle of three brothers. The elder brother was a Wing Commander in the Royal Air Force who worked on rocket research and the younger was a Captain in the Merchant Navy. Chris’s father was Borough Engineer at Redcar on the North Yorkshire coast. His mother was Joan Evelyn Hadley, who worked at a Quaker school. Chris’s paternal grandfather was Headmaster of Middlesborough High School.
After starting school at Wilton House School, Redditch, near Birmingham he continued at Newcomen Primary School, Redcar, in 1953. At Redcar he joined the St. Peter’s Church choir, whose choirmaster was his music master from school. He loved the dressing up and the ceremony of church services. He lamented that when his voice broke he ‘was left with a rather feeble and inadequate tenor voice’ – a dubious assertion at best. Continuing his musical interests, he learnt to play violin, piano and cello, to which he later added recorders, clarinet and bassoon. Later still viola and tenor horn joined that impressive list. His love of music continued throughout his life.
From 1955 he attended Sir William Turner’s School at Coatham, North Yorkshire. He had taken the ‘eleven-plus’ examination a year early, as many bright children did, and he had the opportunity to become a boarder at York Minster Choir School. However, his parents decided, against Chris’s desires, to keep him at home.
In his first form in high-school, he was in the top two or three of his class of thirty. His English master in April 1956, his first year of high-school, commented ‘he must be careful of the inexact use of words’ – a recommendation which seems to have had effect, for Chris loved the exact use of words – in English or other languages – and he used words well.
When it came to entering the Sixth Form, he had to decide between Classics and Science. He certainly read and enjoyed classical literature, Greek and other, all his life, and enjoyed translating or debating Latin epithets. But he opted for Science as ‘more realistic’. He was surprised when his headmaster advised him to drop Chemistry and do Further Mathematics. However, Chris did hold his mathematics master, L. Page, in high regard and he followed the advice. For Pure Mathematics, in his penultimate year in high school, his other mathematics teacher wrote: ‘He has the ability and knowledge to be very successful, but he must guard against careless errors’. This comment apparently did not need repeating, as subsequently Chris was very careful.
Encouraged by his school he got a place at St Edmund Hall, Oxford and a State Scholarship. His undergraduate career in mathematics was undistinguished. He got a Second in Mathematics Finals, which was a disappointment to him, but it appears that he did not get much pleasure from the mathematics there. ‘The only lectures I enjoyed were those of Ken Gravett in Set Theory’, he has reported. Contemporaries in general would have regarded Gravett’s as the most entertaining and stimulating of all their lectures.
Singing flourished and, having sung in various choirs, Chris became a member of Schola Cantorum Oxoniense. This small group went on overseas tours including one to Italy and made at least one commercial record with Chris singing.
In 1966, he was awarded a (U.K.) Science Research Council award to do graduate study. By that time, Mathematical Logic was his preferred area of study. The subject had only recently been admitted into the advanced section (Part II) of the Final Examinations in Mathematics, but there was interest in the subject in Oxford, and it was increasing particularly among the mathematicians, with some philosophers contributing.
At that time graduate students first completed a Diploma in Advanced Mathematics (now renamed an MPhil degree). Ash worked under John Crossley, writing ‘A dissertation on constructive ordinals’. The importance of this enterprise for his future work is today apparent.
Ordinals are numbers which correspond to putting objects in order. Traditionally they are called ‘first’, ‘second’, ‘third’, etc. in English, but written simply as 1, 2, 3, etc… The sequence can be continued into the transfinite and extended to 1, 2, 3, …, ω the first infinite ordinal. After this, following the nineteenth-century notation of Cantor, one progresses to ω +1, ω + 2, …, ω + ω (which is written, awkwardly, as ω ⋅ 2), ω ⋅ 2 + 1, …, ω ⋅ 3, …, ω ⋅ n (for arbitrary finite n), ω⋅ω (written ω2 ) and continues further through ωn (n finite), then ωω. After this come generalized polynomials in ω, including ωωω ⋅ 2 + ωω ⋅ 3, for example. The generating processes for larger ordinals may be less apparent. However, the collection of ordinals is unending. ‘Constructive ordinals’ are those for which one can give a name, or ‘notation’, which encodes the construction process. There are different ways of presenting constructive ordinals (see e.g. Kleene [Kl], Markwald [Md]), but the actual ordinals notated are the same. The constructive ordinals play a fundamental rôle in all of Ash’s subsequent work in logic.
There is another noteworthy aspect of Ash’s diploma dissertation. While most students at this stage seem content to understand others’ proofs and explanations, Ash reworked everything. Chris always liked to be told what a theorem said and then to work out its proof for himself. This practice gave him a very deep understanding and enabled him to write up his work in an exceptionally clear fashion. This took a lot of work, but it also developed his insight and command.
In the 1960s, set theory, recursion theory and model theory were all rapidly becoming more sophisticated. In set theory, Cohen [Co] developed his method of forcing to prove the independence of the Axiom of Choice and the Continuum Hypothesis from the basic axioms of set theory. In recursion theory, the ‘priority method’ was being extended and applied widely, in particular, by Shoenfield [Sho] and Sacks [Sa]. In model theory, there were the notions of homogeneity and saturation, developed by Jónsson [J], and Morley and Vaught [M-V], and there were beautiful results related to ‘categoricity’, the deepest being due to Morley [Mo]. C. Karp [Ka] and others were investigating ‘infinitary’ logic, considering infinite conjunctions and disjunctions.
Recursion theory is the branch of logic dealing with computability and classification of sets, especially sets of natural numbers (or objects which can be coded by natural numbers). A set is decidable, or recursive, if there is an effective procedure for deciding membership in it. A set is recursively enumerable, or r.e., if there is an effective procedure for listing (enumerating) the elements. This method will be discussed further in §3.
Model theory concerns the relation between mathematical structures (such as orderings and fields) and formulae in a mathematical language. The usual formulae are finite, although in infinitary logic they are allowed to be infinite. A sentence is a formula in which all variables are introduced by quantifiers ‘for all’ or ‘there exists’. A theory is the set of all sentences (of the usual kind) true in some structure or class of structures. The models of the theory are the structures in which all sentences of the theory are true. Many of the early results in model theory were related to computability questions. Tarski [Ta] characterized the definable relations in the field of complex numbers, and in the field of real numbers, in the course of proving that the theories of these fields are decidable. By contrast, J. Robinson [Ro] proved that the theory of the rational number field is undecidable.
A theory with infinite models has models of arbitrarily large cardinality – obviously not all isomorphic. A theory is κ-categorical if there is just one model of cardinality κ, up to isomorphism. For example, the theory of the rationals under the usual ordering is ℵ0-categorical. The theory of vector spaces over the field of rationals has infinitely many countable models but is κ-categorical for all uncountable κ. Morley’s Categoricity Theorem says that for a countable theory T, if T is κ-categorical for some uncountable κ, then it is κ-categorical for all uncountable κ.
The group of academics in logic at Oxford had interest in computability at least partly because of Graham Higman’s interest in the word problem for groups [Hig]. Gravett’s interest in set theory naturally led to an interest in the constructive ordinals, combining set theory with computability. But model theory also seized the group’s attention.
Ash was among a strong group of graduate students in logic at Oxford. Their interests were divided between model theory and recursion theory and there was a seminar covering topics from both areas. Ash took some time choosing problems for his PhD thesis. He had rejected a problem suggested by Crossley, his supervisor. Much later – in 1994 – he jokingly said that it had been a mistake to reject the problem, for his thesis took a long time to finish.
Ryll-Nardzewski [Ry] gave very simple criteria for a theory to be ℵ0-categorical. However, as a matter of historical fact it was also the case that all the obvious theories which were ℵ0-categorical were also decidable. It is easy to create an undecidable ℵ0-categorical theory in a language with infinitely many relation symbols. Grzegorczyk [Gr] asked whether there was a theory in a finite language with these properties. Glassmire and Ash independently worked on this problem. Glassmire [Gl] was the first to publish a solution but Ash [1971] produced a construction ‘so simple that I could describe it in abstract’.
This formed part I of Ash’s DPhil thesis. Part II concerns a generalization of Boolean algebras to n-valued Post algebras. The work for Part II actually preceded that for Part I, as it was felt that such structures might lead to undecidable ℵ0-categorical theories (in a finite language). In fact, they are decidable in a strong sense [1972].
In 1969 Ash’s DPhil supervisor (Crossley) moved to a Chair at Monash and Ash obtained a Senior Teaching Fellowship in Mathematics there. He continued work on his thesis. However, Oxford, almost without exception, requires a viva voce examination in Oxford. Consequently, it was not until 1972 that Ash obtained his DPhil. He took out his MA in 1970, but this is a mere technicality and did not require a thesis..His examiners were John Shepherdson (Bristol University) and Robin Gandy (then at Manchester University). In their report they noted: ‘… a bare statement of [the main results] does not give a fair idea of the excellence of the thesis. Firstly the material is beautifully presented – we have seldom seen a dissertation which was so easy to read. Secondly, the author always has complete command of his material. When he has occasion to reprove known results his proofs are pithier and more transparent than those in the literature. (This is particularly true of Foster’s theorem about functionally complete algebras; the original proof was extremely hard to grasp). He picks out just those results needed for his purpose; the examples (see particularly section 6 of part I) are happily chosen. Thirdly, he uses, with evident understanding, a much wider range of results and techniques than is usual in DPhil theses. (In particular, Rabin’s techniques for proving decidability – see [Ra] – are not part of the standard equipment of model theorists).
‘In his oral exam he gave an extremely interesting account of the way in which the work had developed. This made it plain that the thesis had more coherence than might be obvious at first sight; it grew from a wellorganised attack on the problem solved in part I. He also confirmed the impression given by the thesis that he was familiar with all the work, cited or not, which was connected with his own.’
On returning to Monash Ash was promoted to a lectureship (in 1973). Within a short time, two important influences had begun to shape his research career. One was a visitor. Chris subsequently wrote: ‘I was greatly encouraged during this period by a visit from Anil Nerode of Cornell [University]. His apparently limitless store of knowledge of Mathematical Logic set an example for me which I have tried (unsuccessfully) to follow.’ Most logicians would dispute the bracketed word. Nerode worked with Ash on some problems in what was to become Ash’s primary research area. Nerode, in the 1970s, was responsible for getting a number of people interested in an area of logic sometimes called recursive model theory. A more descriptive name, for much of the work, is computable structure theory. This was the title Ash used consistently for his grant proposals.
The other important influence was the great interest in the algebraic structures called semigroups at Monash. Gordon Preston, as Professor, and more especially Tom Hall, as colleague, got Chris interested in their work, and he eventually solved several important problems on semigroups.
Ash’s results in algebra will be discussed in §2. In addition to the results on semigroups, there are results in universal algebra, a subject which sits between algebra and model theory. Ash’s results in logic (after the thesis) will be discussed in §3.
In a memorial booklet [Mem] Gordon Preston wrote: ‘When he first arrived in Australia, about 25 years ago, he was still working on his PhD, a little unsure of himself both mathematically and personally. He was modest and retiring but quickly opened up and showed that he liked his new environment. He made friends easily. I remember him at parties playing the piano for others to sing to and singing along himself. I remember long conversations with him and enjoyed his extensive knowledge of English literature.
‘His mathematical talents developed initially very slowly. He took a long time to complete his PhD, partly because of his desire for perfection. His first research papers had a long gestation period, not just to polish, but to improve arguments, rearrange, and extend results. But in his final development, from this slow start, he became a major figure in world mathematics, with discoveries that will ensure that he is always remembered.’
He was promoted to Senior Lecturer in 1981 and eventually to Reader in 1986. Not long before he died he had been preparing materials towards an application for a personal Chair and these are the source of several quotations in this article. More importantly, they provide more insight into his plans than casual conversations have done.
During his career he had a number of research students: David Billington (now at University of Queensland), Ewan Barker (University of Ballarat), John Love (Omeo, Victoria) and Kevin Davey (now studying at the University of California at Los Angeles) who did Master’s degrees and Geoff Hird (currently at Odyssey Research Associates, Ithaca, New York) who did a PhD. All of these worked on aspects of computable structures.
Chris Ash was a private man who became more reclusive over the years. He had a small number of partners over the years but baulked at marriage. When he could be inveigled into a social event such as lunch or dinner he was always entertaining. If he could be persuaded to play the piano – or any other instrument, it seemed – he demonstrated a talent and great love for music. In possibly the last photograph taken of him, he is playing a piano duet with Alan Robinson (Syracuse University).
Ash’s career in the Department of Mathematics centred on his research. This grew and grew over the years. He was encouraged to put in for Australian Research Council grants but, until the last year or two, he applied only for small grants. These were used to fund visits of workers in his field. He also obtained visiting professorships in the US. In 1975–6 he visited Schmerl at the University of Connecticut (Storrs, Connecticut); in 1980–81 and again in 1985, Terry Millar at the University of Wisconsin at Madison and in 1987, Julia Knight at Notre Dame University (Notre Dame, Indiana). Millar and Millar’s student, John Chisholm, visited Chris. Yuri Gurevich from the University of Michigan (Ann Arbor, Michigan) and Ted Slaman from the University of Chicago also visited Monash and talked or worked with Chris.
The work of Ash and Nerode was closely related to that of the Russian logic school at Novosibirsk, Siberia. Sergei Goncharov visited from there in the early eighties and he and Ash subsequently wrote a paper.
Most important among these connexions was that with Julia Knight, with whom he worked continually for nine years. At the time of writing, there are four joint papers to appear, and Knight is in the process of completing a book which Ash had started [1996].
In teaching, Ash took the utmost pains and gave lectures of exemplary clarity. He was not, however, an administrator. As his career progressed, it was expected that he would, in the usual way, do more senior committee work. In that context, the precision and possibility of getting things exactly right were not available as they were in mathematics, and this caused him anguish. How could he decide, with incomplete data, on the relative merits of incomparable candidates? He found this impossible and intolerable, sought guidance and seemed terrified of making a mistake instead of fearing the consequences of not making a decision.
One other factor made his final years increasingly difficult. His department had adopted a system of calculating points for work, which was intended to spread the workload evenly. Chris did not conform to the usual profile. He was unable to accumulate points through administrative jobs, and his enormous effort in research brought relatively few points. Unfortunately, Chris worried about this, and despite the reassurances of succeeding heads of department, it made him question his worth and justification. This was very sad because all but he could see what an asset he was. Even his election to the Australian Academy of Science in 1994 buoyed him up for only a limited period. At the very same time his research fecundity was growing ever more rapidly – and taking more effort.
He had medical treatment for his psychological state, but it is unclear how much this helped. Certainly he was disaffected by the side-effects of the drugs he was given. In February, 1995, when he died, he left a note in which he characterized himself as ‘too old and unattractive to carry on’. He was found dead on 16 February 1995. The coroner simply recorded that death was due to ‘acute...toxicity’ and that ‘no other person contributed to his death’.
Chris Ash’s interest in algebra was already evident, at least from the standpoint of a mathematical logician, in his Oxford DPhil thesis [1972a]. Six of his later papers show his continuing interest in the questions he looked at in Part II of his thesis, Boolean extensions and Post algebras, for example his 1975 paper [1975a] and his 1986 paper [1986b]. In this work there was a merging of his interests in model theory, in what was possible in algebra if one restricted oneself to what could be effectively constructed, in universal algebra, and in the algebras underlying mathematical logic and their generalizations.
As mentioned above, when Chris arrived at Monash, he found a great deal of activity in semigroups, involving the regular faculty members and many visitors. This quickly attracted him and eventually he became a leading developer of semigroup theory, in particular solving three outstanding problems on which, prior to his solutions, numerous partial results had been obtained over many years. He brought to the solution of these problems a knowledge of techniques in model theory and in ordinal and cardinal arithmetic, his use of which continues to have a major effect on the development of semigroup theory. His first paper on semigroups was a joint one with T.E. Hall [1975c], and although they wrote only one other joint paper, this was the start of a collaboration, witnessed by the explicit attribution of results by each to the other, that continued for most of Chris’s life.
The first result on semigroups of Ash to appear in print was in the 1974 paper of W.D. Munn [Mun]. This is an example, of a semilattice (i.e. a poset [= a partially ordered set] in which any two elements have a greatest lower bound) that is, in Munn’s terminology, subuniform and dense in itself, but not densely subuniform. The construction involves a delicate use of order types and the proof that it has the properties desired is the central result of the paper [1977].
The paper [1975c] with T.E. Hall, already referred to, was an elegant contribution to the problem of determining what kind of poset can be (isomorphic to) the poset of J-classes of some semigroup. Hall had already in [Hal] shown, by an inductive construction, that any finite poset with a least element could be so realised, solving a problem posed by J.L. Rhodes in [Rh]. In their joint paper, starting from a poset P with a least element, they first construct an equivalent directed graph G = G(P), from which they construct an inverse semigroup S = S(G), whose elements are bijections between sets of directed paths in G, and whose poset of J-classes is isomorphic to P. That P has a least element is essential for this construction. As a bonus the construction also led to the discovery of a construction for congruence-free inverse semigroups.
The poset of J-classes of a semigroup does not necessarily have a least element when the semigroup is not finite, but it is always downward directed, i.e. given any two elements of the poset there always exists an element that is less than each of them. Paper [1979c] shows that any downward directed poset can be realised as the poset of J-classes of a completely semisimple inverse semigroup.
The crux of the solution to this problem is in [1979b], in which it is shown that if P is a downward directed poset, then there exists a full, uniform, P-semilattice. The concept of a P-semilattice is due to Ash, and the argument to establish the above existence theorem is complicated and subtle, requiring deep results from universal algebra and set theory. Paper [1980a] provides a corollary: it characterizes the lattices of ideals of a semigroup, including the empty ideal, as those lattices that are complete, distributive, and such that every two non-zero elements have nonzero meet and such that every element is a join of compact, join-irreducible, elements.
Paper [1979a] is an ingenious exercise in the arithmetic of order types constructing a uniform semilattice X such that the Munn semigroup TX (the semigroup of all isomorphisms between principal ideals of X) has no chart. The chosen X is of order type λ + (1+λ)ω1, where λ is the order type of the reals and ω1 is the first uncountable ordinal.
There is now an interlude of seven years before Ash writes again about semigroups, except in the wider context of universal algebra, but where the interest in the problems solved first arose for semigroups.
Paper [1980a] looks at when, and how, a semigroup S can be embedded in a semigroup T so that T has automorphisms extending (some) isomorphisms between subsemigroups of S. In particular, it is shown that an inverse semigroup S may be embedded in an inverse semigroup T such that every isomorphism between inverse subsemigroups of S extends to an inner automorphism of the form s ↦ g–1sg, for some g ∈ T, with g–1g = gg–1 = 1. A second generalization, for inverse semigroups, of the Higman-Neumann-Neumann [1949] theorem on groups with amalgamated subgroups is also offered.
Paper [1985a] introduces an important new concept, that of a generalized variety. A variety is a class of (universal) algebras that consists of all algebras of a given type that satisfy a set of identities. Equivalently, according to the famous Birkhoff [Bi] theorem, a class K of algebras is a variety if and only if it is closed under the formation of morphic images, subalgebras and direct products. If L is any class of algebras, write P(L) for the class of all direct products of members of L, M(L) for the class of all morphic images of members of L, and S(L) for the class of all subalgebras of members of L. Then Birkhoff’s theorem states that K is a variety if and only if K = M(S(P(K))) or, omitting some brackets, MSP(K).
More recently, with the growing emphasis on finite algebras, especially in automata theory, classes of algebras have been studied in which each algebra is required to be finite. In particular, the finite members of a variety form what is called a pseudo-variety. K is a pseudo-variety if and only if K = MSPf (K), where Pf (K) denotes the class of all direct products of a finite number of members of K. Not all pseudo-varieties are obtained by taking the finite members of a variety.
Ash’s concept of a generalized variety is what is required. Define the operator Pow on a class of algebras L by: Pow(L) is the class of all powers of algebras in L. Then a generalized variety K is defined to be a class of algebras such that K = MSPf Pow(K). Ash shows that a pseudo-variety is the same thing as the class of finite members of some generalized variety. In addition, he establishes that a variety is a special case of a generalized variety but the converse is not true.
In the mid-1970s the following problem was circulating in Paris: what is the pseudovariety generated by the finite inverse semigroups? In 1985 (see his [1987b]) Ash showed that it is the class of all finite semigroups for which any two idempotents commute. This is equivalent to showing that any finite semigroup with commuting idempotents is the morphic image of a subsemigroup of a finite inverse semigroup. The proof brought a wealth of new ideas and ingenious techniques and his paper met with wide acclaim. [1987a] presents a special case of his result, the case when J is trivial, but which displays the principal features of the proof. Paper [1990a], written in conjunction with T.E. Hall and J.-E. Pin, gives applications of both the results and the methods used, to investigate recognizable languages associated with pseudovarieties of semigroups with commuting idempotents.
Ash’s final achievement in semigroups ([1990e]) was to prove the so-called ‘type II conjecture’. This had been around since the early ’70s and had attracted great interest and extensive publications had appeared, going part of the way towards its verification. [1990e] is the manuscript of a conference talk (July 1990) in which Ash announced that the conjecture was true and provided the bones of his method of proof. Full details are in [1990e], which also includes important implications of the result.
In his memorial message [Mem] Margolis wrote: ‘The group kernel K(S) of a finite semigroup S is the set of elements that are related to the identity in every relational morphism onto a finite group. The type II subsemigroup SII of S is the smallest subsemigroup of S that contains the idempotents of S and is closed under weak conjugations: if sts = s ∈ S, then sSIIt ∪ tSIIs ⊆ SII.
‘In 1972, Rhodes and Tilson [R-T] proved the SII ⊆ K(S) and that every regular element of S that is in K(S) is, in fact, a member of SII. This proved in particular that if S is a regular semigroup, then SII = K(S). The type II conjecture was that this equality holds for every finite semigroup. Besides, its elegant formulation, the most important consequence of the conjecture is that membership in SII is effective given the multiplication table of S, while that of K(S) a priori involves searching through the infinite collection of all relational morphisms from S to finite groups. The type II conjecture guarantees that membership in K(S) is decidable and many important problems in semigroup theory turned out to be reducible to the effective computation of this subsemigroup.
‘I was aware of the conjecture in 1974 when I was a graduate student at Berkeley. I believe it appeared in print in Semigroup Forum in the mid-70’s in an article by Rhodes that listed some open problems in finite semigroup theory. Not much was done on this problem during the ’70’s. The RhodesTilson article was long and difficult to read and the interests in finite semigroup theory had turned to the development of the new theory of pseudovarieties that had been developed by Eilenberg and Schützenberger to give a firm tie between semigroup theory and the theory of recognizable languages.
‘In the summer of 1980, Jean-Eric Pin asked me if the pseudovariety of finite semigroups generated by finite inverse semigroups was equal to the pseudovariety of finite semigroups all of whose idempotents commuted. After thinking about this for a few days, it occurred to me that this was in fact a special case of the somewhat forgotten type II conjecture! Furthermore, it didn’t seem at first to be much easier than the general case. I was preparing to give a survey talk on finite semigroups at a conference to be held in the fall of 1980 at the University of Nebraska. I thought that this would be a good opportunity to let people in inverse and regular semigroup theory help with a significant problem of finite semigroup theory. I reported the nature of the type II conjecture at the conference and explicitly asked about the question raised by Pin.
‘Luckily, Tom Hall was in the audience and perceived that this was indeed a nontrivial and interesting problem. We were all rewarded in 1985 when Chris confirmed that the Pin question was answered in the affirmative in a brilliant piece of work. The difficulty, of course, lay with the non-regular elements of a finite semigroup, as the regular ones had been handled by Rhodes and Tilson. Chris was able to handle the non-regular elements by using Ramsey’s Theorem. This result in itself led to a number of breakthroughs in this and related theories.
‘Some progress was made on the general problem in the late 80’s. After hearing Tom Hall give a wonderful lecture on Chris’s results at Chico, Rhodes, Birget and I were able to extend the result to proving the type II conjecture in the case that the idempotents of S were a subsemigroup. Tilson, inspired by the result of Chris, gave a new easily understandable proof of the RhodesTilson result on regular elements, which cleared up the connection between weak conjugation and inverse semigroups. This proof indicated heavily that inverse semigroups and Ramsey theory should be the ingredients necessary to prove the general type II conjecture. In the late 80’s Rhodes and Henckell [He] developed a number of new techniques and reduced the type II conjecture to the case of block groups, semigroups whose regular principal factors are Brandt semigroups.
‘In 1990, I came to Monash to attend the Preston retirement conference. I explained these latest developments to Tom and Chris as best I could. During that week before the conference, Chris was able to complete his proof of the type II conjecture. It is a masterpiece. He was actually able to prove much more than the type II conjecture, with a brilliantly conceived generalization of the basic notions. In fact, these improvements were crucial for some of the deepest applications of his work. In fact, the Rhodes type II conjecture follows by applying the generalization to a graph with only one vertex and one arrow!’
The papers on the Type II conjecture were greeted with great excitement when they appeared and they were quickly followed by an explosion of research exploring the deep consequences of both Ash’s theorem and the new techniques he developed. The interested reader can find a good account of some of these consequences in [1990a], [1990e] and [1991b].
In logic, at first Ash worked on miscellaneous problems. From [1981a], joint with Nerode, he developed his own programme of research, but he continued working on miscellaneous problems from time to time. This work was often done in response to the challenges of various logicians, just as the work on semigroups was done in response to the challenges of Tom Hall and other semigroup theorists.
We have already discussed Ash’s thesis. Our discussion of the work Ash did in logic after that is divided into two parts. We begin with the results on miscellaneous problems and then we describe the main programme. The classification is not sharp, of course.
In [1975b], Ash showed that, assuming the Axiom of Choice, the additive groups of real numbers and complex numbers are isomorphic, and that without the Axiom of Choice, they need not be. Continuing this line of thought in [1983a], he showed that many of the standard consequences of the axiom of choice can be expressed in a modeltheoretic way by looking at the infinitary sentences associated with the model. Indeed, he provided a uniform method for establishing the independence of such forms of the axiom of choice.
In his [1975d] Ash characterized the languages in which every sentence which has a model has a finite model, and those in which every universal sentence which has a model has a finite model. (A universal sentence consists of a string of ‘for all’ quantifiers, with no quantifier later.)
Chris liked working on famous hard problems. In [1994a], he recorded his efforts on one such problem, the spectrum problem. The spectrum of a sentence is the set of sizes of finite models of the sentence, and the problem, still open, asks whether the complement of a spectrum is necessarily a spectrum. In attempting to give an affirmative answer, Chris reduced the problem to another statement, conjectured true.
Another famous open problem is the conjecture P ≠ NP, where P is the collection of functions computable in polynomial time by a deterministic machine, and NP refers to the collection of functions computable in polynomial time by a non-deterministic machine (a lucky guess yields a fast computation, while other guesses might not). Chris spent a great deal of time trying to prove that P ≠ NP, until he finally convinced himself that the problem was pure combinatorics.
The most famous problem in model theory is Vaught’s Conjecture, saying that for a countable complete theory T, the number of countable models (up to isomorphism) is either ≤ ℵ0 or 2ℵ0 . Ash had worked on Vaught’s Conjecture early in his career. The little result he obtained is in [1994c]. Unknown to Ash, the referee and the editor, Vaught had proved the result himself, and it had been used in a paper of Shelah [She, p.560].
Ash worked with J.W. Rosenthal on some computability questions in concrete algebraic settings. In [1980b], they showed that the theory of the complex number field with a binary relation for algebraic dependence of pairs is undecidable. In [1986b], they used some differential algebra to obtain a result on algebraically closed fields, saying that for recursive fields F and G of finite transcendence degree, given transcendence bases for F and G, one can effectively determine the transcendence degree of F ∩ G. In [1981b], Ash and Nerode showed the non-functorial nature of the notions of ‘algebraic closure’ and ‘Skolemization’.
As we said earlier, recursion theory involves classifying sets in terms of computability properties. There are different ways to do this. We can classify arbitrary sets of numbers by Turing degree. For sets X and Y, Y is said to be Turing reducible to X (for Alan Turing) if there is an effective procedure for determining membership in Y given answers to questions about membership in X. If the sets X and Y are each reducible to the other, then they are said to be Turing equivalent, or to have the same Turing degree. Sets and relations which admit some kind of effective approximation are classified by level (a constructive ordinal) in the hyperarithmetical hierarchy. This hierarchy begins with the recursive sets and relations. Then come the projections of recursive relations, called Σ01 (these are the same as the recursively enumerable or r.e. sets), and the complements of Σ0 1 relations, called Π0 1 . After that come the projections of Π0 1 relations, called Σ0 1 and their complements, called Π0 1 , and so on. At level ω, one chooses a family of sets running through the lower levels, takes the limit, and begins again with the relations which are recursive relative to this limit. The projections of these are Σ0 ω, the complements of Σ0 ω relations are Π0 ω, etc. For other constructive limit ordinals α, the process is as for ω. A relation which is both Σ0 α and Π0 α is said to be ∆0 α. The arithmetical sets and relations are those at finite levels; i.e. ∆0 n for some finite n.
Terry Millar of the University of Wisconsin-Madison was a research student of Anil Nerode. He and Chris visited each other several times over a fourteen-year period. Although they collaborated on a number of topics that grew into subsequent papers or dissertations of their respective students, they only published one coauthored paper [1983b] together.
Vaught proved that no complete theory could have exactly two countable models up to isomorphism. Ehrenfeucht produced an example of a complete theory with exactly three countable models up to isomorphism. Complete theories with more than one but only finitely many countable models up to isomorphism are now called ‘Ehrenfeucht theories’. Lachlan and Morley answered a question of Nerode’s by showing that there exist decidable Ehrenfeucht theories with undecidable countable models. Millar later showed that the Turing degrees of such models in fact were unbounded in the hyperarithmetic hierarchy. However, all of the known examples at that time depended on producing models with finitely many elements whose behaviour was computably complex. Ash and Millar, in their [1983b], proved that for a broad class of arithmetic Ehrenfeucht theories, any model with computationally ‘simple’ (arithmetic) finite tuples of elements must be arithmetic.
In his [1984] with Rod Downey, who had been a research student at Monash, he considered the lattice of r.e. subspaces of a recursive vector space. A subspace is said to be decidable if we can determine dependence over it. Ash and Downey showed that every r.e. subspace is a direct sum of two decidable subspaces, so the theory of the partially-ordered set of decidable subspaces is undecidable. They also gave other results on the Turing degrees of r.e. subspaces.
[1990b] was written with C.G. Jockusch and J.F. Knight. The notion of ‘jump degree’ was due to Jockusch. The results here continue work in an earlier paper of Knight. Ash was intrigued by some ideas [1990b], although he felt that the proofs which Knight gave for certain results called for reworking. This paper led to [1990c] and [1991a] (see below).
In [1992b], Ash considered generalizations of ‘enumeration reducibility’, at arbitrary levels of the hyperarithmetical hierarchy. The paper involved an interesting kind of forcing, with conditions which, although finite, carry infinite information. This paper led to [1994f].
Chris Ash said that the way to find the ‘right’ proof of a given result was to generalize the result. Ash generalized repeatedly certain results of Goncharov and his own results with Nerode [1981a], until the generalizations grew into an elaborate programme of research in recursive model theory, including powerful new technology for nested priority constructions, the isolation of certain classes of infinitary formulae, and, for applications, the calculation of ‘back and forth’ relations for various kinds of structures.
The problems in the programme call for syntactical conditions to account for limitations on recursive complexity which persist in all recursive copies of a given structure. A structure is recursive if the satisfaction of atomic formulae is decidable. Ash’s programme grew from the three problems stated below:
Problem 1. Let A be a recursive structure, and let R be a further relation on A. When is there an isomorphism f from A onto a recursive B such that f(R) is not recursive? If there is no such f, i.e. if f(R) is always recursive in recursive copies, then R is said to be intrinsically recursive on A.
Problem 2. Let A be a recursive structure. When is there a recursive copy B with no recursive isomorphism from A onto B. If there is no such B, i.e. if for every recursive copy of A, there is a recursive isomorphism, then A is said to be recursively categorical.
Problem 3. Let A be a recursive structure. When is there an isomorphism f from A onto a recursive B such that f is not recursive? If every isomorphism from A onto a recursive structure is recursive, then A is said to be recursively stable. (This term had been used by Goncharov, although in model theory, stable structure usually refers to something quite different.)
There are variants of these problems. Problem 1 can be varied so that the aim is to produce a recursive copy B in which the image of R is not r.e., or Σ0 α , or to produce a copy B, not necessarily recursive, such that the image of R is not Σ0 α relative to B, and there are similar variants of Problems 2 and 3.
Ash’s paper with Nerode [1981a] concerns Problem 1, and the variant in which the aim is to make f(R) not r.e.. If R is definable by an infinitary formula ϕ(c,x) which is an r.e. disjunction of existential formulae, then the image of R is r.e. in all recursive copies. The converse holds provided a certain side condition holds on the one copy.
Problems 2 and 3 were first considered in the mid-1970s by Goncharov [G1], [G2]. Goncharov, Nurtazin and other members of a group at Novosibirsk, in the former USSR, had done considerable work in this area. Goncharov visited Ash and subsequently they wrote [1985b]. This concerns a variant of Problem 2 in which A is decidable (i.e., satisfaction of all formulae of the usual kind is decidable). The aim is to produce a decidable copy with no ∆0 2 isomorphism. There is no satisfying syntactical condition. The paper makes additions to the stock of pathological examples.
Ash’s [1986a] is about the variant of Problem 3 in which the aim is to make f not ∆0 n. The two papers [1986a] and [1986c] represent a tremendous advance. In both papers, the aim was to lift the results of Goncharov on Problem 3 to higher levels – finite in [1986a] and transfinite in [1986c]. These papers introduce, all at once, the most important notions and technology for carrying Ash’s programme to higher levels. First, there is a description of the class of recursive infinitary formulae. In recursive infinitary formulae, the infinite disjunctions and conjunctions are over r.e. sets (making this precise involves ordinal notation in an essential way). Considered all together, the recursive infinitary formulae have the same expressive power as the hyperarithmetical infinitary formulae, but this is a non-trivial theorem. The important feature of recursive infinitary formulae involves their classification as recursive Σα or Πα for various constructive ordinals α. In recursive structures, satisfaction of recursive Σα formulae is Σ0α and satisfaction of recursive Πα formulae is Π0α.
In addition to the recursive infinitary formulae, [1986a] and [1986c] contain an abstract formulation of the object of a ‘priority’ construction, and there are ‘metatheorems’ guaranteeing the success of the construction. The priority method was developed by Friedberg [Fr] and Muchnik [Mu] (independently) to solve a problem on r.e. sets. It is arguably the most important method for obtaining results in recursion theory. Ash applied the method extensively, and his deepest results are contributions to the method itself.
Thus, it seems important to try to describe the method. In a priority construction, the aim is to enumerate a set so as to satisfy a list of ‘requirements’. The information needed for the requirements may not be accessible in an effective way. The enumeration therefore proceeds based on systematic guessing. The strategies for meeting the separate requirements may come into conflict. When this happens, the conflict is resolved according to a system of priorities. Action on behalf of a given requirement typically results in injury to lower priority requirements.
The construction of Friedberg and Muchnik was a finite injury construction. In such a construction, each requirement is injured at most finitely many times, and with ∆0 2 information, it is possible to determine how the requirements are met. There are infinite injury constructions, where with D0 2 information it is possible to determine how the requirements are met. There are infinite injury constructions, where with ∆0 3 information it is possible to determine how the requirements are met. There are constructions involving information at still higher levels.
Harrington had described a ∆0 ω construction in terms of ‘workers’, in 1979, but only in handwritten notes, which Ash had not seen. Marker [Ma] and Knight [Kn], having seen Harrington’s notes, had tried using workers themselves. However, there was no ‘metatheorem’ before Ash.
Priority constructions can be extremely difficult to write out, to read, to check, and to vary. Harrington’s construction was a house of cards. With Ash’s metatheorem, where it applies, the proof is nice and modular. Ash said that before proving the metatheorem, he could not see how to proceed with the higher level version of Problem 3. Moreover, he had suggested to E. Barker, as a problem for his Master’s thesis, the higher level version of Problem 1 [B].
Having described the appropriate formulae, and developed the technology for the priority constructions, Ash obtained results of the kind he wanted. The results have some rather strong effectiveness hypotheses. In particular, in the given copy of the structure, certain ‘back-and-forth’ relations must be r.e. (uniformly). Ash calculated the back-and-forth relations for recursive well-orderings and showed how his results applied to these familiar structures.
The metatheorem from [1986c] was applied by Ash in [1987a], [1990c], [1990d] (slightly modified), [1991a] and [P1]. As planned, Barker used the metatheorem in his Master’s thesis (12), showing that, modulo some effectiveness conditions, R is intrinsically Σ0α on A if and only if it is definable in A by a recursive Σα. Later, Davey [D] used the metatheorem in his Master’s thesis, and two of Knight’s students, K. Hurlburt [Hu] and A. Vlach [V], used it in their PhD theses. Hurlburt was behind some minor corrections which Ash published.
In [1987a] Ash extended Goncharov’s result on Problem 2 to transfinite levels. He showed that his results applied to superatomic Boolean algebras. To do this, he calculated the back-and-forth relations for these structures.
The paper with J.F. Knight, M. Manasse and T. Slaman [1989] varies Problems 1, 2 and 3 by considering arbitrary copies of the given structure, instead of only recursive copies. The proofs use forcing. The results, with no side conditions, give evidence that the recursive infinitary formulae have all the expressive power needed for problems of this general kind. Manasse and Slaman had obtained some of the results before Ash and Knight, but had not published them. J. Chisholm obtained similar results independently [Ch].
In [1990c], with J.F. Knight, conditions are given on a pair of recursive structures A and B under which, for all sets Π0 α sets S, there is a uniformly recursive sequence of structures (Cn)n∈ω such that Cn is isomorphic to A if n∈ S and to B otherwise, and there are some other related results. J. Thurber [Th], in his PhD thesis, used results from the paper to re-work and extend results of L. Feiner [Fe] on Boolean algebras.
An r.e. quotient structure is the quotient of a recursive structure by an r.e. congruence relation. It is like a recursive structure, except that equality is not recursive, only r.e.. Love, in his Master’s thesis [Lo1], considered the variant of Problem 3 for such structures. In working with Love, Ash began thinking of structures in which various other relations were required to be r.e.. He realized that the metatheorem, as originally stated, did not apply. In [1990d], he discussed ‘r.e. structures’ and he modified the metatheorem so that it could be used in this context. There were other simplifications as well.
In [1990b], there was a generalization of a result of Watnik [W], saying that for all constructive ordinals α, Zα ⋅ A has a recursive copy if and only if A has a ∆02α copy. In [1991a] Ash returned to this, generalizing the result further and giving a better proof.
The paper [1992a], with J.F. Knight, considers the following variant of Problem 1. Let A be a recursive structure, and let ϕ(R) be a recursive Π2 sentence, true in an expansion of A, by a recursive relation R. Under what conditions is there a copy B with no relation R satisfying ϕ(R) and recursive relative to B?
Ted Slaman briefly visited Monash and subsequently Ash wrote his [1993], with J.F. Knight and T. Slaman. Slaman observed some uniformity in the proof of [1992a]. He and Ash isolated several related notions, and determined some of the implications between pairs of these notions. Knight made some minor contributions later, when the paper was being written up.
For a time, Ash enjoyed the belief that his metatheorem was completely general; that is, anything which could be done by a nested priority construction could be done using his metatheorem. He was able to prove Harrington’s [1979] result. However, there are problems – variants of the basic three – calling for priority constructions with special features which the original metatheorem could not handle. In [1994d] and [1994e], Ash and Knight developed variants of the metatheorem to solve some of these problems. In [1994e] there is a metatheorem for constructions with requirements at different levels. This can be applied to the variant of Problem 1 involving a family of relations Rn on A, where the aim is to produce a recursive copy in which, for all n, the image of Rn is not Σ0βn . In [1994d] there is a metatheorem for constructions in which sets are being enumerated at different levels. The syntactical conditions are related to those in [L], [1990d] and [Har]. They involve a new classification of recursive infinitary formulae. His [1994d], with J.F. Knight, contains an extension of the metatheorem for constructions with sets enumerated at different levels.
In [1994f], there is a result saying that the formulae isolated in [1994d] are the right ones – [1994f] bears the same relation to [1994d] as [1989] does to [B]. The proof is a forcing construction, using ideas from [1992b] as well as [1989].
At the time of his death, five of Ash’s papers had not appeared, although all had been accepted for publication. Three of these have now appeared. One of the papers [P5] is expository. Among the others, two [1997a], [19972b] were ready to submit when Ash died. The other two [1996], [P1] needed more work, although the results, joint with Knight, had been thought through.
V. Harizanov, a former student of Millar, showed that, in the setting of Problem 1, the conditions of [1981a] for producing a recursive copy of A in which the image of R is not recursive are not sufficient to give it arbitrary r.e. degree. She also found conditions for making the image of R r.e. of arbitrary r.e. degree [Har].
Let A be a recursive structure, and let R be a further relation on A, as in Problem 1, above. A set is simple if it is r.e. and the complement, while infinite, has no infinite r.e. subset. Hird, in his PhD thesis under Ash, gave conditions for making the image of R as simple as possible [Hir].
In [1997a], joint with Knight and Remmel, the aim was to give conditions for making the image of R simultaneously as simple as possible and of arbitrary non-zero r.e. degree. Simply combining the conditions of Harizanov and Hird does not work. Ash and Remmel had worked on the problem some years earlier, but had never published and had misplaced their notes. Ash and Knight started over.
Ershov defined a hierarchy of ∆0 2 sets, based on differences [E1], [E2], [E3]. For a ∆02 set X, there is a recursive ‘guessing’ function g(x,s) such that if x ∈ X, then for all sufficiently large s, g(x,s) = 1, and if x ∉ X, then for all sufficiently large s, g(x,s) = 0. If X is r.e., we can take g such that for each x, the value starts at 0 and changes at most once. For a 2-r.c., or n-r.e. set, the value changes at most twice, or n times. The definition extends through the constructive ordinals. For an α-r.e. set, an ordinal ≤ α accompanies each guess, and the ordinal decreases whenever the guess changes.
In [1996], joint with Knight, again the setting was as in Problem 1. The aim was to give conditions for making the image of R not 2-r.e., or not α-r.e.. In [1997b], joint with Cholak and Knight, the aim was to give conditions, for fixed α, guaranteeing that the image of R can be given arbitrary α-r.e. degree, or made α-r.e. and of arbitrary α- r.e. degree. In [1997b] it is also shown, using forcing, that if R can be given arbitrary ∆0 3 degree, then it can be given arbitrary degree.
In [1995], Ash and Knight showed that the most obvious conditions for lifting Harizanov’s results to arbitrary levels in the hyperarithmetical hierarchy fail. In [P1], joint with Knight, there are results related to this. It is shown that the conditions for making the image of R not ∆0 α are sufficient to give it arbitrary Σ0 α degree modulo ∆0 α, and the conditions for making the image of R Σ0 α and not ∆0 α are sufficient to make it Σ0 α of arbitrary Σ0 α degree modulo ∆0 α. There is a more general statement involving REA sequences, as in [1995]. In addition, the paper considers some model theoretic versions of the Friedberg-Muchnik Theorem. There are conditions on a recursive structure A and a pair of relations R and S, guaranteeing that there is a recursive copy in which the images of R and S are r.e. and independent, or Σ0 α and independent over ∆0 α.
The book [P6] which Ash had started was not meant to be jointly authored. It is entitled Computable Structures and the Hyperarithmetical Hierarchy. Ash had written parts of the first five chapters, and chapter titles for the rest. Knight is in the process of completing the book. It describes Ash’s programme and includes the background material from recursion theory and model theory (material on ordinal notations, infinitary formulae, etc.), necessary for a thorough understanding.
In contrast to his work on semigroups, where a long familiarity with a problem (The Rhodes type-II conjecture) ultimately led to a final successful assault, Ash’s work in logic is more of a continuous process. His deep study accompanied by a passion for elegance enabled him to tackle structures of richer complexity. His work used in [Mun] and his [1979b] took notions of model theory (homogeneous-universal models) and, by adding more structure, enabled him to solve outstanding problems in semigroup theory.
The study of ‘intrinsic’ complexity in mathematical structures, with Nerode’s encouragement at the outset, grew infinitely more complicated as Ash concentrated on it. Again, Ash’s elegance of presentation made complicated results manageable. His aerial view (his metatheorem of [1986c], in particular), opened up a land which previously had looked like an amorphous and virtually pathless swamp, and allowed its mapping and exploration.
The last few years of Chris Ash’s life displayed an ever-increasing productivity. Among semigroupists, his work is widely known and has found extensive application already. Ash’s primary research area was logic and by his own reckoning, his best and deepest results are in [1986c]. Ash’s work in computable structure theory is already admired by the handful of people who specialize in this sort of thing. However, there are signs of growing interest in computable structure theory among the broader community in recursion theory/ computability. The metatheorems are, as yet, understood by only a few people, but the fact that they have been used successfully by students from Monash and Notre Dame points to the possibility of further applications. Lerman and Lempp [L-L1], [L-L2], who in working on certain problems in pure recursion theory, began to develop their own framework for priority constructions, indicate that they used some of Ash’s ideas. The effects of Ash’s work will be felt for a long time to come.
[B] Barker, E.J., ‘Intrinsically Σ0 2 Relations’, MSc
Thesis, Monash University, 1985.
[B-S] Bell, J.L. and A.B. Slomson, Models and Ultraproducts: an Introduction, NorthHolland Publishing Co., 1969.
[Bi] Birkhoff, G., ‘On the structure of abstract algebras’, Proc. Camb. phil. Soc. 31 (1935),433–454.
[C-K] Chang, C.C. and H.J. Keisler, Model Theory, 3rd edition, North-Holland, 1989.
[Ch] Chisholm, J., ‘Effective model theory versus recursive model theory’, J. Symb. Logic 55 (1990), 1168–1191.
[Co] Cohen, P.J., Set Theory and the Continuum Hypothesis, Benjamin, 1966.
[D] Davey, K., ‘Inseparability in recursive copies’, Annals of Pure and Applied Logic 68 (1994), 1–52.
[Fe] Feiner, L., ‘Hierarchies of Boolean Algebras’, J. Symb. Logic 35 (1970), 365–373.
[Fr] Friedberg, R.M., ‘Two recursively enumerable sets of incomparable degrees of unsolvability’, Proc. Natl. Acad. Sci. USA 43 (1957), 236– 238.
[Gl] Glassmire, W.F., ‘There are 2ℵ0 countably categorical theories’, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 19 (1971), 185–190.
[Go1] Goncharov, S.S., ‘Autostability and computable families of constructivizations’, Algebra and Logic 14 (1975), 647–680 (Russian); 392–408 (English).
[Go2] Goncharov, S.S., ‘On the number of nonautoequivalent constructivizations’, Algebra and Logic 16 (1977), 257–282 (Russian), 169–185 (English).
[Gr] Grzegorczyk, A., ‘A kind of categoricity’, Colloq. Math. 9 (1962), 183–187.
[Hal] Hall, T.E., The partially ordered set of all J-classes of a finite semigroup. Semigroup Forum 6 (1973) 263–4 (MR 52 #14111)
[Har] Harizanov, V., ‘Some effects of Ash-Nerode and other decidability conditions on degree spectra’, Annals of Pure and Applied Logic 55 (1991), 51–65.
[He] Henckell, K., S.W. Margolis, J-E. Pin and J. Rhodes, ‘Ash’s type II theorems, pro-finite topology and Mal’cev products, Part I’, J. Algebra and Computation 1 (1991), 411–436.
[Hig] Higman, G., B.H. Neumann and H. Neumann, ‘Embedding theorems for groups’. J. London Math. Soc. 24 (1949), 247–254.
[Hir] Hird, G., ‘Recursive properties of relations on models’, Annals of Pure and Applied Logic 63 (1993), 241–269.
[Hu] Hurlburt, K., ‘Sufficiency conditions for theories with recursive models’, Annals of Pure and Applied Logic 55 (1992), 305–320.
[J] Jónsson, B., ‘Homogeneous universal relational systems’, Math. Scand 8 (1960), 137–142.
[Ka] Karp, C., Languages with Expressions of Infinite Length, North-Holland, 1964.
[Kl] Kleene, S.C., ‘On the forms of predicates in the theory of constructive ordinals (second paper), Amer. J. Math. 77, 405–428.
[Kn] Knight, J.F., ‘Effective construction of models’, Logic Colloquium ’84, ed. Paris, Wilkie and Wilmers. North-Holland, Amsterdam, 1986, 105–119.
[L-L1]Lempp, S. and S. Lerman, ‘Priority arguments using iterated trees of strategies’, Proc. of Recursion Theory Week, ed. AmbosSpies, Miller, Sacks. Springer-Verlag, 1990, 277–296.
[L-L2]Lempp, S. and M. Lerman, ‘A general framework for priority arguments’, Bulletin of Symb. Logic 1 (1995), 189–201.
[Lo1] Love, J.J., ‘Stability of R.E. Quotient Algebras’, Msc Thesis, Monash University,1991.
[Lo2] Love, J.J., ‘Stability among r.e. quotient algebras’, Annals of Pure and Applied Logic 59 (1993), 55–63.
[Ma] Marker, D., ‘Degrees of models of true arithmetic’, in Proc. of Herbrand Symposium, Logic Colloquium ‘81, ed. Stern. NorthHolland, 233–242.
[Md] Markwald, S.W., ‘Zur Theorie derkonstruktiven Wohlordnungen’, Math. Annalen 127, 135–149.
[Mem]In Memoriam Dr Christopher J Ash, FAA, 1945–1995. Tributes from friends and colleagues. Dept. of Mathematics Logic Paper, March 1995.
[Mo] Morley, M., ‘Categoricity in power’, Trans. Amer. Math. Soc. 114 (1965), 514–538.
[M-V] Morley, M. and R. Vaught, ‘Homogeneous universal models’, Math. Scand. 11 (1962),37–57.
[Mu] Muchnik, A.A., ‘On the unsolvability of the problem of reducibility in the theory of algorithms’, Dokl. Akad. Nauk SSSR, N.S.108 (1956), 194–197 (Russian).
[Mun]Munn,W.D., ‘Congruence-free inverse semigroups’. Quart. J. of Mathematics, Oxford (2) 25 (1974) 463–84 52 #14114)
[Ra] Rabin, M., ‘Decidability of second order theories and automata on infinite trees’, Trans. Amer. Math. Soc. 141 (1969), 1–35.
[Rh] Rhodes, J.L., Research problem 24. Semigroup Forum 5 (1972) 92.
[R-T] Rhodes, J. and B. Tilson, ‘An improved bound on complexity’. J. Pure and Applied Algebra 2 (1972), 13–71.
[Ro] Robinson, J., ‘Definability and decision problems in arithmetic’, J. Symb. Logic 14 (1949), 98–114.
[Ry] Ryll-Nardjewski, C., ‘On the categoricity in power À0’, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astron. Phys. 9 (1959), 545–548.
[Sa] Sacks, G., ‘The recursively enumerable degrees are dense’, Annals of Math. 30 (1964), 300–312.
[Se] Seidenberg, A., ‘A new decision method for elementary algebra’, Ann. of Math., ser. 2 60 (1954), 365–374.
[She] Shelah, S., ‘End extensions and numbers of countable models’, J. Symb. Logic 45 (1978), 550–562.
[Sho] Shoenfield, J., ‘Undecidable and creative theories’, Fund. Math. 49 (1961), 171–179.
[Ta] Tarski, A., A Decision Method for Elementary Algebra and Geometry, 2nd ed., revised 1951, iii+63 pp.
[Th] Thurber, J., ‘Recursive and r.e. quotient Boolean algebras’, Arch. Math. Logic 33 (1994), 121–129.
[Vl] Vlach, A., ‘Hyperarithmetical relations in expansions of recursive structures’, Annals of Pure and Applied Logic 66 (1994), 163–196.
[W] Watnik, R., ‘Constructive and recursive scattered order types’, in Logic Year, 1979–80 (Univ. of Conn.), ed. Lerman, Schmerl and Soare. Springer-Verlag, 1981, 312–326.
[1972]On countable n-valued Post algebras. Algebra Universalis, 2, 339–345.
[1972a]Some problems in mathematical logic. Doctoral dissertation, Oxford. v+113 pp.
[1972b]What is mathematical logic? (with C.J. Brickhill, J.N. Crossley, J.C. Stillwell,
N.H. Williams), (79 pp.) Oxford University Press, Oxford 1972. (Translated into Italian, Japanese, Spanish and Bulgarian.)
[1975a]Reduced powers and Boolean extensions. J. Lond. Math. Soc. 2, 9}, 429–432.
[1975b]A consequence of the axiom of choice. J. Aust. Math. Soc. (Ser. A), 19, 306–308.
[1975c] Inverse semigroups on graphs (with T.E. Hall). Semigroup Forum, 11, 140–145.
[1975d]Sentences with finite models. Zeit. f. math. Logik u. Grundl. d. Math., 21, 401–404.
[1977]Dense, uniform and densely sub-uniform chains. J. Aust. Math. Soc. (Ser. A), 23, 1–8.
[1979a]A uniform chain whose inverse semigroup has no chart. Semigroup Forum, 18, 1–4.
[1979b]Uniform labelled semilattices. J. Aust. Math. Soc. (Ser. A), 28, 385–397.
[1979c] The J-classes of an inverse semigroup. J. Aust. Math. Soc. (Ser. A), 28, 427–432.
[1980a]The lattice of ideals of a semigroup. Algebra Universalis, 10, 395–398.
[1980b]Some theories associated with algebraically closed fields (with J.W. Rosenthal), J. Symb. Logic, 45, 359–362.
[1980c] Embedding theorems using amalgamation bases. Proc. Semigroups Conference, Monash University, October 1979, Academic Press, New York, 167–176.
[1981a]Intrinsically recursive relations (with Anil Nerode), Proc. Conference on ‘Aspects of Effective Algebra’, Monash University, August
1979, U.D.A. Book Co., Steel’s Creek, Victoria, Australia, 26–41.
[1981b]Functorial properties of algebraic closure and Skolemization (with A. Nerode), J. Aust. Math. Soc. (Ser. A), 31, 136–141.
[1983a]Model-theoretic forms of the Axiom of Choice. South-East Asian Conference on Logic. Eds. C.T. Chong and M.J. Wicks, North-Holland, 1–12.
[1983b]Persistently finite, persistently arithmetic theories (with T.S. Millar), Proc. Amer. Math. Soc., 89, 487–492.
[1984]Decidable subspaces and recursively enumerable subspaces (with R. Downey). J. Symb. Logic, 49, 1137–1145.
[1985a]Pseudovarieties, generalized varieties, and similarly described classes. J. Algebra, 92, 104–115.
[1985b]Strong D0 2-categoricity (with S.S. Goncharov). Algebra i. Logika (Novosibirsk), 24, 718–727.(Also in the translation series Algebra and Logic, 1986, 471–477.)
[1986a]Stability of recursive structures in arithmetical degrees. Ann. Pure & App. Logic, 32, 113–135.
[1986b]Intersections of algebraically closed fields(with J.W. Rosenthal). Ann. Pure & App. Logic, 30, 103–119.
[1986c] Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Trans. Amer. Math. Soc., 298, 497–514.
[1987a]Categoricity of recursive structures in hyperarithmetical degrees. Ann. Pure & App. Logic, 34, 1–14.
[1987b]Finite semigroups with commuting idempotents. J. Aust. Math. Soc., 43, 81–90.
[1987c] Finite idempotent-commuting semigroups. Semigroups and their applications (Chico, California 1986), eds. S.M. Goberstein and P.M. Higgins, Reidel, 13–23.
[1989] Generic copies of countable structures (with J.F. Knight, M. Manasse, T. Slaman). Ann. Pure & App. Logic, 42, 195–205.
[1990a]On the varieties of languages associated with some varieties of finite monoids with commuting idempotents (with T.E. Hall and J.E. Pin). Information and Computation, 86, 32–42.
[1990b]Jump degrees of orderings (with C.G. Jockusch and J.F. Knight). Trans. Amer. Math. Soc., 319, 573–599.
[1990c] Pairs of recursive structures (with J.F. Knight). Ann. Pure & App. Logic, 46, 211–234.
[1990d]Labelling systems and r.e. structures. Ann. Pure & App. Logic, 47, 99–119.
[1990e] Inevitable sequences and a proof of the ‘type II Conjecture’. Monash Conference on Semigroup Theory in honour of G.B. Preston (Melbourne, 1990). World Scientific, River Edge, N.J., U.S.A., 31–42.
[1991a]A construction for recursive linear orderings. J. Symb. Logic, 56, 673–683.
[1991b]Inevitable graphs: A proof of the type II conjecture and some related decision procedures. Int. Journal of Algebra and Computation, 1, 127–146.
[1992a]Relatively recursive expansions (with J.F. Knight). Fund. Math., 140, 137–155.
[1992b]Generalizations of enumeration reducibility using recursive infinitary propositional sentences. Ann. Pure & App. Logic, 58, 173–184.
[1993] Relatively recursive expansions II (with J.F. Knight and T.A. Slaman). Fundamenta Mathematicae, 142, 147–161.
[1994a]A Conjecture Concerning the Spectrum of a Sentence. Math. Log. Quart., 40, 393–397.
[1994b]Recursive expansions (with J.F. Knight). Fundamenta Mathematicae, 145, 153–169.
[1994c] On countable fractions from an elementary class. J. Symb. Logic, 59, No. 4, 1410–1413.
[1994d]Ramified systems (with J.F. Knight). Ann. Pure & Appl. Logic, 70, 205–221.
[1994e] Mixed systems (with J.F. Knight). J. Symb. Logic}, 59, 1383–1399.
[1994f] A completeness theorem for certain classes of recursive infinitary formulae (with J.F. Knight). Math. Logic Quarterly, 40, 173–181.
[1995] Possible degrees in recursive copies (with J.F.Knight). Annals of Pure and Applied Logic, 75, 215–221.
[1996] Recursive structures and Ershov’s hierarchy (with J.F.Knight). Math. Logic Quarterly, 42, 461–468.
[1997a]Quasi-simple relations in copies of a given recursive structure (with J.F.Knight and J.B.Remmel). Annals of Pure and Applied Logic, 86, 203–218.
[1997b]Permitting, forcing, and copies of a given relation (with P. Cholak and J.F. Knight). Annals of Pure and Applied Logic, 86, 219–236.
[1996] Recursive structures and Ershov’s hierarchy (with J.F.Knight). Math. Logic Quarterly, 42, 461–468.
[P1] Possible degrees in recursive copies II (with J.F.Knight). To appear in Annals of Pure & Applied Logic.
[P2] Isomorphic recursive structures. To appear in volume on constructive mathematics, ed. by A.Nerode, J.B.Remmel & W.Marek.
[P3] Computable Structures and the Hyperarithmetical Hierarchy (with J.F. Knight), book in preparation.
This memoir was originally published in Historical Records of Australian Science, Vol.12, No.1, 1998. It was written by:
© 2024 Australian Academy of Science
