An alternate title for these notes could have been Foundations of Mathematics, but mathematics doesn’t really have a single foundational theory. We need a mix of logic, formal linguistics and computability. None of these can really be understood without the others. Logic has to be expressed in a formal language and the question of whether we can test the validity of statements in this language is one of computability. Formal linguistics is useless if languages can’t be parsed and presents difficulties of interpretation if they are ambiguous. These are computational questions and their analysis requires some form of logical analysis. Similarly the theory of computation is, as we just saw, closely intertwined with linguistic and logical questions.
It’s not just that logic, languages and computability are each dependent on the others. To some extent they are the same subject. The theory of finite state automata, for example, isn’t just related to the theory of regular languages; they are the same theory.
In addition to the complications just discussed, there is not not just one version of most of these theories. Different authors use different definitions. Some of these differences are merely annoying, like the different definitions of “countable” for sets, but don’t change the content of the theories. Some differences reflect the tension between making it easy to reason within the system and making it easy to reason about the system. Some, like the various axiom schemes for set theory, result from fundamental disagreements about what is true. There are more of these disagreements than I’ve had space to address in these notes. For example, even in zeroeth order logic there are adherents of classical logic, which is the version I’ve presented here, but also of intuitionist logic and minimal logic.
The main purpose of studying the foundations of mathematics is therefore not to find an agreed formal system which we can all use to make sure that everything is guaranteed to be correct. The main thing we gain from studying these formal systems is a better understanding of informal reasoning, which is what mathematicians spend almost all of our time doing. If we can, for example, set out precise rules for substitution then we can identify and avoid improper substitutions in informal arguments, and also be more confident in correct uses. Similarly, an understanding of formal languages is useful in understanding and creating mathematical notation. Informal mathematical language is rarely unambiguous, but it’s important to understand the ambiguities which do exist and to try not to create more of them.