# Binary Relations

## Definitions

Given a set of objects A, a binary relation R on the set is defined as a
subset of A x A. The *characteristic function* r for R is the
function r : A x A -> bool such that r(x, y) is true if
(x, y) in R, and false if (x, y) not in R. For a more natural
notation, we can use x ~ y to denote r(x, y).

More generally, a binary relation can be defined on a pair of sets A x B but to keep things simple, we’ll only cover binary relations over a single set.

Binary relations may have several properties. A few interesting ones are:

- A binary relation is
*reflexive*if for any x in A, x ~ x - A binary relation is
*strict*or*irreflexive*if there is no x in A for which x ~ x - A binary relation is
*symmetric*if for any x, y in A, x ~ y implies y ~ x - A binary relation is
*antisymmetric*if for any x, y in A, x ~ y and y ~ x implies x = y - A binary relation is
*transitive*if for any x, y, z in A, if x ~ y and y ~ z, then x ~ z - A binary relation is
*total*if for any x, y in A, either x ~ y, y ~ x, or both (in other words, for any x, y, ~ imposes some relation between them)

### Examples

The relation *is in the subtree rooted at* is a reflexive relation where A
is the set of nodes of a tree. For any pair of nodes x and y, we can
establish whether x is in the subtree rooted at y or not, and for any
x, x ~ x is true.

The relation *is parent of* in a tree is a strict relation: for any x in the
set of tree nodes A, x cannot be a parent of itself.

The relation *edge between* over the vertices of a non-directed graph is a
symmetric relation: for any x and y vertices of the graph, if there is
an edge from x to y, the same edge exists from y to x, in other
words, if x ~ y then y ~ x.

The *is in the subtree rooted at* relation above is also antisymmetric: if for
a pair of nodes we can say x is in the subtree rooted at y and also
y is in the subtree rooted at x, it’s obvious that both x and y
are, in fact, the root of the subtree, thus x ~ y.

The relation *is reachable from* over the vertices of a directed graph is a
transitive relation: if x is reachable from y and y is reachable
from z, then x is reachable from z.

All of the above examples are of total relations. An example of a non-total
relation is *is ancestor of* in a tree. x can be an ancestor of y, in
which case x ~ y, or y can be an ancestor of x, in which case
y ~ x, but it could also be that x and y are in different subtrees,
so neither x ~ y nor y ~ x holds.

## Preorder

A *preorder* is a relation which is reflexive and transitive.

A preorder which is also symmetric is an *equivalence*. A preorder which is
antisymmetric is a *partial order*. More on those below.

An example of preorder is the *is reachable from* relation over a directed
graph in the example above. This relation is obviously reflexive and transitive,
but it is neither symmetric nor antisymmetric. If x is reachable from y,
it doesn’t mean that y is reachable from x, so symmetry is not
guaranteed. Similarly, if x is reachable from y and y is reachable
from x, it does not mean that y equals x.

## Equivalence and Equality

An *equivalence* relation ~ is a binary relation that is reflexive,
symmetric, and transitive. In other words, it is a preorder which also has the
symmetric property.

Such a relation partitions the set over which it is
defined into *equivalence classes* - groups of objects that are equivalent
based on the relation.

An example of equivalence is *same month* over a set of dates. This relation
is reflexive, since a date d has the same month as itself (d ~ d); is
symmetric, since if d1 has the same month as d2, then d2 has the
same month as d1 (d1 ~ d2 => d2 ~ d1); and transitive, since if d1 ~
d2 and d2 ~ d3 => d1 ~ d3.

This relation partitions our set of dates in the equivalence classes
corresponding to *dates in January*, *dates in February*, and so on. Note that
the dates for which the relation holds are equivalent, but not necessarily equal.

An *equality* relation is an equivalence relation which partitions the set A
consisting of n objects into exactly n equivalence classes. In other
words, for any x in A, only x ~ x is true.

## Partial Order and Total Order

A *partial order* relation <= is a binary relation that is reflexive,
antisymmetric, and transitive. In other words, it is a preorder which also has
the antisymmetric property.

An example of a partial order is the *is subset of* relation. It is reflexive
(A is a subset of A), antisymmetric (if A is a subset of B and
B is a subset of A, then A = B), and transitive (if A is a
subset of B and B is a subset of C, then A is a subset of
C).

A *total order* relation is a partial order that is also total. The above
example relation *is subset of* is not total - there could be a pair of sets
A and B such that neither is the subset of the other.

An example of a total order relation is *less than or equal to* for integers.

## Weak Order and Strict Weak Order

A *weak order* relation ~ is a binary relation that is transitive and total.
This implies reflexivity (for any x and y, either x ~ y, y ~ x,
or both, so for x and x we have x ~ x). In other words, it is a
preorder which is also total.

An example of a weak order is *less than or equal absolute value* for complex
numbers. For any two complex numbers c1 and c2, either c1 ~ c2 (
|c1| <= |c2|), c2 ~ c1 (|c2| <= |c1|), or both, so ~ is total.
We also have c1 ~ c2 and c2 ~ c3 implies c1 ~ c3 (|c1| <= |c2|
and |c2| <= |c3| implies |c1| <= |c3|). Unlike a total order though, the
relation is not antisymmetric. We can have c1 ~ c2, c2 ~ c1, with
c1 and c2 distinct complex numbers (any two numbers with the same
absolute value but different components).

A *strict weak order* relation < is a binary relation that is transitive and
strict (irreflexive).

An example of strict weak order is *less than* for integers.

## Applications

Most programming languages provide a way to customize equality, inequality, and
comparison operators (==, !=, <, <=, >, >=). There is an
interesting point to be made about what equality *means* in this context. For
some types, this can simply mean comparing the bits and if they are the same,
the objects are equal. But we also have *logical equality* - two objects can
have different bitwise values but still be considered equal. Even more so for
comparing objects - comparing bit representations usually does not translate to
a meaningful comparison of objects.

Note though that any other function bool r(const T& m1, const T& m2) or member function bool r(const T& other) of T denotes a binary relation on T.

Different algorithms require different types of relations to exist between objects.

For example, we need at least a partial order relation to perform a topological sort. That is, in an directed acyclic graph, we can sort the vertices such that for every edge from a to b, a precedes b in the order. This can be used, for example, on the dependency graph in a makefile to determine how to sequence work.

Having an equivalence relation (eg. ==), we can implement a linear search algorithm to traverse a data structure and find an object equivalent to a given object. The C++ standard library algorithm find is an example of such an algorithm.

Having a total order relation (eg. <=) or a strict weak order (eg. <), allows us to implement binary search over an ordered set of objects. A total order or strict weak order relation also enables comparison sort algorithms.

Similarly, we need a total oreder or strict weak order to be able to determine a minimum or a maximum element from a set of objects (min_element and max_element algorithms in C++).

## Summary

- A binary relation R on a set A is a subset of A x A, denoted by a characterisitc function r : A x A -> bool.
- A binary relation on a type T is denoted by either a free function of the the form bool r(const T&, const T&) or a member function bool r(const T&).
- A binary relations may have several properties: it can be reflexive or strict, symmetric or antisymmetric, transitive, total etc.
- Depending on the properties it has, a relation can be, for example:
- A preorder (reflexive and transitive)
- An equivalence (reflexive, symmetric, and transitive)
- A partial order (reflexive, antisymmetric, and transitive)
- A weak order (reflexive, transitive, and total)
- A strict weak order (irreflexive, transitive, and total)

- Certain algorithms require the types they operate on to have relations with certain properties.