Relations

Definition (Relation)

Let $X$ and $Y$ be sets, and let $X\times Y$ be their Cartesian product. A (binary) relation from $X$ to $Y$ is a subset of $X\times Y$. When $X=Y$, we speak of a relation on (or over or in) $X$.

If $R$ is a relation from $X$ to $Y$, we write $xRy$ to indicate that $(x,y)\in R$, and we say that “$x$ is $R$-related to $y$”.

Example   Trivially, $\varnothing$ and $X\times Y$ are relations from $X$ to $Y$.

Example   The set of all pairs $(x,x)$, where $x\in X$, is the relation of equality between elements of $X$.

Example   The subset of $X\times \mathcal{P}(X)$ consisting of all pairs $(x,S)$ such that $x\in S$ is the relation of belonging between elements of $X$ and subsets of $X$.

Example   A function is a special type of relation.

Definition (Domain and Range of a Relation)

Let $X$ and $Y$ be sets, and let $R$ be a relation from $X$ to $Y$. The domain of $R$ is the set $\mathrm{dom}R$ of all elments $x$ of $X$ with the property that there exists an element $y$ of $Y$ such that $x$ is $R$-related to $y$. The range of $R$ is the set $\mathrm{ran}R$ of all elments $y$ of $Y$ with the property that there exists an element $x$ of $X$ such that $x$ is $R$-related to $y$. Formally,

$$\begin{array}{rl}\mathrm{dom}R& =\left\{x\in X\mid \exists y\in Y:xRy\right\},\\ \mathrm{ran}R& =\left\{y\in Y\mid \exists x\in X:xRy\right\}.\end{array}$$

Example   Let $R$ be the relation of belonging between elements of a set $X$ and subsets of $X$ (see above). Then $R$ has domain $X$ and range $\mathcal{P}(X)\setminus \{\varnothing \}$.

Definition (Inverse Relation)

TODO $R^{-1}$

Definition (Composition of Relations)

TODO

Proposition (Associativity of Composition)

The composition of relations is associative. Explicitly, if $W$, $X$, $Y$, $Z$ are sets, and $R$ is a relation from $W$ to $X$, $S$ is a relation from $X$ to $Y$, $T$ is a relation from $Y$ to $Z$, then

$$(R\circ S)\circ T=R\circ (S\circ T).$$

Definition (Properties of Relations)

A relation $R$ on a set $X$ is said to be

• reflexive if $xRx$ for all $x\in X$.
• irreflexive if there is no $x\in X$ such that $xRx$.
• symmetric if $xRy$ implies $yRx$ for all $x,y\in X$.
• antisymmetric if $xRy$ and $yRx$ imply $x=y$ for all $x,y\in X$.
• transitive if $xRy$ and $yRz$ imply $xRz$ for all $x,y,z\in X$.

Definition (More Properties of Relations)

A relation $R$ from a set $X$ to a set $Y$ is called

• left-total if for all $x\in X$ there exists a $y\in Y$ such that $xRy$.
• right-total if for all $y\in Y$ there exists a $x\in X$ such that $xRy$.
• left-unique if $xRy$ and $x^{\prime }Ry$ implies $x=x^{\prime }$ for all $x,x^{\prime }\in X$ and all $y\in Y$.
• right-unique if $xRy$ and $xR{y}^{\prime }$ implies $y=y^{\prime }$ for all $x\in X$ and all $y,y^{\prime }\in Y$.

Equivalence Relations

Definition (Equivalence Relation)

A reflexive, symmetric and transitive relation is called equivalence relation.

on a nonempty set?

Example   For any set $X$, the relation of equality and the relation $X\times X$ are equivalence relations on $X$.

Definition (Equivalence Class)

Let $R$ be an equivalence relation on a set $X$. We define the equivalence class of an element $x\in X$ to be the set $R(x)=\left\{y\in X:yRx\right\}$. We write $X/R$ for the set of all equivalence classes.

The expression $X/R$ is pronounced “$X$ modulo $R$”.

Two equivalence classes are either disjoint or equal.

Example   If $R$ is the relation of equality on $X$, then $X/R$ is the set of all singletons $\{x\}$ with $x\in X$. For the relation $R=X\times X$ on $X$, we have $X/R=\{X\}$.

Definition (Relation Induced by a Partition)

Let $P$ be a partition of a set $X$. By the relation induced by $P$ we mean the relation $X/P$ on $X$ consisting of all pairs $(x,y)\in X\times X$ such that $x,y\in A$ for some $A\in P$.

Let $X$ be a set.

• If $R$ is a relation on $X$, then the set of equivalence classes $X/R$ is a partition of $X$.
• If $P$ is a partition of $X$, then the induced relation $X/P$ is an equivalence relation on $X$.
• These constructions are mutually inverse.