The theory of relations

I was reading Naive Set Theory by Halmos, and he mentioned a reasonable definition for the composition of two relations, as well as the characterization of an equivalence relation using relation composition. On this page, I want to explore relations in some more detail (this is presently a work in progress).

We define a relation R between two sets X and Y to be any subset of X × Y, which we write as R : X ⇆ Y for short. If (x, y) ∈ R, then we say that x is related to y by R. We will write this symbolically as yRx. While the standard notation for this is xRy, we differ here because it will aid in the notation for relation composition and for functions.

We write R(x) for the set of all y such that yRx. Or, if U is a subset of X, then we write R(U) to be the union of all the R(x), where x ∈ U. We define (y)R and (V)R analogously. If it so happens that R(x) or (y)R are singleton sets, then we pretend that R(x) or (y)R are the element of their corresponding singleton set. Two special sets are the image of a relation, R(X), and the co-image (or domain) of a relation, (Y)R.

The inverse of a relation R : X ⇆ Y is a relation R−1 : Y ⇆ X defined by xR−1y whenever yRx. Generally, something is co- for some relation if the non-co- version applies to its inverse (i.e., “the arrows are reversed”).

There are a few important properties for a relation:

A relation which is both an injection and an co-injection can also be called one-to-one. An example of such a relation is “is the right foot of” where X is the set of feet and Y is the set of people.

A function f : X → Y is a relation which is a co-surjection and a co-injection. This means that for every x ∈ X, there is exactly one y ∈ Y such that yfx. We refer to this y using the notation f(x). A co-function is a relation whose inverse is a function. Note that this means a co-function is a surjection and an injection. Hence, a bijection is a relation which is both a function and a co-function.

We define the composition of two relations R : X ⇆ Y and S : Y ⇆ Z to be a relation SR : X ⇆ Z defined by zSRx whenever zSy and yRx for some y ∈ Y. In general, if R and S are relations which both satisfy the same one of the four properties, then SR has that property, too. In particular, if f : X → Y and g : Y → Z are functions, then we see that gf is also a function: gf is a co-surjection since, for any x ∈ X, there is a y ∈ Y such that yfx, and there is a z ∈ Z such that zgy, hence zgfx; and gf is a co-injection since, if z1, z2 ∈ Z and x ∈ X are such that z1gfx and z2gfx, there are y1, y2 ∈ Y such that y1fx and y2fx, so y1 = y2 by co-injectivity of f, and hence z1 = z2 by co-injectivity of g.

What is the inverse of the composition of relations? Suppose we want to check if x (SR)−1z, which is equivalent to zSRx, which is equivalent to some y ∈ Y existing such that zSy and yRx, which is equivalent to xR−1y and yS−1x for some y ∈ Y, and this is equivalent to xR−1S−1y. Therefore, (SR)−1 = R−1S−1.

One can see that composition of relations is associative, as one would expect (at least one would expect for functions, at least).

Define IA : A ⇆ A to be the relation consisting only of (a, a) for all a ∈ A. Some common properties for a relation R : X → X can be described as follows:

An equivalence relation on X is a relation R : X ⇆ X which satisfies all three of these properties (which I suppose can be succinctly written as IX ⊂ RR ⊂ R ⊂ R−1, using the fact that R ⊂ RR by the reflexive property).

There is a canonical equivalence relation on X for a function f : X → Y defined by f−1f, which says that two elements x1 and x2 in X are related if and only if f(x1) = f(x2). The proof for this is straight-forward. First, for an arbitrary x ∈ X, there is a y ∈ Y such that yfx, so since xf−1x, we have reflexivity: xf−1fx. Second suppose that x2f−1fx1. Then there is a y ∈ Y such that yfx2 and yfx1, so x1fx2, hence symmetry. Third, suppose that x3f−1fx2 and x2f−1fx1. Then there are y and z such that yfx3, yfx2, zfx2, and zfx1. By co-injectivity, y = z = f(x2), and so x3f−1fx1, hence transitivity.

As an aside, since an equivalence relation is equivalent to a partition of a set, we have a first isomorphism theorem for sets by this construction: the set of partitions of X induced by f−1f is in bijective correspondence to the image of f.

Suppose R : X ⇆ X is a relation on a set X. What is the smallest equivalence relation E on X which contains R? We know that IX must be in E for reflexivity, and we know that R−1 must be in E, too. Let S = RR−1, which is the symmetrified R. Let E be the union of IX, S, SS, SSS, SSSS, and so on (this could be called the transitive closure of S if it didn’t have the IX term). For convenience, let Sn represent S composed with itself n times, with S0 = IX. Since each Sn is symmetric, E is symmetric as well. Furthermore, suppose yEx and zEy. Then, ySnx and zSmy for some n, m. Then, zSn + my, and so E is transitive. This shows E is an equivalence relation containing R, but is it the smallest such? Since any equivalence relation which contains R must contain IX, S, SS, and so on, and E contains no more than this, it follows that E is smallest.

It turns out we can define (co-)surjectivity and (co-)injectivity using composition properties, too:

So, if R−1R = IX, then R is co-surjective and injective, and if RR−1 = IY, then R is surjective and co-injective. So, if S : X ⇆ X, and S−1S = SS−1 = IX, then S is a bijection (and, as a consequence, a group of relations with relation composition as the binary operation is actually a group of bijections).

We see that some of the proofs for f−1f being an equivalence relation can be done more algebraically: first, (f−1f)−1 = f−1f, so it is symmetric; second, (f−1f)(f−1f) = f−1(ff−1)f = f−1IAf since f is co-injective, where A ⊂ Y is the image of f, and f−1IAf = f−1f, hence f−1f is transitive.

There are nice algebraic properties for unions and intersections. Let R : X ⇆ Y and U, V ⊂ X. Then R(UV) = R(U) ∪ R(V), by definition. We also have that R(UV) ⊂ R(U) ∩ R(V), since if yRx for some x ∈ UV, then because x is in both U and V, y is in R(U) ∩ R(V). If, in addition, R is surjective, then it is an equality: R(UV) = R(U) ∩ R(V). The inverse of a function is a surjective relation, so this is why unions and intersections work so nicely with them.