Monday: adding negation on nouns, and a proof system with proof by contradiction. Wednesday: the algebraic structures that appear when you try to build models for the extended system, namely orthoposets and their states. Friday: the completeness proof.
By the end of this week you will be able to:
Today we add a complement operation on nouns, check that the larger language can express No and "Some ... are not ...", and set up a proof system whose new rule is proof by contradiction.
English lets us negate a noun: farmer, non-farmer; artist, non-artist. We add this operation to the language. The negation sits on nouns only. There is still no negation of sentences in the syntax.
Let \(\mathsf P\) be a set of nouns. For each noun \(p\) we add a new symbol \(\overline p\), called the complemented noun. The set of literals is \[\mathsf{Lit}=\mathsf P\cup\{\overline p: p\in\mathsf P\}.\] Complementation is extended to all literals by the rule \(\overline{\overline p}=p\). This is called the involutive property. So every literal has a complement, and the complement of the complement is the literal you started with.
The sentences of \(\mathcal S^{\dagger}\) are
All \(p\) are \(q\) and Some \(p\) are \(q\), where \(p\) and \(q\) are any literals.
From now on the letters \(p,q,n,x,y,\dots\) range over literals, not only over nouns.
For instance, with the two nouns \(a\) and \(b\) there are four literals: \(a,\overline a,b,\overline b\). Each sentence is built from a choice of All or Some and an ordered pair of literals, so there are \(2\cdot4\cdot4=32\) sentences. Three of them are All \(\overline a\) are \(b\), Some \(a\) are \(\overline b\), and All \(\overline b\) are \(\overline a\).
A model is exactly what it was before: a set \(M\) with a subset \([\![p]\!]\subseteq M\) for each noun \(p\). The interpretation is extended to complemented nouns by \[[\![\overline p]\!]=M\setminus[\![p]\!].\] Since \(M\setminus(M\setminus A)=A\), this equation holds for every literal \(p\), not only for nouns. Truth in a model is defined as before:
\[\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 \end{aligned}\]The notions \(\mathcal M\vDash\Gamma\) and \(\Gamma\vDash\varphi\) are defined from this exactly as before.
Note what you choose and what you do not choose when you build a model. You choose \([\![p]\!]\) for the nouns. The sets \([\![\overline p]\!]\) are then fixed. Every element of \(M\) lies in exactly one of \([\![p]\!]\) and \([\![\overline p]\!]\) (Figure 1).
Let \(M=\{1,2,3,4,5\}\) with \([\![p]\!]=\{1,2\}\), \([\![q]\!]=\{1,2,3\}\) and \([\![r]\!]=\{1,3,4,5\}\).
Step 1: the complements. They are determined by \(M\): \([\![\overline p]\!]=\{3,4,5\}\), \([\![\overline q]\!]=\{4,5\}\), \([\![\overline r]\!]=\{2\}\).
Step 2: some sentences.
So this model satisfies \(\Gamma=\{\text{All }p\text{ are }q,\ \text{All }\overline p\text{ are }r\}\). We will meet this model again on Wednesday.
The syntax has only All and Some. The word No is gone, and it is not needed.
In every model, No \(p\) are \(q\) is true iff All \(p\) are \(\overline q\) is true.
\([\![p]\!]\cap[\![q]\!]=\varnothing\) says that no element of \([\![p]\!]\) lies in \([\![q]\!]\). This is the same as saying that every element of \([\![p]\!]\) lies in \(M\setminus[\![q]\!]\), which is \([\![p]\!]\subseteq[\![\overline q]\!]\). □
So from now on No \(p\) are \(q\) is an abbreviation for All \(p\) are \(\overline q\). In the same way, the O form of last week is now a sentence of the language: Some \(p\) are not \(q\) is Some \(p\) are \(\overline q\). The table collects the most useful translations.
| In words | Sentence of \(\mathcal S^{\dagger}\) | True in \(\mathcal M\) iff |
|---|---|---|
| No \(p\) are \(q\) | All \(p\) are \(\overline q\) | \([\![p]\!]\cap[\![q]\!]=\varnothing\) |
| Some \(p\) are not \(q\) | Some \(p\) are \(\overline q\) | \([\![p]\!]\setminus[\![q]\!]\neq\varnothing\) |
| Everything is a \(p\) or a \(q\) | All \(\overline p\) are \(q\) | \([\![p]\!]\cup[\![q]\!]=M\) |
| There are no \(p\) | All \(p\) are \(\overline p\) | \([\![p]\!]=\varnothing\) |
| Everything is a \(p\) | All \(\overline p\) are \(p\) | \([\![p]\!]=M\) |
| There is a \(p\) | Some \(p\) are \(p\) | \([\![p]\!]\neq\varnothing\) |
| (never true) | Some \(p\) are \(\overline p\) | \([\![p]\!]\cap(M\setminus[\![p]\!])\neq\varnothing\), impossible |
A sentence of the form Some \(p\) are \(\overline p\), where \(p\) is any literal, is called a contradiction. We write \(\bot\) for any sentence of this form. A contradiction has no models, so \(\bot\vDash\varphi\) holds for every sentence \(\varphi\): the condition "every model of \(\bot\) is a model of \(\varphi\)" is true because there are no models of \(\bot\).
For instance Some \(q\) are \(\overline q\) and Some \(\overline q\) are \(q\) are both contradictions. The second one has the form Some \(p\) are \(\overline p\) with \(p=\overline q\), because \(\overline{\overline q}=q\).
All \(p\) are \(\overline p\) is not a contradiction. It has models: it is true exactly when \([\![p]\!]=\varnothing\). Only the Some version is impossible.
Claim: All \(y\) are \(p\), All \(\overline y\) are \(p\), All \(p\) are \(q\) \(\vDash\) All \(x\) are \(q\).
Let \(\mathcal M\) be a model of the three hypotheses, and let \(m\) be any element of \(M\). Either \(m\in[\![y]\!]\) or \(m\in[\![\overline y]\!]\), because these two sets cover \(M\). In the first case the first hypothesis gives \(m\in[\![p]\!]\). In the second case the second hypothesis gives \(m\in[\![p]\!]\). So \([\![p]\!]=M\). The third hypothesis then gives \([\![q]\!]=M\). Every subset of \(M\) is included in \(M\), so \([\![x]\!]\subseteq[\![q]\!]\). □
The noun \(x\) does not occur in the hypotheses at all. Nothing like this could happen in \(\mathcal S\). The new step is the case distinction on \(y\) and \(\overline y\).
Self-check only. Nothing here counts towards your grade.
Work in the model of Example 5.3: \(M=\{1,2,3,4,5\}\), \([\![p]\!]=\{1,2\}\), \([\![q]\!]=\{1,2,3\}\), \([\![r]\!]=\{1,3,4,5\}\). Mark each sentence true or false.
The complements are \([\![\overline p]\!]=\{3,4,5\}\), \([\![\overline q]\!]=\{4,5\}\), \([\![\overline r]\!]=\{2\}\).
In \(\mathcal S\) a sentence All \(p\) are \(q\) had no sentence that says the opposite. In \(\mathcal S^{\dagger}\) every sentence has one.
| \(\varphi\) | \(\overline\varphi\) |
|---|---|
| All \(x\) are \(y\) | Some \(x\) are \(\overline y\) |
| Some \(x\) are \(y\) | All \(x\) are \(\overline y\) |
In both rows the first literal stays, the second literal is complemented, and All and Some are exchanged.
For every sentence \(\varphi\) and every model \(\mathcal M\):
(1) Apply the table twice. All \(x\) are \(y\) becomes Some \(x\) are \(\overline y\), which becomes All \(x\) are \(\overline{\overline y}\), and \(\overline{\overline y}=y\). The other case is the same.
(2) Let \(\varphi\) be All \(x\) are \(y\). Then \(\mathcal M\nvDash\varphi\) iff some element of \([\![x]\!]\) is not in \([\![y]\!]\), iff some element of \([\![x]\!]\) is in \(M\setminus[\![y]\!]=[\![\overline y]\!]\), iff \([\![x]\!]\cap[\![\overline y]\!]\neq\varnothing\), iff \(\mathcal M\vDash\overline\varphi\). If \(\varphi\) is a Some sentence, then \(\varphi=\overline\psi\) for the All sentence \(\psi=\overline\varphi\), by (1). The case just proved gives \(\mathcal M\vDash\varphi\) iff \(\mathcal M\nvDash\overline\varphi\), which is the claim. □
So the two diagonals of the square of opposition are now an operation on sentences of the language.
The bar on a noun is syntax: \(\overline p\) is a symbol of \(\mathcal S^{\dagger}\). The bar on a sentence is only our notation. \(\overline\varphi\) is a name for another sentence of the language, given by the table. There is still no negation sign for sentences, and no "and", "or" or "if".
Self-check only. Nothing here counts towards your grade.
Type the semantic negation of each sentence. Write a complemented noun with a tilde in front of the
letter: ~p stands for \(\overline p\). For example, the sentence
Some \(\overline p\) are \(q\) is typed as Some ~p are q. Simplify double complements:
write q, not ~~q.
(a) All \(p\) are \(q\)
(b) Some \(\overline p\) are \(q\)
(c) All \(p\) are \(\overline q\)
(d) Some \(\overline p\) are \(\overline q\)
(a) Some \(p\) are \(\overline q\).
(b) All \(\overline p\) are \(\overline q\). The first literal \(\overline p\) is not touched.
(c) Some \(p\) are \(q\), because \(\overline{\overline q}=q\). In words: the negation of No \(p\) are \(q\) is Some \(p\) are \(q\).
(d) All \(\overline p\) are \(q\).
The rules for All and Some are the ones you know, now read with literals in place of nouns. The rules of \(\mathbf S\) that mention No are dropped. In their place there is one new rule, of a new kind.
The letters \(p,q,n\) range over all literals. The rule (raa) reads: if a tree ends in a contradiction \(\bot\), then we may choose any sentence \(\varphi\), put brackets around some or all of the leaves of the tree that are equal to \(\varphi\), and add \(\overline\varphi\) as a new root. The bracketed leaves are called withdrawn. It is allowed that no leaf is equal to \(\varphi\); then nothing is withdrawn.
We write \(\Gamma\vdash\varphi\) if there is a proof tree with root \(\varphi\) in which every leaf that is not withdrawn is a sentence of \(\Gamma\) or an instance of (axiom).
The name (raa) is short for reductio ad absurdum, proof by contradiction. Since \(\overline{\overline\psi}=\psi\), the rule can be used to prove any sentence \(\psi\): assume \(\overline\psi\), derive a contradiction, withdraw the assumption, and conclude \(\overline{\overline\psi}=\psi\). In practice: to prove \(\psi\) by (raa), the assumption to make is the semantic negation of \(\psi\).
Claim: Some \(p\) are \(q\), No \(q\) are \(n\) \(\vdash\) Some \(p\) are not \(n\). In the notation of \(\mathcal S^{\dagger}\): Some \(p\) are \(q\), All \(q\) are \(\overline n\) \(\vdash\) Some \(p\) are \(\overline n\).
This is one application of (darii). The rule asks for All \(q\) are \(n\) and Some \(p\) are \(q\), and its letter \(n\) may be any literal; here it is the literal \(\overline n\). The traditional name of this syllogism is Ferio. In \(\mathbf S^{\dagger}\) it is not a new rule. It is an instance of (darii).
Claim: All \(p\) are \(q\), No \(q\) are \(r\) \(\vdash\) No \(r\) are \(p\). In the notation of \(\mathcal S^{\dagger}\): All \(p\) are \(q\), All \(q\) are \(\overline r\) \(\vdash\) All \(r\) are \(\overline p\).
Step 1: choose the assumption. The sentence to prove is All \(r\) are \(\overline p\). Its semantic negation is Some \(r\) are \(\overline{\overline p}\), that is, Some \(r\) are \(p\). We assume this, together with the two hypotheses.
Step 2: derive a contradiction.
The root Some \(r\) are \(\overline r\) is a contradiction.
Step 3: withdraw the assumption and apply (raa). We put brackets around the leaf Some \(r\) are \(p\) and add its negation as the new root:
The leaves that are not withdrawn are All \(p\) are \(q\) and All \(q\) are \(\overline r\). Both are hypotheses, so this tree shows the claim. Compare it with the semantic proof of the soundness of (camestres) from last week: "suppose towards a contradiction that some \(m\) is in \([\![r]\!]\cap[\![p]\!]\) ...". The tree is that argument, written in the proof system.
Claim: All \(p\) are \(q\) \(\vdash\) All \(\overline q\) are \(\overline p\).
The negation of the conclusion is Some \(\overline q\) are \(\overline{\overline p}\), that is, Some \(\overline q\) are \(p\). We assume it and look for a contradiction.
The (darii) step uses All \(p\) are \(q\) and Some \(\overline q\) are \(p\) and gives Some \(\overline q\) are \(q\). This is a contradiction: it has the form Some \(x\) are \(\overline x\) with \(x=\overline q\). We will use (antitone) many times on Wednesday. A special case is the conversion of No: from All \(p\) are \(\overline q\) we get All \(q\) are \(\overline p\), that is, from No \(p\) are \(q\) we get No \(q\) are \(p\).
Claim: No \(p\) are \(p\) \(\vdash\) No \(p\) are \(q\). In the notation of \(\mathcal S^{\dagger}\): All \(p\) are \(\overline p\) \(\vdash\) All \(p\) are \(\overline q\).
The negation of the conclusion is Some \(p\) are \(q\).
The tree never uses any property of the literal \(q\). If we replace \(\overline q\) by an arbitrary literal \(n\), the same tree shows All \(p\) are \(\overline p\) \(\vdash\) All \(p\) are \(n\). This is the rule (zero) of last week: if there are no \(p\), then all \(p\) are \(n\).
If \(\Gamma\cup\{\varphi\}\vDash\bot\), then \(\Gamma\vDash\overline\varphi\).
Let \(\mathcal M\) be a model of \(\Gamma\). If \(\mathcal M\) were also a model of \(\varphi\), it would be a model of \(\Gamma\cup\{\varphi\}\) and so of \(\bot\). But \(\bot\) has no models. So \(\mathcal M\nvDash\varphi\), and by Proposition 5.8 we get \(\mathcal M\vDash\overline\varphi\). □
The other rules are sound for the same reasons as last week. An induction on proof trees then gives the soundness theorem for \(\mathbf S^{\dagger}\): if \(\Gamma\vdash\varphi\), then \(\Gamma\vDash\varphi\). The induction hypothesis has to speak about the leaves that are not withdrawn; Proposition 5.15 is the step for (raa).
If \(\Gamma\cup\{\varphi\}\vdash\bot\), then \(\Gamma\vdash\overline\varphi\).
Take a proof tree with root \(\bot\) whose non-withdrawn leaves are in \(\Gamma\cup\{\varphi\}\). Withdraw every leaf that is equal to \(\varphi\). There may be none, and this is not a problem. Apply (raa) at the root. The new tree has root \(\overline\varphi\), and all of its non-withdrawn leaves are in \(\Gamma\). □
A set \(\Gamma\) is inconsistent in \(\mathbf S^{\dagger}\) if \(\Gamma\vdash\bot\). Otherwise \(\Gamma\) is consistent.
For instance \(\Gamma=\{\text{All }p\text{ are }q,\ \text{Some }p\text{ are }\overline q\}\) is inconsistent:
An inconsistent set proves every sentence \(\psi\). Indeed, if \(\Gamma\vdash\bot\) then also \(\Gamma\cup\{\overline\psi\}\vdash\bot\), because a proof tree over \(\Gamma\) is also a proof tree over any larger set. Lemma 5.16 then gives \(\Gamma\vdash\overline{\overline\psi}=\psi\). So the rule (X) of last week is not needed: (raa) does its job.
"Consistent" is defined with \(\vdash\), not with models. It is a property of the proof system. If we changed the rules, the consistent sets could change. The matching semantic notion, "has a model", appears on Friday, and one of the main results of the week is that the two notions agree.
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\text{All }\overline p\text{ are }p\}\). In words: everything is a \(p\). Build a proof tree over \(\Gamma\) with root All \(q\) are \(p\).
How to use the editor: for every sentence choose how it is obtained. Choosing a rule opens the
premise boxes above the sentence: none for (axiom), one for (some1), (some2) and (raa), two for
(barbara) and (darii). Type a complemented noun with a tilde, for example ~p. A leaf is
either an assumption from \(\Gamma\), an instance of (axiom), or a withdrawn assumption. A withdrawn
assumption must be the semantic negation of the conclusion of an (raa) step below it.
The negation of the root All \(q\) are \(p\) is Some \(q\) are \(\overline p\). Assume it. Then (some2) gives Some \(\overline p\) are \(q\), and (some1) gives Some \(\overline p\) are \(\overline p\). Now (darii) with the hypothesis All \(\overline p\) are \(p\) gives Some \(\overline p\) are \(p\). This is a contradiction, of the form Some \(x\) are \(\overline x\) with \(x=\overline p\). Apply (raa) and withdraw the assumption: the root is All \(q\) are \(p\).
Read from the root upwards, the tree is: (raa), (darii) with the leaf All \(\overline p\) are \(p\) on one side, and on the other side (some1), (some2), and the withdrawn leaf [Some \(q\) are \(\overline p\)].
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\text{All }p\text{ are }q,\ \text{Some }r\text{ are }\overline q\}\). Build a proof tree over \(\Gamma\) with root Some \(r\) are \(\overline p\). In words: all \(p\) are \(q\), some \(r\) are not \(q\), so some \(r\) are not \(p\). The traditional name of this syllogism is Baroco.
The root is a Some sentence, so its negation is an All sentence: the negation of Some \(r\) are \(\overline p\) is All \(r\) are \(p\). Assume it.
(barbara) on All \(r\) are \(p\) and All \(p\) are \(q\) gives All \(r\) are \(q\). From the hypothesis Some \(r\) are \(\overline q\), (some2) gives Some \(\overline q\) are \(r\). Then (darii) on All \(r\) are \(q\) and Some \(\overline q\) are \(r\) gives Some \(\overline q\) are \(q\), a contradiction. (raa) withdraws All \(r\) are \(p\) and concludes Some \(r\) are \(\overline p\).
There is no direct proof of this conclusion with (darii) and (some2) alone. The assumption All \(r\) are \(p\) is what connects \(r\) to \(q\).
Today we turn the provable All sentences of a set \(\Gamma\) into an ordered structure with a complement, and we study the subsets of this structure that behave like the points of a model.
The completeness proof for \(\mathbf A\) used a model whose points were the nouns, ordered by provability. We want to do something similar for \(\mathbf S^{\dagger}\). The literals are again ordered by provability, but now they come in pairs \(p,\overline p\), and the order and the complement interact. We first describe this kind of structure in general.
A poset (partially ordered set) is a preorder \((P,\le)\) that is also antisymmetric: if \(x\le y\) and \(y\le x\), then \(x=y\).
For instance, the subsets of a set ordered by \(\subseteq\) form a poset. The nouns under \(\le_\Gamma\) for \(\Gamma=\{\text{All }a\text{ are }b,\ \text{All }b\text{ are }a\}\) form a preorder that is not a poset: \(a\le b\) and \(b\le a\), but \(a\) and \(b\) are different nouns.
An orthoposet is a tuple \((P,\le,0,\overline{\phantom{x}})\) such that
We write \(1\) for \(\overline 0\). It is a maximum element: for every \(x\) we have \(0\le\overline x\), and so \(x=\overline{\overline x}\le\overline 0=1\) by conditions 3 and 4. We always assume \(0\neq1\).
The word comes from papers on quantum logic. You can read it as "poset with a negation".
Let \(X\) be any set. Take \(P=\mathcal P(X)\), the set of all subsets of \(X\), ordered by \(\subseteq\), with \(0=\varnothing\) and \(\overline A=X\setminus A\). We check the five conditions.
Figure 2(a) shows the case \(X=\{1,2\}\). Here \(1=\overline\varnothing=X\).
Figure 2(b) shows a poset with six elements: \(0\) at the bottom, \(1\) at the top, and four elements \(x_1,x_2,x_3,x_4\) in between that are pairwise incomparable. Define the complement by \[\overline 0=1,\quad \overline 1=0,\quad \overline{x_1}=x_2,\quad \overline{x_2}=x_1,\quad \overline{x_3}=x_4,\quad \overline{x_4}=x_3.\]
Conditions 1, 2 and 4 can be read off directly. For condition 3, the only strict relations are \(0<x_i\), \(x_i<1\) and \(0<1\); the complement sends \(0<x_i\) to \(\overline{x_i}<1\) and \(x_i<1\) to \(0<\overline{x_i}\), which are again true. For condition 5, suppose \(x\le y\) and \(x\le\overline y\) with \(x\neq0\). If \(x=x_i\), then \(y\) and \(\overline y\) both lie in \(\{x_i,1\}\). This is impossible, because the complement of \(x_i\) is a different middle element and the complement of \(1\) is \(0\). If \(x=1\), then \(y=\overline y=1\), which is also impossible.
This orthoposet is not a power set: a power set of a finite set has \(2^n\) elements, and \(6\) is not a power of \(2\).
Take the chain \(0<a<1\) with three elements. Suppose it had a complement operation. An antitone involution of a chain reverses the order, so \(\overline 0=1\), \(\overline 1=0\) and \(\overline a=a\). But then \(a\le a\) and \(a\le\overline a\), and condition 5 forces \(a=0\). This is false. So condition 5 is a real restriction: no element other than \(0\) may lie below its own complement.
Let \(\Gamma\) be a set of sentences of \(\mathcal S^{\dagger}\), and let \(\le\) be the preorder \(\le_\Gamma\) on the literals. Define \[p\equiv q\quad\text{iff}\quad p\le q\ \text{ and }\ q\le p.\] This is an equivalence relation. We write \([p]\) for the equivalence class of \(p\), that is, the set of all literals \(q\) with \(p\equiv q\). The elements of \(P_\Gamma\) are these classes, with
\(P_\Gamma\) is well defined, and it is an orthoposet.
Well defined. If \(p\equiv p'\) and \(q\equiv q'\), then \(p\le q\) iff \(p'\le q'\), by transitivity. If \(p\equiv p'\), then \(\overline p\equiv\overline{p'}\) by (antitone), so the complement does not depend on the chosen literal. If \(p\le\overline p\) and \(q\le\overline q\), then \(p\le q\) and \(q\le p\) by (zero), so \([p]=[q]\) and \(0\) is unique.
The five conditions. (1) A preorder becomes a poset when equivalent elements are identified: if \([p]\le[q]\) and \([q]\le[p]\), then \(p\equiv q\), so \([p]=[q]\). (2) By (zero), or by the choice of the new element \(0\). (3) By (antitone). (4) Because \(\overline{\overline p}=p\) for literals. (5) Suppose \([x]\le[y]\) and \([x]\le[\overline y]\). From All \(x\) are \(y\) and All \(x\) are \(\overline y\) one can derive All \(x\) are \(\overline x\); you will build this proof tree in Homework 5. So \(x\le\overline x\), and \([x]=0\) by the definition of \(0\). □
Positive facts. Every sentence All \(u\) are \(v\) in \(\Gamma\) gives \(u\le v\) and, by (antitone), also \(\overline v\le\overline u\). Write down both. Then join chains by transitivity. If you find \(u\le\overline u\), then \(u\) is below everything. If you find \(\overline u\le u\), then \(u\) is above everything.
Negative facts. To show \(u\not\le v\), give a model of \(\Gamma\) in which All \(u\) are \(v\) is false. A model with one element is often enough.
For a set \(\Gamma\) that contains only All sentences, the positive facts found in this way are all the positive facts there are. The book proves this in Section 3.6.
Let the nouns be \(x,y,z,w\) and let \[\Gamma=\{\text{All }y\text{ are }x,\ \ \text{All }\overline y\text{ are }x,\ \ \text{All }z\text{ are }\overline y,\ \ \text{All }\overline z\text{ are }y,\ \ \text{All }z\text{ are }w\}.\]
Step 1: positive facts. Each sentence of \(\Gamma\) and its (antitone) partner:
\(y\le x\) and \(\overline x\le\overline y\); \(\overline y\le x\) and \(\overline x\le y\); \(z\le\overline y\) and \(y\le\overline z\); \(\overline z\le y\) and \(\overline y\le z\); \(z\le w\) and \(\overline w\le\overline z\).
Step 2: equivalence classes. We have \(y\le\overline z\) and \(\overline z\le y\), so \(y\equiv\overline z\). In the same way \(\overline y\equiv z\). The classes are \[[x]=\{x\},\quad[\overline x]=\{\overline x\},\quad[y]=\{y,\overline z\},\quad [\overline y]=\{\overline y,z\},\quad[w]=\{w\},\quad[\overline w]=\{\overline w\}.\]
Step 3: the zero. \(\overline x\le y\le x\), so \(\overline x\le x=\overline{\overline x}\). The literal \(\overline x\) lies below its own complement, so \(0=[\overline x]\) and \(1=[x]\). This agrees with the meaning of \(\Gamma\): all \(y\) and all non-\(y\) are \(x\), so everything is an \(x\) and nothing is a non-\(x\).
Step 4: the order. \(\overline w\le\overline z\equiv y\) gives \([\overline w]\le[y]\), and \(\overline y\equiv z\le w\) gives \([\overline y]\le[w]\). There are no other relations between the four middle classes. For instance \(y\not\le w\): take the model with \(M=\{1\}\), \([\![x]\!]=[\![y]\!]=\{1\}\) and \([\![z]\!]=[\![w]\!]=\varnothing\). All five sentences of \(\Gamma\) are true in it, for example All \(\overline z\) are \(y\) holds because \([\![\overline z]\!]=\{1\}=[\![y]\!]\). But \(1\in[\![y]\!]\) and \(1\notin[\![w]\!]\), so All \(y\) are \(w\) is false. The same model shows \(\overline w\not\le w\), and the other negative facts are shown in the same way.
The result is the hexagon of Figure 3.
Let \(\Gamma=\{\text{All }a\text{ are }c,\ \text{All }b\text{ are }c,\ \text{All }c\text{ are }d,\ \text{All }c\text{ are }e\}\).
The positive facts are \(a\le c\), \(b\le c\), \(c\le d\), \(c\le e\), their (antitone) partners \(\overline c\le\overline a\), \(\overline c\le\overline b\), \(\overline d\le\overline c\), \(\overline e\le\overline c\), and what follows by transitivity. No two different literals are equivalent, so every class has one element and we write \(u\) for \([u]\). No literal lies below its own complement. For instance \(a\not\le\overline a\): in the model with \(M=\{1\}\) and \([\![u]\!]=\{1\}\) for all five nouns, \(\Gamma\) is true and All \(a\) are \(\overline a\) is false. So we add a new \(0\) and a new \(1\). The result has twelve elements (Figure 4).
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\text{All }p\text{ are }q,\ \ \text{All }q\text{ are }\overline r,\ \ \text{All }\overline s\text{ are }p\}\). Start by writing down the three (antitone) partners. Then decide each claim.
From \(\Gamma\): \(p\le q\), \(q\le\overline r\), \(\overline s\le p\). Partners: \(\overline q\le\overline p\), \(r\le\overline q\), \(\overline p\le s\).
What should the points of a canonical model be? Look at a model from the point of view of one of its elements.
Take \(\Gamma=\{\text{All }p\text{ are }q,\ \text{All }\overline p\text{ are }r\}\) and the model of Example 5.3: \(M=\{1,2,3,4,5\}\), \([\![p]\!]=\{1,2\}\), \([\![q]\!]=\{1,2,3\}\), \([\![r]\!]=\{1,3,4,5\}\). For each \(m\in M\) let \(S_m\) be the set of literals \(u\) with \(m\in[\![u]\!]\):
\(S_1=\{p,q,r\}\), \(S_2=\{p,q,\overline r\}\), \(S_3=\{\overline p,q,r\}\), \(S_4=S_5=\{\overline p,\overline q,r\}\).
Each of these sets has three properties.
To build a model from syntax we turn this around. We take all the sets with these three properties as the points of the model. The three properties do not mention any model, so they can be stated for any orthoposet.
Let \(P\) be an orthoposet and \(S\subseteq P\).
A state always contains \(1\), because it is non-empty and up-closed. It never contains \(0\): with \(0\) it would contain everything, and then it would not be consistent.
Let \(X=\{1,2,3\}\). For each \(i\in X\) the set \(T_i=\{A\subseteq X: i\in A\}\) is a state. It is up-closed, since a superset of a set containing \(i\) contains \(i\). It is complete and consistent, since \(i\) lies in exactly one of \(A\) and \(X\setminus A\). These three states come from the points of \(X\), as in Example 5.27.
There is a fourth state, which does not come from a point (Figure 5): \[S=\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\},\] the sets with at least two elements. It is up-closed. For each \(A\), exactly one of \(A\) and \(X\setminus A\) has at least two elements, because their sizes add up to \(3\). So \(S\) is complete and consistent.
Two sets that are not states: \(\{\{1,2,3\}\}\) is up-closed and consistent but not complete, since it contains neither \(\{1\}\) nor \(\{2,3\}\). The set \(T_1\cup\{\{2,3\}\}\) is up-closed and complete but not consistent, since it contains \(\{1\}\) and \(\{2,3\}\).
These four are all the states. A state contains \(\{i\}\) or \(\{j,k\}\) for each of the three ways to split \(X\). If it contains some \(\{i\}\), then by up-closure it contains all of \(T_i\), and by consistency nothing else. If it contains no one-element set, it contains all three two-element sets and is \(S\).
Take \(P_\Gamma\) from Example 5.25 (Figure 3). A state contains \(1=[x]\) and not \(0=[\overline x]\). It contains exactly one of \([y],[\overline y]\) and exactly one of \([w],[\overline w]\). That leaves four candidates:
So the hexagon has exactly three states: \[S_1=\{[\overline w],[y],[x]\},\qquad S_2=\{[y],[w],[x]\},\qquad S_3=\{[z],[w],[x]\}.\] In \(S_3\) we wrote \([z]\) for the class \([\overline y]=[z]\).
Self-check only. Nothing here counts towards your grade.
The check below tests your set against Definition 5.28. It does not compare it with a stored answer.
(a) Tick the elements of a state that contains \(\{3\}\).
(b) Tick the elements of a state that contains \(\{1,2\}\) but does not contain \(\{1\}\).
(a) Up-closure forces every superset of \(\{3\}\): \(\{3\},\{1,3\},\{2,3\},\{1,2,3\}\). This set is already complete, and adding anything else would break consistency. So the answer is \(T_3\).
(b) Since \(\{1\}\) is not in the state, completeness forces its complement \(\{2,3\}\). There are two states of this kind: \(T_2=\{\{2\},\{1,2\},\{2,3\},\{1,2,3\}\}\) and the state \(S\) of Example 5.29. Both are accepted.
Self-check only. Nothing here counts towards your grade.
Take \(P_\Gamma\) from Example 5.26 (Figure 4), for \(\Gamma=\{\text{All }a\text{ are }c,\ \text{All }b\text{ are }c,\ \text{All }c\text{ are }d,\ \text{All }c\text{ are }e\}\). Tick the elements of a state that contains \(\overline a\) and \(d\). There are several correct answers.
A state contains \(1\), not \(0\), and exactly one literal from each of the five pairs. Up-closure is the only other condition. With \(\overline a\) and \(d\) fixed there are four states:
\(\{\overline a,b,c,d,e,1\}\), \(\{\overline a,\overline b,c,d,e,1\}\), \(\{\overline a,\overline b,\overline c,d,e,1\}\), \(\{\overline a,\overline b,\overline c,d,\overline e,1\}\).
The typical mistakes: choosing \(b\) without \(c\) (then the set is not up-closed, since \(b\le c\)), or choosing \(c\) together with \(\overline e\) (then up-closure adds \(e\), and the set is not consistent).
On Friday we will need states that contain two given elements. The next results say exactly when such a state exists and how to build it.
Every state is extendible.
Let \(S\) be a state and suppose \(p,q\in S\) with \(p\le\overline q\). Since \(S\) is up-closed, \(\overline q\in S\). Then \(S\) contains \(q\) and \(\overline q\), and this contradicts consistency. □
A set \(\{p,q\}\) is not extendible iff \(p\le\overline q\).
If \(p\le\overline q\), the set is not extendible by definition. Conversely, suppose \(\{p,q\}\) is not extendible. There are four cases. If \(p\le\overline q\), we are done. If \(q\le\overline p\), then \(p=\overline{\overline p}\le\overline q\) by the antitone and involutive properties. If \(p\le\overline p\), then \(p=0\) by complement inconsistency (take \(x=y=p\)), so \(p\le\overline q\). If \(q\le\overline q\), then \(q=0\), so \(\overline q=1\) and \(p\le\overline q\). □
For instance, in the hexagon \(\{[y],[w]\}\) is extendible, because \([y]\not\le\overline{[w]}=[\overline w]\). The set \(\{[\overline y],[\overline w]\}\) is not extendible, because \([\overline y]\le[w]=\overline{[\overline w]}\). This matches Example 5.30.
Let \(S\) be an extendible subset of an orthoposet \(P\), and let \(p\in P\). Then \(S\cup\{p\}\) is extendible or \(S\cup\{\overline p\}\) is extendible.
Suppose neither set is extendible. Since \(S\cup\{p\}\) is not extendible, there are \(u,v\in S\cup\{p\}\) with \(u\le\overline v\), and because \(S\) itself is extendible, at least one of \(u,v\) is \(p\). We treat the main case, where exactly one of them is \(p\). If \(u=p\), then \(p\le\overline v\) with \(v\in S\). If \(v=p\), then \(u\le\overline p\) with \(u\in S\), and the antitone property gives \(p\le\overline u\). Either way there is some \(s\in S\) with \(p\le\overline s\).
The same argument for \(S\cup\{\overline p\}\) gives some \(t\in S\) with \(\overline p\le\overline t\), that is, \(t\le p\). Together: \(t\le p\le\overline s\) with \(s,t\in S\). This contradicts the assumption that \(S\) is extendible.
The remaining cases are those with \(p\le\overline p\) or \(\overline p\le p\), that is, \(p=0\) or \(p=1\). They are handled in the same way, using that an extendible set cannot contain \(0\). □
Let \(P\) be a finite orthoposet and \(S_0\subseteq P\). The following are equivalent:
(1)⇒(2). States are extendible by Proposition 5.31, and every subset of an extendible set is extendible.
(2)⇒(1). List the elements of \(P\) as \(p_1,\dots,p_n\). Build \(S_0\subseteq S_1\subseteq\dots\subseteq S_n\) as follows: \(S_{i}\) is \(S_{i-1}\cup\{p_i\}\) if this set is extendible, and \(S_{i-1}\cup\{\overline{p_i}\}\) otherwise. By Lemma 5.33 every \(S_i\) is extendible. Let \(S=S_n\). We check that \(S\) is a state.
Non-empty and complete: for each \(p_i\), step \(i\) has put \(p_i\) or \(\overline{p_i}\) into \(S\).
Consistent: if \(p\in S\) and \(\overline p\in S\), then the pair \(p,\overline p\) satisfies \(p\le p=\overline{\overline p}\). This contradicts extendibility.
Up-closed: let \(p\in S\) and \(p\le q\), and suppose \(q\notin S\). By completeness \(\overline q\in S\). Then the pair \(p,\overline q\) satisfies \(p\le q=\overline{\overline q}\), which again contradicts extendibility. □
The proof is an algorithm. The finiteness assumption is harmless for us: in every example the set of nouns is finite, and then \(P_\Gamma\) is finite.
To test whether \(S\cup\{x\}\) is extendible it is enough to check that \(x\neq0\) and that \(x\not\le\overline s\) for every \(s\in S\). By the antitone property, \(x\le\overline s\) is the same as \(s\le\overline x\).
Work in \(P_\Gamma\) from Example 5.26 (Figure 4).
(a) A state that contains \(d\) and \(\overline e\). First, \(d\not\le\overline{\overline e}=e\), so \(\{d,\overline e\}\) is extendible. Start with \(S=\{d,\overline e\}\) and go through \(1,a,b,c\).
The pairs \(d,\overline d\) and \(e,\overline e\) are already decided, and \(0\) is never added. The result is \(S=\{\overline a,\overline b,\overline c,d,\overline e,1\}\). It is up-closed: \(\overline e\le\overline c\le\overline a,\overline b\) are all in \(S\), and above \(d\) there is only \(1\).
(b) A state that contains \(a\) and \(\overline d\). Here \(a\le c\le d=\overline{\overline d}\), so \(\{a,\overline d\}\) is not extendible, and by Lemma 5.34 no state contains both. In terms of models: \(\Gamma\) proves All \(a\) are \(d\), so no point of any model of \(\Gamma\) is an \(a\) and a non-\(d\).
Today we build a model whose points are the states of \(P_\Gamma\), show that it satisfies every consistent \(\Gamma\), and conclude that \(\mathbf S^{\dagger}\) proves every sentence that follows semantically from \(\Gamma\).
Let \(\Gamma\) be a set of sentences of \(\mathcal S^{\dagger}\). The universe \(M_3\) is the set of all states of \(P_\Gamma\). Each noun \(u\) is interpreted by \[[\![u]\!]=\{S\in M_3:[u]\in S\}.\] The book calls this the third canonical model. The first was the model of nouns for \(\mathbf A\). The second, for \(\mathbf S\), had the Some sentences of \(\Gamma\) as its points.
The equation \([\![u]\!]=\{S\in M_3:[u]\in S\}\) holds for complemented nouns as well. Indeed, for a noun \(u\), \[[\![\overline u]\!]=M_3\setminus[\![u]\!]=\{S:[u]\notin S\}=\{S:[\overline u]\in S\}.\] The last step uses that states are complete and consistent: a state misses \([u]\) exactly when it contains \([\overline u]\). This is the reason for these two conditions in the definition of a state.
Take \(\Gamma\) from the box above. Then \(M_3=\{S_1,S_2,S_3\}\). We read off, for each noun, which states contain its class:
\([\![x]\!]=\{S_1,S_2,S_3\}\), \([\![y]\!]=\{S_1,S_2\}\), \([\![z]\!]=\{S_3\}\), \([\![w]\!]=\{S_2,S_3\}\).
Check \(\Gamma\). The complements are \([\![\overline y]\!]=\{S_3\}\) and \([\![\overline z]\!]=\{S_1,S_2\}\).
Use it. Is All \(y\) are \(w\) a consequence of \(\Gamma\)? In \(\mathcal M_3\) we have \(S_1\in[\![y]\!]\) and \(S_1\notin[\![w]\!]\). So \(\mathcal M_3\) is a model of \(\Gamma\) in which All \(y\) are \(w\) is false, and \(\Gamma\nvDash\) All \(y\) are \(w\). By soundness, \(\Gamma\nvdash\) All \(y\) are \(w\).
The names of the points do not matter. Writing \(1,2,3\) for \(S_1,S_2,S_3\), the model is \(M=\{1,2,3\}\), \([\![x]\!]=\{1,2,3\}\), \([\![y]\!]=\{1,2\}\), \([\![z]\!]=\{3\}\), \([\![w]\!]=\{2,3\}\). The construction produced it without any guessing.
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\text{All }p\text{ are }q,\ \text{All }q\text{ are }\overline r\}\). No literal lies below its complement, so \(P_\Gamma\) has a new \(0\) and a new \(1\), and it has exactly four states. Each of them also contains \(1\):
\(S_1=\{p,q,\overline r\}\), \(S_2=\{\overline p,q,\overline r\}\), \(S_3=\{\overline p,\overline q,r\}\), \(S_4=\{\overline p,\overline q,\overline r\}\).
(a) Give the following sets in \(\mathcal M_3\). Type the numbers of the states,
separated by commas; for example 1, 3 stands for \(\{S_1,S_3\}\).
\([\![q]\!]=\)
\([\![\overline r]\!]=\)
(b) Which of these sentences are true in \(\mathcal M_3\)?
(a) \([\![q]\!]=\{S_1,S_2\}\), the states that contain \(q\). \([\![\overline r]\!]=\{S_1,S_2,S_4\}\), the states that contain \(\overline r\). By Remark 5.38 this is the same as the complement of \([\![r]\!]=\{S_3\}\).
(b)
Sentence 4 is true in \(\mathcal M_3\), but it is not provable from \(\Gamma\): in the empty model \(\Gamma\) holds and every Some sentence is false. So the canonical model of \(\Gamma\) alone does not decide Some sentences. Section 11 explains how the completeness proof deals with this.
Let \(\Gamma\) be a consistent set of sentences of \(\mathcal S^{\dagger}\). Then \(\mathcal M_3\vDash\Gamma\).
All sentences. Let All \(x\) are \(y\) be in \(\Gamma\). Then \([x]\le[y]\) in \(P_\Gamma\). Let \(S\in[\![x]\!]\), so \([x]\in S\). States are up-closed, so \([y]\in S\), that is, \(S\in[\![y]\!]\). By Remark 5.38 this argument works for all literals \(x,y\). Hence \([\![x]\!]\subseteq[\![y]\!]\).
Some sentences. Let Some \(x\) are \(y\) be in \(\Gamma\). We need a state that contains both \([x]\) and \([y]\). Suppose \(\{[x],[y]\}\) were not extendible. By Proposition 5.32, \([x]\le[\overline y]\), that is, \(\Gamma\vdash\) All \(x\) are \(\overline y\). Put this proof tree in the place of the left leaf below:
The root is a contradiction, so \(\Gamma\vdash\bot\). This contradicts the assumption that \(\Gamma\) is consistent. So \(\{[x],[y]\}\) is extendible, and by Lemma 5.34 there is a state \(S\) with \([x]\in S\) and \([y]\in S\). Then \(S\in[\![x]\!]\cap[\![y]\!]\), and \(\mathcal M_3\vDash\) Some \(x\) are \(y\). □
Look at where each property of states was used. Up-closed gives the All sentences. Complete and consistent give the correct interpretation of complemented nouns. The existence of enough states (Lemma 5.34) gives the Some sentences, and this is the only place where consistency of \(\Gamma\) is needed.
Let \(\Gamma=\{\text{All }p\text{ are }q,\ \text{Some }p\text{ are }\overline q\}\). This set is inconsistent (Definition 5.17), so it proves every sentence. In particular \(u\le v\) for all literals \(u,v\). All literals are equivalent, and \(P_\Gamma\) has a single element, which is \(0\) and \(1\) at the same time. A state would have to contain this element and also not contain it. So there are no states, and \(\mathcal M_3\) is the model with empty universe. In that model every All sentence is true and every Some sentence is false. So \(\mathcal M_3\nvDash\) Some \(p\) are \(\overline q\), and \(\mathcal M_3\) is not a model of \(\Gamma\). This must happen, because an inconsistent set has no model at all: by soundness, a model of \(\Gamma\) would be a model of \(\bot\).
On Wednesday we assumed \(0\neq1\) in an orthoposet. The structure \(P_\Gamma\) can violate this, as in Example 5.41. The proof of Lemma 5.40 is still correct. The part about All sentences does not need any states to exist. In the part about Some sentences we showed that \(\{[x],[y]\}\) is extendible, and when \(0=1\) no non-empty set is extendible; so \(0\neq1\) holds whenever the consistent set \(\Gamma\) contains a Some sentence.
For every set \(\Gamma\) of sentences of \(\mathcal S^{\dagger}\) and every sentence \(\varphi\): \[\Gamma\vdash\varphi\quad\text{iff}\quad\Gamma\vDash\varphi.\]
Soundness, from left to right, is the induction on proof trees discussed on Monday.
For completeness we show the contrapositive: if \(\Gamma\nvdash\varphi\), then \(\Gamma\nvDash\varphi\). So assume \(\Gamma\nvdash\varphi\).
Step 1. The set \(\Gamma\cup\{\overline\varphi\}\) is consistent. Otherwise \(\Gamma\cup\{\overline\varphi\}\vdash\bot\), and Lemma 5.16 gives \(\Gamma\vdash\overline{\overline\varphi}=\varphi\), against our assumption.
Step 2. By Lemma 5.40, the canonical model \(\mathcal M_3\) of the set \(\Gamma\cup\{\overline\varphi\}\) satisfies \(\Gamma\cup\{\overline\varphi\}\).
Step 3. So \(\mathcal M_3\vDash\Gamma\) and \(\mathcal M_3\vDash\overline\varphi\). By Proposition 5.8, \(\mathcal M_3\nvDash\varphi\). We have a model of \(\Gamma\) in which \(\varphi\) is false, so \(\Gamma\nvDash\varphi\). □
For the logic \(\mathbf A\), one canonical model of \(\Gamma\) made every unprovable sentence false. In \(\mathcal S^{\dagger}\) no single model can do this. Take \(\Gamma=\varnothing\). Neither Some \(p\) are \(p\) nor All \(p\) are \(\overline p\) is provable from \(\varnothing\), and the two sentences are negations of each other, so every model makes one of them true. This is why the proof builds a different model for each \(\varphi\).
Let \(\mathsf P=\{p\}\), \(\Gamma=\varnothing\), and \(\varphi=\) Some \(p\) are \(p\).
First attempt: the canonical model of \(\Gamma\). From \(\varnothing\) only the axioms All \(p\) are \(p\) and All \(\overline p\) are \(\overline p\) are provable All sentences. So \(P_\varnothing\) has four elements: a new \(0\), the incomparable elements \([p]\) and \([\overline p]\), and a new \(1\). There are two states, \(\{[p],1\}\) and \(\{[\overline p],1\}\), and \([\![p]\!]\) consists of the first one. Then \(\varphi\) is true in this model, so it does not refute \(\varphi\).
The proof's model. We have \(\overline\varphi=\) All \(p\) are \(\overline p\). For \(\Gamma\cup\{\overline\varphi\}=\{\text{All }p\text{ are }\overline p\}\) we get \(p\le\overline p\), so \([p]=0\) and \([\overline p]=1\). Now \(P\) has two elements, and its only state is \(\{1\}\). The model \(\mathcal M_3\) has one point, \([\![p]\!]=\varnothing\), and \(\varphi\) is false in it. So \(\varnothing\nvDash\) Some \(p\) are \(p\).
A set \(\Gamma\) is satisfiable if it has a model. Otherwise it is unsatisfiable.
For instance \(\{\text{All }p\text{ are }\overline p,\ \text{Some }q\text{ are }q\}\) is satisfiable: take \(M=\{1\}\), \([\![p]\!]=\varnothing\), \([\![q]\!]=\{1\}\). The set \(\{\text{All }p\text{ are }q,\ \text{Some }p\text{ are }\overline q\}\) is unsatisfiable, since the second sentence is the negation of the first.
A set \(\Gamma\) of sentences of \(\mathcal S^{\dagger}\) is consistent iff it is satisfiable.
If \(\Gamma\) is consistent, then \(\mathcal M_3\vDash\Gamma\) by Lemma 5.40, so \(\Gamma\) is satisfiable. If \(\Gamma\) is inconsistent, then \(\Gamma\vdash\bot\), and by soundness every model of \(\Gamma\) is a model of \(\bot\). There are no models of \(\bot\), so \(\Gamma\) has no model. □
Consistency is defined with proof trees, and satisfiability is defined with models. The corollary says that the two definitions pick out the same sets. It took the whole construction of this week to prove it.
The completeness proof gives a way to work on a concrete question "does \(\varphi\) follow from \(\Gamma\)?". Either you find a proof tree, or you build the states for \(\Gamma\cup\{\overline\varphi\}\) and obtain a counter-model.
If \(\Gamma\) is consistent, then the Some sentences of \(\Gamma\) do not change the order: \(\Gamma\vdash\) All \(u\) are \(v\) iff the All sentences of \(\Gamma\) alone prove it. So \(P_\Gamma\) can be computed from the All sentences, as on Wednesday. This is Exercise 3.9 in the book.
Let \(\Gamma=\{\text{All }a\text{ are }b,\ \ \text{All }\overline b\text{ are }c,\ \ \text{Some }a\text{ are }\overline c\}\).
Question 1: does \(\Gamma\) prove Some \(b\) are \(\overline c\)? Yes. The witness given by Some \(a\) are \(\overline c\) is an \(a\), so it is a \(b\):
Question 2: does \(\Gamma\) prove All \(c\) are \(b\)? We try the method of the proof. Let \(\varphi=\) All \(c\) are \(b\), so \(\overline\varphi=\) Some \(c\) are \(\overline b\), and let \(\Gamma'=\Gamma\cup\{\overline\varphi\}\).
Step 1: the order. From the All sentences: \(a\le b\) and \(\overline b\le c\), with partners \(\overline b\le\overline a\) and \(\overline c\le b\). Nothing else follows by transitivity. No two literals are equivalent and no literal lies below its complement, so \(P_{\Gamma'}\) consists of the six literals and a new \(0\) and \(1\).
Step 2: the states. Choose one literal from each pair so that the choice is up-closed: with \(a\) we must take \(b\); with \(\overline b\) we must take \(\overline a\) and \(c\); with \(\overline c\) we must take \(b\). This leaves five states, each together with \(1\):
| state | literals | in \([\![a]\!]\) | in \([\![b]\!]\) | in \([\![c]\!]\) |
|---|---|---|---|---|
| \(S_1\) | \(a,\ b,\ c\) | yes | yes | yes |
| \(S_2\) | \(a,\ b,\ \overline c\) | yes | yes | no |
| \(S_3\) | \(\overline a,\ b,\ c\) | no | yes | yes |
| \(S_4\) | \(\overline a,\ b,\ \overline c\) | no | yes | no |
| \(S_5\) | \(\overline a,\ \overline b,\ c\) | no | no | yes |
Step 3: check \(\Gamma'\) in \(\mathcal M_3\). All \(a\) are \(b\): \(\{S_1,S_2\}\subseteq\{S_1,S_2,S_3,S_4\}\). All \(\overline b\) are \(c\): \(\{S_5\}\subseteq\{S_1,S_3,S_5\}\). Some \(a\) are \(\overline c\): \(S_2\) is a witness. Some \(c\) are \(\overline b\): \(S_5\) is a witness. All four hold. In particular \(\Gamma'\) has a model, so it is consistent, as the method requires.
Step 4: conclude. \(S_5\in[\![c]\!]\) and \(S_5\notin[\![b]\!]\), so All \(c\) are \(b\) is false in a model of \(\Gamma\). Hence \(\Gamma\nvDash\) All \(c\) are \(b\), and by soundness \(\Gamma\nvdash\) All \(c\) are \(b\).
The canonical model is usually larger than necessary. Here the two points \(S_2\) and \(S_5\) alone already form a counter-model: \(M=\{2,5\}\), \([\![a]\!]=\{2\}\), \([\![b]\!]=\{2\}\), \([\![c]\!]=\{5\}\).
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{\text{All }p\text{ are }q,\ \ \text{All }\overline q\text{ are }r,\ \ \text{Some }p\text{ are }r\}\) and let \(\varphi\) be All \(r\) are \(q\). Build a model of \(\Gamma\) in which \(\varphi\) is false.
The universe is fixed as \(M=\{1,2,3\}\). Tick the elements you want in \([\![p]\!]\), \([\![q]\!]\) and \([\![r]\!]\). The complements are computed from your choice: every element that you leave out of \([\![q]\!]\) belongs to \([\![\overline q]\!]\). The check evaluates your model; any correct model is accepted.
We need a witness for Some \(p\) are \(r\); by All \(p\) are \(q\) it is also in \([\![q]\!]\). And we need an element of \([\![r]\!]\) outside \([\![q]\!]\). One solution: \([\![p]\!]=\{1\}\), \([\![q]\!]=\{1\}\), \([\![r]\!]=\{1,2,3\}\).
The sentence All \(\overline q\) are \(r\) says that every element is in \([\![q]\!]\) or in \([\![r]\!]\). An element that is left out of all three sets breaks it. This is the usual mistake: with \([\![p]\!]=\{1\}\), \([\![q]\!]=\{1\}\), \([\![r]\!]=\{1,2\}\), the element \(3\) is in \([\![\overline q]\!]\) and not in \([\![r]\!]\).
The method of Example 5.46 gives a model as well: the states for \(\Gamma\cup\{\text{Some }r\text{ are }\overline q\}\) are the choices that respect \(p\le q\) and \(\overline q\le r\), namely \(\{p,q,r\}\), \(\{p,q,\overline r\}\), \(\{\overline p,q,r\}\), \(\{\overline p,q,\overline r\}\), \(\{\overline p,\overline q,r\}\).
Self-check only. Nothing here counts towards your grade.
By Corollary 5.45 you may answer in either way: find a model, or find a proof tree that ends in a contradiction.
We now know that \(\Gamma\vdash\varphi\) and \(\Gamma\vDash\varphi\) are the same relation. What we do not have yet is an efficient procedure that decides it. Searching for proof trees is harder than it was for \(\mathbf A\), because (raa) allows us to assume any sentence at any time. Next week we turn \(P_\Gamma\) into a graph that can be computed directly from \(\Gamma\), as we did with the all-graph for \(\mathbf A\), and we use it to finish the completeness proof for the smaller system \(\mathbf S\) as well.
~p for \(\overline p\), both in the
text boxes and in the tree editor. Under every text box there is a row of buttons that insert
symbols such as \(\vdash\), \(\vDash\), \(\subseteq\), \(\varnothing\), \(\bot\) at the cursor.Work in the model \(M=\{1,2,3,4,5,6\}\) with \([\![a]\!]=\{1,2\}\), \([\![b]\!]=\{2,3,4\}\) and \([\![c]\!]=\{1,2,3,4,5\}\).
Build a proof tree for each of the following, using only the rules of Definition 5.10. The root is
fixed. For every sentence, choose how it is obtained: an assumption from \(\Gamma\), a withdrawn
assumption, or a rule. Choosing a rule opens the premise boxes above the sentence: none for (axiom),
one for (some1), (some2) and (raa), two for (barbara) and (darii). Type a complemented noun as
~p. Remember that the premise of (raa) must be a contradiction, and that a withdrawn leaf
must be the semantic negation of the conclusion of an (raa) step below it.
Let the nouns be \(a,b,c,d,e\) and let \[\Gamma=\{\text{All }a\text{ are }b,\ \ \text{All }b\text{ are }a,\ \ \text{All }c\text{ are }\overline b,\ \ \text{All }\overline d\text{ are }d,\ \ \text{All }e\text{ are }c\}.\]
Keep \(\Gamma\) from Question 3.