by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[Logic and Semantics, entry directory]
[Graham Priest, entry directory]
[Priest, Introduction to Non-Classical Logic, entry directory]
[The following is summary of Priest’s text, which is already written with maximum efficiency. Bracketed commentary and boldface are my own, unless otherwise noted. I do not have specialized training in this field, so please trust the original text over my summarization. I apologize for my typos and other unfortunate mistakes, because I have not finished proofreading, and I also have not finished learning all the basics of these logics.]
Summary of
Graham Priest
An Introduction to Non-Classical Logic: From If to Is
Part II:
Quantification and Identity
12.
Classical First-order Logic
12.5
Identity
Brief summary:
(12.5.1) The identity predicate is a binary predicate symbolizes as ‘=’ and formulated as ‘a1 = a2’. We can write ‘¬a1 = a2’ as ‘a1 ≠ a2’. (12.5.2) “In any interpretation, ⟨D, v⟩, v(=) is {⟨d, d⟩: d ∈ D}. That is, ⟨d, e⟩ is in the denotation of the identity predicate, just if d is e” (272). (12.5.3) We add two tableau rules for identity to our given list. One is like the principle of identity, where we can always add in a tableau a formula of the form a = a. The other is the Substitutivity of Identicals, where whenever we have a formula of the form a = b, we can always substitute one term for the other in the formulas.
| Double Negation Development (¬¬D) |
| ¬¬A ↓ A |
| Conjunction Development (∧D) |
| A ∧ B ↓ A ↓ B |
| Negated Conjunction Development (¬∧D) |
| ¬(A ∧ B) ↙ ↘ ¬A ¬B |
| Disjunction Development (∨D) |
| A ∨ B ↙ ↘ A B |
| Negated Disjunction Development (¬∨D) |
| ¬(A ∨ B) ↓ ¬A ↓ ¬B |
| Conditional Development (⊃D) |
| A ⊃ B ↙ ↘ ¬A B |
| Negated Conditional Development (¬⊃D) |
| ¬(A ⊃ B) ↓ A ↓ ¬B |
| Biconditional Development (≡D) |
| A ≡ B ↙ ↘ A ¬A B ¬B |
| Negated Biconditional Development (≡D) |
| A ≡ B ↙ ↘ A ¬A ¬B B |
| Negated Existential Development (¬∃D) |
| ¬∃xA ↓ ∀x¬A |
| Negated Universal Development (¬∀D) |
| ¬∀xA ↓ ∃x¬A |
| Universal Instantiation Development (UI,D) |
| ∀xA ↓ Ax(a)
where a is any constant on the branch. (If there are not any, we select one at will.) |
| Particular Instantiation Development (PI,D) |
| ∃ xA↓ Ax(c)
where c is any constant that does not occur so far on the branch. |
| Principle of Identity Development (=D) |
| . ↓ a = a
(You can always add a line of the form a = a) |
| Substitutivity of Identicals (SI,D) |
| a = b ↓ Ax(a) ↓ Ax(b)
where A is any atomic sentence distinct from a = b. |
(6-8; 266, 272, with names and additional text at the bottom made by me)
(12.5.4) Because SI allows us to substitute identical terms, if we have a formula of the form a = b on one line and Saa on another, then we can also have Sba, Sab, and Sbb. (12.5.5) “The first identity rule has two functions. The first is to close any branch with a line of the form a ≠ a. The second is to allow us, given an identity, to interchange a and b: a = b ; a = a ; b = a [...] This allows us to close any tableau with lines of the form a = b and b ≠ a, and also to apply SI substituting a for b, instead of the other way around” (273). Note, in our tableau, we will not add lines of a = a in order to close branches with ¬a = a. Rather, if we obtain ¬a = a, we simply close them there. Likewise, if on a branch we have a = b and b ≠ a, we will simply close the branch there without the added steps. (12.5.6) We will use the comments in the above two sections in our frequent encounters with tableaux for identity. (12.5.7) Priest next gives a tableau example for a valid formula. (12.5.8) Priest then gives a tableau example for an invalid formula. (12.5.9) “To read off a counter-model from an open branch, we take a domain which contains a distinct object, ∂b, for every constant, b, on the branch. v(b) is ∂b. v(P) is the set of n-tuples ⟨∂b1, . . . , ∂bn⟩ such that Pb1 . . . bn occurs on the branch. Of course, if ¬Pb1 . . . bn is on the branch, ⟨∂b1, . . . , ∂bn⟩ ∉ v(P), since the branch is open. (If a predicate or constant does not occur on the branch, the value given to it by v is a don’t care condition: it can be anything one likes.)” (p.268). However, “whenever we have a bunch of lines of the form a = b, b = c, etc., we choose one of the constants, say, a, and let all the constants in the bunch denote ∂a” (274). (12.5.10) Priest gives an example counter-model. (12.5.11) The tableaux are sound and complete.
[Basics of the Identity Predicate]
[The Denotation of the Identity Predicate]
[The Identity Rules for the Tableaux]
[Substitutivity of Identicals]
[The Two Functions of the First Identity Rule]
[The Frequency of Tableaux for Identity]
[Tableau Example 1]
[Tableau Example 2]
[Counter-Models]
[An Example Counter-Model]
[The Soundness and Completeness of the Tableaux]
Summary
[Basics of the Identity Predicate]
[The identity predicate is a binary predicate symbolizes as ‘=’ and formulated as ‘a1 = a2’. We can write ‘¬a1 = a2’ as ‘a1 ≠ a2’.]
[Priest will now examine the identity predicate and its behavior in classical logic. It is a binary predicate that is symbolized as =. But instead of our normal convention of putting both terms after the symbol for the predicate, here we use the familiar convention of putting terms on both sides of the predicate symbol. And for ¬a1 = a2 we write a1 ≠ a2.]
In this section we consider the behaviour of the identity predicate. We can take this to be one of the binary predicates, say P02. It is normally written as =, and written between its arguments, not to the left of them, thus: a1 = a2. I will follow this convention. a1 ≠ a2 is an alternative notation for ¬a1 = a2.
(272)
[The Denotation of the Identity Predicate]
[“In any interpretation, ⟨D, v⟩, v(=) is {⟨d, d⟩: d ∈ D}. That is, ⟨d, e⟩ is in the denotation of the identity predicate, just if d is e” (272).]
[The next idea I may missummarize, so please read the quotation below. It might be the following. The identity predicate is a binary predicate. Let us recall some ideas from section 12.3.1. Priest writes:
Dn is the set of all n-tuples of members of D, {⟨d1, ..., dn⟩: d1, ..., dn ∈ D}.
(p.264, section 12.3.1)
Suppose we have in our domain a, b, and c. D2 might then be:
{⟨a, a⟩, ⟨a, b⟩, ⟨a, c⟩, ⟨b, b⟩, ⟨b, c⟩, ⟨c, c⟩}
But I am guessing. Priest writes now: “In any interpretation, ⟨D, v⟩, v(=) is {⟨d, d⟩: d ∈ D}.” So I would guess that v(=) is here {⟨a, a⟩, ⟨b, b⟩, ⟨c, c⟩}. Then he writes: “That is, ⟨d, e⟩ is in the denotation of the identity predicate, just if d is e.” So, a couple (a 2-tuple) is assigned to the identity predicate only if both terms are the same object, I think.]
In any interpretation, ⟨D, v⟩, v(=) is {⟨d, d⟩: d ∈ D}. That is, ⟨d, e⟩ is in the denotation of the identity predicate, just if d is e.
(272)
[The Identity Rules for the Tableaux]
[We add two tableau rules for identity to our given list. One is like the principle of identity, where we can always add in a tableau a formula of the form a = a. The other is the Substitutivity of Identicals, where whenever we have a formula of the form a = b, we can always substitute one term for the other in the formulas.]
[Our tableau rules will be those from section 12.4.1 plus two new ones. I will place all of them here below for reference.
| Double Negation Development (¬¬D) |
| ¬¬A ↓ A |
| Conjunction Development (∧D) |
| A ∧ B ↓ A ↓ B |
| Negated Conjunction Development (¬∧D) |
| ¬(A ∧ B) ↙ ↘ ¬A ¬B |
| Disjunction Development (∨D) |
| A ∨ B ↙ ↘ A B |
| Negated Disjunction Development (¬∨D) |
| ¬(A ∨ B) ↓ ¬A ↓ ¬B |
| Conditional Development (⊃D) |
| A ⊃ B ↙ ↘ ¬A B |
| Negated Conditional Development (¬⊃D) |
| ¬(A ⊃ B) ↓ A ↓ ¬B |
| Biconditional Development (≡D) |
| A ≡ B ↙ ↘ A ¬A B ¬B |
| Negated Biconditional Development (≡D) |
| A ≡ B ↙ ↘ A ¬A ¬B B |
| Negated Existential Development (¬∃D) |
| ¬∃xA ↓ ∀x¬A |
| Negated Universal Development (¬∀D) |
| ¬∀xA ↓ ∃x¬A |
| Universal Instantiation Development (UI,D) |
| ∀xA ↓ Ax(a)
where a is any constant on the branch. (If there are not any, we select one at will.) |
| Particular Instantiation Development (PI,D) |
| ∃ xA↓ Ax(c)
where c is any constant that does not occur so far on the branch. |
| Principle of Identity Development (=D) |
| . ↓ a = a
(You can always add a line of the form a = a) |
| Substitutivity of Identicals (SI,D) |
| a = b ↓ Ax(a) ↓ Ax(b)
where A is any atomic sentence distinct from a = b. |
(6-8; 266, 272, with names and additional text at the bottom made by me)
In other words, anywhere in a tableau we can add a formula of the form a = a, and if a = b, then we can substitute one for the other in formulas.]
The tableau rules that need to be added to handle = are as follows:
Principle of Identity
Development (=D)
.
↓
a = a
(You can always add a line of the form a = a)
Substitutivity of Identicals (SI,D)
a = b
↓
Ax(a)
↓
Ax(b)
(where A is any atomic sentence distinct from a = b.)
(272, with names and additional text at the bottom made by me)
Ax(b) The first rule says that we can always add a line of the form a = a. In the second, which is called the Substitutivity of Identicals (SI), A is any atomic sentence distinct from a = b. (It could be any sentence, but this is enough, and makes for more manageable tableaux.) As usual, the two lines above the arrow can occur in any order, and do not have to be consecutive.
(272)
[Substitutivity of Identicals]
[Because SI allows us to substitute identical terms, if we have a formula of the form a = b on one line and Saa on another, then we can also have Sba, Sab, and Sbb.]
[(ditto)]
SI says, in effect, that when we have a line of the form a = b we can substitute b for any number of occurrences of a in any line (above or below) with an atomic formula. Thus, suppose that the line is of the form Saa. This is (Sxa)x(a), (Sax)x(a), and (Sxx)x(a). Hence, we can apply the rule to get, respectively, (Sxa)x(b), (Sax)x(b), and (Sxx)x(b); that is, Sba, Sab, and Sbb. Note that one cannot check a line of the form a = b to indicate that | one has finished with it, since one may have to come back and apply it to a new formula of the form Ax(a). But, as for UI, one can keep track of the lines to which it has been applied.
(272-273)
[The Two Functions of the First Identity Rule]
[“The first identity rule has two functions. The first is to close any branch with a line of the form a ≠ a. The second is to allow us, given an identity, to interchange a and b: a = b ; a = a ; b = a [...] This allows us to close any tableau with lines of the form a = b and b ≠ a, and also to apply SI substituting a for b, instead of the other way around” (273). Note, in our tableau, we will not add lines of a = a in order to close branches with ¬a = a. Rather, if we obtain ¬a = a, we simply close them there. Likewise, if on a branch we have a = b and b ≠ a, we will simply close the branch there without the added steps.]
[Priest next explains the two main functions of the first identity rule, which again is:
| Principle of Identity Development (=D) |
| . ↓ a = a
(You can always add a line of the form a = a) |
The first function seems to be the following. Suppose in our branch we somehow obtain a ≠ a. We can thus close the branch by adding a = a. For the second function, suppose we have a = b on one line and b ≠ a on another. We need to get b = a in order to close the branch. To obtain it, we will use both rules for identity. So we already have a = b. We then add a = a using the first rule. Finally, by using SI, we substitute the first a of a = a with b to get b = a.]
The first identity rule has two functions. The first is to close any branch with a line of the form a ≠ a. The second is to allow us, given an identity, to interchange a and b:
a = b
a = a
b = a
(The last line is obtained by substituting b for the first occurrence of a in the second line.) This allows us to close any tableau with lines of the form a = b and b ≠ a, and also to apply SI substituting a for b, instead of the other way around. In practice it is simplest to forget the lines of the form a = a, but to close all branches that contain a line of the form a = a, or lines of the form a = b and b ≠ a, and to apply SI to the constants on both sides of an identity. I will follow this procedure.
(273)
[The Frequency of Tableaux for Identity]
[We will use the comments in the above two sections in our frequent encounters with tableaux for identity.]
[(ditto)]
We will meet tableau for identity many times in this book. The comments of 12.5.4 and 12.5.5, in the appropriate form, should be taken as carrying over to all of these.
(273)
[Tableau Example 1]
[Priest next gives a tableau example for a valid formula.]
[(ditto)]
Here is a tableau to show that ⊢ a = b ⊃ (∃xSxa ⊃ (a = a ∧ ∃xSxb)).
⊢ a = b ⊃ (∃xSxa ⊃ (a = a ∧ ∃xSxb))
1.
.
.
2.
.
3.
.
4.
.
5.
.
6.
.
7.
.
8.
.
9.
.
10.
¬(a = b ⊃
(∃xSxa ⊃ (a = a ∧ ∃xSxb)))
↓
a = b
↓
¬(∃xSxa ⊃ (a = a ∧ ∃xSxb))
↓
∃xSxa
↓
¬(a = a ∧ ∃xSxb)
↓
Sca
↙ ↘
¬a = a ¬∃xSxb
× ↓
∀x¬Sxb
↓¬Scb
↓
Scb
×
P
.
.
1¬⊃
.
1¬⊃
.
2¬⊃
.
2¬⊃
.
4PI
.
5¬⊃
(7×=)
5¬⊃
.
8UI
.
6,2SI
(10×9)
Valid
(enumeration and step accounting are my own and are probably mistaken)
|
The last line on the right branch is obtained by SI, with the identity on line two being applied to line six.
(273-274)
[Tableau Example 2]
[Priest then gives a tableau example for an invalid formula.]
[(ditto)]
Here is another example to show that a = b ⊬ ∀x∃y(Py ∧ x = y).
a = b ⊬ ∀x∃y(Py ∧ x = y)
1.
.
2.
.
3.
.
4.
.
5.
.
6.
.
7.
.
8.
.
9.
.
10.
a = b
↓
¬∀x∃y(Py ∧ x = y)
↓
∃x¬∃y(Py ∧ x = y)
↓
¬∃y(Py ∧ c = y)
↓
∀y¬(Py ∧ c = y)
↓
¬(Pc ∧ c = c)
↓
¬(Pb ∧ c = b)
↓
¬(Pa ∧ c = a)
↙ ↘
¬Pc ¬c = c
↙ ↘ ×
¬Pb ¬c = b
↙ ↘ ↙ ↘
¬Pa ¬c = a ¬Pa ¬c = a
P
.
P
.
2¬∀
.
3PI
.
2¬⊃
.
5UI
.
5UI
.
5UI
6¬∧
(9×=)
7¬∧
.
8¬∧
(open)
invalid
(enumeration and step accounting are my own and are probably mistaken)
Since there are no atomic formulas other than a = b on any branch, there are no applications of SI to be made.
(274)
[Counter-Models]
[“To read off a counter-model from an open branch, we take a domain which contains a distinct object, ∂b, for every constant, b, on the branch. v(b) is ∂b. v(P) is the set of n-tuples ⟨∂b1, . . . , ∂bn⟩ such that Pb1 . . . bn occurs on the branch. Of course, if ¬Pb1 . . . bn is on the branch, ⟨∂b1, . . . , ∂bn⟩ ∉ v(P), since the branch is open. (If a predicate or constant does not occur on the branch, the value given to it by v is a don’t care condition: it can be anything one likes.)” (p.268). However, “whenever we have a bunch of lines of the form a = b, b = c, etc., we choose one of the constants, say, a, and let all the constants in the bunch denote ∂a” (274).]
[Recall from section 12.4.8 how we constructed counter-models:
To read off a counter-model from an open branch, we take a domain which contains a distinct object, ∂b, for every constant, b, on the branch. v(b) is ∂b. v(P) is the set of n-tuples ⟨∂b1, . . . , ∂bn⟩ such that Pb1 . . . bn occurs on the branch. Of course, if ¬Pb1 . . . bn is on the branch, ⟨∂b1, . . . , ∂bn⟩ ∉ v(P), since the branch is open. (If a predicate or constant does not occur on the branch, the value given to it by v is a don’t care condition: it can be anything one likes.)
(p.268, section 12.4.8)
I may get this next idea wrong, but formulating counter-models with the identity predicate might involve the following; yet, consult the quotation below to be sure. Whenever we have a = b sorts of formulas, given the substitutability, it is redundant to make a counter-model that designates the objects for identical constants. And so, suppose we have a = b. Our counter-model would only need one object designation for both a and b. Or suppose we have a = b, b = c. I am not certain, but perhaps here even we would only need one of the three. Now note, from what is given in the example in section below, it seems that the counter-model needs to designate the equivalence in the following way: v(a) = v(b) = ∂a.]
To read off a counter-model from an open branch, we proceed as before, except that whenever we have a bunch of lines of the form a = b, b = c, etc., we choose one of the constants, say, a, and let all the constants in the bunch denote ∂a. It does not matter which constant was chosen from those said to be identical, since SI has been applied as often as possible.
(274)
[An Example Counter-Model]
[Priest gives an example counter-model.]
[Priest next makes a counter-model from the leftmost branch of the example tableau in section 12.5.8. I am going to guess how this works, so please see the quotation below. In that branch, we have constants a, b, and c. But since a = b, we will only place a and c in the domain. And we have ¬Pa and ¬Pc, that means we have v(P) = φ. Also note that we will set up the constant designations in accordance with the equivalences, so we have: v(a) = v(b) = ∂a, v(c) = ∂c. Now, let us look at the inference again to see if we can find that it makes the premise true and the conclusion false:
a = b ⊬ ∀x∃y(Py ∧ x = y)
I am going to guess that the premise is true, because our counter-model establishes that equivalence of a and b. Next, we are saying that P does not hold for a or for c. That alone makes the left conjunct false and thus the whole conjunction false. For, there is no y such that P holds for it.]
Thus, in the interpretation given by the leftmost open branch of the tableau in 12.5.8, D = {∂a, ∂c}, v(a) = v(b) = ∂a, v(c) = ∂c, and v(P) is given by the following table:
∂a
∂c
P
×
×
so that v(P) = φ. I leave it as an exercise to check that this counter-model works.
(274)
[The Soundness and Completeness of the Tableaux]
[The tableaux are sound and complete.]
[(ditto)]
The soundness and completeness of the tableaux are proved in 12.9.
(275)
From:
Priest, Graham. 2008 [2001]. An Introduction to Non-Classical Logic: From If to Is, 2nd edn. Cambridge: Cambridge University.
No comments:
Post a Comment