What is mathematical logic?

What does mathematical logic mean?

In the book Analysis 1 by Terence Tao, it says:

The purpose of this appendix is to give a quick introduction to mathematical logic, which is the language one uses to conduct rigourous mathematical proofs.

Checking Wikipedia:

Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory.

This seems like a completely different definition. Why, for example, is set theory considered part of logic?

• "Why, for example, is set theory considered part of logic?" Why would it not be, when it was one of the initial areas of logic in the 20th century? When people don't treat set theory as part of logic, it seems to me a little like a young person disavowing their heritage because they're embarrassed by their parents. – Carl Mummert Nov 1 '16 at 0:22
• @CarlMummert I do not think of set theory as part of logic. It has nothing to do with embarrasment. – Andrés E. Caicedo Nov 1 '16 at 3:30
• A mathematical definition of logic can only be tautologic, right ? – reuns Nov 1 '16 at 5:58
• I would say, besides the fact that since the times of Bourbaki basically every entity in math is a set or can be viewed as one, proofs themselves are quite inherently set concepts, being formulated using quantifiers over some universe. – The Vee Nov 1 '16 at 11:04
• Terence Tao's $31$ page appendix is really a description of the basic language and tools of mathematical proof to help understand the rest of the Analysis I book, rather than the deeper subject of mathematical logic. The sections are called: Mathematical statements; Implication; The structure of proofs; Variables and quantifiers; Nested quantifiers; Some examples of proofs and quantifiers; Equality. – Henry Nov 1 '16 at 11:25

Logic is generally understood to be the study of sound reasoning. Mathematical logic in the sense Tao uses this word is the kind of logic one uses when doing mathematics. This includes dealing with logical connectives (such as "and", "or", "if", and "if and only if"), quantifiers ("for all" and "exists"), variables, and proofs.

But, as it sometimes happens in natural languages, one and the same word can have two (or more) different (though sometimes related) meanings. This might be the cause of your confusion. In fact, mathematical logic can also mean the branch of mathematics that deals with formulae, theories, proofs, models, … as mathematical objects. Of course, as all other branches of mathematics do, this branch of mathematics also uses mathematical logic in the former sense.

The reason why some people regard set theory as a subfield of mathematical logic$^*$ in the latter sense is that these fields are historically quite related. You may be interested to learn about the foundational crisis. I found a talk given by mathematician Chaitin that gives a good overview over this topic: see Part 1, Part 2, Part 3, Part 4.

By the way, the appendix on logic is included in the sample chapters of Tao's book.

$^*$ But at the end of the day this is just a termininological convention.

EDIT: This answer is just a restatement of Henry's comment:

Terence Tao's 31 page appendix is really a description of the basic language and tools of mathematical proof to help understand the rest of the Analysis I book, rather than the deeper subject of mathematical logic. The sections are called: Mathematical statements; Implication; The structure of proofs; Variables and quantifiers; Nested quantifiers; Some examples of proofs and quantifiers; Equality.

Mathematical logic is a strange beast.

It is a perfectly ordinary branch of mathematics whose goal is ... to study mathematics itself.

Thus, the different branches of mathematical logic are devoted to the study of some basic building blocks of mathematical practice : language, model, proof, computation.

• Kind of like the meta to stackexchange ? :) – nl-x Nov 1 '16 at 12:52
• @nl-x - Maybe rather like working in stackexchange source code would be in relation to the Stack Overflow. Meta is more like (philosophical) logic, with the main site traffic being analyzed without a strict formalism. – Jirka Hanika Nov 1 '16 at 14:39
• -1: I think this does not help the OP, because the cause of his confusion is the fact that the term mathematical logic has two different meanings. Describing only one of these meanings is misleading. – user377104 Nov 1 '16 at 17:26

The names and scopes of areas of mathematics are not always crisply delineated. In this case set theory is a bit of a grey area. There's an argument for considering it part of the broader subject of mathematical logic, but there are many set theorists who wouldn't consider themselves logicians.

Likewise, whether recursion theory is part of logic or computer science depends on who you ask.

That being said, the two descriptions are not in conflict. The four subfields that Wikipedia lists are all ingredients of the study of "what a rigorous proof is" and what rigorous proofs can and can't achieve.

Proof theory and model theory are both unquestionably part of logic.

Set theory is part of the common language of mathematical proofs -- it is used as a general way to speak about the things of actual interest in whatever your field is. Figuring out the appropriate rules for how set theory can be used therefore (arguably!) belongs as part of the study of common features of mathematical proofs in general.

Recursion theory is the study of mechanical computation, and is -- in addition to being the foundation for computer science -- an important technical tool for proving famous results of proof theory, such as Gödel's incompleteness theorem.

• I don't know anyone who thinks recursion theory is part of number theory . . . – Noah Schweber Oct 31 '16 at 21:40
• I think recursion theory is part of recursion theory. – Monty Harder Oct 31 '16 at 22:15
• @NoahSchweber: Hmm, I thought I'd seen it called "formal number theory", but that seems to be misremembered. – hmakholm left over Monica Oct 31 '16 at 22:18
• @Noah Schweber: for the purposes of selling naturality of unsolvable problems, people do sometimes argue that recursion theory (which is of course completely intertwined with first-order and second-order arithmetic) is a facet of number theory. This is particularly true for classical Turing computability on the natural numbers. Goedel argued that his incompleteness theorem was really just a surprising fact about number theory, not some new phenomenon unrelated to ordinary mathematics. – Carl Mummert Oct 31 '16 at 23:47
• @CarlMummert Was the fact that exponentiation of natural numbers is definable from addition and multiplication a surprising fact, or was it already known? Or am I all wrong in thinking it has something to do with Goedel's proof? – bof Nov 1 '16 at 0:37

Mathematical logic means many things, depending on context. In particular, it includes two related areas of study:

1. Using mathematical to study "logical" topics such as proofs, models, computability, and sets.

2. Using those logical topics to study mathematics.

The quote from Tao only scratches the surface of mathematical logic. It is analogous to calling the elementary facts about sets at the beginning of a textbook "set theory", when the true study of set theory goes much deeper.

The reason that logic is divided into "proof theory, model theory, computability theory, and set theory" is historical, which is to say it is not based on any kind of rigorous argument. Those four areas were developed during a similar time period, and were all originally motivated by certain foundational issues in math. Some of these areas and their subareas are still closely connected to foundations of math, while others are less closely connected.

Over time, as "logic" became its own subfield of mathematics, these topics became more and more fixed as "logic". The Handbook of Mathematical Logic in 1977 crystallized this division into four areas.

Another common feature of the four areas is a focus on formal languages and formal definability. This is not common in other areas of mathematics, where only natural language is typically used.

The four parts, though, are not intended to be exhaustive. Parts of category theory are closely related in spirit to the other areas of logic, even though category theory is not one of the four areas. Some areas of model theory are much more "mathematical" than other areas of mathematical logic. So the entire idea of dividing "logic" into four parts has to be taken with a grain of salt.

• In my answer I distinguish between two meanings of the word "mathematical logic". Is your point number 2 the former of these two meanings I described? – user377104 Nov 1 '16 at 17:30
• Can you hear me? – user377104 Nov 4 '16 at 18:53
• I did see your comment but I was not sure how to reply. – Carl Mummert Nov 4 '16 at 22:03
• Could you give examples of your points 1. and 2.? In which sense is mathematical logic concerned with using logical topics to study math? In which sense can one use mathematical topics to study proofs, models, computability? – user377104 Nov 16 '16 at 19:54

Mathematical logic involves three steps:

1. Axioms: "Let's agree to the fact that this essential property is true. And we will all consider it true for the sake of building these mathematics.".
2. Definitions: "Let's define these mathematical objects $\mathbb{O}$ as those with these axiomatic properties" defined in 1), and we will all to some extent agree for the sake of working together.
3. For the object defined in 2) $\mathbb{O}$, let's see how far we get by using the fact that "$\mathcal{P}_1 \overset{logic}{\Longrightarrow} \mathcal{P}_2$", where $\mathcal{P}_1$ is a property of $\mathbb{O}$ given in 2).

Here $\overset{logic}{\Longrightarrow}$ is the reasoning that leads to property $\mathcal{P}_2$ by arguing saying:

"If $\mathbb{O}$ does verify $\mathcal{P}_2$ then we are negating the fact that $\mathbb{O}$ verifies $\mathcal{P_1}$. But we all agree to the fact that $\mathcal{P_1}$ holds, so let's say $\mathcal{P_2}$ does not hold". Or "$\mathbb{O}$ verifies $\mathcal{P}_2$ and this fact does not conflict with the fact that $\mathcal{P}_1$ is true, so let's say $\mathbb{O}$ verifies $\mathcal{P}_2$".

• That's a strange view on what 'mathematical logic' is... – Stefan Mesken Nov 1 '16 at 14:43

Modern mathematical logic is "mathematical" also in another sense: some branches of it are simply mathematical disciplines, like e.g. Computability theory and Constructive mathematics,