M384 Logic
Week 3: The Logic of All p are q
Topics: the language \(\mathcal{A}\), its models and its semantics; the proof system with the rules (axiom) and (barbara); proof trees; soundness and completeness; induction on proof trees.
Source: L. S. Moss, Logic from Language, Chapter 1, Sections 1.1 to 1.3.
By the end of this week you will be able to:
- list all sentences of \(\mathcal{A}\) for a given set of nouns and decide which of them are true in a given model;
- prove \(\Gamma \models \varphi\) by an argument about an arbitrary model, and refute it by giving a countermodel;
- build proof trees over \(\Gamma\) with the rules (axiom) and (barbara), and check whether a given tree is a proof tree;
- state what soundness and completeness mean and explain why soundness is the easier half;
- prove a statement about all proof trees by induction on proof trees.
This week has two class days (Wednesday, September 9 and Friday, September 11).
Day 1 (Wednesday, September 9): Syntax and semantics of \(\mathcal{A}\)
Today we define our first real logical system: its sentences, its models, and what it means for a sentence to follow from a set of sentences.
- A model interprets each noun as a subset of a universe. A sentence is true or false only inside a model.
- \(\Gamma \models \varphi\) means: every model of all sentences in \(\Gamma\) is also a model of \(\varphi\) (Definition 0.3 from Week 2).
- The empty set is a subset of every set: \(\emptyset \subseteq X\) for all \(X\).
- Inclusion is reflexive and transitive: \(X \subseteq X\), and if \(X \subseteq Y\) and \(Y \subseteq Z\) then \(X \subseteq Z\).
The language \(\mathcal{A}\)
Every logical system in this course has a syntax and a semantics. Syntax is about the form of sentences; semantics is about their meaning. We begin with the syntax of the smallest system in the book. It has one kind of sentence and nothing else: no if, no and, no not.
We start with a collection \(\mathbf{P}\) of nouns. The nouns can be real words (usually plural animal names) or just letters \(p, q, n, \ldots\). The set \(\mathbf{P}\) may be finite or infinite.
The sentences of \(\mathcal{A}\) are the expressions
\(\All{p}{q}\)
where \(p\) and \(q\) are any nouns in \(\mathbf{P}\). There is nothing else in the language. The letter \(\mathcal{A}\) stands for "all".
Strictly speaking, \(\mathcal{A}\) is a family of languages, one for each set \(\mathbf{P}\). We usually do not mention \(\mathbf{P}\) unless it matters. Note that \(p\) and \(q\) may be the same noun, so \(\All{p}{p}\) is a sentence.
Let \(\mathbf{P} = \{n, p, q\}\). List all sentences of \(\mathcal{A}\).
A sentence is determined by an ordered pair of nouns (first noun, second noun). With 3 nouns there are \(3 \times 3 = 9\) pairs, so there are exactly nine sentences:
| \(\All{n}{n}\) | \(\All{n}{p}\) | \(\All{n}{q}\) |
| \(\All{p}{n}\) | \(\All{p}{p}\) | \(\All{p}{q}\) |
| \(\All{q}{n}\) | \(\All{q}{p}\) | \(\All{q}{q}\) |
In general, if \(\mathbf{P}\) has \(k\) nouns, then \(\mathcal{A}\) has \(k^2\) sentences. The order of the two nouns matters: \(\All{p}{q}\) and \(\All{q}{p}\) are different sentences.
Models and truth
The semantics tells us what the sentences mean. As in Week 2, meaning is given by models. A noun denotes a set of things, so a model interprets each noun as a subset of a universe.
A model for \(\mathcal{A}\) is a pair \(\mathbf{M} = (M, \sem{\ })\) consisting of a set \(M\), called the universe, together with an interpretation function
\(\sem{\ } : \mathbf{P} \to \mathcal{P}(M)\)
which assigns to every noun \(p \in \mathbf{P}\) a subset \(\sem{p} \subseteq M\). We read \(\sem{p}\) as "the meaning of \(p\) in \(\mathbf{M}\)".
We write \(\mathbf{M}\) for the model and \(M\) for its universe. The universe is a set; the model is a structure, a set together with an interpretation function. In practice we often name a model by its universe and let the context decide.
\(\mathbf{M} \models \All{p}{q} \quad\text{iff}\quad \sem{p} \subseteq \sem{q}.\)
We read this as "\(\mathbf{M}\) satisfies \(\All{p}{q}\)" or "\(\All{p}{q}\) is true in \(\mathbf{M}\)". If \(\sem{p} \not\subseteq \sem{q}\), we write \(\mathbf{M} \not\models \All{p}{q}\) and say that the sentence is false in \(\mathbf{M}\).
To show that \(\All{p}{q}\) is false in a model, you exhibit a witness: an element that belongs to \(\sem{p}\) but not to \(\sem{q}\). To show that it is true, you check that no such element exists.
Take \(\mathbf{P} = \{n, p, q\}\) as in Example 1. Let \(M = \{1,2,3,4,5\}\) and
\(\sem{n} = \emptyset, \qquad \sem{p} = \{1,3,4\}, \qquad \sem{q} = \{1,3\}.\)
Which of the nine sentences are true in this model \(\mathbf{M}\)? Figure 1 shows the model.
We check each sentence with Definition 1.4.
| Sentence | Inclusion to check | Truth value |
|---|---|---|
| \(\All{n}{n}\) | \(\emptyset \subseteq \emptyset\) | true |
| \(\All{n}{p}\) | \(\emptyset \subseteq \{1,3,4\}\) | true |
| \(\All{n}{q}\) | \(\emptyset \subseteq \{1,3\}\) | true |
| \(\All{p}{n}\) | \(\{1,3,4\} \subseteq \emptyset\) | false (witness 1) |
| \(\All{p}{p}\) | \(\{1,3,4\} \subseteq \{1,3,4\}\) | true |
| \(\All{p}{q}\) | \(\{1,3,4\} \subseteq \{1,3\}\) | false (witness 4) |
| \(\All{q}{n}\) | \(\{1,3\} \subseteq \emptyset\) | false (witness 1) |
| \(\All{q}{p}\) | \(\{1,3\} \subseteq \{1,3,4\}\) | true |
| \(\All{q}{q}\) | \(\{1,3\} \subseteq \{1,3\}\) | true |
Six sentences are true and three are false. Two points deserve attention.
First, \(\All{n}{p}\) and \(\All{n}{q}\) are true even though there are no \(n\)'s at all. This is because \(\emptyset\) is a subset of every set. In this logic, a sentence about an empty noun is always true.
Second, \(\All{p}{p}\) is true, and so is every sentence of the form \(\All{x}{x}\), in every model, because \(\sem{x} \subseteq \sem{x}\).
Let \(\mathbf{P} = \{\mathit{cats}, \mathit{pets}, \mathit{mammals}\}\), \(M = \{1,2,3,4,5,6\}\), and
\(\sem{\mathit{cats}} = \{1,2\}, \qquad \sem{\mathit{pets}} = \{2,3,4\}, \qquad \sem{\mathit{mammals}} = \{1,2,3,5\}.\)
Decide the truth value of each sentence.
(a) \(\All{\mathit{cats}}{\mathit{mammals}}\)
(b) \(\All{\mathit{cats}}{\mathit{pets}}\)
(c) \(\All{\mathit{pets}}{\mathit{mammals}}\)
(a) True. Both 1 and 2 belong to \(\{1,2,3,5\}\), so \(\{1,2\} \subseteq \{1,2,3,5\}\).
(b) False. Element 1 is in \(\sem{\mathit{cats}}\) but not in \(\sem{\mathit{pets}} = \{2,3,4\}\). One witness is enough.
(c) False. Element 4 is in \(\sem{\mathit{pets}}\) but not in \(\sem{\mathit{mammals}}\).
The English meaning of the nouns plays no role. Only the sets matter. A model is free to make "cats" and "pets" almost disjoint.
Semantic consequence
Once we have models and a definition of truth, we get the notion of consequence for free, exactly as in Week 2. In this chapter \(\Gamma\) always denotes a set of sentences of \(\mathcal{A}\); we also call \(\Gamma\) a set of assumptions or a theory.
\(\Gamma \models \varphi\) means: for every model \(\mathbf{M}\), if \(\mathbf{M} \models \psi\) for every \(\psi \in \Gamma\), then \(\mathbf{M} \models \varphi\).
\(\Gamma \not\models \varphi\) means: there is a model \(\mathbf{M}\) of all sentences in \(\Gamma\) with \(\mathbf{M} \not\models \varphi\). Such an \(\mathbf{M}\) is called a countermodel.
When \(\Gamma\) is written out explicitly, we drop the braces: we write \(\All{p}{q},\ \All{n}{p} \models \All{n}{q}\) instead of \(\{\All{p}{q}, \All{n}{p}\} \models \All{n}{q}\).
To show \(\Gamma \models \varphi\), take an arbitrary model of \(\Gamma\) and argue that \(\varphi\) must be true in it. One example model is not enough.
To show \(\Gamma \not\models \varphi\), give one concrete countermodel and check every sentence of \(\Gamma\) in it, then check that \(\varphi\) fails.
Show that \(\All{p}{q},\ \All{n}{p} \models \All{n}{q}\).
Let \(\mathbf{M}\) be any model (for a set of nouns containing \(n, p, q\)). Assume \(\mathbf{M} \models \All{p}{q}\) and \(\mathbf{M} \models \All{n}{p}\). We must show \(\mathbf{M} \models \All{n}{q}\).
By Definition 1.4, the first assumption says \(\sem{p} \subseteq \sem{q}\), and the second says \(\sem{n} \subseteq \sem{p}\). Inclusion of sets is transitive, so \(\sem{n} \subseteq \sem{q}\). By Definition 1.4 again, \(\mathbf{M} \models \All{n}{q}\).
Since \(\mathbf{M}\) was an arbitrary model of the two assumptions, we are done.
This is an informal proof: a short mathematical argument written in English. Tomorrow we will see formal proofs, which are objects built inside a proof system. Both kinds of proof are important, and it is worth keeping them apart.
Show that \(\All{p}{q} \not\models \All{q}{p}\).
We need a model where \(\All{p}{q}\) is true and \(\All{q}{p}\) is false. Take \(M = \{1,2\}\), \(\sem{p} = \{1\}\), \(\sem{q} = \{1,2\}\) (Figure 2).
Check the assumption: \(\{1\} \subseteq \{1,2\}\), so \(\mathbf{M} \models \All{p}{q}\).
Check the conclusion: \(2 \in \sem{q}\) but \(2 \notin \sem{p}\), so \(\mathbf{M} \not\models \All{q}{p}\).
One countermodel is enough, but there are many. The model \(N = \{61\}\), \(\sem{p} = \emptyset\), \(\sem{q} = \{61\}\) also works: \(\emptyset \subseteq \{61\}\) and \(\{61\} \not\subseteq \emptyset\).
Does \(\All{p}{q},\ \All{r}{q} \models \All{p}{r}\)?
No. Two nouns can both be included in \(q\) without being included in each other. Take \(M = \{1,2\}\), \(\sem{p} = \{1\}\), \(\sem{r} = \{2\}\), \(\sem{q} = \{1,2\}\).
Assumptions: \(\{1\} \subseteq \{1,2\}\) and \(\{2\} \subseteq \{1,2\}\), so both sentences of \(\Gamma\) are true.
Conclusion: \(1 \in \sem{p}\) but \(1 \notin \sem{r}\), so \(\All{p}{r}\) is false.
Compare with Example 4. There the middle noun \(p\) appeared on the right of one assumption and on the left of the other, which is exactly what transitivity needs. Here \(q\) appears on the right of both, and transitivity does not apply.
Here is a larger question of the same kind. Let
\(\Gamma = \{\All{j}{k},\ \All{j}{l},\ \All{k}{l},\)
\(\All{l}{k},\ \All{l}{m},\ \All{k}{n},\)
\(\All{m}{q},\ \All{p}{q},\ \All{q}{p}\}.\)
Is \(\Gamma \models \All{p}{n}\)? You can settle this one by hand. The real question is whether there is an algorithm that settles every question of this form, and how to prove that the algorithm is correct. Tomorrow's proof system is the first step toward the answer; the full answer comes in Section 1.6.
Day 2 (Friday, September 11): The proof system and induction on proof trees
Today we turn from meaning to form: a proof system with two rules, the trees it builds, and the induction principle that lets us prove something about every proof tree at once.
- \(\mathbf{M} \models \All{p}{q}\) iff \(\sem{p} \subseteq \sem{q}\); and \(\Gamma \models \varphi\) iff every model of \(\Gamma\) satisfies \(\varphi\).
- Every sentence \(\All{x}{x}\) is true in every model, and \(\subseteq\) is transitive.
- A definition that builds objects step by step (an inductive definition) comes with a matching proof principle (proof by induction). You have seen this for the natural numbers.
Two rules
So far everything was semantic: defined in terms of models. A proof system is purely syntactic. It tells us which sentences may be written below which other sentences, without any reference to models or meaning. The proof system for \(\mathcal{A}\) is called \(\mathsf{A}\) (same letter, different font, because a language does not automatically come with a proof system).
In each rule, the sentences above the line are the premises and the sentence below the line is the conclusion. The rule (axiom) has no premises.
The rule (barbara) says: a node labeled \(\All{p}{q}\) may have two nodes above it, one labeled \(\All{p}{n}\) and the other \(\All{n}{q}\), for some noun \(n\). The rule (axiom) says: a node labeled \(\All{p}{p}\) needs nothing above it. The name "barbara" comes from medieval logic, where universal statements were coded by the letter A and the three A's of this rule were padded with consonants to make a word.
- If \(\All{x}{y}\) belongs to \(\Gamma\), then the one-point tree labeled \(\All{x}{y}\) is a proof tree over \(\Gamma\). This point is both the root and the only leaf; no rule is written.
- For every noun \(x\), the one-point tree labeled \(\All{x}{x}\), justified by (axiom), is a proof tree over \(\Gamma\).
- If \(T_1\) and \(T_2\) are proof trees over \(\Gamma\) whose roots are \(\All{x}{y}\) and \(\All{y}{z}\) respectively, then the tree \(T\) obtained by putting \(T_1\) on the left, \(T_2\) on the right, and a new root \(\All{x}{z}\) below them, justified by (barbara), is a proof tree over \(\Gamma\) (Figure 3).
We write \(\Gamma \vdash \varphi\) if there is a proof tree over \(\Gamma\) whose root is \(\varphi\). We read this as "\(\Gamma\) proves \(\varphi\)" or "\(\varphi\) follows from \(\Gamma\) in \(\mathsf{A}\)".
Two remarks on the definition. First, a leaf that is not an axiom must be a sentence of \(\Gamma\); nothing else may appear at the top of a tree. Second, not every sentence of \(\Gamma\) has to be used. A proof tree is allowed to ignore assumptions.
Let \(\Gamma = \{\All{l}{m},\ \All{q}{l},\ \All{m}{p},\ \All{n}{p},\ \All{l}{q}\}\). Show that \(\Gamma \vdash \All{q}{p}\).
We verify that this is a proof tree over \(\Gamma\) by walking through Definition 1.10 from the top down.
The leaves \(\All{q}{l}\), \(\All{l}{m}\), and \(\All{m}{p}\) belong to \(\Gamma\), so each is a one-point proof tree (clause 1). The leaf \(\All{m}{m}\) is an axiom (clause 2).
The node \(\All{l}{m}\) in the middle is obtained by (barbara) from \(\All{l}{m}\) and \(\All{m}{m}\), with middle noun \(m\) (clause 3). The node \(\All{l}{p}\) is obtained from \(\All{l}{m}\) and \(\All{m}{p}\), with middle noun \(m\). The root \(\All{q}{p}\) is obtained from \(\All{q}{l}\) and \(\All{l}{p}\), with middle noun \(l\).
Two further observations. The sentences \(\All{n}{p}\) and \(\All{l}{q}\) of \(\Gamma\) are not used; that is allowed. And there is a smaller proof tree with the same root: delete the axiom and the (barbara) step above it, and use the leaf \(\All{l}{m}\) directly. The rule (axiom) exists so that sentences \(\All{x}{x}\) can be proved even when \(\Gamma\) says nothing about \(x\).
When trees get wide we often drop the rule names; the shape of the tree makes clear which rule is used at each node.
Let \(\Gamma = \{\All{a}{b},\ \All{b}{c},\ \All{c}{d}\}\). Show that \(\Gamma \vdash \All{a}{d}\) in two different ways.
Both trees below are proof trees over \(\Gamma\) with root \(\All{a}{d}\).
In the first tree we combine \(\All{a}{b}\) and \(\All{b}{c}\) first (middle noun \(b\)), then use \(c\) as the middle noun at the root. In the second tree we combine \(\All{b}{c}\) and \(\All{c}{d}\) first, then use \(b\) at the root. All leaves are in \(\Gamma\), and each (barbara) step has matching middle nouns, so both are proof trees. \(\Gamma \vdash \varphi\) only asks for the existence of some proof tree.
Let \(\Gamma = \{\All{a}{b},\ \All{b}{c},\ \All{c}{d}\}\) as in Example 8. Explain why neither tree below is a proof tree over \(\Gamma\).
(a) In the first tree the leaf \(\All{a}{c}\) is neither a sentence of \(\Gamma\) nor an axiom. A leaf must be one of these two. The sentence \(\All{a}{c}\) is provable from \(\Gamma\), but then it must appear as the root of its own subtree, as in Example 8; it cannot simply be written at the top.
(b) In the second tree both leaves are in \(\Gamma\), but the step is not an instance of (barbara): the second noun of the left premise is \(b\) and the first noun of the right premise is \(c\). The rule requires these to be the same middle noun.
The conclusion \(\All{a}{d}\) is correct in both cases, but a proof tree is judged by its form, not by whether its root happens to be true.
The language \(\mathcal{A}\) does not come with the proof system \(\mathsf{A}\); we chose the two rules. We could add a third rule, for example one that concludes \(\All{w}{z}\) directly from three premises \(\All{w}{x}\), \(\All{x}{y}\), \(\All{y}{z}\). That would be a different proof system for the same language. It would not prove anything new, since the new rule can be simulated by two (barbara) steps, but the trees would look different.
Soundness and completeness
We now have two relations between \(\Gamma\) and \(\varphi\): the semantic relation \(\Gamma \models \varphi\), defined by models, and the syntactic relation \(\Gamma \vdash \varphi\), defined by proof trees. The main work of this chapter is to connect them, in both directions.
A proof system is sound for a semantics if whenever \(\Gamma \vdash \varphi\), also \(\Gamma \models \varphi\).
A proof system is complete for a semantics if whenever \(\Gamma \models \varphi\), also \(\Gamma \vdash \varphi\).
Soundness says the system never proves a false consequence. Completeness says the system is strong enough to prove every true consequence. We prove soundness today (Proposition 1.14). Completeness comes later in the chapter and needs different tools.
Induction on proof trees
Definition 1.10 is an inductive definition: it starts with the simplest proof trees (one-point trees) and says how to build a new proof tree from two given ones. Whenever a class of objects is defined this way, the main tool for proving something about all objects in the class is proof by induction. For the natural numbers the steps are "prove it for 0" and "prove it for \(n+1\) assuming it for \(n\)". For proof trees the steps follow the three clauses of the definition.
Suppose we want to prove a statement of the form "for all proof trees \(T\) over \(\Gamma\), \(S(T)\)". It is enough to do the following three steps.
- Prove \(S(T)\) for every one-point tree \(T\) labeled with a sentence \(\All{x}{y}\) of \(\Gamma\).
- Prove \(S(T)\) for every one-point tree \(T\) labeled \(\All{x}{x}\) and justified by (axiom).
- Let \(T\) be built by (barbara) from \(T_1\) and \(T_2\) as in Figure 3. Assume \(S(T_1)\) and \(S(T_2)\) (the induction hypotheses), and prove \(S(T)\).
After these steps, \(S(T)\) holds for every proof tree \(T\) over \(\Gamma\).
Why does this work? Every proof tree is built in finitely many steps from one-point trees. Steps 1 and 2 cover the starting trees; step 3 shows that the property is preserved by the only building operation. So there is no way to build a tree without the property.
For every proof tree \(T\) over \(\Gamma\), every noun that occurs in \(T\) also occurs in some leaf of \(T\).
We write out this first induction in full. Let \(S(T)\) be the statement "every noun occurring in \(T\) occurs in some leaf of \(T\)".
Step 1. Let \(T\) be the one-point tree labeled by a sentence \(\All{u}{v}\) of \(\Gamma\). The nouns occurring in \(T\) are \(u\) and \(v\). The only leaf of \(T\) is its single node, and both nouns occur there. So \(S(T)\) holds.
Step 2. Let \(T\) be the one-point tree \(\All{k}{k}\) justified by (axiom). The only noun is \(k\), the only leaf is the node itself, and \(k\) occurs there. So \(S(T)\) holds.
Step 3. Let \(T\) be obtained by (barbara) from \(T_1\) and \(T_2\), with roots \(\All{n}{l}\) and \(\All{l}{m}\), so the root of \(T\) is \(\All{n}{m}\). Assume \(S(T_1)\) and \(S(T_2)\). Take any noun \(x\) that occurs in \(T\). Then \(x\) occurs in \(T_1\), or in \(T_2\), or in the root of \(T\).
If \(x\) occurs in \(T_1\), then by \(S(T_1)\) it occurs in a leaf of \(T_1\). Every leaf of \(T_1\) is a leaf of \(T\), so we are done. The case of \(T_2\) is the same.
If \(x\) occurs in the root \(\All{n}{m}\), then \(x = n\) or \(x = m\). If \(x = n\), then \(x\) occurs in the root \(\All{n}{l}\) of \(T_1\), hence in \(T_1\), and the previous case applies. If \(x = m\), it occurs in the root of \(T_2\), and again the previous case applies.
In every case \(x\) occurs in a leaf of \(T\), so \(S(T)\) holds. This completes the induction.
If \(\Gamma \vdash \varphi\), then \(\Gamma \models \varphi\).
We prove the following statement \(S(T)\) for all proof trees \(T\) over \(\Gamma\): "every model of \(\Gamma\) satisfies the root of \(T\)". If we have this, then whenever \(\Gamma \vdash \varphi\) there is a tree with root \(\varphi\), and \(S\) of that tree says exactly \(\Gamma \models \varphi\).
Step 1. \(T\) is a one-point tree labeled by a sentence \(\varphi \in \Gamma\). A model of \(\Gamma\) satisfies every sentence of \(\Gamma\), in particular \(\varphi\). So \(S(T)\) holds.
Step 2. \(T\) is the one-point tree \(\All{p}{p}\) justified by (axiom). In every model \(\sem{p} \subseteq \sem{p}\), so \(\All{p}{p}\) is true in every model whatsoever, in particular in every model of \(\Gamma\). So \(S(T)\) holds.
Step 3. \(T\) has root \(\All{n}{q}\), obtained by (barbara) from \(T_1\) with root \(\All{n}{p}\) and \(T_2\) with root \(\All{p}{q}\). The induction hypotheses say: every model of \(\Gamma\) satisfies \(\All{n}{p}\), and every model of \(\Gamma\) satisfies \(\All{p}{q}\). Fix a model \(\mathbf{M}\) of \(\Gamma\). Then \(\sem{n} \subseteq \sem{p}\) and \(\sem{p} \subseteq \sem{q}\), so by transitivity of \(\subseteq\), \(\sem{n} \subseteq \sem{q}\); that is, \(\mathbf{M} \models \All{n}{q}\). Since \(\mathbf{M}\) was an arbitrary model of \(\Gamma\), \(S(T)\) holds.
By Definition 1.15, \(S(T)\) holds for every proof tree over \(\Gamma\), which proves the proposition.
Every soundness proof in this course has this shape: an induction on proof trees where each rule is checked separately, and the heart of each check is a simple fact about sets. For (barbara) the fact is transitivity of \(\subseteq\); for (axiom) it is reflexivity. Later we will usually not write soundness proofs out.
Soundness is also a weak statement. If we deleted (barbara), the system would still be sound. If we deleted both rules, so that \(\Gamma \vdash \varphi\) never held, the system would still be sound. The interesting question is whether the system proves enough, and that is completeness.
Prove that for every proof tree \(T\) over \(\Gamma\), the number of leaves of \(T\) is one more than the number of nodes justified by (barbara). (Leaves are the one-point subtrees: sentences from \(\Gamma\) and axioms.)
Write \(\ell(T)\) for the number of leaves and \(b(T)\) for the number of (barbara) nodes. The statement is \(S(T)\): \(\ell(T) = b(T) + 1\).
Step 1. A one-point tree from \(\Gamma\) has one leaf and no (barbara) node: \(1 = 0 + 1\).
Step 2. An axiom tree also has one leaf and no (barbara) node: \(1 = 0 + 1\).
Step 3. Let \(T\) be built from \(T_1\) and \(T_2\) by (barbara), and assume \(\ell(T_1) = b(T_1) + 1\) and \(\ell(T_2) = b(T_2) + 1\). The leaves of \(T\) are exactly the leaves of \(T_1\) together with the leaves of \(T_2\), so \(\ell(T) = \ell(T_1) + \ell(T_2)\). The (barbara) nodes of \(T\) are those of \(T_1\), those of \(T_2\), and the new root, so \(b(T) = b(T_1) + b(T_2) + 1\). Therefore
\(\ell(T) = (b(T_1) + 1) + (b(T_2) + 1) = (b(T_1) + b(T_2) + 1) + 1 = b(T) + 1.\)
This completes the induction. You can check it on Example 7: four leaves and three (barbara) nodes.
Homework 3
M384 Logic, Week 3. Total: 100 points.
- Fill in your name and surname in the field below before saving the PDF.
- Show your work. Answers without reasons receive no credit, and each countermodel must be checked against every sentence of \(\Gamma\).
- Each question has two answer modes: Type and Write by hand. In "Write by hand" the text boxes are replaced by a drawing area where you can write with a pen, your finger, or the mouse. Only the answer of the mode selected for each question goes into the PDF; switching modes does not delete what you entered in the other mode.
- Your answers are saved automatically in this browser. If you open the file on a different computer or in a different browser, they will not be there.
- When finished, click "Save homework as PDF", check that all your answers appear, and upload the PDF to Canvas.
Question 1 (20 points)
Let \(\mathbf{P} = \{\mathit{ants}, \mathit{bees}, \mathit{insects}, \mathit{flyers}\}\). Consider the model \(\mathbf{M}\) with universe \(M = \{1,2,3,4,5,6\}\) and
\(\sem{\mathit{ants}} = \{1,2\}, \quad \sem{\mathit{bees}} = \{3,4\}, \quad \sem{\mathit{insects}} = \{1,2,3,4,5\}, \quad \sem{\mathit{flyers}} = \{3,4,6\}.\)
(a) For each sentence below, say whether it is true or false in \(\mathbf{M}\). If it is false, give a witness: an element of the first set that is not in the second.
| Sentence | Truth value | Witness (if false) |
|---|---|---|
| \(\All{\mathit{ants}}{\mathit{insects}}\) | ||
| \(\All{\mathit{bees}}{\mathit{flyers}}\) | ||
| \(\All{\mathit{flyers}}{\mathit{bees}}\) | ||
| \(\All{\mathit{insects}}{\mathit{flyers}}\) | ||
| \(\All{\mathit{ants}}{\mathit{bees}}\) | ||
| \(\All{\mathit{bees}}{\mathit{insects}}\) | ||
| \(\All{\mathit{flyers}}{\mathit{flyers}}\) | ||
| \(\All{\mathit{insects}}{\mathit{insects}}\) |
(b) Give a model \(\mathbf{N}\) for the same nouns in which \(\All{\mathit{flyers}}{\mathit{bees}}\) is true, \(\All{\mathit{bees}}{\mathit{flyers}}\) is false, and \(\All{\mathit{ants}}{\mathit{insects}}\) is true. Write the universe and all four sets, and check the three sentences.
Question 2 (25 points)
Let \(\Gamma = \{\All{p}{q},\ \All{q}{r},\ \All{s}{q}\}\).
(a) Prove that \(\Gamma \models \All{p}{r}\). Argue about an arbitrary model of \(\Gamma\), as in Example 4.
(b) Does \(\Gamma \models \All{s}{p}\)? If yes, prove it. If no, give a countermodel: write the universe and the four sets, then verify each sentence of \(\Gamma\) and show that \(\All{s}{p}\) fails.
(c) Does \(\Gamma \models \All{p}{s}\)? Answer in the same way as in (b).
Question 3 (25 points)
Let \(\mathbf{P} = \{j,k,l,m,n\}\) and \(\Gamma = \{\All{k}{m},\ \All{j}{k},\ \All{m}{n},\ \All{n}{m},\ \All{l}{j}\}\).
(a) Give a proof tree over \(\Gamma\) with root \(\All{l}{n}\). The root is fixed; build the tree upward. The editor does not check your tree.
(b) Give a proof tree over \(\Gamma\) with root \(\All{m}{m}\) that uses the rule (barbara) at least once.
(c) Is \(\All{n}{k}\) provable from \(\Gamma\)? Give a complete argument. If you use a result from this week, name it and say exactly where it is used.
Question 4 (30 points)
(a) Let \(\Gamma\) be any set of sentences of \(\mathcal{A}\). Prove by induction on proof trees over \(\Gamma\) (Definition 1.15) the following statement \(S(T)\):
if the root of \(T\) is \(\All{p}{q}\) with \(p \neq q\), then \(\Gamma\) contains a sentence of the form \(\All{p}{r}\) for some noun \(r\).
Write the three steps separately and say clearly where the induction hypotheses are used.
(b) Let \(\Gamma = \{\All{a}{b},\ \All{b}{c},\ \All{c}{d}\}\). Use part (a) to show that \(\Gamma \nvdash \All{d}{a}\), without using any model.
(c) For the same \(\Gamma\), give a countermodel showing \(\Gamma \not\models \All{d}{a}\), and check it.
(d) Parts (b) and (c) establish \(\Gamma \nvdash \All{d}{a}\) and \(\Gamma \not\models \All{d}{a}\) by different routes. Which of soundness and completeness would allow you to deduce (b) from (c)? Which would allow you to deduce (c) from (b)? Explain in each case which direction of Definition 1.12 is used.