Stephen Cole Kleene

Quick Info

5 January 1909
Hartford, Connecticut, USA
25 January 1994
Madison, Wisconsin, USA

Stephen C Kleene was an American mathematician and logician best known his work on recursion theory.


Stephen C Kleene's father was Gustav Adolph Kleene, a professor of economics at Trinity College, Hartford, Connecticut at the time of his son's birth. He remained there for the rest of his career. He retired, becoming professor emeritus, and died at his summer home in Union, Maine in August 1946. This home was on a farm in Maine which had belonged to his wife, inherited from her mother, Drucilla Cole. Both Gustav and his son Stephen considered this farm their 'real home.' Gustav wrote books such as The problem of medical charity (1904) and Profit and wages: A study in the distribution of income (1916). Stephen's mother was Alice Lena Cole who was a poet and writer of plays. Before marrying she published poems such as The lawsuit published in The Youth's Companion (1892), The dead bee published in The Century (1899), The lost spell published in Atlantic Monthly (1900) and Escape published in Atlantic Monthly (1900). After her marriage she published KIRSTIN; KIRSTIN. Play in Four Acts (1914) under her married name Alice Cole Kleene. It was described by a critic in the New York Times as a "pretty play with graceful lyrics."

Stephen Kleene studied for his first degree at Amherst College, Amherst, Massachusetts, being awarded his Bachelor's Degree summa cum laude in 1930. He then went to Princeton University where his doctoral studies were supervised by Alonso Church. It had been Oswald Veblen who had proposed that the development of logic required careful analysis by mathematicians. Church, one of Veblen's students, had been appointed to Princeton in 1929 and was making remarkable advances in this area. J Barkley Rosser was also a doctoral student of Church's at Princeton, arriving in 1933 while Kleene was there. It was certainly an exciting place to be undertaking research applying mathematical techniques to logic with visitors such as Kurt Gödel - Kleene attended a course he gave at the Institute for Advanced Study. Kleene received a doctorate from Princeton for his thesis entitled A Theory of Positive Integers in Formal Logic in 1934. He writes in the Introduction to his thesis:-
... we shall be concerned primarily with the development of the system of logic based on a set of postulates proposed by A Church. Our object is to demonstrate empirically that the system is adequate for the theory of positive integers, by exhibiting a construction of a significant portion of the theory within the system. By carrying out the construction on the basis of a certain subset of Church's formal axioms, we show that this portion at least of the theory of positive integers can be deduced from logic without the use of the notions of negation, class, and description.
After the award of his doctorate Kleene taught at Princeton until he joined the University of Wisconsin at Madison as an Instructor in 1935. He was promoted to Assistant Professor at Wisconsin in 1937 before leaving in 1941 (unhappy at his failure to be promoted) to become Assistant Professor back at Amherst College where he had studied for his first degree. In 1942 he married Nancy Elliot; they had four children, Paul, Kenneth, Bruce, and Pamela. Nancy Elliot was the daughter of George Roy Elliott, professor of English at Amherst College and a literary critic who specialized in Shakespeare. Also in 1942 Kleene left Amherst College to undertake war service with the US Navy as a navigation instructor at the Naval Reserve Midshipmen's School in New York. Later he was a project director at the Naval Research Laboratory in Washington DC. By the time he left the navy after the end of World War II, Kleene had risen to the rank of lieutenant commander.

He returned to the University of Wisconsin at Madison in 1946 as an associate professor being promoted to full professor two years later. In 1964 he was named Cyrus C Duffee Professor and continued to hold that chair until he retired in 1979. He served two terms as the Chair of the Department of Mathematics and one term as the Chair of the Department of Numerical Analysis (later renamed the Department of Computer Science). He also served as Dean of the College of Letters and Science in 1969-74. During his years at the University of Wisconsin he was thesis advisor to 13 Ph.D. students.

In 1970 Kleene's wife Nancy died. Eight years later he remarried Jeanne Steinmetz. He died of pneumonia aged 85.

Kleene's research was on the theory of algorithms and recursive function theory, an area which he created and retained an interest in throughout his life. He developed the field of recursion theory with Church, Gödel, Turing and others. He contributed to mathematical Intuitionism which had been founded by Brouwer. In particular he lectured on Recursive functions and intuitionistic mathematics at the International Congress of Mathematicians in Cambridge, Massachusetts, in 1950. In this lecture he spoke about how his interpretation of intuitionistic number theory by means of a "realization" might extend to intuitionistic set theory. He explored these ideas further in the book The foundations of intuitionistic mathematics, especially in relation to recursive functions (1965) written jointly with Richard Vesley. Chapters I, II, and IV of the book were written by Kleene while Chapter III is by Vesley. G Kreisel writes in a review:-
Chapter I is by far the best introduction to intuitionistic logic which is at present available for a mathematical logician.
Michael Dummett, a leading authority, was also greatly impressed:-
... chapter one of this book provides the first systematic exposition of the foundations of intuitionist analysis set out as an axiomatic system treating Brouwer's fan theorem, the bar theorem, and the continuity principle (called Brouwer's principle). In these respects, this was far superior to the earlier well-known axiomatization by Heyting.
Kleene's work on recursion theory helped to provide the foundations of theoretical computer science. By providing methods of determining which problems are soluble, Kleene's work led to the study of which functions can be computed. He spent the summer of 1951 at the RAND Corporation and discovered an important characterisation of finite automata. His RAND report on his work that summer has been very influential for theoretical computer science.

At a lecture in the University of Chicago in 1995, Robert Soare described Kleene's work in these terms:-
Kleene's formulation of computable function via six schemata is one of the most succinct and useful, and his previous work on lambda functions played a major role in supporting Church's Thesis that these classes coincide with the intuitively calculable functions.

From 1930's on Kleene more than any other mathematician developed the notions of computability and effective process in all their forms both abstract and concrete, both mathematical and philosophical. He tended to lay the foundations for an area and then move on to the next, as each successive one blossomed into a major research area in his wake.

Kleene developed a diverse array of topics in computability: the arithmetical hierarchy, degrees of computability, computable ordinals and hyperarithmetic theory, finite automata and regular sets with enormous consequences for computer science, computability on higher types, recursive realizability for intuitionistic arithmetic with consequences for philosphy and for program correctness in computer science.
Kleene's best known books are Introduction to Metamathematics (1952) and Mathematical Logic (1967). Kleene writes in the first of these:-
The aim of this book is to provide a connected introduction to the subjects of mathematical logic and recursive functions in particular, and to the newer foundational investigations in general.
J R Shoenfield, reviewing the second, writes:-
The growth of the undergraduate curriculum in mathematics has given rise to a number of texts treating serious mathematical results in a slower and more detailed manner than is customary in graduate texts. Since the number of such texts in the field of logic is quite small, this book by an outstanding authority in the field is especially welcome. ... The author clearly feels that a fairly thorough treatment of a few topics is preferable to a little bit of everything. ... Difficult proofs are broken down into a large number of simple cases; some of these cases are usually left to the reader. There are many illuminating examples; the author is usually more interested in giving enough examples to illustrate the important points of the proof than in giving complete details of the proof. Clarity and simplicity are never sacrificed for elegance. Historical notes and bibliographical references are frequent, but are not allowed to overshadow the mathematics.
Among the awards and honours that Kleene received for his outstanding contributions we mention the Leroy P Steele Prize which he was awarded by the American Mathematical Society in 1983:-
.. for three important papers which formed the basis for later developments in generalized recursion theory and descriptive set theory "Arithmetical predicates and function quantifiers", "On the forms of the predicates in the theory of constructive ordinals (second paper)", and "Hierarchies of number-theoretic predicates".
Perhaps his most prestigious award was the National Medal of Science presented by President Bush at a White House East Room Ceremony on 13 November 1990:-
For his leadership in the theory of recursion and effective computability and for developing it into a deep and broad field of mathematical research.
Other honours included election to the National Academy of Sciences (1969), election as President of the Association for Symbolic Logic (1956-58), president of the International Union of the History and the Philosophy of Science (1961) and of the Union's Division of Logic, Methodology and Philosophy of Science (1960-62). He was editor of the Journal of Symbolic Logic for twelve years.

In [3], Keisler describes Kleene's interests outside mathematics:-
Kleene had a strong interest in nature and the environment and visited his family farm in Maine almost every summer. He discovered a variety of butterfly Beloria Todde Ammiralis Ba Kleenei. He was an avid climber and, until well into his seventies, led the biannual logic picnic at Madison (now the Kleene Memorial Logic Picnic) on hikes up the cliffs at Devil's Lake. Steve Kleene's knowledge of mushrooms was legendary.
Mac Lane. in [5], recounts an experience climbing with Kleene:-
In 1949 he and I, about to attend a meeting at Dartmouth of the American Mathematical Society, got together on a project to climb all the peaks in the Presidential range, and we were joined by a third climber, a vacationing bellhop. Then, as we three stood finally on top of the last peak (Mount Madison), a thunderstorm struck. Kleene bounded down from the peak shouting, "Get down; it's lightning." I stepped down a bit, searched for our third companion only to find him flat on the ground, unconscious. Steve (quicker by way of his height) went down to the Madison Pass hut for help. When we got the injured man there we found that the lightning had singed his scalp and left a blister on his foot opposite a hobnail. We ferried him to a hospital, and I (complete with a burned-out seat of the pants) notified his employer at the elegant Eastern Slopes Inn. He later recovered. Steve and I continued to climb assorted mountains and Steve kept on rock climbing.
Keisler [3] also describes his personality:-
Although a private man, he was a skilful and enthusiastic teller of anecdotes. He possessed a powerful voice that always made it possible for others to know without seeing him whether he was in the maths building.

References (show)

  1. Biography in Encyclopaedia Britannica.
  2. A biographical sketch of Stephen C Kleene, The Kleene Symposium, Stud. Logic Foundations Math 101 (Amsterdam-New York, 1980), vii-ix.
  3. J E Keisler, Stephen Cole Kleene 1909-1994, Notices Amer. Math. Soc. 41 (1994), 792-793.
  4. S Mac Lane, Stephen Cole Kleene - a reminiscence, Dedicated to the late Stephen Cole Kleene, Ann. Pure Appl. Logic 81 (1996), 3-7.
  5. S Mac Lane, Stephen Cole Kleene, Biographical Memoirs National Academy of Sciences 75 (1998), 154-163.
  6. Ph.D students of Stephen C Kleene, The Kleene Symposium, Stud. Logic Foundations Math 101 (Amsterdam-New York, 1980), xvii.
  7. J R Shoenfield, The mathematical work of S C Kleene. Bull, Symbolic Logic 1 (1) (1995), 9-43.
  8. The bibliography of Stephen C Kleene, The Kleene Symposium, Stud. Logic Foundations Math 101 (Amsterdam-New York, 1980), xii-xvi.

Additional Resources (show)

Honours (show)

Cross-references (show)

Written by J J O'Connor and E F Robertson
Last Update December 2008