Raitis Veinbahs more about me my toy projects my github my asciinema

A proof about the identity relation

August 1, 2015

While working through the exercises of «How to Prove it» by Daniel Velleman, I stumbled upon the ¶ 5.1 Functions and the exercise 5.1.8. which has more than one proof, so I thought I’d post the one I imagined here to showcase my recently acquired proof writing skills.

8. Suppose A is a set. Show that iA is the only relation on A that is both an equivalence relation on A and also a function from A to A.

eq(r) = reflexive(r) and symmetric(r) and transistive(r)
eqendof(r) = eq(r) and r : A -> A

    eq   = equivalence relation
    endo = endomorphic function — from A to A
    f    = function

a. exists r: eqendof(r) and forall z: eqendof(z) -> z = r
or equivalently
b. exists r: eqendof(r) and forall z: z ≠ r -> not eqendof(z)

a. As per usual, we first prove existence, which here is trivial. Uniqueness is a tiny bit trickier and we can prove it by assuming f has the same property and equaling f to iA.

The chapter quickly presents Theorem 5.1.4., which claims ∀a ∈ A(f(a) = g(a)), then f = g. So if f is the function from A to A, then by letting a ∈ A, f ⊆ iA and iA ⊆ f is obvious.

b. There’s another way, however:

Suppose z ≠ iA, then it should be that it’s not an equivalence relation.

If that’s so there must be an element inside one of them that’s not in the other.

  1. If iA has such element, then z is not reflexive, so it’s not an equivalence relation, so eqendof(z) is false.
  2. If z has such element, then there’s a p in z that’s a pair of different elements: ∃ p in z: p = (x, y) and x ≠ y.
    1. Then x is in A and x = z(x) because it’s an equivalence relation, but also y = z(x) by 2.
    2. z(x) != z(x) so it’s not a function and therefore doesn’t have eqendof(z) is false.

Wasn’t that fun!