Chapter 39 Rules for identity

In chapter 30, we mentioned the philosophically contentious thesis of the identity of indiscernibles. This is the claim that objects which are indiscernible in every way are, in fact, identical to each other. It was also mentioned that we will not subscribe to this thesis. It follows that, no matter how much you learn about two objects, we cannot prove that they are identical. That is unless, of course, you learn that the two objects are, in fact, identical, but then the proof will hardly be very illuminating.

The general point, though, is that no sentences which do not already contain the identity predicate could justify an inference to ‘ $a=b$ ’. So our identity introduction rule cannot allow us to infer to an identity claim containing two different names.

However, every object is identical to itself. No premises, then, are required in order to conclude that something is identical to itself. So this will be the identity introduction rule:

Line number	Subproof level	Formula	Justification
	0	$\mathscr{c}=\mathscr{c}$	=I

Notice that this rule does not require referring to any prior lines of the proof. For any name $\mathscr{c}$ , you can write $\mathscr{c}=\mathscr{c}$ on any line, with only the =I rule as justification.

Our elimination rule is more fun. If you have established ‘ $a=b$ ’, then anything that is true of the object named by ‘ $a$ ’ must also be true of the object named by ‘ $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, from ‘ $R(a,a)$ ’ and ‘ $a=b$ ’, you are justified in inferring ‘ $R(a,b)$ ’, ‘ $R(b,a)$ ’ or ‘ $R(b,b)$ ’. More generally:

Line number	Formula	Justification
$m$	$\mathscr{a}=\mathscr{b}$
$n$	$\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{a}\ldots)$
	$\mathscr{A}(\ldots\mathscr{b}\ldots\mathscr{a}\ldots)$	=E $m$ , $n$

The notation here is as for $\exists$ I. So $\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{a}\ldots)$ is a formula containing the name $\mathscr{a}$ , and $\mathscr{A}(\ldots\mathscr{b}\ldots\mathscr{a}\ldots)$ is a formula obtained by replacing one or more instances of the name $\mathscr{a}$ with the name $\mathscr{b}$ . Lines $m$ and $n$ can occur in either order, and do not need to be adjacent, but we always cite the statement of identity first. Symmetrically, we allow:

Line number	Formula	Justification
$m$	$\mathscr{a}=\mathscr{b}$
$n$	$\mathscr{A}(\ldots\mathscr{b}\ldots\mathscr{b}\ldots)$
	$\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{b}\ldots)$	=E $m$ , $n$

This rule is sometimes called Leibniz’s Law, after Gottfried Leibniz.

To see the rules in action, we will prove some quick results. First, we will prove that identity is symmetric:

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$a=b$	AS
$2$	1	$a=a$	=I
$3$	1	$b=a$	=E $1$ , $2$
$4$	close subproof, 0	$a=b\rightarrow b=a$	$\rightarrow$ I $1$ – $3$
$5$	0	$\forall y(a=y\rightarrow y=a)$	$\forall$ I $4$
$6$	0	$\forall x\,\forall y(x=y\rightarrow y=x)$	$\forall$ I $5$

We obtain line $3$ by replacing one instance of ‘ $a$ ’ in line $2$ with an instance of ‘ $b$ ’; this is justified given ‘ $a=b$ ’.

Second, we will prove that identity is transitive:

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$a=b\wedge b=c$	AS
$2$	1	$a=b$	$\wedge$ E $1$
$3$	1	$b=c$	$\wedge$ E $1$
$4$	1	$a=c$	=E $2$ , $3$
$5$	close subproof, 0	$(a=b\wedge b=c)\rightarrow a=c$	$\rightarrow$ I $1$ – $4$
$6$	0	$\forall z((a=b\wedge b=z)\rightarrow a=z)$	$\forall$ I $5$
$7$	0	$\forall y\,\forall z((a=y\wedge y=z)\rightarrow a=z)$	$\forall$ I $6$
$8$	0	$\forall x\,\forall y\forall z((x=y\wedge y=z)\rightarrow x=z)$	$\forall$ I $7$

We obtain line $4$ by replacing ‘ $b$ ’ in line $3$ with ‘ $a$ ’; this is justified given ‘ $a=b$ ’.

Practice exercises

A. For each of the following claims, provide an FOL proof that shows it is true.

1.

$P(a)\vee Q(b),Q(b)\rightarrow b=c,\neg P(a)\vdash Q(c)$
2.

$m=n\vee n=o,A(n)\vdash A(m)\vee A(o)$
3.

$\forall x\ x=m,R(m,a)\vdash\exists x\,R(x,x)$
4.

$\forall x\,\forall y(R(x,y)\rightarrow x=y)\vdash R(a,b)\rightarrow R(b,a)$
5.

$\neg\exists x\neg x=m\vdash\forall x\,\forall y(P(x)\rightarrow P(y))$
6.

$\exists x\,J(x),\exists x\,\neg J(x)\vdash\exists x\,\exists y\,\neg x=y$
7.

$\forall x(x=n\leftrightarrow M(x)),\forall x(O(x)\vee\neg M(x))\vdash O(n)$
8.

$\exists x\,D(x),\forall x(x=p\leftrightarrow D(x))\vdash D(p)$
9.

$\exists x\bigl{[}(K(x)\wedge\forall y(K(y)\rightarrow x=y))\wedge B(x)\bigr{]}% ,Kd\vdash B(d)$
10.

$\vdash P(a)\rightarrow\forall x(P(x)\vee\neg x=a)$

B. Show that the following are provably equivalent:

‣

$\exists x\bigl{(}[F(x)\wedge\forall y(F(y)\rightarrow x=y)]\wedge x=n\bigr{)}$
‣

$F(n)\wedge\forall y(F(y)\rightarrow n=y)$

And hence that both have a decent claim to symbolize the English sentence ‘Nick is the $F$ ’.

C. In chapter 26, we claimed that the following are logically equivalent symbolizations of the English sentence ‘there is exactly one $F$ ’:

‣

$\exists x\,F(x)\wedge\forall x\,\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x% =y\bigr{]}$
‣

$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
‣

$\exists x\,\forall y(F(y)\leftrightarrow x=y)$

Show that they are all provably equivalent. (Hint: to show that three claims are provably equivalent, it suffices to show that the first proves the second, the second proves the third and the third proves the first; think about why.)

D. Symbolize the following argument

There is exactly one $F$ .
There is exactly one $G$ .
Nothing is both $F$ and $G$ .
∴

There are exactly two things that are either $F$ or $G$ .

And offer a proof of it.