December 09, 2020
<Back to Index>
This page is sponsored by:
PAGE SPONSOR

Dana Stewart Scott (born October 11, 1932) is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. His research career has spanned computer science, mathematics and philosophy, and has been characterized by a marriage of a concern for elucidating fundamental concepts in the manner of informal rigor, with a cultivation of mathematically hard problems that bear on these concepts. His work on automata theory earned him the ACM Turing Award in 1976, while his collaborative work with Christopher Strachey in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has worked also on modal logic, topology and category theory. He is the editor - in - chief of the new journal Logical Methods in Computer Science.

He received his BA in Mathematics from the University of California, Berkeley, in 1954. He wrote his Ph.D. thesis on Convergent Sequences of Complete Theories under the supervision of Alonzo Church while at Princeton, and defended his thesis in 1958. Solomon Feferman (2005) writes of this period:

Scott began his studies in logic at Berkeley in the early 50s while still an undergraduate. His unusual abilities were soon recognized and he quickly moved on to graduate classes and seminars with Tarski and became part of the group that surrounded him, including me and Richard Montague; so it was at that time that we became friends. Scott was clearly in line to do a Ph. D. with Tarski, but they had a falling out for reasons explained in our biography. Upset by that, Scott left for Princeton where he finished with a Ph. D. under Alonzo Church. But it was not long before the relationship between them was mended to the point that Tarski could say to him, “I hope I can call you my student".

After completing his Ph.D. studies, he moved to the University of Chicago, working as an instructor there until 1960. In 1959, he published a joint paper with Michael O. Rabin, a colleague from Princeton, entitled Finite Automata and Their Decision Problem, which introduced the idea of nondeterministic machines to automata theory. This work led to the joint bestowal of the Turing Award on the two, for the introduction of this fundamental concept of computational complexity theory.

Scott took up a post as Assistant Professor of Mathematics, back at the University of California, Berkeley, and involved himself with classical issues in mathematical logic, especially set theory and Tarskian model theory.

During this period he started supervising Ph.D. students, such as James Halpern (Contributions to the Study of the Independence of the Axiom of Choice) and Edgar Lopez - Escobar (Infinitely Long Formulas with Countable Quantifier Degrees). Scott's work as research supervisor has been an important source of his intellectual influence.

Scott also began working on modal logic in this period, beginning a collaboration with John Lemmon, who moved to Claremont, California, in 1963. Scott was especially interested in Arthur Prior's approach to tense logic and the connection to the treatment of time in natural - language semantics, and began collaborating with Richard Montague, whom he had known from his days as an undergraduate at Berkeley. Later, Scott and Montague independently discovered an important generalization of Kripke semantics for modal and tense logic, called Scott - Montague semantics.

John Lemmon and Scott began work on a modal logic textbook that was interrupted by Lemmon's death in 1966. Scott circulated the incomplete monograph among colleagues, introducing a number of important techniques in the semantics of model theory, most importantly presenting a refinement of canonical model that became standard, and introducing the technique of constructing models through filtrations, both of which are core concepts in modern Kripke semantics. Scott eventually published the work as An Introduction to Modal Logic (Lemmon & Scott, 1977).

Following an initial observation of Robert Solovay, Scott formulated the concept of Boolean - valued model, as Solovay and Petr Vopěnka did likewise at around the same time. In 1967 Scott published a paper, A Proof of the Independence of the Continuum Hypothesis, in which he used Boolean - valued models to provide an alternate analysis of the independence of the continuum hypothesis to that provided by Paul Cohen. This work led to the award of the Leroy P. Steele Prize in 1972.

Scott took up a post as Professor of Mathematical Logic on the Philosophy faculty of Oxford University in 1972.

This period saw Scott working closely with Christopher Strachey, and the two managed, despite intense administrative pressures, to oversee a great deal of fundamental work on providing a mathematical foundation for the semantics of programming languages, the work for which Scott is best known. Together, their work constitutes the Scott - Strachey approach to denotational semantics; it constitutes one of the most influential pieces of work in theoretical computer science and can perhaps be regarded as founding one of the major schools of computer science. One of Scott's largest contributions is his formulation of domain theory, allowing programs involving recursive functions and looping - control constructs to be given a denotational semantics. Additionally, he provided a foundation for the understanding of infinitary and continuous information through domain theory and his theory of information systems.

Scott's work of this period led to the bestowal of:

  • The 1990 Harold Pender Award for his application of concepts from logic and algebra to the development of mathematical semantics of programming languages;
  • The 1997 Rolf Schock Prize in logic and philosophy from the Royal Swedish Academy of Sciences for his conceptually oriented logical works, especially the creation of domain theory, which has made it possible to extend Tarski's semantical paradigm to programming languages as well as to construct models of Curry's combinatory logic and Church's calculus of lambda conversion; and
  • The 2001 Bolzano Prize for Merit in the Mathematical Sciences by the Czech Academy of Sciences.
  • The 2007 EATCS Award for his contribution to theoretical computer science.
At Carnegie Mellon University, Scott proposed the theory of equilogical spaces as a successor theory to domain theory; among its many advantages, the category of equilogical spaces is a cartesian closed category, whereas the category of domains is not. In 1994, he was inducted as a Fellow of the Association for Computing Machinery.


Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo – Fraenkel set theory, the most widely accepted axiomatization of set theory.

Cohen was born in Long Branch, New Jersey, into a Jewish family that had immigrated to the U.S. from Poland. He graduated in 1950 from Stuyvesant High School in New York City.

Cohen next studied at the Brooklyn College from 1950 to 1953, but he left before earning his bachelor's degree when he learned that he could start his graduate studies at the University of Chicago with just two years of college. At Chicago, Cohen completed his master's degree in mathematics in 1954 and his Doctor of Philosophy degree in 1958, under supervision of the Professor of Mathematics, Antoni Zygmund. The subject of his doctoral thesis was Topics in the Theory of Uniqueness of Trigonometric Series.

Cohen is noted for developing a mathematical technique called forcing, which he used to prove that neither the continuum hypothesis (CH), nor the axiom of choice, can be proved from the standard Zermelo – Fraenkel axioms (ZF) of set theory. In conjunction with the earlier work of Gödel, this showed that both of these statements are logically independent of the ZF axioms: these statements can be neither proved nor disproved from these axioms. In this sense, the continuum hypothesis is undecidable, and it is probably the most widely known example of a natural statement that is independent from the standard ZF axioms of set theory.

For his result on the continuum hypothesis, Cohen won the Fields Medal in mathematics in 1966, and also the National Medal of Science in 1967. The Fields Medal that Cohen won continues to be the only Fields Medal to be awarded for a work in mathematical logic.

Apart from his work in set theory, Cohen also made many valuable contributions to Analysis. He was awarded the Bôcher Memorial Prize in mathematical analysis in 1964 for his paper "On a conjecture by Littlewood and idempotent measures", and lends his name to the Cohen - Hewitt factorization theorem.

Cohen was a professor at Stanford University, where he supervised Peter Sarnak's graduate research, among those of other students.

Angus MacIntyre of the University of London stated about Cohen: "He was dauntingly clever, and one would have had to be naďve or exceptionally altruistic to put one's 'hardest problem' to the Paul I knew in the '60s." He went on to compare Cohen to Kurt Gödel, saying: "Nothing more dramatic than their work has happened in the history of the subject." Gödel himself wrote a letter to Cohen in 1963, a draft of which stated, "Let me repeat that it is really a delight to read your proof of the ind[ependence] of the cont[inuum] hyp[othesis]. I think that in all essential respects you have given the best possible proof & this does not happen frequently. Reading your proof had a similarly pleasant effect on me as seeing a really good play."

While studying the continuum hypothesis, Cohen is quoted as saying that he "had the feeling that people thought the problem was hopeless, since there was no new way of constructing models of set theory. Indeed," he said in an interview in 1985, "they thought you had to be slightly crazy even to think about the problem."

"A point of view which the author [Cohen] feels may eventually come to be accepted is that CH is obviously false. The main reason one accepts the axiom of infinity is probably that we feel it absurd to think that the process of adding only one set at a time can exhaust the entire universe. Similarly with the higher axioms of infinity. Now \aleph_1 is the cardinality of the set of countable ordinals, and this is merely a special and the simplest way of generating a higher cardinal. The set C [the continuum] is, in contrast, generated by a totally new and more powerful principle, namely the power set axiom. It is unreasonable to expect that any description of a larger cardinal which attempts to build up that cardinal from ideas deriving from the replacement axiom can ever reach C.

Thus C is greater than \aleph_n, \aleph_\omega, \aleph_a, where a = \aleph_\omega, etc. This point of view regards C as an incredibly rich set given to us by one bold new axiom, which can never be approached by any piecemeal process of construction. Perhaps later generations will see the problem more clearly and express themselves more eloquently."

An "enduring and powerful product" of Cohen's work on the Continuum Hypothesis, and one that has been used by "countless mathematicians" is known as forcing, and it is used to construct mathematical models to test a given hypothesis for truth or falsehood.

Shortly before his death, Cohen gave a lecture describing his solution to problem of the Continuum Hypothesis at the Gödel centennial conference, in Vienna 2006. A video of this lecture is now available online.