Deduction: introduction · Topos Uranos

Summary

This lesson opens the second unit of the course, devoted to deduction. It presents its five lessons and the thread that joins them, from the definition of a formal deductive system to De Morgan's laws and the distributive laws; it places the unit on the path of the course, between language, already built, and semantics and metatheory, which are to come, and anticipates what these will say about it; it justifies the choice of an axiomatic system, which is built in two stages (Łukasiewicz's system, with three axiom schemas and modus ponens, and the course system, which adds to it the rule of replacement of double negation), and explains why that second rule is needed and why it is postulated instead of proved; it shows with a short deduction how much work an elementary piece of reasoning hides; it specifies what is taken from the previous unit, namely unique readability, induction (strong induction on the natural numbers and structural induction) and the unfolding of abbreviations, and gives advice for studying it.

Learning objectives

Describe the sequence of the five lessons of the unit and explain which results of each one the next one uses.
Place deduction on the path of the course, distinguish derivability $\Gamma \vdash \varphi$ from semantic consequence $\Gamma \models \varphi$ and explain what soundness and completeness will assert.
Explain why the course system adds to Łukasiewicz's a second primitive rule, the replacement of double negation, starting from what the three schemas can and cannot see in a joint denial.
Read a short deduction by numbered lines, distinguish the deduction of formulas from deduction about deductions, recognize what the unit takes from the previous one and organize its study starting from the entry assessment.

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 thirteen questions are of two kinds. The first three concern what the unit takes for granted from the previous one: unique readability, strong induction and the unfolding of abbreviations; anyone who misses one of them should review, before going on, the lesson that the question names. The remaining ten cover, in order, the five lessons of this unit: three the first, three the second, two the third, one the fourth and one the fifth. Anyone who has never studied a deductive system should not expect to get them right, and that does not matter: each 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.

Entry assessment

Before starting the unit, measure your starting point. It is a short self-assessment: it is not graded and its result is stored only in your browser.

Question 1From earlier unitsThe string $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ is a compound formula, of the form $\sigI\varphi\psi$ . What are its components $\varphi$ and $\psi$ ?
$\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ and $\psi = \sigO\sigI$ .
$\varphi = \sigI\sigO\sigI$ and $\psi = \sigO\sigO\sigI\sigO\sigI$ .
It admits two decompositions, depending on where the string is cut after the initial disk.
$\varphi$ is the whole string that follows the initial disk, and $\psi$ is the empty string.
Question 2From earlier unitsIn a proof by strong induction that every natural number $n$ has a property $P(n)$ , what may be assumed when proving $P(n)$ ?
That $P(m)$ holds for every natural number $m$ less than $n$ .
Only that $P(n - 1)$ holds.
That $P(m)$ holds for every natural number $m$ less than or equal to $n$ .
Nothing, until $P(1)$ and $P(2)$ have been proved separately.
Question 3From earlier unitsWith the official abbreviations of the course, which formula does $(\varphi \rightarrow \psi)$ designate, written with joint denial and negation?
$\neg(\neg\varphi \downarrow \psi)$ .
$(\neg\varphi \downarrow \psi)$ .
$\neg(\varphi \downarrow \neg\psi)$ .
None in particular: it depends on how one decides to read it.
Question 4Schema A1 is $(\varphi \rightarrow (\psi \rightarrow \varphi))$ . Is the formula $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ an instance of A1?
No: the same formula would have to be substituted for the first and the last occurrence of $\varphi$ , and here they are $v_{1}$ and $v_{3}$ .
Yes, with $\varphi := v_{1}$ and $\psi := v_{2}$ .
Yes, because every implication whose consequent is another implication is an instance of A1.
No, because the instances of a schema cannot contain variables.
Question 5A deduction already contains the lines $\psi$ and $(\varphi \rightarrow \psi)$ , where $\varphi$ and $\psi$ are distinct formulas. Which formula does modus ponens applied to those two lines allow one to write?
None: modus ponens requires the antecedent $\varphi$ , and what one has is the consequent.
$\varphi$ .
$(\psi \rightarrow \varphi)$ .
$\neg\varphi$ .
Question 6It is known that $\{\varphi\} \vdash \psi$ , that is, that there is a deduction of $\psi$ whose only premise is $\varphi$ . What does the deduction theorem then assert?
That $\vdash (\varphi \rightarrow \psi)$ : the implication is a theorem.
That $\vdash \psi$ : the premise can simply be dropped.
That $\vdash (\psi \rightarrow \varphi)$ .
That $\{\psi\} \vdash \varphi$ .
Question 7What is derivable, with no further premises, from the set $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ ?
$(\varphi \rightarrow \chi)$ .
$\chi$ , by applying modus ponens twice.
$(\chi \rightarrow \varphi)$ .
$(\varphi \wedge \chi)$ .
Question 8The rule of replacement of double negation (RDN) changes, in a line, a single occurrence of a subformula, and it acts on the string of the base language. How many occurrences of the subformula $\neg v_{1}$ does the string designated by $(v_{1} \rightarrow v_{2})$ contain?
Two.
One, the one corresponding to the antecedent.
None: the formula contains no negations.
Four.
Question 9Which formula is obtained from $(\neg\varphi \rightarrow \psi)$ by contraposition, without adding double negations?
$(\neg\psi \rightarrow \varphi)$ .
$(\psi \rightarrow \neg\varphi)$ .
$(\varphi \rightarrow \neg\psi)$ .
$(\neg\psi \rightarrow \neg\varphi)$ .
Question 10Do $(\varphi \vee \psi)$ and $(\neg\varphi \rightarrow \psi)$ designate the same formula?
No: the first is $\neg(\varphi \downarrow \psi)$ and the second, $\neg(\neg\neg\varphi \downarrow \psi)$ ; they are distinct formulas, equivalent by deduction.
Yes, by the definition of implication.
Yes, because both are read “ $\varphi$ or $\psi$ ”.
No, and neither is derivable from the other.
Question 11It is known that $\varphi \dashv\vdash \varphi'$ , that is, that each one is derivable from the other. What justifies that also $\neg\varphi \dashv\vdash \neg\varphi'$ ?
A theorem, the replacement of equivalents, which is proved with the deduction theorem and contraposition.
No special justification: it is enough to “negate both sides” of the equivalence.
The definition of negation, because $\neg\varphi$ is $(\varphi \downarrow \varphi)$ .
Nothing, because it is not true: negation can separate equivalent formulas.
Question 12From the set of premises $\Gamma \cup \{\neg\varphi\}$ one deduces a formula $\chi$ and its negation $\neg\chi$ . What can be concluded?
That $\Gamma \vdash \varphi$ .
That $\Gamma \vdash \neg\varphi$ .
That every formula is derivable from $\Gamma$ .
Nothing: a deduction that reaches a contradiction proves nothing.
Question 13To which formula is the negation of an implication, $\neg(\varphi \rightarrow \psi)$ , equivalent?
To $(\varphi \wedge \neg\psi)$ .
To $(\neg\varphi \rightarrow \neg\psi)$ .
To $(\varphi \rightarrow \neg\psi)$ .
To $(\neg\varphi \wedge \psi)$ .