Relations

Why

How can we relate the elements of two sets?

Definition

A relation is a set of ordered pairs (see Ordered Pairs). So if an object $z$ is an element of a relation, there exist two other objects $x$ and $y$ so that $z = (x, y)$.

Domain and range

The domain of a relation is the set of all elements which appear as the first coordinate of some ordered pair of the relation (the projection onto the first coordinate, see Ordered Pair Projections). The range of a relation is the set of all elements which appear as the second coordinate of some ordered pair of the relation (the projection onto the second coordinate).

When the domain of a relation $R$ is a subset of $X$ and the range is a subset of $Y$, we say $R$ is a relation between $X$ and $Y$ or (from $X$ to $Y$). If $X = Y$, then we speak of $R$ as a relation on (or in) $X$.

Notation

If $R$ is a relation, we express that $(x, y) \in R$ by writing $x\,R\,y$, which we read aloud as “$x$ is in relation $R$ to $y$”. We denote the domain of $R$ by $\dom R$ and the range of $R$ by $\ran R$.

Examples

Empty relation

For an uninteresting relation, consider the empty set. We call the empty set the empty relation. In the empty (set) relation, no object is related to any other. Both the domain and range of $\varnothing$ are $\varnothing$.

Total relation

Next, consider the product of any two sets $X$ and $Y$. In $X \times Y$, all objects are related. The domain is $X$ and the range is $Y$.

Equality

For a more interesting example, define $R \subset X \times X$ by

\[ R = \Set{(x, y) \in X \times X}{x = y}. \]

This relation is the relation of equality (see Identities) between two objects. Here $x\,R\,y \iff x = y$. $\dom R = \ran R = X$.

Belonging

Another similar example is if we consider the set $X$ and $\powerset{X}$, and the relation

\[ R := \Set{(x, y) \in X \times \powerset{X}}{x \in y}. \]

This relation is the relation of belonging (see Sets). Here $x\,R\,y \iff x \in y$. Here $\dom R = X$ and $\ran R = \powerset{X}$.

Properties

Often relations are defined over a single set, and there are a few useful properties to distinguish.

A relation is reflexive if every element is related to itself.
A relation is symmetric if two objects are related regardless of their order.
A relation is transitive if a first element is related to a second element and the second element is related to the third element, then the first and third element are related.

Equality is reflexive, symmetric and transitive whereas belonging is neither. Exercise: what is inclusion?