Proofs with Identity

Identity needs its own rule in proofs. You already use identity in translations (At Least, At Most and Exactly); here it joins the quantifier rules (Proofs with Quantifiers) and quantifier order (Quantifier Order) in the proof system.

The identity rule (Id).
Form of Id	From	Infer
Reflexivity	(nothing)	$a = a$
Symmetry	$a = b$	$b = a$
Substitution	$Fa$ and $a = b$	$Fb$ (replacing some or all occurrences)

Key idea

Id has three forms: write $a = a$ at any time; turn $a = b$ around into $b = a$; and from a line about $a$ plus $a = b$, replace $a$ by $b$ in some or all places. Every use is justified "Id" with the lines it cites.

Why it works

Everything is identical to itself, so $a = a$ needs no premise. Identity goes both ways: if $a$ is $b$, then $b$ is $a$. And if $a$ and $b$ are one object, anything true of it under one name is true under the other: if Mark Twain wrote a novel and Mark Twain is Samuel Clemens, then Samuel Clemens wrote a novel. Substitution is that principle written as a rule.

Substitution makes the antecedent match.

Worked examples

Worked example: Substitution

From $Fa$ and $a = b$, infer what by Id?

Replace $a$ by $b$ in $Fa$.

Answer: $Fb$

Worked example: Either direction

From $Ga$ and $b = a$, may you infer $Gb$ by Id?

The identity may be used either way round: $b = a$ also tells you $a$ and $b$ are one object.

Answer: Yes.

Worked example: Proving a non-identity

Premises $Fa$ and $\neg Fb$. Prove $a \ne b$.

Line 3: $a = b$ (AIP).
Line 4: $Fb$ by Id 1, 3.
Line 5: $Fb \land \neg Fb$ by Conj 4, 2.
Line 6: $a \ne b$ by IP 3–5.

Answer: If they were one object, it would both be and not be $F$.

Common mistake

Substituting in the wrong place, or treating $a = b$ as a premise about a property. Id replaces a name by another name for the same object, inside a line you already have; it never changes a predicate letter, and $a = b$ is not a fact about $a$'s qualities. A check: the new line must be exactly the old one with some occurrences of one name swapped for the other.

Identity proofs often combine Id with the other rules: substitution to make two lines match, then MP, MT or DS to use them. When two names appear and an identity links them, ask which substitution would make a premise's antecedent (or a disjunct) look exactly like a line you already have.

Id never cites more than two lines: the identity and the line where a name is replaced.

With identity, the proof system is complete for the whole language of this course: every valid argument with names, predicates, quantifiers and $=$ has a proof. The capstone lesson explains what that claim means.

Reflexivity and EG together: Ava is something that is identical to Ava and is F.

Proofs with Identity

Worked examples

Practice

Builds on

Leads to

Sources and further reading