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?

  • $\begingroup$ I think we have (at least) three issues in place here : (i) the historical "event" regarding the foundational crisis: see Foundations of mathematics during end XIX-beginning XX centuries. Very interesting, a lot of good books about it worth to be studied. (ii) the philosophical issue regarding : do we need a "secure" basis for our mathematical/scientific knowledge ? A deep issue regarding Philosophy of Mathematics. (iii) A "conceptual frameworek" to be used ... 1/2 $\endgroup$ Jul 2 '14 at 16:06
  • $\begingroup$ ... to organize (almost all) existing mathematical knowledge around some "basic" concepts/language/principles : we have set theory, category theory, others. Computability theory is a very important field of study and research, but I do not think that it can "colelct" all of math. $\endgroup$ Jul 2 '14 at 16:09
  • 3
    $\begingroup$ You can define a system for dealing with set theory, category theory, logic, and anything else you can think of with a Turing complete language. How can it not "collect" (sic?) all math? If there exists some aspect of mathematics that is not Turing complete in some sense, and humans can still understand it, then humans posses some sort of hyper-Turing computational ability. That may be true, but I don't know of any evidence to support it. $\endgroup$ Jul 2 '14 at 16:16
  • 1
    $\begingroup$ Regarding your last comment, it seems to me that understanding things and computing them are two different things. For example, we can understand the halting set even though it is not computable. Granted, a mathematician's way of understanding it involves proving things about it, and mathematical proof can itself be formalized in terms of computations, but this just means that the words "in some sense" in your comment are too vague. $\endgroup$ Jul 2 '14 at 18:01
  • $\begingroup$ Also, what is the purpose of the last two sentences in your question about the continuum hypothesis? That could be (and has been) its own question on this site. I think you need to focus your question more if you want a useful answer. $\endgroup$ Jul 2 '14 at 18:03

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.

  • $\begingroup$ Could you say that an interpretation is an isomorphism between theories than? $\endgroup$ Jul 2 '14 at 19:47
  • 1
    $\begingroup$ @Sintrastes More like an embedding, because it only goes one way. (And even if there are embeddings going both ways, in which case we say the theories are bi-interpretable, it's not clear to me whether this implies that there is an isomorphism; I'd guess not.) $\endgroup$ Jul 2 '14 at 19:52
  • 3
    $\begingroup$ (There are several notion of "interpretability in both directions", the obvious one is "mutual interpretability" in the literature. The one that one could think of as isomorphism in an appropriate category is "bi-interpretability". This is strictly stronger than mutual interpretability. A good reference for this is A. Visser, Categories of theories and interpretations, in Logic in Tehran, Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 284–341.) $\endgroup$ Jul 2 '14 at 20:59
  • $\begingroup$ @Andres Right, I should have written "mutually interpretable" above. That reference looks interesting, thanks. $\endgroup$ Jul 2 '14 at 21:14
  • 1
    $\begingroup$ @TrevorWilson It is the current standard reference in the area. As set theorist we are mainly interested in mutual interpretability. But the different flavors are useful when working on arithmetic and its fragments. Ali Enayat, by the way, has recently shown that for us, mutual interpretability cannot be replaced with bi-interpretability. He has a draft (Some interpretability results concerning $\mathsf{ZF}$) that does not appear to be available from his page, but I suspect he'll share it with you if you email him. $\endgroup$ Jul 2 '14 at 21:25

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.

  • $\begingroup$ Couldn't one use category theory for describing how objects do things instead of first order logic or set theory? I suppose that's just an "alternate" basis for mathematics. $\endgroup$ Jul 2 '14 at 18:24
  • $\begingroup$ Category Theory isn't exempt from first order logic, think for instance of the definition of an identity morphism, which might go a little something like this: "given arbitrary objects $X, Y, Z$ and morphisms $f : X \to Y, g : Y \to Z$ the identity morphism on $Y$, $id_y$ has the properties $f \circ id_Y = f, id_Y \circ g = g$." Here we see the statement "given arbitrary..." which is in fact the universal quantifier. Formulating the rest with the standard logical connectors should be easy enough. Category theory is first order logic! $\endgroup$ Jul 9 '14 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.