THE LOGIC NOTES

Identity Identity and existence

In this section we shall consider one further extension of the logical apparatus, and a very important one. This is the addition of a means of describing things as identical or different. 'Identical' here is to mean strictly one and the same thing, not just 'exactly similar' as it often does in colloquial speech. Examples of true identity statements include

Tully is Cicero
Hesperus is Venus
George Orwell is Eric Blair
32 is 9

There are other locutions for saying such things. Other ways of saying that Hesperus is Venus include

Hesperus and Venus are identical
Hesperus is the same thing as Venus
Hesperus and Venus are one and the same

Do not confuse the 'is' of identity with the copula, or 'is' of predication. Be clear as to the difference between the roles of 'is' in the two sentences

Tasmania is no place for the faint-hearted
Tasmania is Van Diemen's Land

In the former, the 'is' is part of a monadic predicate, so the best formalisation is something like Ft. The latter asserts that the objects Tasmania and Van Diemen's Land are in fact not distinct but the same place.

The formal notation for identity is the symbol '='. Where t and u are terms, we may form an identity statement by inserting '=' between them

t = u

as is familiar from primary school arithmetic. Technically, the identity symbol is a dyadic predicate, but we write it in infix position (between the two terms) rather than in prefix position, for reasons of familiarity. It symbolises a relation: the trivial relation that everything has to itself and nothing has to anything else.

Negated identity statements may be written

tu

rather than

NOT(t = u)

Atm t = u =E
Aum
  =I
t = t
:   Rules for Identity

again for familiarity and convenience, though the two ways of writing them mean exactly the same and may be used interchangeably as desired. Again there are several locutions for non-identity: we may say that thigs are different, distinct, not the same, are two, etc.

The rules for introduction and elimination of identity in proofs are quite simple. In the first place, everything is itself, as a matter of logic. Accordingly, the introduction rule for '=' allows any self-identity statement to be introduced on a line by itself, resting on no assumptions at all. The annotation is simply the expression '=I'. No line numbers are cited, as the identity is not derived from anything but taken as a theorem. This allows us to prove sequents like that in iIproof. Note that the identity on line (2) is a theorem, not an assumption. Incidentally, this proof also illustrates the point made earlier that SOMEI need not turn every a into the variable x.

SP {Fa ⊢ SOMEx ( x = a AND Fx )} PL {1} {1} {Fa} {A} PL { } {2} {a = a} {=I} PL {1} {3} {a = a AND Fa} {1,2 ANDI} PL {1} {4} {SOMEx (x = a AND Fx)} {3 SOMEI} EP
:   Proof by =I

The elimination rule corresponds to another very simple insight into the logical force of the particle. If a and b are one and the same thing, then whatever is true of a is true of b (because its being true of a just is its being true of b). To put the point another way, if a and b differ in some respect—say, a is red and b is not—then they are not identical. This law, or principle, of the indiscernability of identicals gives rise to the rule =E (see idRules). The reading this time is that Atmis a formula containing the term t and that Aumresults from it by replacing at least one occurence of t by u. The name m is a "dummy": it never actually appears, since t replaces it in one formula and u in the other. Its effect is to allow that there may be "side" occurrences of t or u (or both) in the formula being transformed. If so, these are unchanged by the substitution. The annotation consists of the two input line numbers and '=E', and the assumption numbers simply accumulate as in rules like ANDI and IMPE.

This possibility of substituting only some of the occurrences of a term allows the following trivial proof. SP {a = b ⊢ b = a} PL {1} {1} {a = b} {A} PL { } {2} {a = a} {=I} PL {1} {3} {b = a} {1,2 =E} EP

Here the first a but not the second in line (2) is replaced by b to give the conclusion. That is, in this case, to spell out the way this instance of the rule meets the formal specification in idRules, m is some dummy name like c, so A is the formula a = c. The terms t and u are a and b respectively, meaning that Atmis a = a and Aumis a = b. In the light of this proof, we can be assured that it does not matter which way round we read an identity statement. Hence no damage is done if we relax formalities far enough to allow u = t as the first premise of =E instead of the official t = u. This saves the tedium of adding two lines to every proof in which we have an identity the "wrong" way about.

SP {SOMEx ( x = a AND Fx ) ⊢ Fa} PL {1} {1} {SOME x ( x = a  AND  Fx )} {A} PL {2} {2} {b = a  AND  Fb} {A} PL {2} {3} {b = a} {2 ANDE} PL {2} {4} {Fb} {2 ANDE 2} PL {2} {5} {Fa} {3, 4 =E} PL {1} {6} {Fa} {1, 5 [2] SOMEE} EP
:   Proof by =E

For an example of a proof involving =E, see iEproof. The sequent is the converse of that proved earlier using =I. Note that SOMEE is allowed as the final step, even though the conclusion contains the arbitrary name a, for the typical name for which the variable substitutes is not a but b.

The addition of a notation for identity has greatly increased the expressive power of the limited language of first order logic. Without identity we can formalise 'Ted is running'

Rt

and such claims as that someone runs faster than Ted

SOMEx Fxt

but not a lot else in that vocabulary. With identity we can say

Ted alone is running Rt  AND  ALL(x: Rx) x = t
Everyone other than Ted is running ALL(x: xt) Rx
Ted is the fastest ALL(x: xt) Ftx
There is more than one runner SOME(x,y: xy) (Rx AND Ry)

The third of these is of some general interest. In English, adjectives like 'fast' which admit of degrees give rise to both comparative and superlative forms. The comparative 'faster than' may be formalised as a two-place relation as above. The logic of comparatives can be studied as a subject in its own right. Such relations obey certain laws such as:

ALL(x,y: Fxy) NOTFyx
ALL(x,y: Fxy) ALL(z: Fyz) Fxz
ALL(x,y: NOTFxy) ALL(z: Fxz) Fyz

Try to see why each of these is true of 'faster than'. Now the superlative 'fastest' is systematically related to the comparative. The fastest is the one faster than any other. To express this relationship, we need to be able to say 'other', and for this we may use '≠'. Thus the identity symbol yields a reduction of the logic of superlatives to that of comparatives which in turn can be represented in the calculus of relations. The effect is explanatory and a conceptual simplification.

The fourth of the above examples also generalises in interesting ways. With identity we have a means of saying that there are at least two things of a given kind. Without identity we cannot even say that there are two or more things in existence. Note that

SOMEx SOMEy (Fx AND Fy)

does not assert the existence of two F s, for they must be distinct:

SOME(x : Fx) SOME(y: Fy) xy

or with unrestriced (monadic) quantifiers:

SOMEx SOMEy ((Fx AND Fy) AND xy)

An equivalent formula which is slightly shorter is

ALLx SOME(y : Fy) xy

It may not be immediately evident why this shorter formula asserts the existence of at least two Fs. Informally, we may argue like this: take any individual a; by instantiating the formula to a we get SOME(y: Fy) ay, so clearly we have at least one F which we may call b; then similarly there exists an F, y, such that by; that is, we have another F, so there must be at least two of them.

SP {ALLx SOMEy (Fy  AND  x ≠ y) ⊢ SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y)} PL {1} {1} {ALLx SOMEy (Fy  AND  x ≠ y)} {A} PL {1} {2} {SOMEy (Fy  AND  a ≠ y)} {1 ALLE} PL {3} {3} {Fb  AND  a ≠ b} {A} PL {3} {4} {Fb} {3 ANDE} PL {1} {5} {SOMEy (Fy  AND  b ≠ y)} {1 ALLE} PL {6} {6} {Fc  AND  b ≠ c} {A} PL {6} {7} {Fc} {6 ANDE} PL {6} {8} {b ≠ c} {6 ANDE} PL {3,6} {9} {Fb AND Fc} {4, 7 ANDI} PL {3,6} {10} {(Fb AND Fc)  AND  b ≠ c} {8, 9 ANDI.} PL {3,6} {11} {SOMEy ((Fb AND Fy)  AND  b ≠ y)} {10 SOMEI} PL {3,6} {12} {SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y)} {11 SOMEI} PL {1,3} {13} {SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y)} {5, 12 [6] SOMEE} PL {1} {14} {SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y)} {2, 13 [3] SOMEE} EP
:   Plurality of Fs
Click to reconstruct the proof

This argument, formalised with unrestricted quantifiers, may be proved rigorously as shown in plurality1. Note that the identity rules are not required, so the same argument would go through with an arbitrary relation Rxy in place of the nonidentity relation xy. The converse is also provable (though not for arbitrary R) and constitutes a good exercise in combining the identity rules with SOMEE and ALLI (plurality2).

SP {SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y) ⊢ ALLx SOMEy (Fy  AND  x ≠ y)} PL {1} {1} {SOMEx SOMEy ((Fx AND Fy)  AND  x ≠ y)} {A } PL {2} {2} {NOTSOMEy (Fy  AND  a ≠ y)} {A } PL {3} {3} {SOMEy ((Fb AND Fy)  AND  b ≠ y)} {A } PL {4} {4} {(Fb AND Fc)  AND  b ≠ c} {A } PL {4} {5} {Fb AND Fc} {4 ANDE } PL {4} {6} {b ≠ c} {4 ANDE } PL {4} {7} {Fb} {5 ANDE } PL {4} {8} {Fc} {5 ANDE } PL {9} {9} {a = b} {A } PL {4,9} {10} {a ≠ c} {6,9 =E } PL {9} {11} {Fc  AND  a ≠ c} {8,10 ANDI } PL {4,9} {12} {SOMEy (Fy  AND  a ≠ y)} {11 SOMEI } PL {2,4} {13} {a ≠ b} {2,12 [9] RAA } PL {2,4} {14} {Fb  AND  a ≠ b} {7,13 ANDI } PL {2,4} {15} {SOMEy (Fy  AND  a ≠ y)} {14 SOMEI } PL {4} {16} {NOTNOTSOMEy (Fy  AND  a ≠ y)} {2,15 [2] RAA } PL {4} {17} {SOMEy (Fy  AND  a ≠ y)} {16 NOTNOTE } PL {3} {18} {SOMEy (Fy  AND  a ≠ y)} {3,17 [4] SOMEE } PL {1} {19} {SOMEy (Fy  AND  a ≠ y)} {1,18 [3] SOMEE } PL {1} {20} {ALLx SOMEy (Fy  AND  x ≠ y)} {19 ALLI } EP
:   Plurality of Fs: Converse Proof
Click to reconstruct the proof

Clearly, in a similar way, we can say that there are at least three Fs:

SOME(x: Fx) SOME(y: Fy) SOME(z: Fz) (xy  AND  xz  AND  yz)

or more concisely and conveniently

ALLx ALLy SOME(z: Fz) (xz  AND  yz)

Generally, to say that there are more than n (i.e. at least n + 1) Fs:

ALLx1 ... ALLxn SOME(y: Fy) (x1 ≠ y  AND  ...  AND  xny)

To assert that there are at most two Fs is to deny that there are more than two. The same applies to 'at most n' for any chosen number n. Since we have the apparatus to say 'more than n' and we can express negation, 'at most' is expressible using identity. For example, we can straightforwardly formalise the creed of Unitarianism: there is one God at most:

SOMEx ALL(y: Gy) x = y

Equivalently, all gods are identical:

ALL(x: Gx) ALL(y: Gy) x = y

To say that there are at most two Fs we can use

SOMEx SOMEy ALL(z: Fz) (x = z  OR  y = z)

and generally, for any given number n we can express 'There are at most n Fs':

SOMEx1 ... SOMExn ALL(y: Fy) (x1 = y  OR  ...  OR  xn = y)

Finally, there are exactly twenty Fs if there are at least twenty and at most twenty; that is, if there are twenty and no more. The same goes for any other number n. Thus we can express these numerically definite quantifiers just by conjoining the appropriate pairs of numerically indefinite ones. In the cases of small numbers, there are neater ways of expressing them using biconditionals. So 'there is exactly one F' may be written

SOMEx ALLy (Fy  ↔  x = y)

and 'there are exactly two Fs'

SOME(x,y: xy) ALLz (Fz  ↔  (x = z  OR  y = z))

The most important numerically definite quantifier is 'There is exactly one...' which expresses the existence and uniqueness of something satisfying a description. To say that there is exactly one F is to assert the existence of such a thing as the F. The formalisation of expressions of the form 'the F' opens up so many philosophical issues that it has been given a section to itself below. Meanwhile, we can note that the introduction of a notation for identity, trivial as it may at first seem, has given us a systematic way of proving valid such "arithmetical" arguments as

There are at most 70 guests at the party.
At least 60 of them are students.
Exactly 15 of the party guests are logicians.
Therefore at least 5 students are logicians.

Don't try writing out the proof of this for real—unless you have a lot of time to kill!

What is interesting, and important, is that these arguments turn out to be valid in virtue of pure logic, and do not require any reference to number theory. We cannot prove in first order logic that 70 − 60 = 10 or that 15 − 10 = 5, but we can secure some of the uses which these equations have in reasoning.