Language: introduction · Topos Uranos

Summary

This lesson opens the first unit of the course, devoted to the language of propositional logic. It presents the unit's four lessons and the thread that joins them, from the distinction between validity and truth to the formalization of English arguments; it places the unit on the complete path of the course, which goes from language to deduction, to semantics and to metatheory, and explains why syntax must precede the other three; it justifies the choice of a language of only two symbols, the circle and the disk, with a single formation rule; it specifies the little that is taken for granted, namely careful reading and elementary arithmetic; it states the problem that the unit solves, that of writing so that each expression has a single reading and of proving it for infinitely many formulas, and it gives advice for studying the unit.

Learning objectives

Describe the sequence of contents of the unit and explain what each lesson contributes to the next.
Place the unit on the path of the course (language, deduction, semantics and metatheory) and explain why syntax is studied before the other three parts.
Explain, with an example, why a notation with the connective between its arguments and without parentheses is ambiguous, and why the language of circles and disks is not.
Recognize the little that the unit presupposes and organize its study, with the entry self-assessment as the starting point.

Entry assessment

Before working through the unit, it is worth measuring the starting point. This assessment is a self-assessment: it is not graded, and its only purpose is to guide your study. Its eleven questions cover, in order, the four lessons of the unit: three the first, three the second, two the third and three the fourth. Anyone who has never studied logic should not expect to get them all right, and that does not matter: every answer, right or wrong, explains the point and names the lesson that deals with it. The same skills are measured again at the end, in the synthesis lesson; since this is the first unit of a course with no entry requirements, there are no questions about previous units.

The contents of the unit

This unit serves, above all, the first of the course objectives, to distinguish the object language from the metalanguage and to decide with the formation rules whether a string is a formula; it also serves the second, to formalize statements and arguments of natural language, and it prepares the fourth, to prove metatheorems by induction, which will accompany the course up to its last unit. Its goal is that whoever completes it should know what logic studies, have at hand a formal language built with full rigor, know how to prove properties of all its formulas and be able to translate into it statements and arguments of English, knowing what the translation preserves and what it loses. Its four lessons form a chain in which each one rests on the previous ones.

What is mathematical logic. It delimits the object of the discipline: not the truth of particular statements, but validity, the relation between premises and conclusion that guarantees that the truth of the former passes to the latter. It distinguishes validity from truth, shows why natural language, ambiguous and able to speak about itself, is not enough to study it, and establishes the distinction between object language and metalanguage. It analyzes, with their hypotheses made explicit, the liar, Berry, barber and Russell paradoxes, and it ends with the map of the course.
The language of propositional logic. It teaches the indispensable minimum about sets and strings of symbols, counts the strings that can be written with two symbols and builds the base language: infinitely many variables written with circles and disks, a single formation rule and a closure clause, from which a principle for proving properties of all formulas is derived. It gives a procedure for deciding whether a string is a formula and builds, on the base language, the metalanguage that will be used from then on: metavariables, joint denial written with parentheses and the official abbreviations of the other connectives.
Induction on the natural numbers and on formulas. It teaches induction on the natural numbers, simple and strong, and carries it over to formulas. With it, the lesson proves the weight lemma and, from the lemma, the unique readability theorem, which the previous lesson had stated: each compound formula decomposes in only one way. Unique readability legitimizes, finally, definitions by recursion on formulas (length, subformulas, depth) and the substitution of one subformula by another.
The formalization of natural language. It builds the bridge between English and the formal language: the dictionary of a formalization, the reading of each connective deduced from that of the primitive connective, the subtleties of “but”, “only if” and “unless”, the scope of the connectives, the material conditional and what propositional logic cannot express. It ends by formalizing complete arguments as a set of premises and a conclusion, which the following units will submit to deduction and to semantics.

The unit ends with the synthesis and challenges lesson, which gathers what has been achieved into a deductive chain, repeats in its exit assessment the skills of the entry assessment and proposes challenges that combine several lessons.

The place of the unit in the course

For the simplest language of logic, the course goes along the complete path of a logical theory, and it does so in four parts, which are its four content units. The first, this one, fixes the language. The second, deduction, defines what it means for a formula $\varphi$ to be obtained from a set of formulas $\Gamma$ by means of axioms and rules of inference, which will be written $\Gamma \vdash \varphi$ ; it is the syntactic face of validity, in which symbols are manipulated without attending to their meaning. The third, semantics, assigns to each formula a truth value under each valuation and defines what it means for $\varphi$ to be a consequence of $\Gamma$ , which will be written $\Gamma \models \varphi$ ; it is the semantic face of validity. The fourth, metatheory, proves that both faces coincide: soundness says that everything derivable is a consequence, and completeness, that every consequence is derivable.

If this is so, syntax is not a preamble that can be cut short, but the condition of the other three parts. A deduction is a sequence of formulas, and to decide whether a sequence is one, one has to know, without hesitation, which strings are formulas and how they decompose; a valuation is extended from the variables to all formulas by recursion, and recursion gives a single value to each formula only if each formula is read in only one way; the theorems of metatheory are proved by induction, on the complexity of formulas or on the length of deductions. From this follows the order of the unit: first, what one wants to study and why a formal language is needed; then, the language; next, the instrument for proving something about all its formulas, with which unique readability is proved; and, finally, the bridge to the arguments of English, which are the reason for everything that comes before.

Why a language of circles and disks

The language of the course has an alphabet of only two symbols, the circle $\sigO$ and the disk $\sigI$ , and a single formation rule: if $\varphi$ and $\psi$ are formulas, so is $\sigI\varphi\psi$ . The $n$ th variable is the string of $n$ circles followed by a disk, $v_{n} = \sigO^{n}\sigI$ . At first sight, the choice is strange, because formulas written in this way are hard to read. It has, however, four precise reasons.

The first is that two symbols are enough to write infinitely many variables without leaving a finite alphabet, so that every formula is, literally, a finite string of symbols from a two-element set, and questions about the language are questions about strings, which can be counted and compared. The second is that a single rule leaves a single case in each proof by induction: what is proved for the variables and for $\sigI\varphi\psi$ is thereby proved for all formulas, without one case per connective. The third is that the rule puts the connective in front of its two arguments, as in the notation that Jan Łukasiewicz proposed in the 1920s, and that is why it needs no parentheses: unique readability is proved with a one-page argument, which assigns to each variable the weight $+1$ and to each connective disk the weight $-1$ . The fourth is that the single connective, joint denial, “neither $\varphi$ nor $\psi$ ”, is enough to express all the others, as Charles Sanders Peirce observed around 1880 and Henry Sheffer published in 1913, and as the unit on semantics will prove; so the economy of the language sacrifices nothing of what propositional logic can say.

Now, the price of that economy is readability, and the unit pays it in the metalanguage: nobody will write strings of circles and disks day to day, but their names, $(\varphi \downarrow \psi)$ , $\neg\varphi$ , $(\varphi \rightarrow \psi)$ , defined only once and unfoldable, at any moment, into the string they designate. Therefore, the course works with two levels at once: a minimal base language, about which theorems are proved, and a convenient notation, with which one writes; and the distinction between object language and metalanguage, which the first lesson introduces, is what makes it possible not to confuse them.

What is taken for granted

The unit starts from almost nothing. It does not presuppose having studied logic, or knowing set theory, or ever having proved a theorem: what it uses about sets is taught in the second lesson, and what it uses about induction, in the third. It presupposes only two things. The first, careful reading: in a formal language, a symbol added or omitted changes the string, and the order of the words of a definition matters as much as the words themselves. The second, the elementary arithmetic of the natural numbers, which in this course are $1, 2, 3, \ldots$ : adding and multiplying, computing powers of $2$ , telling even numbers from odd ones and recognizing a prime number.

Anyone who wants additional support for induction can consult the lessons on the Peano axioms and on summations and induction of the course Algebra and Geometry I; it is not necessary, because the third lesson of this unit teaches induction starting from its statement.

The problem the unit solves

Logic studies validity, and validity depends on the form of arguments. But to speak of form with rigor, each expression must have a single form, and natural language does not guarantee it: “twice three plus four” may be $10$ or $14$ , depending on how it is grouped. This raises two problems, which are those of the unit. The first is to build a language in which each expression is read in only one way. The second is to prove it: formulas are infinitely many, and no case-by-case check, however long, establishes that all of them are read in only one way. The following example shows both problems in a single expression.

ExampleOne expression, two strings

The expression $v_{1} \downarrow v_{2} \downarrow v_{3}$ , written with the connective between its arguments and without parentheses, does not indicate which of the two connectives is the main one. In the language of circles and disks, by contrast, each grouping is a different string, and the string itself says how it is grouped.

Proof

$((v_{1} \downarrow v_{2}) \downarrow v_{3}) = \resaltar{\sigI\sigI} v_{1} v_{2} v_{3}$
First reading: the first connective joins $v_{1}$ with $v_{2}$ , and the second is the main one. In the base language, the two disks go in front.
$(v_{1} \downarrow (v_{2} \downarrow v_{3})) = \sigI v_{1} \resaltar{\sigI} v_{2} v_{3}$
Second reading: the second connective joins $v_{2}$ with $v_{3}$ , and the first is the main one. The second disk goes between $v_{1}$ and $v_{2}$ .
$\sigI\resaltar{\sigI}\sigO\sigI\sigO\sigO\sigI\sigO\sigO\sigO\sigI \neq \sigI\resaltar{\sigO}\sigI\sigI\sigO\sigO\sigI\sigO\sigO\sigO\sigI$
Written with circles and disks, the two strings already differ in their second symbol: they are different formulas.
$\sigI \; \resaltar{\sigI \; v_{1} \; v_{2}} \; v_{3}: \quad -1, \quad 0, \quad +1$
To read the first string, it is enough to count: after the initial disk, each connective disk subtracts $1$ and each variable adds $1$ , and the first component ends where the sum first reaches $+1$ .
$\sigI \, \resaltar{(\sigI v_{1} v_{2})} \, \resaltar{v_{3}}$
Whence the first component is $\sigI v_{1} v_{2}$ and the second, $v_{3}$ : the string is read as the first reading, and in no other way. That this count works for all formulas, and not only for this one, is the unique readability theorem, which the third lesson proves by induction.

The unit's answer to these two problems has, therefore, two parts. For the first, a language whose single rule puts the connective in front, so that parentheses are superfluous, and a metalanguage whose abbreviations each designate a single string. For the second, a principle of proof, induction on the complexity of formulas, which passes from a finite number of verifications (the variables and the rule) to all formulas, just as induction on the natural numbers passes from $1$ and from the step from $k$ to $k + 1$ to all numbers. With both parts, the form of an argument becomes a precise object, and the question of its validity can be posed with rigor in the following units.

How to study the unit

It is advisable to begin with this entry assessment and to note the questions missed, which point to the lessons where one must linger. The four lessons must be studied in order, because each one uses what the previous ones establish. In the second and the third, study requires paper and pencil: strings of circles and disks are hard to read on a screen, and it is advisable to copy them, separate their words (each variable and each single disk) and note the weight of each one, until the count of unique readability becomes a habit. Proofs are published as step-by-step players, and each step should be justifiable before moving on. In the first and the fourth, the work is one of careful reading: faced with each English sentence, ask exactly what it asserts, what readings it admits and which formula represents it. Finally, the hint and the answer of each proposed problem are opened only after having seriously attempted it.

Where it leads

At the end of the unit, the language will be fixed, and the following units will build on it without discussing it again. The unit on deduction will define a system of axioms and two rules of inference, modus ponens and, once double negation has been proved, replacement of double negation, whose deductions are sequences of formulas; its axioms are written with the official abbreviations, which this unit defines, and its deduction theorem is proved by induction on the length of deductions, with the instrument learned here. Its first lesson is the one on formal deductive systems. The unit on semantics will assign truth values to the variables and extend them to all formulas by recursion, which is possible only thanks to unique readability; it will justify with tables the informal readings of the connectives that the fourth lesson uses, and it will prove, in the lesson on functional completeness, that joint denial is enough to express any connective. The unit on metatheory, finally, will prove by induction soundness and completeness, and the arguments that this unit teaches how to formalize can at last be decided by deduction or by semantics indifferently.

Outside this course, the syntax of a formal language is that of every programming language: a compiler, like those of Programming in C++ I, begins by deciding whether a program is well formed and by decomposing it in a single way. The distinction between validity and truth is also the starting point of Aristotelian Logic, which studies the form of syllogisms; and the induction of the third lesson is the same one that proves the properties of numbers in Algebra and Geometry I. In all those domains, as in the drafting of regulations and contracts, the lesson is the same: saying precisely what is asserted requires a language in which each expression has a single reading.