Properties of Relations Exercise

Prove the following for any non-empty domain:

1. All asymmetric relations are irreflexive:

(x)(y)(Rxy ⊃ ~Ryx) // (x)~Rxx

2. All irreflexive and transitive relations are asymmetric:

(x)~Rxx, (x)(y)(z)((Rxy & Ryz) ⊃ Rxz) //(x)(y)(Rxy ⊃ ~Ryx)

3. All intransitive relations are irreflexive.

            (x)(y)(z)(((Rxy & Ryz) ⊃ ~Rxz) ⊃  (x)~Rxx)

4. Prove that identity is transitive:

    (x)(y)(z)((x = y) & (y = z) ⊃ (x = z))

5. Show that no relation can be:

a. Intransitive and reflexive

b. Asymmetrical and non-reflexive

c. Transitive, reflexive, and asymmetric

d. Transitive, non-symmetric and irreflexive.

Selected Proofs