views updated

# MODERN LOGIC: SINCE GÖDEL: FRIEDMAN AND REVERSE MATHEMATICS

During the second half of the twentieth century, many mathematicians lost interest in the foundations of mathematics. One of the reasons for this decline was an increasingly popular view that general set theory and Gödel-style incompleteness and independence results do not have much effect on mathematics as it is actually practiced. That is, as long as mathematicians study relatively concrete mathematical objects, they can avoid all foundational issues by appealing to a vague hybrid of philosophical positions including Platonism, formalism, and sometimes even social constructivism. Harvey Friedman (born 1948) has continually fought this trend, and in 1984 he received the National Science Foundation's Alan T. Waterman Award for his work on revitalizing the foundations of mathematics.

One of Friedman's methods of illustrating the importance of foundational issues is to isolate pieces of mathematics that either display the incompleteness phenomenon or require substantial set theoretic assumptions and which most mathematicians would agree fall within the scope of the central areas of mathematics. For example, he has created numerous algebraic and geometric systems that make no explicit reference to logic but which, under a suitable coding, contain a logical system to which Gödel's incompleteness theorems apply. Furthermore, these systems look similar to many systems used by mathematicians in their everyday work. Friedman uses these examples to argue that incompleteness cannot be dismissed as a phenomenon that occurs only in overly general foundational frameworks contrived by logicians and philosophers.

Friedman has also done a large amount of work concerning the necessary use of seemingly esoteric parts of Zermelo-Frankel set theory and its extensions. He has found theorems concerning concrete objects in mathematics that require the use of uncountably many iterations of the power set axiom and others that require the use of large cardinal axioms. These investigations have culminated in what Friedman calls Boolean relation theory.

In his 1974 address to the International Congress of Mathematicians, Friedman started the field of reverse mathematics by suggesting a three-step method for measuring the complexity of the set theoretic axioms required to prove any given theorem T. First, formalize the theorem T in some version of set theory. (Typically a formal system called second order arithmetic is used.) Second, find a collection of set theoretic axioms S which suffices to prove T. Third, prove the axioms in S from the theorem T (while working in a suitably weak base theory). If the third step is successful, then the equivalence between S and T shows that S is the weakest collection of axioms which suffices to prove T. If the third step fails, then the second step must be repeated until a proof of T is found using only axioms that can be proved from T. Because the third step involves proving axioms from theorems as opposed to the usual action of proving theorems from axioms, this type of analysis is now called reverse mathematics. It is frequently possible to draw a number of foundational conclusions concerning a theorem T once the equivalent collection S of set theoretic axioms has been isolated.

## Bibliography

Friedman, H. "Some Systems of Second Order Arithmetic and Their Use." Proceedings of the 1974 International Congress of Mathematicians, vol. 1, 235242. Montreal: Canadian Math Congress, 1975.

Harrington, L. A., M. D. Morley, A. Scedrov, and S. G. Simpson, eds. Harvey Friedman's Research on the Foundations of Mathematics. Studies in Logic and the Foundations of Mathematics, vol. 117. Amsterdam: North Holland Press, 1985.

Peter Cholak (2005)

Reed Solomon (2005)