What is the meaning/purpose of finding the "foundations of mathematics"?

Question

I've read in a lot of places how there was a "foundational crisis" in defining the "foundations of mathematics" in the 20th century. Now, I understand that mathematics was very different then, I suppose the ideas of Church, Godel, and Turing were either in their infancy, or not well-known, but I still hear this kind of language a lot today, and I don't know why.

From my perspective, mathematics is essentially the study of any kind of formal system understandable by an intelligent, yet finite being. By definition then, the only reasonable "foundation for all of mathematics" must be a Turing complete language, and the choice of what specific language is basically arbitrary (except for concerns of elegance). The idea of creating a finite set of axioms that describes "all of mathematics" seems fruitless to me, unless what is being described is a Turing complete system.

Is this idea of finding a foundation for all of "mathematics" still prominent today? I suppose I can understand why this line of reasoning was once prominent, but I don't see why it is relevant today. Is the continuum hypothesis true? Well, do you want it to be?

Answer 1

The question is broad, so I'll just try to address one of the sub-questions. I'll change it a little bit to allow for the possibility of pluralism:

What is the meaning of finding a "foundation of mathematics”?

As an example, I'll try to explain why set theory is a foundation of mathematics, and what it means for it to be one. This isn't intended to exclude other possible foundations, although they tend to be subsumed by set theory in a sense discussed below.

Based on one of the OP's comments above, I'll treat the mention of computability in the question figuratively rather than literally. Roughly speaking, a Turing-complete system of computation is one that can simulate any Turing machine, and so by the Church–Turing thesis, can simulate any other (realistic) system of computation. Therefore a Turing-complete system of computation can be taken as a "foundation" for computation.

As far as this question is concerned, I think that under the appropriate analogy between computation and mathematical logic, the notion of simulation of one computation by another corresponds to the notion of interpretation of one theory in another. By an interpretation of a theory $T_1$ in a theory $T_2$ I mean an effective translation procedure which, given a statement $\varphi_1$ in the language of $T_1$, produces a corresponding statement $\varphi_2$ in the language of $T_2$ such that $\varphi_1$ is a theorem of $T_1$ if and only if $\varphi_2$ is a theorem of $T_2$. So a mathematician working in the theory $T_1$ is essentially (modulo this translation procedure) working in some "part" of the theory $T_2$.

In these terms, a foundation of mathematics could be reasonably described as a (consistent) mathematical theory that can interpret every other (consistent) mathematical theory. However, it follows from the incompleteness theorems that no such "universal" theory can exist. But remarkably, the set theory $\mathsf{ZFC}$ can interpret almost all of "ordinary" (non-set-theoretic) mathematics. For example, if I'm working in analysis and I prove some theorem about continuous functions, then my theorem and its proof can in principle be translated into a theorem of $\mathsf{ZFC}$ and its proof in $\mathsf{ZFC}$. (Under this translation, a continuous function is a set of ordered pairs, which are themselves sets of sets, satisfying a certain set-theoretic property, etc.)

This means that set theory can serve as a foundation for most of mathematics. For set theory itself, no one theory (e.g. $\mathsf{ZFC}$) can serve as a universal foundation. But we can informally define a hierarchy of set theories ($\mathsf{ZFC}$, $\mathsf{ZFC} + {}$"there is an inaccessible cardinal", $\mathsf{ZFC} + {}$"there is a measurable cardinal", etc.) called the large cardinal hierarchy, strictly increasing in interpretability strength, which seems to be practically universal in the sense that every "natural" mathematical theory, set-theoretic or otherwise, can be interpreted in one of these theories. (The reason this doesn't violate the incompleteness theorem is that the large cardinal hierarchy is defined informally in an open-ended way, so we can't just take its union and get a universal theory.)

Your last point about the continuum hypothesis raises an important question: what if the various candidate set theories branch off in many different directions rather than lining up in a neat hierarchy? Well, it turns out so far that the natural theories we consider do line up in the interpretability hierarchy, even if they do not line up in the stronger sense of inclusion. For example, the methods of inner models and of forcing used to prove the independence of $\mathsf{CH}$ from $\mathsf{ZFC}$ also give interpretations of the two candidate extensions $\mathsf{ZFC} + \mathsf{CH}$ and $\mathsf{ZFC} + \neg \mathsf{CH}$ by one other (and by $\mathsf{ZFC}$ itself,) showing that they inhabit the same place in the interpretability hierarchy. If you believe $\mathsf{CH}$ and I believe $\neg\mathsf{CH}$ we can still interpret each others results, rather than dismissing them as meaningless.

Answer 2

Mathematics is a science of discovery. It's domain is The Mathematical Principle a peculiar entity or feature of the universe we inhabit; one might formulate the principle as follows:

Given a string of symbols and well defined symbolic transformations, applying a well specified series of transformations to the initial string always yields the same result.

All mathematics is symbol manipulation (usually we prefer to work in syntax trees, but there is an isomorphism between syntax trees and strings.) We usually start by designating a number of strings as starting points (axioms) and a number of transformations (inference rules), and then we add the rule that any derivable string is a valid starting point too (theorems.)

Now, by this very general definition includes weird systems such as the MIU system by Douglas Hofstadter. Usually we are a bit more refined.

In the more refined form we use a stratified syntax of objects and statements, with functions mapping objects to objects, predicates or relations mapping objects to statements, and logical connectives mapping statements to statements.

The most common inference rule in this system is modus ponnens in the logic, and it turns out most interesting things can be derived from that.

The question is now what objects to use and how to gain objects to use. The usual way to gain objects is using quantifiers, the universal and existential are common, and most quantifiers can be reduced to these two.

Now, what objects do we use? It is all well and fined to write down a lot of formulae in first-order logic, but we need to actually make them do something, and this is where the foundational crisis comes in.

Because they just plain didn't know what to do here. If you pick up Russel & co.'s Principia Mathematica, you'll find a lot of outdated ideas, because the modern techniques just plain weren't invented back then.

What ideas? The purely set-theoretic ordered pair. Principia uses several dozen pages on duplicating all the set axioms but for relations. Only in 1914 did Norbert Wiener come up with {{a,{}},{b}} for ordered pairs and only in 1921 Kazimierz Kuratowski came up with {{a,b},{b}} using the axiom of pairing.

Really it was Zermelo & Frankelen and Gödel who made the day with the eponymous ZF and Completeness Theorems solidifying the basis for First Order logic. This was as late as 1920's. We have only had well-founded mathematics for eight decades!

The whole deal comes down to Model Theory, which studies the interplay of a universe of elements and a first-order syntax (composed of the two quantifiers, a logic, equality and some relations and predicates, some constants, and some functions.)

The power of ZF comes from it's ability to quote formulas and prove their validity for specific sets. Using this we can quote each single axiom of Peano Arithmetic and prove it is true for the Von Neumann set-theoretic naturals; and suddenly Peano Arithmetic has a model. ZF is incredibly powerful because like this, it contains almost every theory, and many nice properties can be proven of theories and universes in general.