Equivalence

This page uses an old notation and may be superseded by newer material.

Among the primitive properties of relations, I define equivalence. An equivalence, r, satisfies: r relates x to y implies r relates y to y, y to x and x to x; and r relates x to y and y to z implies r relates x to z.

Now, quotient(r) is x-> ({x}:r|), so quotient(r)(x) is the equivalence class of x, under r; and its reverse, ({({x}:r|)}: (y in A: A->y) :(|r)), relates each equivalence class to each of its members. Thus, quotient(r)&on;(reverse(quotient(r))) is the identity on equivalence classes of r, that is on collections of form ({x}:r|). Now, since r is an equivalence, reverse(quotient(r))&on;quotient(r) relates each x to each member of its r-equivalence class: which is exactly what r does, so we have reverse(quotient(r))&on;quotient(r) =r.

Thus we can factorize any equivalence as reverse(q)&on;q for some mapping, q. Note that f&on;(reverse(f)) is an identity for any mapping, f: it is (f|), in fact. We can then use quotient(r) and its reverse to describe the relationships between equivalence classes, their members and relations (most notably mappings) involving these. For a general mapping f, we find that reverse(f)&on;f is trivially an equivalence. This defines a mapping from mappings to equivalences: composing it after quotient gives the identity on (the collection of) equivalences; reversing the order gives a projection from mappings to

For an equivalence S and any x in S, we have ({x}:S|) as the collection of values to which S relates x. This contains x and is equal to (|S:{x}), the collection of values which S relates to x. It is known as the S-equivalence class of x (and conventionally denoted as [x]_S or similar). The relation which relates each member of ({x}:S|) to every member of ({x}:S|) is a sub-equivalence of S.

We can use x->({x}:S|) as a quotient mapping; we can push-out any relation ((|S):r:) through it to r relates x to z: ({x}:S|)->z. This is mainly of interest when r&on;S = r, so that r relates y to z and S relates x to y always implies r relates x to z – S-equivalent things are r-related to the same things as one another. This actually says that S is a sub-relation of reverse(r)&on;r. When this condition holds and r is a mapping, the push-out is again a mapping. We can pull-back any relation (:t:(|S)) to t relates x to y: x->({y}:S|); if each ({x}:t|) is a sub-relation of some ({y}:S|), this pull-back is then a mapping (whether t was or not).

Rectangles

I'm going to want to decompose any equivalence as a union of disjoint symmetric restrictions of All. General restrictions of All are rectangular in the same sense as an identity is diagonal.

I'll describe a relation, r, as rectangular precisely if: r relates x to a and r relates b to y implies r relates x to y – that is, r = ((|r):all:(r|)). Notice that any rectangular relation is trivially transitive – and that, for a rectangular relation, symmetric and reflexive are equivalent. Proofs: given r rectangular

transitivity

r&on;r relates x to z precisely if there's some a for which r relates x to a and a to z, which then implies that r, being rectangular, relates x to z. Thus r&on;r is a sub-relation of r. (Of course, (|r) and (r|) might be disjoint, making r&on;r empty, but that's still a sub-relation of r.)

symmetric implies reflexive

Whenever r relates x to y, we have r relates y to x by symmetry: combining these two in first one order then the other and applying the rectangular property, we find that r relates x to x and y to y.

reflexive implies symmetric

Whenever r relates x to y, we have r relating y to y and x to x, so r, being rectangular, relates y to x.

So a rectangular relation which is either symmetric or reflexive is an equivalence, has each of its initial values as a final value (and vice versa) and relates each of its (initial/final) values to each of its values. It is entirely characterized by its collection of values: if it is C, we have (|C) = (C|) = {x in C} and C= x, y in C: x->y. From any relation r, define square(r) = x, y in r: x->y, the each to every relation on r's fixed points.

The way to get an equivalence to resemble a collection is to decompose it as a union of disjoint rectangular sub-equivalences. Each value, x, of the equivalence relation, S, is in ({x}:S|), and square(({x}:S|)) is a sub-equivalence of S: so we can achieve the desired decomposition using E = {({x}:S|): x in S}, the collection of S-equivalence classes. S is then unite(E:square|) and E constitutes a complete description of S.