Formal Logic 101 – Part 24: Proofs using Identity and Definite Descriptions

When using Identity symbolizations there are a handful of rules all of which (I would argue) are quite intuitive and in line with our normal understanding of the “=” sign.

First, we have “Identity Reflexivity” (ID. Ref), which simply states “a=a” at any point in a proof we may introduce “a=a” (or “b=b”, etc.) and simply cite “ID. Ref.” as our justification.

Secondly, we have “Identity Symmetry” (ID. Sym), which is a replacement rule stating that “a=b” is identical to “b=a”.

Thirdly, “Identity Substitution” (ID. Sub) which is another replacement rule, and states that, from “Ab” and “b=c”, we may conclude “Ac”.

Lastly, there is Identity Transitivity (ID. Trans), yet another replacement rule stating that from “a=b” and “b=c” we may conclude “a=c”.

Those are the extent of our rules surrounding identity. Again, I expect that none of these rules should be particularly shocking or controversial, and they all fit well with our typical understanding of how the equal sign works.

Identity and Indirect Proofs.

One of the major uses of Identity statements is to show that two things are not identical.
As a (perhaps overly obvious) example: Max is a dog. Charles is not a dog. Therefore, Max and Charles are not the same creature.

1. Dm               P
2. ~Dc              P – Prove m≠c
As with any indirect proof, we assume the opposite of that which we wish to prove.

3. m=c              A – prove contradiction
4. Dc                1,3 ID Sub
5. Dc ^ ~Dc     2,4, Conj
6. m≠c              3-5 I.P.

Do note, however, that this only works when needing to prove that two things are not identical. We cannot readily move from “Max is a dog,” and “Charles is a dog,” to “Max is Charles.”

*****
To wrap up the series, I’d like to provide an example of a fairly long proof that uses most of our rules.

Let us suppose that we’re in a pet store. We’re told that there every animal in the store that barks is a dog. And, of course, every dog is a canine. Lastly, we’re told that there are at most two canines, and also that there are at least two creatures that bark. From this, we should be reasonably confident that there are exactly two dogs… but can we prove it?
1. (x)(Bx → Dx)                                                                P
2. (x)(Dx → Cx)                                                               P
3. (x)(y)(z){[(Cx ^ Cy) ^ Cz] → [(x=y v x=z) v y=z]}     P
4. (∃x)(∃y)[(Bx ^ By) ^ x≠y]                                            P – Prove (∃x)(∃y){[(Dx ^ Dy) ^ x≠y] ^ (z)[Dz → (z=x v z=y)]}

Ok, we have our premises laid out. None of our quantifiers are negated, so there’s no real cause to use quantifier negation. So what we’ll probably want to do next is get everything out from behind those quantifiers so we can work with them. Recall that Existential Instantiation has restrictions, and Universal Instantiation doesn’t, so it’s best to use EI first.

5. ((∃y)[(Ba ^ By) ^ a≠y]                                                4 EI – flag a
6. (Ba ^ Bb) ^ a≠b                                                          5 EI – flag b
7. (y)(z){[(Ca ^ Cy) ^ Cz] → [(a=y v a=z) v y=z]}        3 UI
8. (z){[(Ca ^ Cb) ^ Cz] → [(a=b v a=z) v b=z]}           7 UI

Note that our intended conclusion includes (z), so we will presumably need to use Universal Instantiation. In order to use that appropriately, we will need to use a flagged subproof.

9. c                                                                                  F.S (U.G.)
10. [(Ca ^ Cb) ^ Cc] → [(a=b v a=c) v b=c]                8 U.I.

Now presumably we will want to reach [(Ca ^ Cb) ^ Cc], so we can conclude the second half of line 10. Fortunately, it looks like lines 1, 2, and 6 will be able to get us there.

11. Ba → Da                                                        1 UI
12. Da → Ca                                                        2 UI

13. Bb → Db                                                        1 UI
14. Db → Cb                                                        2 UI
15. Ba ^ Bb                                                           6 simp
16. Ba                                                                   15 simp
17. Bb                                                                   15 simp
18. Da                                                                   11,16 MP
19. Db                                                                   13,17 MP
20. Ca                                                                   12,18 MP
21. Cb                                                                   14, 19 MP
22. Ca ^ Cb                                                           20, 21 Conj

From here we need to figure out how to get Cc. We’ve already used c on line 9, so we can’t use EI on line 4 to get Bc like we’ve done for Ba or Bb. That said, if you’ll notice, our intended conclusion includes (z)[Dz → (z=x v z=y)]. So we’ll presumably need to assume the front half of the if-then statement at some point, and use conditional proof. And if we assume Dc we can use that and line 2 to conclude Cc. So let’s see about accomplishing both goals at the same time.

23. Dc                                                                                    Assumption - (c=a v c=b)
24. Dc → Cc                                                                         2 U.I.
25. Cc                                                                                    23,24 MP
26. (Ca ^ Cb) ^ Cc                                                                22,25 Conj
27. (a=b v a=c) v b=c                                                          10,26 MP
28. a≠b                                                                                  6 simp
29. a=b v (a=c v b=c)                                                          27 Assoc
30. a=c v b=c                                                                        28,29 D.S.
31. Dc → a=c v b=c                                                             23-30 C.P.
32. Dc → c=a v c=b                                                             31 ID Sym
33. (z)[Dz→(z=a v z=b)]                                                      9-32 U.G.
34. Da ^ Db                                                                           18, 19 conj
35. (Da ^ Db) ^ a≠b                                                              28, 34 conj
36. [(Da ^ Db) ^ a≠b] ^ (z)[Dz→(z=a v z=b)]                     33, 35 Conj
37. (∃y){[(Da ^ Dy) ^ a≠y] ^ (z)[Dz→(z=a v z=y)]}            36 EG
38. (∃x)(∃y){[(Dx ^ Dy) ^ x≠y] ^ (z)[Dz→(z=x v z=y)]}      37 EG

And there we go, we’ve now proven that there are exactly two dogs.

 

Alright! Congratulations, for sticking with us through all of this. We have now covered the entirety of “first-order” predicate logic. If you were to take a symbolic logic course in college, this would be roughly the extent of what you would cover in that course.

While I’m sure a professor would be able to cover more, and while I wouldn’t presume to pretend that a series of blog posts would suffice to replace an actual college course with an actual professor, I hope that this has at least provided an introductory understanding of formal logic.

Thank you for coming along with us on this adventure. I'm not sure how many people will read them, but I’m hoping that the people who do read them find them useful.

Back to Part 23