Monday: building models, the completeness proof for A, and a decision procedure. Wednesday and Friday: the classical syllogistic \(\mathcal S\). The four categorical sentence forms, their exact truth conditions, and the proof system.
By the end of this week you will be able to:
Today we build a model out of the syntax of \(\mathcal A\), use it to prove completeness, and turn that proof into an algorithm that returns either a proof tree or a counter-model.
We proved soundness: if \(\Gamma\vdash\varphi\) then \(\Gamma\vDash\varphi\). The open question is the other direction.
The completeness proof starts from a simple idea. The proof system tells us, for each pair of nouns, whether one is provably included in the other. That relation between nouns already looks like an ordering, so let us name it.
Let \(\Gamma\) be a set of sentences. For nouns \(u,v\) write \[u\le_\Gamma v \quad\text{iff}\quad \Gamma\vdash \text{All } u \text{ are } v.\] We drop the subscript and write \(u\le v\) when \(\Gamma\) is clear.
For instance, if \(\Gamma=\{\text{All }a\text{ are }b,\ \text{All }b\text{ are }c\}\), then \(a\le b\) and \(b\le c\) by one-point trees, and \(a\le c\) by one application of (barbara).
For every \(\Gamma\), the pair \((\mathsf P,\le_\Gamma)\) is a preorder.
Reflexivity. For any noun \(u\), the one-point tree justified by (axiom) proves All \(u\) are \(u\). So \(u\le u\). This is exactly what (axiom) is in the system for.
Transitivity. Suppose \(u\le v\) and \(v\le w\). Take a proof tree \(T_1\) with root All \(u\) are \(v\) and a proof tree \(T_2\) with root All \(v\) are \(w\). Put them side by side and apply (barbara). The result is a proof tree over \(\Gamma\) with root All \(u\) are \(w\), so \(u\le w\). □
The two rules of the system are therefore not an arbitrary pair. They are precisely what is needed to make \(\le_\Gamma\) reflexive and transitive.
In a preorder \(P\), the down-set of an element \(p\) is \[\downarrow\! p=\{q\in P: q\le p\}.\]
For instance, in a preorder with \(a\le b\le c\) and nothing else besides the reflexive pairs, \(\downarrow\! c=\{a,b,c\}\), \(\downarrow\! b=\{a,b\}\) and \(\downarrow\! a=\{a\}\).
We now build a model. The surprising part is where the material comes from: the points of the model are the nouns of the language, and the interpretation of a noun is read off from the proof system.
Let \(\Gamma\) be a set of sentences of \(\mathcal A\). The canonical model \(\mathcal M=(M,[\![\ ]\!])\) is given by \[M=\mathsf P,\qquad [\![u]\!]=\ \downarrow\! u=\{v\in\mathsf P:\Gamma\vdash \text{All } v \text{ are } u\}.\]
In words: the universe is the set of nouns, and a noun \(u\) denotes the set of all nouns that \(\Gamma\) proves to be included in \(u\).
Let \(\mathsf P=\{a,b,c,d\}\) and \[\Gamma=\{\text{All }a\text{ are }b,\ \ \text{All }b\text{ are }c,\ \ \text{All }d\text{ are }c\}.\]
Step 1: find what is provable. From All \(a\) are \(b\) and All \(b\) are \(c\), (barbara) gives All \(a\) are \(c\). Adding the three sentences of \(\Gamma\), the reflexive instances from (axiom), and nothing else, the provable sentences are
All \(a\) are \(a\), All \(a\) are \(b\), All \(a\) are \(c\), All \(b\) are \(b\), All \(b\) are \(c\), All \(c\) are \(c\), All \(d\) are \(c\), All \(d\) are \(d\).
Step 2: read off the down-sets. \([\![u]\!]\) collects the nouns \(v\) with \(\Gamma\vdash\) All \(v\) are \(u\), so we scan the list above for sentences ending in \(u\):
\([\![a]\!]=\{a\}\qquad [\![b]\!]=\{a,b\}\qquad [\![c]\!]=\{a,b,c,d\}\qquad [\![d]\!]=\{d\}\)
Step 3: check the model against \(\Gamma\). All \(a\) are \(b\) needs \(\{a\}\subseteq\{a,b\}\): true. All \(b\) are \(c\) needs \(\{a,b\}\subseteq\{a,b,c,d\}\): true. All \(d\) are \(c\) needs \(\{d\}\subseteq\{a,b,c,d\}\): true. So this model satisfies \(\Gamma\).
Step 4: use it as a test. Is All \(c\) are \(b\) true here? That needs \(\{a,b,c,d\}\subseteq\{a,b\}\), which fails, since \(c\notin\{a,b\}\). So the canonical model is a model of \(\Gamma\) in which All \(c\) are \(b\) is false, and therefore \(\Gamma\nvDash\) All \(c\) are \(b\).
Step 3 of the example was not luck. It happens for every \(\Gamma\).
The canonical model of \(\Gamma\) satisfies \(\Gamma\).
Let All \(p\) are \(q\) belong to \(\Gamma\). That is a one-point proof tree, so \(p\le q\). We must show \([\![p]\!]\subseteq[\![q]\!]\). Take \(v\in[\![p]\!]\). By Definition 4.4 this means \(v\le p\). Since \(\le\) is transitive (Proposition 4.2) and \(p\le q\), we get \(v\le q\), that is, \(v\in[\![q]\!]\). As \(v\) was arbitrary, \([\![p]\!]\subseteq[\![q]\!]\). □
If \(\Gamma\vDash\) All \(p\) are \(q\), then \(\Gamma\vdash\) All \(p\) are \(q\).
Let \(\mathcal M\) be the canonical model of \(\Gamma\). By Lemma 4.6, \(\mathcal M\vDash\Gamma\). Our hypothesis says every model of \(\Gamma\) satisfies All \(p\) are \(q\), so in particular \(\mathcal M\vDash\) All \(p\) are \(q\). By the definition of truth, \([\![p]\!]\subseteq[\![q]\!]\).
Now we only need one element of \([\![p]\!]\), and there is an obvious candidate. Since \(p\le p\) by (axiom), we have \(p\in[\![p]\!]\). Hence \(p\in[\![q]\!]\), which by Definition 4.4 says \(\Gamma\vdash\) All \(p\) are \(q\). □
The proof shows more than it claims. If \(\Gamma\nvdash\) All \(p\) are \(q\), then All \(p\) are \(q\) is already false in the canonical model. So to settle whether a sentence follows from \(\Gamma\), you never have to look at more than one model. A model with this property is called a characteristic model of \(\Gamma\).
Building a model out of syntactic objects can look like a category mistake at first. It is not. A model is a set with an interpretation function, and nothing stops the set from being a set of nouns. Completeness is a statement about the relation between syntax and semantics, so it is reasonable that one structure carrying both aspects settles it.
Completeness is a theorem about all \(\Gamma\) and all \(\varphi\). It does not yet tell you what to do when someone hands you a specific finite \(\Gamma\) and a specific \(\varphi\). For that we reorganise the same information as a graph.
A graph is a pair \(\mathcal G=(G,\to)\) with \(G\) a set of nodes and \(\to\) a relation on \(G\).
A path from \(g\) to \(h\) is a finite sequence of nodes, each joined to the next by an edge. We write \(g\to^{*}h\) when such a path exists. Paths of length \(0\) are allowed, so \(g\to^{*}g\) always holds. The relation \(\to^{*}\) is the reflexive-transitive closure of \(\to\).
Given \(\Gamma\subseteq\mathcal A\) and a set \(S\) of nouns, the all-graph \(\mathcal G_{\Gamma,S}\) has node set \(S\) and \[x\to_\Gamma y \quad\text{iff}\quad \text{All } x \text{ are } y \text{ belongs to }\Gamma.\] The graph is read straight off \(\Gamma\): one edge per sentence, no reasoning involved.
For instance, with \(\Gamma=\{\text{All }a\text{ are }b,\ \text{All }b\text{ are }c\}\) and \(S=\{a,b,c\}\), the all-graph has the two edges \(a\to b\) and \(b\to c\). Then \(a\to^{*}c\) via the path \(a\to b\to c\), while \(c\to^{*}a\) fails because no edge leaves \(c\).
Let \(\Gamma\) be a set of sentences of \(\mathcal A\), let \(S\) contain every noun occurring in \(\Gamma\), let \(\mathcal G\) be the all-graph of \(\Gamma\) on \(S\), and let \(p,q\in S\). The following are equivalent:
(1)⇒(2). Induction on the length \(n\) of a path from \(p\) to \(q\). If \(n=0\) then \(p=q\) and (axiom) proves All \(p\) are \(p\). Suppose the claim holds for \(n\), and let a path of length \(n+1\) run from \(p\) to \(q\), with \(q'\) the node just before \(q\). The initial segment has length \(n\), so by induction hypothesis \(\Gamma\vdash\) All \(p\) are \(q'\). The last edge means All \(q'\) are \(q\) is in \(\Gamma\). One application of (barbara) at the bottom finishes it.
(2)⇒(3). This is soundness.
(3)⇒(1). We prove the contrapositive. Assume \(p\not\to_\Gamma^{*}q\), and let \(\mathcal N\) have universe \(S\) with \([\![u]\!]=\{v\in S: v\to^{*}_\Gamma u\}\). First, \(\mathcal N\vDash\Gamma\): if All \(x\) are \(y\) is in \(\Gamma\) and \(z\in[\![x]\!]\), then a path from \(z\) to \(x\) extended by the edge \(x\to y\) is a path from \(z\) to \(y\), so \(z\in[\![y]\!]\). Second, \(p\in[\![p]\!]\) because of the empty path, while \(p\notin[\![q]\!]\) by assumption. So \(\mathcal N\nvDash\) All \(p\) are \(q\). □
Notice that the model \(\mathcal N\) in the last part is the canonical model again, cut down to the finitely many nouns that actually occur. That is what makes the whole thing computable.
Let \(\Gamma=\{\text{All }a\text{ are }b,\ \text{All }b\text{ are }c,\ \text{All }c\text{ are }d\}\). The path \(a\to b\to c\to d\) has three edges, so the tree has three leaves from \(\Gamma\) and two applications of (barbara), each one consuming the next edge:
A path with \(n\) edges gives a tree with \(n-1\) applications of (barbara); a path with \(0\) edges gives the one-point tree justified by (axiom).
Let \(\mathsf P=\{j,k,l,m,n,p,q\}\) and let \(\Gamma\) consist of
All \(j\) are \(k\), All \(j\) are \(l\), All \(k\) are \(l\), All \(l\) are \(k\), All \(l\) are \(m\), All \(k\) are \(n\), All \(m\) are \(q\), All \(p\) are \(q\), All \(q\) are \(p\).
Question: does \(\Gamma\vDash\) All \(p\) are \(n\)?
Steps 1–2. \(S\) is all seven nouns. The all-graph has nine edges, one per sentence (Figure 1).
Step 3. Follow the arrows from \(p\). We can reach \(q\), and from \(q\) we return to \(p\). There is no edge out of \(p\) or \(q\) to anywhere else, so the only nodes reachable from \(p\) are \(p\) and \(q\).
Step 4–5. In particular \(p\not\to^{*}n\), so the answer is no, and the algorithm hands back a counter-model. Its universe is \(S\), and each \([\![u]\!]\) is the set of nodes from which \(u\) can be reached:
\([\![j]\!]=\{j\}\), \([\![k]\!]=[\![l]\!]=\{j,k,l\}\), \([\![m]\!]=\{j,k,l,m\}\), \([\![n]\!]=\{j,k,l,n\}\), \([\![p]\!]=[\![q]\!]=\{j,k,l,m,p,q\}\).
Check the conclusion: \(p\in[\![p]\!]\) but \(p\notin[\![n]\!]\), so All \(p\) are \(n\) is false here, while all nine sentences of \(\Gamma\) are true. It is often easier to see this in the associated preorder, drawn as a Hasse diagram in Figure 2: nouns that reach each other are merged into one node, and \([\![u]\!]\) is everything at or below \(u\).
Self-check only. Nothing here counts towards your grade.
Let \(\mathsf P=\{a,b,c,d,e,f,g,h\}\) and let \(\Gamma\) consist of the ten sentences
All \(a\) are \(b\), All \(b\) are \(c\), All \(c\) are \(a\), All \(c\) are \(d\), All \(d\) are \(f\), All \(f\) are \(e\), All \(e\) are \(d\), All \(e\) are \(g\), All \(g\) are \(h\), All \(b\) are \(h\).
Draw the all-graph on paper first. Then work through Algorithm 4.11 for each of the following claims.
(a) Does the entailment hold?
(b) For the claim \(\Gamma\vDash\) All \(b\) are \(e\), give a path in the all-graph that witnesses it. Type the nouns along the path in order, separated by commas, starting with \(b\) and ending with \(e\). Any correct path is accepted.
(c) For the claim \(\Gamma\vDash\) All \(f\) are \(c\), the algorithm returns the counter-model \(\mathcal N\) with universe \(S\). Write down \([\![c]\!]\) and \([\![f]\!]\) in \(\mathcal N\), as comma-separated lists of nouns.
\([\![c]\!]=\)
\([\![f]\!]=\)
The all-graph has two cycles, \(a\to b\to c\to a\) and \(d\to f\to e\to d\), joined by the edge \(c\to d\), and then a tail \(e\to g\to h\) with a shortcut \(b\to h\).
(a) All \(b\) are \(e\): yes, \(b\to c\to d\to f\to e\). All \(f\) are \(c\): no; from \(f\) you can only reach \(d,e,f,g,h\), and none of the edges into the first cycle starts there. All \(a\) are \(h\): yes, \(a\to b\to h\). All \(g\) are \(d\): no; \(g\) reaches only \(g\) and \(h\).
(b) \(b,c,d,f,e\). Going round a cycle first, as in \(b,c,a,b,c,d,f,e\), is also a path; it just gives a bigger proof tree.
(c) \([\![c]\!]=\{a,b,c\}\) and \([\![f]\!]=\{a,b,c,d,e,f\}\). Since \(f\in[\![f]\!]\) but \(f\notin[\![c]\!]\), All \(f\) are \(c\) fails in \(\mathcal N\), while every sentence of \(\Gamma\) holds there.
Self-check only. Nothing here counts towards your grade.
Let \(\mathsf P=\{m,n,p,q,r,s\}\) and let \(\Gamma\) consist of
All \(m\) are \(n\), All \(n\) are \(p\), All \(p\) are \(m\), All \(q\) are \(p\), All \(r\) are \(q\), All \(q\) are \(s\), All \(s\) are \(q\).
Let \(\varphi\) be All \(p\) are \(s\). Decide with the algorithm whether \(\Gamma\vDash\varphi\). If it does not, enter a model of \(\Gamma\) in which \(\varphi\) is false. The universe below is \(S=\mathsf P\) itself, so you can enter the model \(\mathcal N\) from step 5 of the algorithm directly, but any model that does the job is accepted; the check evaluates your model, it does not compare it with a stored one.
Rows are the nouns being interpreted; columns are the elements of the universe. Tick the cell in row \(u\), column \(v\) to put the element \(v\) into \([\![u]\!]\).
From \(p\) the only nodes reachable are \(p, m, n\) (the cycle \(m\to n\to p\to m\)); the edge \(q\to p\) points into that cycle, not out of it. So \(p\not\to^{*}s\) and \(\Gamma\nvDash\varphi\).
Step 5 of the algorithm gives \([\![u]\!]=\{v: v\to^{*}u\}\):
\([\![m]\!]=[\![n]\!]=[\![p]\!]=\{m,n,p,q,r,s\}\), \([\![q]\!]=[\![s]\!]=\{q,r,s\}\), \([\![r]\!]=\{r\}\).
Then \(p\in[\![p]\!]\) but \(p\notin[\![s]\!]\). A smaller model also works: put a single element into exactly \([\![m]\!],[\![n]\!],[\![p]\!]\), the nouns reachable from \(p\), and leave the other three sets empty.
Today we add Some and No to the language, give each of the four classical sentence forms an exact truth condition, and check which claims of the traditional square of opposition survive.
We keep the nouns and the models of the previous chapter and add two new sentence formers.
Starting from a set \(\mathsf P\) of nouns, the sentences of \(\mathcal S\) are
All \(p\) are \(q\), Some \(p\) are \(q\), No \(p\) are \(q\), for \(p,q\in\mathsf P\).
A model is exactly what it was: a set \(M\) with a subset \([\![p]\!]\subseteq M\) for each noun. Truth in a model is given by
\[\begin{aligned} \mathcal M&\vDash \text{All } p \text{ are } q &&\text{iff}\quad [\![p]\!]\subseteq[\![q]\!]\\ \mathcal M&\vDash \text{Some } p \text{ are } q &&\text{iff}\quad [\![p]\!]\cap[\![q]\!]\neq\varnothing\\ \mathcal M&\vDash \text{No } p \text{ are } q &&\text{iff}\quad [\![p]\!]\cap[\![q]\!]=\varnothing \end{aligned}\]The notions \(\Gamma\vDash\varphi\) and \(\Gamma\nvDash\varphi\) are defined from this exactly as before.
Let \(M=\{1,2,3,4,5\}\) with \([\![\text{hawks}]\!]=\{2\}\), \([\![\text{birds}]\!]=\{1,2,5\}\), \([\![\text{turtles}]\!]=\{3,4\}\).
Traditional logic sorts categorical sentences along two axes: quantity (universal or particular) and quality (affirmative or negative). Two choices on each axis give four combinations, and these are the four sentence forms. They carry one-letter names that go back to medieval Latin: the affirmative ones are labelled with the vowels of affirmo, giving A and I, and the negative ones with the vowels of nego, giving E and O.
| Label | Form | Quantity / quality | True in \(\mathcal M\) iff |
|---|---|---|---|
| A | All \(p\) are \(q\) | universal affirmative | \([\![p]\!]\subseteq[\![q]\!]\) |
| E | No \(p\) are \(q\) | universal negative | \([\![p]\!]\cap[\![q]\!]=\varnothing\) |
| I | Some \(p\) are \(q\) | particular affirmative | \([\![p]\!]\cap[\![q]\!]\neq\varnothing\) |
| O | Some \(p\) are not \(q\) | particular negative | \([\![p]\!]\setminus[\![q]\!]\neq\varnothing\) |
The official syntax of \(\mathcal S\) in Definition 4.14 contains only three sentence formers: All, Some and No. That covers A, E and I. It does not contain the O form Some \(p\) are not \(q\).
The O form needs a negation sitting on a noun: Some \(p\) are non-\(q\). Adding complemented nouns gives a larger language, called \(\mathcal S^{\dagger}\), and that is next week's topic. For this week we use the O form only when we talk about the four forms, as in the square below. Every reasoning problem you are asked to solve stays inside A, E and I.
The traditional square arranges the four forms in a diagram and claims four kinds of relation between them. Now that the truth conditions are exact, we can simply check each claim.
In every model \(\mathcal M\):
(1) \([\![p]\!]\subseteq[\![q]\!]\) holds exactly when no element of \([\![p]\!]\) lies outside \([\![q]\!]\), that is, exactly when \([\![p]\!]\setminus[\![q]\!]=\varnothing\).
(2) The two truth conditions are \([\![p]\!]\cap[\![q]\!]=\varnothing\) and \([\![p]\!]\cap[\![q]\!]\neq\varnothing\), which are negations of one another by definition. □
So A and O are exact contradictories, and so are E and I. These are the two diagonals of the square, and they hold with no side conditions at all.
The traditional square also claims three further relations. Each one fails, and each one fails for the same reason: a model in which \([\![p]\!]=\varnothing\).
Let \(M=\{1\}\), \([\![p]\!]=\varnothing\), \([\![q]\!]=\{1\}\). Then:
Reading this off:
Aristotle and the medieval tradition read All \(p\) are \(q\) as carrying existential import: saying it commits you to there being some \(p\). Under that reading the whole square is correct. Our Definition 4.14 takes the modern reading, on which All \(p\) are \(q\) is true whenever \([\![p]\!]\) is empty.
Neither reading is wrong; they are different sentences. What matters is that once you fix the truth condition, which inferences are valid is settled, and you can no longer appeal to the picture. If you want the traditional square back, you have to add the assumption Some \(p\) are \(p\) to \(\Gamma\).
Before we have a proof system, entailment claims have to be settled by hand: a positive claim needs an argument about arbitrary models, a negative claim needs one counter-model.
Let \(\mathcal M\) be any model of the two hypotheses. So \([\![p]\!]\subseteq[\![q]\!]\) and \([\![p]\!]\cap[\![r]\!]\neq\varnothing\).
The second hypothesis hands us an element: pick \(x\in[\![p]\!]\cap[\![r]\!]\). Then \(x\in[\![p]\!]\), and the first hypothesis gives \(x\in[\![q]\!]\). Also \(x\in[\![r]\!]\). So \(x\in[\![q]\!]\cap[\![r]\!]\), which is therefore non-empty, that is, \(\mathcal M\vDash\) Some \(q\) are \(r\).
\(\mathcal M\) was arbitrary, so the entailment holds. □
The shape of this argument is worth remembering: a Some hypothesis is used by naming a witness, and an All hypothesis is used by pushing that witness into a bigger set.
Fix a model of the hypotheses: \([\![p]\!]\subseteq[\![v]\!]\), \([\![q]\!]\subseteq[\![w]\!]\) and \([\![v]\!]\cap[\![w]\!]=\varnothing\). Then \[[\![p]\!]\cap[\![q]\!]\ \subseteq\ [\![v]\!]\cap[\![w]\!]\ =\ \varnothing,\] because intersection is monotone in both arguments. A subset of the empty set is empty, so \([\![p]\!]\cap[\![q]\!]=\varnothing\), which is the conclusion. □
Claim: Some \(p\) are \(q\), Some \(q\) are \(n\), All \(q\) are \(m\) \(\nvDash\) Some \(p\) are \(n\).
One counter-model suffices. Take \(M=\{1,2\}\) with \([\![p]\!]=\{1\}\), \([\![q]\!]=\{1,2\}\), \([\![n]\!]=\{2\}\), \([\![m]\!]=\{1,2\}\).
The point is that two Some sentences sharing a noun need not share a witness. Here \(q\) is met by \(p\) at the point \(1\) and by \(n\) at the point \(2\), and nothing forces these to coincide.
When you have to falsify something, you need a universe and you need witnesses for the Some sentences. A convenient choice is to take the Some sentences of \(\Gamma\) themselves as the points of the model, and to put the sentence Some \(x\) are \(y\) into \([\![x]\!]\) and \([\![y]\!]\). Each Some sentence then witnesses itself and nothing else, which is exactly the minimum needed. In Example 4.20 this produces a two-point model that is the same as the one above after renaming.
This is the same move as in the canonical model of Day 1, where the points were nouns. Nothing requires the elements of a model to be numbers.
Self-check only. Nothing here counts towards your grade.
Work in the model \(M=\{1,2,3,4,5\}\) with \([\![\text{hawks}]\!]=\{2\}\), \([\![\text{birds}]\!]=\{1,2,5\}\), \([\![\text{turtles}]\!]=\{3,4\}\). Mark each sentence true or false.
Self-check only. Nothing here counts towards your grade.
Build a model over \(M=\{1,2,3\}\) in which All \(p\) are \(q\) is true and Some \(p\) are \(q\) is false. Tick the elements you want in each set. Your model is tested directly, so any correct choice is accepted.
You have no choice about \([\![p]\!]\): it must be empty. If some \(x\) were in \([\![p]\!]\), then All \(p\) are \(q\) would put \(x\) into \([\![q]\!]\) as well, and then \(x\) would witness Some \(p\) are \(q\).
So take \([\![p]\!]=\varnothing\) and let \([\![q]\!]\) be anything at all, for instance \(\{1,2,3\}\) or \(\varnothing\). Both sentences then come out as required.
Today we set up the proof system \(\mathbf S\), check that each rule is sound, and build proof trees with it.
In (X) the conclusion \(\varphi\) is an arbitrary sentence of \(\mathcal S\). The letters \(p,q,n,r\) range over all nouns, and different letters need not name different nouns.
Soundness is again proved by induction on proof trees, exactly as for \(\mathbf A\). The induction itself is routine; all the content sits in checking one rule at a time. Fix a model \(\mathcal M\).
Assume \([\![p]\!]\subseteq[\![q]\!]\) and \([\![q]\!]\cap[\![r]\!]=\varnothing\). Suppose towards a contradiction that \([\![r]\!]\cap[\![p]\!]\neq\varnothing\), and take \(m\) in it. From \(m\in[\![p]\!]\) and the first assumption, \(m\in[\![q]\!]\). Together with \(m\in[\![r]\!]\) this puts \(m\) in \([\![q]\!]\cap[\![r]\!]\), contradicting the second assumption. So \([\![r]\!]\cap[\![p]\!]=\varnothing\). □
The system has no rule that simply swaps the two nouns in a No sentence. We get the effect out of (camestres) by feeding it a trivial left premise.
Matching against the rule: its left premise All \(p\) are \(q\) is instantiated as All \(p\) are \(p\), so the rule's \(q\) is our \(p\); its right premise No \(q\) are \(r\) is instantiated as No \(p\) are \(q\), so the rule's \(r\) is our \(q\); the conclusion No \(r\) are \(p\) therefore reads No \(q\) are \(p\). This derived step is often called E-conversion, or (anti).
This is Example 4.19 again, now as a proof rather than a semantic argument. Two applications of (camestres) are enough.
Upper step: the rule's \(p,q,r\) are our \(p,v,w\), giving No \(w\) are \(p\). Lower step: the rule's \(p,q,r\) are our \(q,w,p\), giving No \(p\) are \(q\). The characteristic feature of (camestres) is that it swaps the order of the nouns each time, so applying it twice restores the order you wanted.
In words: if there is at least one \(n\), and every \(n\) is both a \(p\) and a \(q\), then some \(p\) is a \(q\). This is the inference that the traditional square treated as automatic; here it needs the extra premise Some \(n\) are \(n\).
The bottom step needs its All premise on the left and its Some premise on the right, in the order given in Definition 4.21; (some2) is what puts the nouns in the position that (darii) can use.
Let \(\Gamma=\{\text{Some }p\text{ are }q,\ \text{No }q\text{ are }p\}\) and let \(\varphi\) be any sentence at all, say All \(m\) are \(n\). We first convert the No sentence as in Example 4.22, and then the two contradictory sentences meet at (X).
Soundness of \(\mathbf S\) holds, by the induction sketched in section 9. Completeness is only partly available at this point. What can be proved now is the particular half: if \(\Gamma\vDash\) Some \(p\) are \(q\), then \(\Gamma\vdash\) Some \(p\) are \(q\). The proof builds a second canonical model whose points are the Some sentences of \(\Gamma\), in the style of the trick in section 7.
That model does not settle the All and No cases; it can satisfy an All sentence that is not provable. Repairing this is easier in the larger language \(\mathcal S^{\dagger}\), where negation is allowed on nouns and No \(p\) are \(q\) becomes a notational variant of All \(p\) are non-\(q\). That is next week.
Self-check only. Nothing here counts towards your grade.
For each line, decide whether the conclusion follows from the premises by one application of one rule of Definition 4.21. Some lines are semantically correct but still need more than one step, and those count as "no".
Self-check only. Nothing here counts towards your grade.
Here is a derivation of Some \(c\) are \(d\) from
\(\Gamma=\{\text{Some }a\text{ are }b,\ \text{All }a\text{ are }c,\ \text{All }b\text{ are }d\}\), with
two nodes left blank. Fill them in. Write sentences in the form
All a are b, Some a are b or No a are b.
The check re-runs every step of the tree against the rules, so it tells you which step breaks if your answer is wrong.
Node (a) is Some \(a\) are \(d\). The rule (darii) applied to All \(b\) are \(d\) and Some \(a\) are \(b\) has the rule's \(q=b\), \(n=d\), \(p=a\), so the conclusion is Some \(a\) are \(d\).
Node (b) is Some \(d\) are \(c\). The rule (darii) applied to All \(a\) are \(c\) and Some \(d\) are \(a\) has \(q=a\), \(n=c\), \(p=d\), so the conclusion is Some \(d\) are \(c\). One more (some2) turns it into Some \(c\) are \(d\).
Let \(\mathsf P=\{a,b,c,d\}\) and \[\Gamma=\{\text{All }a\text{ are }b,\ \ \text{All }b\text{ are }c,\ \ \text{All }c\text{ are }a,\ \ \text{All }d\text{ are }b\}.\]
Let \(\mathsf P=\{j,k,m,n,p,q\}\) and let \(\Gamma\) consist of
All \(j\) are \(k\), All \(k\) are \(m\), All \(m\) are \(k\), All \(n\) are \(m\), All \(p\) are \(n\), All \(q\) are \(p\), All \(p\) are \(q\).
Work in the model \(M=\{1,2,3,4,5,6\}\) with \([\![a]\!]=\{1,2\}\), \([\![b]\!]=\{2,3,4\}\), \([\![c]\!]=\{5,6\}\), \([\![d]\!]=\varnothing\).
Give a proof tree for each of the following, using only the rules of Definition 4.21. Write the name of the rule at every step. Leaves must be sentences of \(\Gamma\) or instances of (axiom).