# 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`x`_{1},`x`_{2}∈`X`and`y`∈`Y`are such that`y``R``x`_{1}and`y``R``x`_{2}, then`x`_{1}=`x`_{2}. 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 `S``R` : `X` ⇆ `Z` defined by `z` `S``R` `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 `S``R` has that
property, too. In particular, if `f` : `X` → `Y` and `g` : `Y` → `Z` are
functions, then we see that `g``f` is also a function: `g``f` 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` `g``f` `x`; and `g``f` is a co-injection since, if `z`_{1}, `z`_{2} ∈ `Z` and
`x` ∈ `X` are such that `z`_{1} `g``f` `x` and `z`_{2} `g``f` `x`, there are
`y`_{1}, `y`_{2} ∈ `Y` such that `y`_{1} `f` `x` and `y`_{2} `f` `x`, so `y`_{1} = `y`_{2}
by co-injectivity of `f`, and hence `z`_{1} = `z`_{2} by co-injectivity of
`g`.

What is the inverse of the composition of relations? Suppose we
want to check if `x` (`S``R`)^{−1} `z`, which is equivalent to
`z` `S``R` `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`^{−1}`S`^{−1} `y`. Therefore, (`S``R`)^{−1} = `R`^{−1}`S`^{−1}.

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

Define `I`_{A} : `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`I`_{X}⊂`R`. - A relation is
*symmetric*if`R`⊂`R`^{−1}(or, equivalently, if`R`^{−1}⊂`R`). - A relation is
*transitive*if`R``R`⊂`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 `I`_{X} ⊂ `R``R` ⊂ `R` ⊂ `R`^{−1}, using the fact that `R` ⊂ `R``R` by the
reflexive property).

There is a canonical equivalence relation on `X` for a function
`f` : `X` → `Y` defined by `f`^{−1}`f`, which says that two elements `x`_{1}
and `x`_{2} in `X` are related if and only if `f`(`x`_{1}) = `f`(`x`_{2}). 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`^{−1}`f` `x`. Second suppose that `x`_{2} `f`^{−1}`f` `x`_{1}. Then there is a `y` ∈ `Y` such that `y` `f` `x`_{2}
and `y` `f` `x`_{1}, so `x`_{1} `f` `x`_{2}, hence symmetry. Third, suppose
that `x`_{3} `f`^{−1}`f` `x`_{2} and `x`_{2} `f`^{−1}`f` `x`_{1}. Then there
are `y` and `z` such that `y` `f` `x`_{3}, `y` `f` `x`_{2}, `z` `f` `x`_{2}, and `z` `f` `x`_{1}. By co-injectivity, `y` = `z` = `f`(`x`_{2}), and so
`x`_{3} `f`^{−1}`f` `x`_{1}, 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`^{−1}`f`
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 `I`_{X} 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 `I`_{X}, `S`, `S``S`, `S``S``S`,
`S``S``S``S`, and so on (this could be called the *transitive
closure* of `S` if it didn’t have the `I`_{X} term). For
convenience, let `S`^{n} represent `S` composed with itself `n` times,
with `S`^{0} = `I`_{X}. Since each `S`^{n} is symmetric, `E` is symmetric as
well. Furthermore, suppose `y` `E` `x` and `z` `E` `y`. Then,
`y` `S`^{n} `x` and `z` `S`^{m} `y` for some `n`, `m`. Then, `z` `S`^{n + 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 `I`_{X}, `S`, `S``S`, 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
`I`_{Y}⊂`R``R`^{−1}. - A relation is co-surjective if and only if
`I`_{X}⊂`R`^{−1}`R`. - A relation is injective if and only if
`R`^{−1}`R`⊂`I`_{X}. - A relation is co-injective if and only if
`R``R`^{−1}⊂`I`_{Y}.

So, if `R`^{−1}`R` = `I`_{X}, then `R` is co-surjective and injective, and
if `R``R`^{−1} = `I`_{Y}, then `R` is surjective and co-injective. So, if
`S` : `X` ⇆ `X`, and `S`^{−1}`S` = `S``S`^{−1} = `I`_{X}, 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`^{−1}`f` being an equivalence
relation can be done more algebraically: first, (`f`^{−1}`f`)^{−1} = `f`^{−1}`f`, so it is symmetric; second, (`f`^{−1}`f`)(`f`^{−1}`f`) = `f`^{−1}(`f``f`^{−1})`f` = `f`^{−1}`I`_{A}`f` since `f` is co-injective, where
`A` ⊂ `Y` is the image of `f`, and `f`^{−1}`I`_{A}`f` = `f`^{−1}`f`, hence
`f`^{−1}`f` 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.