# Christopher John Ash 1945-1995

J.N. Crossley, J.F. Knight and G.B. Preston.

## Work in logic

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.

### 3.2 The main programme

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.)

## Conclusion

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.

## References

[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.

## Bibliography

[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.

## Preprints

[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.