Properties of Relations - Selected Proofs
1. All asymmetric relations are irreflexive:
(x)(y)(Rxy ⊃ ~Ryx) // (x)~Rxx
Proof:
| 1. | (x)(y)(Rxy ⊃ ~Ryx) | Prem. | |
| 2. | ~(x)~Rxx | Assump., IP | SP1 |
| 3. | (∃x)~~Rxx | Q.N. 2 | SP1 |
| 4. | (∃x)Rxx | D.N. 3 | SP1 |
| 5. | Raa | EI, 4 flag a | SP1 |
| 6. | (y)(Ray ⊃ ~Rya) | UI, 1 | SP1 |
| 7. | Raa ⊃ ~Raa | UI, 6 | SP1 |
| 8. | ~Raa | M.P. 5, 7 | SP1 |
| 9. | Raa & ~Raa | Conj., 5, 8 | SP1 |
| 10. | (x)~Rxx | IP, 2-9 |
3. All intransitive relations are irreflexive.
(x)(y)(z)(((Rxy & Ryz) ⊃ ~Rxz) ⊃ (x)~Rxx)
| 1. | (x)(y)(z)((Rxy & Ryz) ⊃ ~Rxz) | Assump. CP | SP1 | |
| 2. | ~(x)~Rxx | Assump IP | SP1 | SP2 |
| 3. | (∃x)~~Rxx | QN, 2 | SP1 | SP2 |
| 4. | (∃x)Rxx | D.N. 3 | SP1 | SP2 |
| 5. | Raa | E.I. 4, flag a | SP1 | SP2 |
| 6. | (y)(z)((Ray & Ryz) ⊃ ~Raz) | U.I., 1 | SP1 | SP2 |
| 7. | (z)((Raa & Raz) ⊃ ~Raz) | U.I. 6 | SP1 | SP2 |
| 8. | ((Raa & Raa) ⊃ ~Raa) | U.I. 7 | SP1 | SP2 |
| 9. | Raa & Raa | Rep., 5 | SP1 | SP2 |
| 10. | ~Raa | M.P. 8, 9 | SP1 | SP2 |
| 11. | Raa & ~Raa | Conj., 5, 10 | SP1 | SP2 |
| 12. | (x)~Rxx | I.P., 2-11 | SP1 | |
| 13. | (x)(y)(z)((Rxy & Ryz) ⊃ ~Rxz) ⊃ (x)~Rxx | C.P. 1 - 12 |
| table of contents | List of Exercises |