9-2. INFERENCE RULES FOR IDENTITY
You now know what '=' means, and you have practiced using '=' to say various things. You still need to learn how to use '=' in proofs. In this section I will give the rules for '=' both for derivations and for trees. If you have studied only one of these methods of proof, just ignore the rules for the one you didn't study.
As always, we must guide ourselves with the requirement that our rules be truth preserving, that is, that when applied to sentences true in an interpretation they should take us to new sentences also true in that interpretation. And the rules need to be strong enough to cover all valid arguments.
To understand the rules for both derivations and trees, you need to appreciate two general facts about identity. The first is that everything is self-identical. In any interpretation which uses the name 'a', 'a=al will be true. Thus we can freely use statements of self-identity. In particular, selfidentity should always come out as a logical truth.
The second fact about identity which our rules need to reflect is
144 Identity, Functions, ad Dejinitc Descriptionr 9-2. Inference Ruler for Identity 143
just this: If a=b, then anything true about a is true about b, and conversely.
I'm going to digress to discuss a worry about how general this second fact really is. For example, if Adam believes that Clark Kent is a weakling and if in addition Clark Kent is Superman, does it follow that Adam believes that Superman is a weakling? In at least one way of understanding these sentences the answer must be "no," since Adam may well be laboring under the false belief that Clark Kent and Superman are different people.
Adam's believing that Clark Kent is a weakling constitutes an attitude on Adam's part, not just toward a person however named, but toward a person known under a name (and possibly under a further description as well). At least this is so on one way of understanding the word 'believe'. On this way of understanding 'believe', Adam's attitude is an attitude not just about Clark Kent but about Clark Kent under the name 'Clark Kent'. Change the name and we may change what this attitude is about. What is believed about something under the name 'a' may be different from what is believed about that thing under the name 'b', whether or not in fact a=b.
This problem, known as the problem of substitutivity into belief, and other so-called "opaque" or "intensional" contexts, provides a major research topic in the philosophy of language. I mention it here only to make clear that predicate logic puts it aside. An identity statement, 'a= b', is true in an interpretation just in case 'a' and 'b' are names of the same thing in the interpretation. Other truths in an interpretation are specified by saying which objects have which properties, which objects stand in which relations to each other, and so on, irrespective of how the objects are named. In predicate logic all such facts must respect identity.
Thus, in giving an interpretation of a sentence which uses the predicate 'B', one must specify the things in the interpretation, the names of these things, and then the things of which 'B' is true and the things of which 'B' is false. It is most important that this last step is independent of which names apply to which objects. Given an object in the interpretation's domain, we say whether or not 'B' is true of that object, however that thing happens to be named. Of course, we may use a name in saying whether or not 'B' is true of an object-indeed, this is the way I have been writing down interpretations. But since interpretations are really characterized by saying which predicates apply to which objects, if we use names in listing such facts, we must treat names which refer to the same thing, so-called Co-Referential Names, in the same way. If 'a' and 'b' are names of the same thing and if we say that 'B' is true of this thing by saying that 'Ba' is true, then we must also make 'Bb' true in the interpretation.
In short, given the way we have defined truth in an interpretation, if 'a= b' is true in an interpretation, and if something is true of 'a' in the interpretation, then the same thing is true of 'b' in the interpretation. - Logicians say that interpretations provide an Extensional Semantics for predicate logic. "Semantics" refers to facts concerning what is true, and facts concerning meaning, insofar as rules of meaning have to do with what comes out true in one or another circumstance. "Extensional" means that the Extension of a predicate-the collection of things of which the predicate is true-is independent of what those things are called. Parts of English (e.g., 'Adam believes Clark Kent is a weakling') are not extensional. Predicate logic deals with the special case of extensional sentences. Because predicate logic deals with the restricted and special case of extensional sentences, in predicate logic we can freely substitute one name for another when the names name the same thing.
Now let's apply these two facts to write down introduction and elimination rules for identity in derivations. Since, for any name, s, s=s is always true in an interpretation, at any place in a derivation which we can simply introduce the identity statement s = s:
I Where r is any name.
If s does not occur in any governing premises or assumptions, it occurs arbitrarily and gets a hat. To illustrate, let's demonstrate that '(Vx)(x= x)' is a logical truth:
The second fact, that co-referential names can be substituted for each other, results in the following two rules:
The indicated substitutions may be for any number of occurrences of the name substituted for.
To illustrate, let's show that '(Vx)(Vy)[x = y 3 (Fx 3 Fy)]' is a logical truth:
144 Identity, Functions, and Definite Descrif~tMN 9-2. Inference Ruks for Identity 145
Now we'll do the rules for trees. We could pmceed much as we did with derivations and require that we write identities such as 'a=a' wherever this will make a branch close. An equivalent but slightly simpler rule instructs us to close any branch on which there appears a negated self-identity, such as 'afa'. This rule makes sense because a negated self-identity is a contradiction, and if a contradiction appears on a branch, the branch cannot represent an interpretation in which all its sentences are true. In an exercise you will show that this rule has the same effect as writing selfidentities, such as 'a=a', wherever this will make a branch close.
Rule f : For any name, s, if sf s appears on a branch, close the branch.
Let's illustrate by proving '(Vx)(x =x)' to be a logical truth:
J1 -(Vx)(x=x) -S J2 (3x)(xf X) 1, -V 3 afa 2, 3 X
The second rule for trees looks just like the corresponding rules for derivations. Substitute co-referential names:
Rule =: For any names, s and t, if s=t appears on a branch, substitute s for t and t for s in any expression on the branch, and write the result at the bottom of the branch if that sentence does not already appear on the branch. Cite the line numbers of the equality and the sentence into which you have substituted. But do not check either sentence. Application of this rule to a branch is not completed until either the branch closes or until all such substitutions have been made.
Let's illustrate, again by showing '(Vx)(Vy)[x= y 3 (Fx 3 Fy)]' to be a logical truth:
J1 -(Vx)(Vy)lx=y 3 (Fx 3 Fy)l J2 (3x)(3y)-Ix=y 3 (Fx 3 Fy)l J3 -[a=b > (Fa 3 Fb)] 4 a=b 45 -(Fa 3 Fb) 6 Fa 7 -Fb 8 -Fa X
Before closing this discussion of identity, I should mention that identity provides an extreme example of what is called an Equivalence Relation. Saying that identity is an equivalence relation is to attribute to it the following three characteristics:
Identity is Reflexive. Everything is identical with' itself: (Vx)(x=x). In general, to say that relation R is reflexive is to say that (Vx)R(x,x).
Identity is Symmetric. If a first thing is identical with a second, the second is identical with the first: (Vx)(Vy)(x= y 3 y = x). In general, to say that relation R is symmetric is to say that (Vx)(Vy)(R(x,y) 3 R(y,x)).
Identity is Transitive. If a first thing is identical with a second, and the second is identical with a third, then the first is identical with the third: (Vx)(Vy)(Vz)[(x = y & y = z) 3 x = z]. In general, to say that relation R is transitive is to say that (Vx)(Vy)(Vz)[(R(x,y) & R(y,z)) 3 R(x,z)].
You can prove that identity is an equivalence relation using either derivations or trees.
Here are some other examples of equivalence relations: being a member of the same family, having (exactly) the same eye color, being teammates on a soccer team. Items which are related by an equivalence relation can be treated as the same for certain purposes, depending on the relation. For example, when it comes to color coordination, two items with exactly the same color can be treated interchangeably. Identity is the extreme case of an equivalence relation because "two" things related by identity can be treated as the same for all purposes.
Equivalence relations are extremely important in mathematics. For example two numbers are said to be Equul Modulo 9 if they differ by an exact multiple of 9. Equality modulo 9 is an equivalence relation which is useful in checking your arithmetic (as you know if you have heard of the "rule of casting out 9s").
9-3. Show that each of the two =E rules can be obtained from the other, with the help of the =I rule.
146 Identify, Fundmas, and Definite Descriptions 9-4.
Show that the rule f is equivalent to requiring one to write, on each branch, self-identities for each name that occurs on the branch. Do the following three exercises using derivations, trees, or both:
9-5. Show that the following are logical truths:
9-6. Show that (3x)(Vy)(Fy = y = x) and (3x!)Fx are logically equivalent.
9-7. Prove that = is an equivalence relation.
9-8. Show the validity of the following arguments: a) (Vx)(x= a 3 Fx) b) Fa C) (3x)(Fx & x=a) Fa (Vx)(x = a 3 Fx) Fa d) (Vx)(x= a 3 Fx) e) Pa fl a=b (VX)(FX 3 ~b) (3y)(y=a&y=b)
9-9. 1 stated that being teammates on a soccer team is an equivalence relation. This is right, on the assumption that no one belongs to more than one soccer team. Why can the relation, being teammata on a soccer team, fail to be an equivalence relation if someone belongs to two teams? Are there any circumstances under which being teammates on a soccer team is an equivalence relation even though one or more people belong to more than one team?