In which order should I learn the foundations of mathematics?

Question

I know from Wikipedia that those are the four pillars of the foundations of mathematics:

Proof theory
Aximatic Set theory
Model Theory
Recursion Theory

and I want to learn all of them, the problem is that I don't know whether the order matters (which one should I start with) or not, or what is the best order.

and what are the prerequisites to learn them.

the same questions for Category theory

Answer 1

Well, naive set theory is really the foundation of all others. I would say studying model theory before Axiomatic set theory, recursion theory and proof theory makes sense, although I don't know much about recursion theory and proof theory.

Answer 2

I do not know much about recursion theory and proof theory, but our professor specializing in foundations treats them as graduate topics, whereas he offers courses in axiomatic set theory and logic at an advanced undergraduate level. Speaking of logic: I think some study of first order logic is essential if you want to study foundations. Thus I think first study axiomatic set theory and some first order logic. The study of models actually stems from the study of logic. I definitely wouldn't advise studying model theory without some understanding of the theory of logic.

Answer 3

My recommendation:

First learn Boolean Arithmetic. Be able to solve any problem in boolean arithmetic, including

• making truth tables
• converting to and from DNF/CNF,
• kargnaugh maps

Second, learn one of the first order logics (FOL). There are a few to choose from, fitch style would be fine or something like that. Be able to prove some basic predicate logic theorems in a FOL. Study peano arithmetic, be able to solve basic natural number arithmetic problems in the FOL you chose using Peano's axioms.

Third, learn lambda calculus. This includes $\alpha$, $\beta$, and $\eta$ transforms. There actually isn't a whole lot to it. Optionally you could look at the consistency theorem of lambda calculus. At least be able to understand the encoding of natural numbers and boolean true/false values in lambda calculus, and be able to do basic computations using those.

Next, optionally, it probably would be well rounded to learn a little about combinator theory. Combinator theory is the father of lambda calculus and the sire of all of constructive logic. There is no real reason to go in depth into it, just get a general idea of what combinators are and how to convert between combinator representation and lambda representation. It is totally optional though.

Now you have a bit of a choice depending on your goals. If you want to study logic for the sake of real/complex analysis, then you should familiarize yourself with the axioms and reasoning of ZFC. ZFC are first order logic axioms, together with your first order logic you'll properly be able (theoretically) to prove any theorem of mathematics outside of the study of logic itself. You could even do this after learning FOL.

Alternatively, or as well, if you plan on using logic with software then you should learn a typed lambda calculus. Typed lambda calculus is more or less the basis of current formal logic. This will actually bring you full circle around to FOL, since the axioms of constructive FOL are really just consequences of type theory without mentioning the underlying lambda theory. If you already know a programming language like Haskell, then something like Martin-Lof theory may be accessible to you.

There are a whole lot of things I didn't mention though. Model theory, category theory, and computability (recursion) theory are a few. I (this is probably a minority opinion) consider them much less important than what I mentioned above.

Good luck~