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 y R x. While the standard notation for this is x R y, 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 y R x. 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 x R−1 y whenever y R x. 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:
- R is a surjection if for any y ∈ Y, there exists an x ∈ X such that y R x. We can also define surjectivity by the condition R(X) = Y.
- R is a co-surjection if R−1 is a surjection. Similarly, we can also say that R is co-surjective if (Y)R = X.
- R is an injection if whenever x1, x2 ∈ X and y ∈ Y are such that y R x1 and y R x2, then x1 = x2. We could just have well said that R is one-to-many. An example of such a relation is “is the biological mother of” if X and Y are both the set of all people.
- R is a co-injection if R−1 is an injection. This property is the same as saying that R is many-to-one. An example of this is the relation “lives in” for X being the set of all people and Y being the set of all houses. Note that this relation isn’t necessarily a co-surjection since not everyone needs to live in a house.
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 y f x. 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 z SR x whenever z S y and y R x 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 y f x, and there is a z ∈ Z such that z g y, hence z gf x; and gf is a co-injection since, if z1, z2 ∈ Z and x ∈ X are such that z1 gf x and z2 gf x, there are y1, y2 ∈ Y such that y1 f x and y2 f x, 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)−1 z, which is equivalent to z SR x, which is equivalent to some y ∈ Y existing such that z S y and y R x, which is equivalent to x R−1 y and y S−1 x for some y ∈ Y, and this is equivalent to x R−1S−1 y. 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:
- A relation is reflexive if IX ⊂ R.
- A relation is symmetric if R ⊂ R−1 (or, equivalently, if R−1 ⊂ R).
- A relation is transitive if RR ⊂ R.
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 y f x, so since x f−1 x, we have reflexivity: x f−1f x. Second suppose that x2 f−1f x1. Then there is a y ∈ Y such that y f x2 and y f x1, so x1 f x2, hence symmetry. Third, suppose that x3 f−1f x2 and x2 f−1f x1. Then there are y and z such that y f x3, y f x2, z f x2, and z f x1. By co-injectivity, y = z = f(x2), and so x3 f−1f x1, 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 = R ∪ R−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 y E x and z E y. Then, y Sn x and z Sm y for some n, m. Then, z Sn + m y, 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:
- A relation is surjective if and only if IY ⊂ RR−1.
- A relation is co-surjective if and only if IX ⊂ R−1R.
- A relation is injective if and only if R−1R ⊂ IX.
- A relation is co-injective if and only if RR−1 ⊂ IY.
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(U ∪ V) = R(U) ∪ R(V), by definition. We also have that R(U ∩ V) ⊂ R(U) ∩ R(V), since if y R x for some x ∈ U ∩ V, 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(U ∩ V) = 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.