Understanding the nature and structure of proofs; Reverse Mathematics and Proof Theory. Prerequisites? Good introductory texts?

Question

I'm still studying maths at undergraduate level, but intend to continue exploring topics in pure maths after I have graduated, so am thinking already about what directions I'd like to persue now, (as I like to be several steps ahead of myself!)

One area which seems particularly interesting is 'reverse mathematics'. I'd be interested to learn what the prerequisites would be for understanding it. Presumably it is a part of logic, and is related in some way to proof theory? If say, I wanted to explore questions such as, 'are there a finite number of ways of proving something?', would this be the right direction to take? (In fact, is there already an answer to this question?)

Apologies if the above is a bit broad/vague. This is my first post, and I plan to add to it as I learn more!

Update 1: Can anyone recommend a good introductory text on reverse mathematics and/or proof theory?

Answer 1

You probably already know this, from the references you mentioned, but since you didn't explicitly list it, I'll say it here. The "bible" of reverse mathematics is Steve Simpson's book "Systems of Second-Order Arithmetic".

As for the relevant areas of logic, I'd say that recursion theory is (currently) more closely connected to reverse mathematics than proof theory is.

Finally, your question whether there are only a finite number of ways to prove something is an interesting one, but it presupposes that there is a clear and plausible definition of what it means for two proofs to be really different. If one views proofs as just being deductions in some formal system, then, as soon as you have one proof of a result, you can generate infinitely many more by inserting trivial and irrelevant steps, or by other silly reformulations of your original proof. For your question to be meaningful, one has to exclude such trivialities and ask how many genuinely different proofs there are for a given result. And it's not easy (maybe not even possible) to draw a clear line between genuinely different proofs and silly variations.

Answer 2

I have found some interesting theses and other texts on or featuring Reverse Mathematics:

Beyond the Arithmetic- featuring a section on reverse mathematics http://www.math.cornell.edu/~shore/theses/AntonioFriendlier.pdf (Wayback Machine)

Introduction to Reverse Mathematics http://www.math.harvard.edu/theses/senior/cobb/cobb.pdf (Wayback Machine)

Harvey Friedman's page- founder of reverse mathematics https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/

The Reverse Mathematics Zoo- an interesting collection of diagrams, organising various relations among reverse mathematics principles http://math.berkeley.edu/~damir/The_Zoo.html (Wayback Machine)

The Role of Reverse Mathematics http://www.math.psu.edu/simpson/papers/hilbert/node5.html (Wayback Machine)

Reverse Mathematics: the Playground of Logic - Gödel Lecture by Richard Shore http://www.math.cornell.edu/~shore/papers/pdf/RMGodelLect11rev.pdf (Wayback Machine)

Open Questions in Reverse Mathematics https://math.berkeley.edu/~antonio/papers/questionsRM.pdf

Answer 3

Historically, reverse math is very closely tied to ideas in proof theory, but as Andreas points out, over the last decade or so, the connection to recursion theory has been very strong. For the foundational ideas in the area (in Simpson's book, for instance, or many of Friedman's writings) proof theory is very relevant.

Probably the two main introductions to proof theory right now are:

1. Proofs and Types by Girard (available online)
2. Basic Proof Theory, by Troelstra and Schwichtenberg

(A note on the Troelstra and Schwichtenberg book: the book is harder than most textbooks to get through solo, because it's very detailed; looking through it solo requires more than the usual amount of work identifying for oneself what the big picture is.)

Finally, in regards to your question about whether a statement has only finitely many proofs: proof theory is definitely the right place to look for questions like that. As Andreas points out, it turns out that it's very hard to phrase questions like that coherently, because it's easy to modify a proof in a trivial way, but hard to define precisely what should constitute a trivial modification.

Answer 4

The Wikipedia article on reverse mathematics is pretty good, and the concept is easy enough to understand once you know some basic proof theory. The proof theory article is also good. I don't know if it's appropriate to name names, but an MO regular involved in the topic has heavily contributed to those Wikipedia articles and related ones.

Herbert Ruge Jervell's online book draft on proof theory is pretty accessible if you have had some exposure to logic. It's at: http://folk.uio.no/herman/bevisteori.ps (Wayback Machine)

H. Schwichtenberg's notes are maybe a little more advanced: http://www.mathematik.uni-muenchen.de/~schwicht/lectures/logic/ws03/ml.pdf

As others have said, the main reference on reverse math is Simpson's book. I haven't read it but he has a bunch of material on his web site that is informative. https://www.personal.psu.edu/t20/

You might like Harvey Friedman's site too. He has reversals of many innocent-looking theorems, whose requirements go all the way from weak fragments of PA up to consistency statements of the more abstruse large cardinals. https://u.osu.edu/friedman.8/

Answer 5

As for your question on prerequisites, the more logic you know the better. Of course the basic concepts---proofs, models, Peano arithmetic, incompleteness, compactness, nonstandard models, primitive recursion---really help to understand the program of reverse math. But also more advanced logic topics are useful. Computability theory and proof theory have already been mentioned. Knowing more about model theory helps, as does set theory (topics such as comprehension axioms, independence, descriptive set theory, and forcing offer insight into reverse mathematics).

Although having said that, after knowing the logical basics, it is quite possible to just jump into the subject and learn at least the main ideas of reverse mathematics. The first chapter of Subsystems of Second Order Arithmetic is available on Steve Simpson's website. It is a good (and long) introduction to the basics of reverse mathematics. (It also may help one decide if they want to purchase the whole book.)

Last, reverse mathematics connects logic to other areas of mathematics. To understand say that "$\mathsf{ACA}_0$ is equivalent over $\mathsf{RCA}_0$ to the the Bolzano Weierstrass theorem", it is helpful to know the Bolzano Weierstrass theorem and a proof of it. In that direction, having a standard undergraduate mathematics education---real analysis, abstract algebra, topology, etc.---goes a long way.