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).

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.

Valid CSS ? Valid HTML ? Written by Eddy.