What is mathematical logic

What logic studies

All knowledge that is not obtained by direct observation is obtained by reasoning: from certain assertions that are accepted one passes to another that follows from them. In geometry, whoever knows that the angles of a triangle add up to two right angles concludes that no triangle has two obtuse angles; in medicine, whoever knows that a certain disease produces fever, and that the person examined has none, rules that disease out. Logic is the discipline that studies when that step is legitimate, and mathematical logic is the one that studies it with the methods of mathematics: defining its objects exactly, which are languages, formulas and deductions, and proving theorems about them.

To state precisely what it studies, it is convenient first to fix the vocabulary. A proposition is a declarative sentence of which it makes sense to say that it is true or that it is false: “$7$ is a prime number” is a true proposition; “every even number is greater than $5$”, a false proposition. On the other hand, questions (“what time is it?”), commands (“close the door”) and expressions with free variables, such as “$x$ is even”, whose value depends on what $x$ designates, are not propositions.

An argument is a list of propositions, the premises, together with another proposition, the conclusion, which is presented as a consequence of them. The premises may be any propositions whatsoever: true, false, known or mere suppositions; the only thing that distinguishes them is the place they occupy in the argument. We shall write arguments with the premises on successive lines and the conclusion preceded by “therefore”:

Logic is not a theory of truth

If this is so, logic does not have the task of finding out whether the premises of an argument are true. Whether $28$ is a multiple of $4$ is decided by arithmetic; whether a person has a fever, by the thermometer; whether a battle took place in a certain year, by history. Nor does it fall to logic to define what truth is, a question that belongs to philosophy. Logic grants that propositions have a truth value, whatever it may be, and studies how those values are related to one another: in particular, when the truth of some propositions forces the truth of another. In other words, logic is not a theory of truth, but a theory of the transmission of truth.

Now, what transmits truth does not depend on the subject matter of the argument, but on its structure. Compare the previous argument with this one: “if an animal is a mammal, it breathes air; the whale is a mammal; therefore, the whale breathes air”. Both have the same form: “if something is $A$, it is $B$; $c$ is $A$; therefore, $c$ is $B$”. The form of an argument is what remains when its non-logical terms (numbers, animals, properties) are replaced by letters, keeping the logical words: “not”, “and”, “or”, “if… then”, “all”, “some”. Each argument obtained from a form by giving content to its letters is an instance of it.

A form is valid when none of its instances has all its premises true and its conclusion false; an argument is valid when its form is. An instance with true premises and a false conclusion is called a counterexample to the form: whence a form is invalid exactly when it has a counterexample.

In the proofs of this lesson we shall use a shorthand of English: $V(A)$ abbreviates “$A$ is true” and $F(A)$, “$A$ is false”; $\neg$ abbreviates “not”, $\wedge$ abbreviates “and”, $\vee$ abbreviates “or”, $\Rightarrow$ abbreviates “if… then” and $\Leftrightarrow$ abbreviates “if and only if”; $\forall$ is read “for all” and $\exists$, “there exists”. These signs are here mere abbreviations of words of the metalanguage, and the double arrows are reserved throughout the course for that use. In the next lesson the single-stroke signs, $\rightarrow$ and $\leftrightarrow$, will appear, together with $\neg$, $\wedge$ and $\vee$, as abbreviations of a formal language, with a meaning that the course will fix exactly; the difference in stroke between the arrows will recall at which level one is speaking.

The proposition states what validity guarantees; it is worth seeing just as clearly what it does not guarantee. Of the eight possible combinations of the validity of the argument, the truth of all its premises and the truth of its conclusion, only one is excluded, that of the valid argument with true premises and a false conclusion; the others all occur.

From this follows the practical rule that the lesson will exercise: to show that an argument is invalid it is not enough to point out that some premise or the conclusion is false, and to show that it is valid it is not enough that everything in it be true; the former requires exhibiting a counterexample to its form, and the latter, a reasoning that holds for all its instances.

Natural language and formal language

The definition of validity rests on two operations: recognizing the form of an argument and deciding whether a proposition is true or false. Both presuppose that each sentence has a single reading. Natural language, English, Chinese or Arabic, which human beings learn without formal instruction and use to communicate, does not meet that condition: its flexibility, which makes it fit for poetry, conversation and nuance, also makes it ambiguous.

• Lexical ambiguity: a word has several meanings. “I sat down by the bank” may refer to the edge of a river or to a financial institution.
• Syntactic ambiguity: a sentence admits several structures. “Twice three plus four” may be $2 \cdot 3 + 4 = 10$ or $2 \cdot (3 + 4) = 14$.
• Scope ambiguity: it is unclear which part of the sentence a logical word affects. “All the students did not pass” may mean that none passed or that not all passed.
• Imprecise connectives: “or” sometimes allows both alternatives to hold (“a degree or experience is required”) and sometimes excludes it (“coffee or tea”); “if… then” sometimes expresses a cause, sometimes a rule, sometimes a mere succession.

To ambiguity is added a deeper feature: natural language can speak about itself. It contains the words “sentence”, “true” and “define”, and with them it can form sentences that refer to themselves, such as “this sentence has five words”. This self-reference is, in general, harmless; but, as will be seen, combined with the notion of truth it produces sentences that can be neither true nor false.

A formal language is designed to eliminate both sources of difficulty. One fixes an alphabet, a collection of symbols, and some formation rules that say, leaving no room for interpretation, which sequences of symbols are well-formed expressions; the meaning of each expression is fixed afterwards by equally precise definitions. Thus, asking whether a sequence of symbols belongs to the language is a question that is settled mechanically, by checking rules, and each expression is read in only one way. The language of this course, which the lesson on the language of propositional logic builds, has an alphabet of only two symbols, the circle $\sigO$ and the disk $\sigI$, and a single formation rule.

The price is flexibility: a formal language is no good for conversation, and each formal language expresses only what its rules allow. It is not true, however, that all expressive power is sacrificed: the formal languages of first-order logic suffice to write almost all of mathematics. What is sacrificed is ambiguity and uncontrolled self-reference; what is gained is the possibility of proving theorems about the language itself.

Object language and metalanguage

To study a language one has to speak about it, and to speak about it another language is needed. The object language is the language under study; the metalanguage is the language in which it is studied. In a Latin grammar written in English, Latin is the object language and English the metalanguage. In this course, the object language will be the formal language of circles and disks, and the metalanguage will be English, enriched with mathematical signs and with Greek letters, $\varphi$, $\psi$, which will designate arbitrary formulas of the object language without belonging to it.

The distinction is central for a precise reason: the assertions that the course will prove about the formal language (that every formula is read in only one way, that everything derivable is true) are not formulas of the formal language, but sentences of the metalanguage. That is why they will be called metatheorems, to distinguish them from the theorems that the deductive system produces within the object language.

An elementary form of the distinction is the one that separates the use of an expression from its mention. In “Rome is a city” the word is used to speak about the city; in “‘Rome’ has four letters” the word is mentioned, and the quotation marks indicate it: the sentence speaks about the word, not about the city. Confusing the two produces absurd statements, such as “Rome has four letters”, or fallacious arguments, such as “Rome is a city; ‘Rome’ is a four-letter word; therefore, a city is a four-letter word”.

The paradoxes of language

A contradiction is an assertion together with its negation, such as $V(A) \wedge \neg V(A)$. A paradox is a piece of reasoning that, starting from hypotheses that seem acceptable and advancing by steps that seem valid, arrives at a contradiction. By the proposition on what validity guarantees, if the steps are really valid, some hypothesis is false: resolving a paradox consists in finding which. One should not confuse paradox with ambiguity, which is merely the multiplicity of readings, nor with what is merely surprising.

The liar

The oldest paradox of this kind is attributed to Eubulides of Miletus, in the fourth century before the common era. In its precise form it does not speak of lying, which presupposes the intention to deceive, but of falsity: let $m$ be the sentence “the sentence $m$ is false”. To obtain the contradiction two hypotheses suffice, which it is worth writing out explicitly.

• Bivalence (B): every proposition is true or false, and not both; being false is equivalent to not being true.
• Truth schema (T): a sentence is true if and only if what it says is the case. For example, “snow is white” is true if and only if snow is white.

The theorem does not say that logic is contradictory, but that the two hypotheses cannot be maintained together for a language that contains the sentence $m$. There are, therefore, three ways out: abandoning bivalence and admitting sentences without a truth value; restricting the truth schema; or preventing the language from forming the sentence $m$. The third is that of Alfred Tarski, in 1933: the predicate “is true” of a language does not belong to that language, but to its metalanguage. In such a language, $m$ is not a well-formed sentence, and the paradox cannot be stated.

Berry's paradox

Published by Bertrand Russell in 1906, who attributed it to George Berry, a librarian at Oxford, this paradox does not use the word “true”, but the word “define”. An English phrase is said to define a natural number when it describes it in such a way that the number can be identified without ambiguity: “the smallest prime number greater than ten” defines $11$. Let us consider the phrase “the smallest natural number that cannot be defined in fewer than twenty words”, which must be read just as it is written, and let us call $b$ the number it purports to define. The natural numbers, in this course, are $1, 2, 3, \ldots$

The usual exposition, which confines itself to observing that the phrase has fewer than twenty words, omits half of the argument: that the number $b$ exists, which requires the finiteness of the vocabulary and the choice of the first number missing. The hypothesis that fails is the second: “define” is not a precise relation of English, because the phrase that defines $b$ uses the very word “define”, and its sense depends on which phrases count as definitions. In a formal language $L$ one can make precise what “definable in $L$” means, but that notion is expressible only in the metalanguage; the phrase that defines $b$ does not belong to $L$, and the contradiction disappears: $b$ is not definable in $L$ with few symbols, although it is so in the metalanguage.

The barber and Russell's set

The barber paradox is usually told thus: in a village there is a barber, a man of the village, who shaves all the men of the village who do not shave themselves, and only them. Does the barber shave himself? The words “and only them” are essential: a barber who shaved all those who do not shave themselves, without the restriction, could also shave himself without any contradiction. The paradox is a particular case of a general lemma, of diagonal form, which it is worth proving once and for all.

The conclusion about the barber is harmless: nobody had claimed that such a barber existed. The same does not happen with its version in set theory. In 1902, Russell wrote to Gottlob Frege that his system, which aimed to found arithmetic on logic, admitted the following comprehension principle: for every property there is a set whose elements are exactly the objects that have it. Applied to the property of not belonging to itself, the principle asserts that there exists the set

Unlike the barber, here the existence of $Z$ was not a supposition in a story, but a principle of the theory. Russell's paradox is not resolved by declaring that $Z$ does not exist, but by reforming the theory: Zermelo's axiomatic set theory, of 1908, only allows forming, with a property, subsets of an already given set, and with that restriction the contradiction is not deduced.

What is not a paradox

The observation that the empty set exists although it has no elements, as if an existing object had to be made of existing objects, has sometimes been called the “paradox of the empty set”. There is no contradiction in it whatsoever: a set is not made of its elements as a wall is made of its bricks, but is determined by them, and the collection of the elements of a set may have none, just as an empty box is still a box. That a fact is surprising does not make it paradoxical; a paradox requires deducing a contradiction, and here none is deduced.

How a formal language deals with them

From the foregoing it follows that a formal language does not avoid the paradoxes by magic, but in two precise ways. The first is that it may lack the resources that produce them. The language of propositional logic, which this course builds, has no sentences that refer to themselves and no truth predicate: in it the liar sentence cannot be written, and its semantics assigns to each formula, under each assignment of values to the variables, a single truth value. The second is that, in richer languages, the paradox becomes a theorem: the liar's reasoning, carried out rigorously, proves that the truth of a sufficiently expressive language is not definable in that same language (Tarski); that of the barber and of Russell proves that certain collections are not sets; and arguments related to Berry's lie at the heart of Kurt Gödel's incompleteness theorems, of 1931. Thus, what in natural language is a perplexity, in a formal language is information.

The four pillars of mathematical logic

Mathematical logic was born at the end of the nineteenth century and the beginning of the twentieth, with Frege, Peano, Russell and David Hilbert, as the answer to a precise question: on what foundations mathematics rests and whether those foundations are free from contradiction. Today it is divided into four great branches, which constantly intertwine.

• Proof theory: it studies formal proofs as mathematical objects, that is, as finite sequences of formulas that follow explicit rules; it asks what can be proved in a system, whether a system is consistent and how some proofs are transformed into others. The deduction unit of this course is a first contact with it.
• Model theory: it studies the relation between a formal language and the structures that interpret it, its models; it asks which structures satisfy a set of formulas and which properties of structures can be expressed in a given language. The semantics unit, with its assignments of truth values, is its most elementary version.
• Set theory: it studies sets with precise axioms, such as those of Zermelo and Fraenkel, in which almost all of mathematics can be written; it was born, in good part, from the need to avoid Russell's paradox.
• Computability theory: it studies which problems can be solved by a mechanical procedure and which cannot. Propositional logic is decidable, as the course will show: there is a procedure that decides in a finite number of steps whether a formula is valid; predicate logic, on the other hand, is not.

No pillar is studied in depth without touching the others: completeness, a central result of this course, is at once a theorem of proof theory and of model theory, and the decidability obtained from it belongs to computability.

The map of the course

The course travels, for the simplest language of logic, the propositional one, the complete path of a logical theory, in four units.

1. Language: syntax. The object language is built with its two-symbol alphabet and its formation rule, it is proved that each formula is read in only one way, one learns to prove by induction, and statements and arguments of natural language are translated into the formal language, pointing out what the translation preserves and what it loses.
2. Deduction: a system of axioms and rules of inference is fixed, and it is defined what it means for a formula $\varphi$ to be deduced from a set of formulas $\Gamma$, which is written $\Gamma \vdash \varphi$. It is the syntactic face of validity: manipulating symbols according to rules, without attending to their meaning.
3. Semantics: each formula is given a truth value under each assignment, and it is defined what it means for $\varphi$ to be a consequence of $\Gamma$, which is written $\Gamma \models \varphi$: every assignment that makes the formulas of $\Gamma$ true makes $\varphi$ true. It is the semantic face of validity, the definition of this lesson made precise.
4. Metatheory: it is proved that both faces coincide. Soundness says that everything derivable is a consequence, and completeness, that every consequence is derivable. Afterwards compactness is studied, together with a mechanical method, resolution, for deciding whether a set of formulas can be satisfied.

If this is so, the course is the first complete example of a mathematical theory whose object is reasoning itself; and all its assertions about the formal language will be, as has been seen in this lesson, sentences of the metalanguage proved with the rigor of mathematics.

Solved problems

The following problems exercise, in increasing difficulty, the distinctions of the lesson: refuting an argument whose sentences are all true, separating the readings of an ambiguous statement, classifying expressions of the object language and of the metalanguage, and analyzing two pieces of reasoning of paradoxical appearance to decide whether they are paradoxes.

Proposed problems

The first two problems exercise validity and ambiguity; the third, use and mention; the last two ask you to analyze a new paradox and to apply the diagonal lemma outside linguistics. Each one has a hint, which is best opened only after having attempted the problem.