Language: synthesis and challenges

Summary

This lesson closes the unit devoted to the language of propositional logic. It rebuilds the deductive chain that runs from the distinction between validity and truth, and from the analysis of the paradoxes, to the unique readability of formulas and to the formalization of statements and arguments, pointing out at each link which principle is used and in which lesson it is proved; it places what has been achieved within the plan of the course and explains why the language already built raises the question of the next unit, devoted to deduction. It repeats in its exit assessment the skills of the entry assessment, and it ends with six challenges, harder than the problems of the lessons, which require combining the tools of several of them.

Learning objectives

Rebuild the logical order of the results of the unit, identifying the principle on which each one rests and the lesson in which it is proved.
Explain how the closure principle, the decomposition into words, the weight lemma and unique readability are linked, and why the recursive definitions and the comparison of formalizations depend on the last of these.
Distinguish what the unit proved from what it accepted as hypotheses (bivalence, the truth schema, the principle of induction and the reading of joint denial) and from what it left for the following units.
Solve problems that combine the diagonal lemma, the counting of strings, induction on formulas, the weight argument and the unfolding of abbreviations.

What the unit achieved

The unit set out to build, from an alphabet of two symbols, a language in which each formula is read in only one way, to prove the properties of that language rigorously and to build a bridge between it and the language in which we reason. The purpose has been fulfilled with a few reservations, each one declared in its place: bivalence and the truth schema, which the first lesson accepted not as truths but as explicit hypotheses, in order to examine what happens when they are maintained together; the principle of induction on the natural numbers, which is accepted as the fifth Peano axiom; the informal reading of joint denial, which is stipulated and which the unit on semantics will turn into a definition; and the indispensable minimum of set theory (membership, inclusion and union), which was taught where it was needed. With those reservations, the path travelled can be read as a single deductive chain in four segments.

Reasoning and speaking about language

The lesson on what mathematical logic is fixed the object of the course: not the truth of statements, which belongs to each science, but its transmission. An argument is valid when its form admits no instance with true premises and a false conclusion, and from that definition the lesson deduced the only thing that validity guarantees: if the premises are true, so is the conclusion; whence a valid argument with a false conclusion has some false premise, and a form is invalid exactly when it has a counterexample. That same result turned the analysis of the paradoxes into a procedure: if the steps of a piece of reasoning that ends in a contradiction are valid, some hypothesis is false, and resolving the paradox is finding which. This is how the liar was treated, in which bivalence and the truth schema cannot be maintained together for a sentence that declares itself false, and this is how Berry's paradox and the adjective “heterological” were treated. From the barber a general lemma was extracted, the diagonal lemma, which proves that the barber does not exist and that the unrestricted comprehension principle is contradictory. Finally, the lesson established the distinction between object language and metalanguage, and between the use of an expression and its mention, which governs everything that follows: the results of the unit about formulas are not formulas, but metatheorems.

The language of circles and disks

The lesson on the language of propositional logic introduced sets and strings, counted the strings of each length (there are $2^{n}$ of length $n$ , and $2^{N + 1} - 2$ of lengths $1$ to $N$ ) and built the base language: the variables $v_n = \sigO^{n}\sigI$ and a single rule, which from two formulas $\varphi$ and $\psi$ forms $\sigI\varphi\psi$ . The clause “nothing else is a formula” was made precise by defining formulas as the strings that belong to every closed set, and from that definition the closure principle was deduced, with which it was proved that every formula is a variable or is $\sigI\varphi\psi$ , and not both, that every formula ends in a disk and that it contains an odd number of disks. The observation that the variables and the single disk form a prefix code gave the unique decomposition into words, and with it the notion of weight. The lesson also built the metalanguage with which one works from then on: the metavariables, joint denial written $(\varphi \downarrow \psi)$ and the six official abbreviations, each defined only once in terms of the previous ones, so that every abbreviated expression designates a single string.

Induction and unique readability

The lesson on induction on the natural numbers and on formulas justified the counts that the previous lesson had concluded with “and so on”, derived strong induction from simple induction and, applying strong induction to length, obtained structural induction, which turns out to be the same induction on the natural numbers transferred to formulas. With this tool it proved the weight lemma: every formula weighs $+1$ , and every nonempty proper word prefix weighs at most $0$ . From this follow, in this order, that no formula is a proper prefix of another and that every compound formula is read in a unique way. Unique readability is the link on which the rest of the unit hangs: it justifies the decision procedure that the lesson on the language had described as a debt that is settled, and it legitimizes the definitions by recursion (length, the number of variables and of connective disks, subformulas, depth and substitution), which without it could assign two different values to one formula.

From English to formulas

The lesson on the formalization of natural language built the bridge towards everyday language. It fixed the convention of the letters $p$ , $q$ , $r$ , $s$ and $t$ as names of five particular variables, required every formalization to declare its dictionary and derived, from the stipulated reading of joint denial alone, the reading of each abbreviation. With unique readability it proved that two different groupings of the same connectives are different formulas, and with the recursive definition of length it computed how long the unfolded abbreviations are, which gives a quick criterion for telling formalizations apart. It showed that the material conditional is false only when the antecedent is true and the consequent false, and that this is the only reading, depending only on the truth of the parts, that makes the conditional theorems of mathematics true; it pointed out what formalization loses (quantifiers, time, causality, modality) and ended by formalizing complete arguments as a set of premises $\Gamma$ and a conclusion.

The following figure gathers the four segments into a single chain. Each node of the column is a definition or a result, numbered according to the logical order and joined by an arc to the earlier links that its proof uses; around them float the supports, that is, the principles to which the chain turns again and again, each joined by a solid line to the links that rest on it and by a dotted one to the link where it is established, except those accepted without proof, which are drawn as rings. Clicking a support highlights all the links that use it, and each link refers to the lesson in which it is proved. Note that the decision procedure, although it is set out in the lesson on the language, occupies its logical place after unique readability, on which it rests.

Supports of the chain

ABivalence. Every proposition is true or false, and not both; being false is equivalent to not being true. It is accepted as an explicit hypothesis in the analysis of the paradoxes. Admitted without proof in this unit.
BTruth schema. A sentence is true if and only if what it says is the case. It is accepted as an explicit hypothesis; Tarski's solution keeps it, but only for the sentences of a language that does not contain its own truth predicate. Admitted without proof in this unit.
CPrinciple of induction. If a property holds for $1$ and, whenever it holds for a natural number $k$ , it holds for $k + 1$ , then it holds for all natural numbers. It is the fifth Peano axiom, and it is accepted. Admitted without proof in this unit.
DDiagonal lemma. No object $b$ of a collection satisfies $R(b, x) \Leftrightarrow \neg R(x, x)$ for every $x$ of the collection. Established in: 3. Diagonal lemma.
EClosure principle. A property that all the variables have and that passes from $\varphi$ and $\psi$ to $\sigI\varphi\psi$ is had by all formulas. Established in: 5. Closure principle.
FStructural induction. Induction on the complexity of formulas, derived from strong induction on length: its base case is the variables, and its inductive step, the single formation rule. Established in: 9. Structural induction.
GUnique readability. If $\sigI\varphi\psi = \sigI\varphi'\psi'$ , with all four strings formulas, then $\varphi = \varphi'$ and $\psi = \psi'$ . Established in: 11. Unique readability.
HReading of joint denial. The formula $(\varphi \downarrow \psi)$ is true exactly when $\varphi$ and $\psi$ are both false. It is the only reading that is stipulated; the others are deduced from it, and the unit on semantics will make it precise. Admitted without proof in this unit.

Segment 1 Reasoning and speaking about language
- Distinguish validity from truth and refute an invalid form with a counterexample.
- Recognize the ambiguities of natural language and separate the readings of a statement.
- Distinguish the object language from the metalanguage, and the use of an expression from its mention.
- Analyze a paradox by isolating its hypotheses and deciding which one must be abandoned.
1. What validity guarantees. If an argument is valid and all its premises are true, its conclusion is true; whence a valid argument with a false conclusion has some false premise, and a form is invalid exactly when it has a counterexample.
  Proved in: What is mathematical logic.
2. The liar paradox. Applied to the sentence $m$ , “the sentence $m$ is false”, bivalence and the truth schema give $V(m) \Leftrightarrow \neg V(m)$ ; for a language that contains $m$ , one of the two hypotheses must be abandoned, and Tarski's way out is that no language should contain its own truth predicate, so that $m$ cannot be formed.
  Uses: 1. What validity guarantees. Rests on: A (Bivalence), B (Truth schema). Proved in: What is mathematical logic.
3. Diagonal lemma. If $R$ is a relation between the objects of a collection $D$ , such that each $R(x, y)$ is true or false, no $b$ of $D$ satisfies $R(b, x) \Leftrightarrow \neg R(x, x)$ for every $x$ of $D$ .
  Rests on: A (Bivalence). Proved in: What is mathematical logic.
4. The barber and Russell. There is no man of the village who shaves exactly the men of the village who do not shave themselves; and the unrestricted comprehension principle is contradictory, because it asserts the existence of the set $Z = \{ x : x \notin x \}$ .
  Rests on: D (Diagonal lemma). Proved in: What is mathematical logic.
Segment 2 The language of circles and disks
- Describe sets of strings and count the strings of each length.
- Define formulas as the smallest closed set and deduce from this the closure principle.
- Prove properties of all formulas and use them to rule out strings.
- Decompose a string into words and unfold abbreviations down to the base language.
1. Closure principle. The set $\mathcal{F}$ of formulas is the smallest set of strings that contains the variables $v_n = \sigO^{n}\sigI$ and that, together with $\varphi$ and $\psi$ , contains $\sigI\varphi\psi$ ; therefore, a property that the variables have and that passes from $\varphi$ and $\psi$ to $\sigI\varphi\psi$ is had by all formulas.
  Proved in: The language of propositional logic.
2. Form of formulas. Every formula is a variable or is $\sigI\varphi\psi$ with $\varphi$ and $\psi$ formulas, and not both: every variable begins with $\sigO$ , and every compound formula, with $\sigI$ .
  Rests on: E (Closure principle). Proved in: The language of propositional logic.
3. Last symbol and number of disks. Every formula ends in a disk and contains an odd number of disks; whence neither the concatenation of two formulas nor the string $\sigI\varphi$ is a formula.
  Rests on: E (Closure principle). Proved in: The language of propositional logic.
4. Decomposition into words. Every string that ends in a disk is decomposed in a unique way into words, that is, into variables $\sigO^{n}\sigI$ and single disks, because each word ends in its only disk and none is a proper prefix of another.
  Proved in: The language of propositional logic.
Segment 3 Induction and unique readability
- Prove by simple and strong induction, and derive from them induction on the complexity of formulas.
- Prove the weight lemma and derive unique readability.
- Decide whether a string is a formula and reconstruct its formation.
- Define functions on formulas by recursion and prove relations between them.
1. Structural induction. Strong induction is derived from simple induction; applied to length, it gives the principle of induction on complexity: if the variables have a property and it passes from $\varphi$ and $\psi$ to $\sigI\varphi\psi$ , all formulas have it.
  Uses: 6. Form of formulas. Rests on: C (Principle of induction). Proved in: Induction on the natural numbers and on formulas.
2. Weight lemma. If each occurrence of a variable weighs $+1$ and each connective disk $-1$ , every formula weighs $+1$ and every nonempty proper word prefix of a formula weighs at most $0$ ; in particular, every formula has one more occurrence of a variable than connective disks.
  Uses: 8. Decomposition into words. Rests on: F (Structural induction). Proved in: Induction on the natural numbers and on formulas.
3. Unique readability. No formula is a proper prefix of another; whence, if $\sigI\varphi\psi = \sigI\varphi'\psi'$ with all four strings formulas, then $\varphi = \varphi'$ and $\psi = \psi'$ .
  Uses: 7. Last symbol and number of disks, 8. Decomposition into words, 10. Weight lemma. Proved in: Induction on the natural numbers and on formulas.
4. Decision procedure. A string that ends in $\sigO$ is not a formula; if it ends in $\sigI$ , it is decomposed into words. If the first word is a variable, the string is a formula exactly when that variable is its only word. If it is a disk, the debt is kept after it: if the debt never becomes zero, the string is not a formula; if it does, the cut between $\varphi$ and $\psi$ lies where it becomes zero for the first time, and each part is examined in the same way, bearing in mind that the empty string is not a formula.
  Uses: 6. Form of formulas, 7. Last symbol and number of disks, 8. Decomposition into words. Rests on: G (Unique readability). Proved in: The language of propositional logic.
5. Definition by recursion. Given a value for each variable and a rule that computes the value of $\sigI\varphi\psi$ from $\varphi$ , from $\psi$ and from their values, there is exactly one function on formulas that respects them; this is how length, subformulas, depth and substitution are defined, and substitution always produces formulas.
  Uses: 6. Form of formulas. Rests on: C (Principle of induction), F (Structural induction), G (Unique readability). Proved in: Induction on the natural numbers and on formulas.
Segment 4 From English to formulas
- Formalize statements with an explicit dictionary, deciding the scope of each connective.
- Unfold abbreviations to decide whether two formalizations are the same formula.
- Distinguish the material conditional from the “if… then” of everyday language and point out what formalization loses.
- Formalize complete arguments as a set of premises and a conclusion.
1. Length of the abbreviations. If $L(\varphi) = a$ and $L(\psi) = b$ , the strings of $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ and $(\varphi \wedge \psi)$ have lengths $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ and $8a + 8b + 15$ ; two formalizations of different lengths are different formulas.
  Uses: 13. Definition by recursion. Proved in: Formalization of natural language.
2. Scope and different formulas. The groupings $((p \wedge q) \vee r)$ and $(p \wedge (q \vee r))$ are different strings: if they coincided, unique readability, applied twice, would force the variable $r$ to coincide with the compound formula $(p \wedge q)$ .
  Uses: 6. Form of formulas. Rests on: G (Unique readability). Proved in: Formalization of natural language.
3. Material conditional. The implication $(\varphi \rightarrow \psi)$ , which abbreviates $(\neg\varphi \vee \psi)$ , is false only when $\varphi$ is true and $\psi$ false; it is the only reading, depending only on the truth of the parts, that makes the conditional theorems of mathematics true.
  Rests on: H (Reading of joint denial). Proved in: Formalization of natural language.

Towards deduction. The chain stops where the language is built and the arguments are formalized as a set of premises and a conclusion. It remains to decide when a formula follows from others: first by manipulating symbols with rules, in the next unit, and later by attending to their truth.