Identity: Computations

§ 1 Models for Identity

Identity is a special predicate of QL. We write it a bit differently than other two-place predicates: $x=y$ instead of $Ixy$. We also do not need to include it in a symbolization key. The sentence $x=y$ always means $x$ is identical to $y$,' and it cannot be interpreted to mean anything else. In the same way, when you construct a model, you do not get to pick and choose which ordered pairs go into the extension of the identity predicate. It always contains just the ordered pair of each object in the UD with itself.

The sentence $\forall x Ixx$, which contains an ordinary two-place predicate, is contingent. Whether it is true for an interpretation depends on how you interpret $I$, and whether it is true in a model depends on the extension of $I$.

The sentence $\forall x x=x$ is a tautology. The extension of identity will always make it true.

Notice that although identity always has the same interpretation, it does not always have the same extension. The extension of identity depends on the UD. If the UD in a model is the set {Doug}, then $extension(=)$ in that model is {$<$Doug, Doug$>$}. If the UD is the set {Doug, Omar}, then $extension(=)$ in that model is {$<$Doug, Doug$>$, $<$Omar, Omar$>$}. And so on.

If the referent of two constants is the same, then anything which is true of one is true of the other. For example, if $referent(a)=referent(b)$, then $Aa \leftrightarrow Ab$, $Ba\leftrightarrow Bb$, $Ca\leftrightarrow Cb$, $Rca\leftrightarrow Rcb$, $\forall x Rxa\leftrightarrow \forall x Rxb$, and so on for any two sentences containing $a$ and $b$. In metaphysics, this is called principle of the indiscernibility of identicals

In our system, the reverse of this principle is not true. It is possible that anything which is true of $a$ is also true of $b$, yet for $a$ and $b$ still to have different referents. This may seem puzzling, but it is easy to construct a model that shows this. Consider this model:

$$UD: \{Rosencrantz, Guildenstern\}$$

$$a: Rosencrantz$$

$$b: Guildenstern$$

$$= : \{ <Rosencrantz,Rosencrantz>,<Guildenstern,Guildenstern>\}$$

$$\text{For all predicates }P, extension(P) = \emptyset$$

This specifies an extension for every predicate of QL: All the infinitely-many predicates are empty. This means that both $Aa$ and $Ab$ are false, and they are equivalent; both $Ba$ and $Bb$ are false; and so on for any two sentences that contain $a$ and $b$. Yet $a$ and $b$ refer to different things. We have written out the extension of identity to make this clear: The ordered pair $<referent(a),referent(b)>$ is not in it. In this model, $a=b$ is false and $a\neq b$ is true.

§ 2 Deduction with Idetnity

The identity predicate is not part of QL, but we add it when we need to symbolize certain sentences. For proofs involving identity, we add two rules of proof.

Suppose you know that many things that are true of $a$ are also true of $b$. For example: $Aa\wedge Ab$, $Ba\wedge Bb$, $\neg Ca\wedge\neg Cb$, $Da\wedge Db$, $\neg Ea\wedge\neg Eb$, and so on. This would not be enough to justify the conclusion $a=b$. In general, there are no sentences that do not already contain the identity predicate that could justify the conclusion $a=b$. This means that the identity introduction rule will not justify $a=b$ or any other identity claim containing two different constants.

However, it is always true that $a=a$. In general, no premises are required in order to conclude that something is identical to itself. So this will be the identity introduction rule, abbreviated =I:

$$c = c \quad =I$$

Notice that the =I rule does not require referring to any prior lines of the proof. For any constant c, you can write $c=c$ on any point with only the =I rule as justification.

If you have shown that $a=b$, then anything that is true of $a$ must also be true of $b$. For any sentence with $a$ in it, you can replace some or all of the occurrences of $a$ with $b$ and produce an equivalent sentence. For example, if you already know $Raa$, then you are justified in concluding $Rab$, $Rba$, $Rbb$. Recall that $A[a|b]$ is the sentence produced by replacing a in A with b. This is not the same as a substitution instance, because b may replace some or all occurrences of a. The identity elimination rule =E justifies replacing terms with other terms that are identical to it:

§ 3 Trees with Identity

To deal with identity, we enrich our tree rules with a new composition rule:

Identity decomposition: when a path contains both $\alpha = \beta$ and $\theta_1$, where $\theta_1$ contains $\alpha$ in one of its predicates, a new node with $\theta_2$ where at least one occurrence of $\alpha$ has been replaced by a $\beta$. The node $\alpha = \beta$ does not get checked and be used indefinitely.

For example, say $a = b$ and $Paa$ is on the same path. I am allowed to add to the path $Pab$, $Pba$ and $Pbb$. Note that we do not have to change all occurrences of $a$ unless we want to.

With the introduction of the identity symbol, we also introduce a new condition under which a branch should be closed:

When $\neg \alpha = \alpha$ occurs on a branch, the branch is contradictory and should be closed.