Relations on Sets

Definition: Let $X$ be a set. A (binary) Relation on $X$ is a subset $R \subseteq X \times X$ where $X \times X$ is defined to be the The Cartesian Product of Set $X$ with itself. If $(x, y) \in R$ we write $x \: R \: y$ which means "$x$ relates $y$" and if $(x, y) \not \in R$ we write $x \: \not R \: y$ which means "$x$ does not relate $y$".

In general if $X$ and $Y$ are sets then a binary relation between $X$ and $Y$ is a subset $R \subseteq X \times Y$. We will mostly be looking deeply into relations where $X = Y$, i.e., relations on various sets to themselves.

Consider the set $A$ of positive integers from $1$ to $10$ inclusive:

(1)

\begin{align} \quad A = \{ 1, 2, ..., 10 \} \end{align}

The strict inequality $<$ is a relation $R$ on $X \times X$ where the pairs $(x, y) \in R \subseteq X \times X$ are such that the numerical value of $x$ is strictly less than the numerical value of $y$, that is $x < y$.

Consider a set $X$ of all subsets of $E = \{ x, y, z \}$. Then the containment $\subseteq$ is a relation $R$ on $X \times X$ where the pairs $(A, B) \in R \subseteq X \times X$ are such that $A$ is a subset of $B$, that is $A \subset B$.

If $X = \{1, 2, 3, 4 \}$ and $Y = \{6, 8, 10 \}$ then define the relation $R$ from $X$ to $Y$ such that elements $X$ when squared are less than elements in $Y$. We thus have that:

(2)

\begin{align} \quad R = \{ (1, 6), (1, 8), (1, 10), (2, 6), (2, 8), (2, 10), (3, 10) \} \end{align}

Therefore $1 \: R \: 6$, $1 \: R \: 8$, …, and $3 \: R \: 10$. The graph below illustrates this relation.

For a final example, if $X = \{1, 3, 4, 6, 7 \}$ and $Y = \{1, 2, 3, 5 \}$ then define the relation $R$ from $X$ to $Y$ such that the sum of an element in $X$ plus an element in $Y$ is odd. This relation can also be described such that $x \: R \: y$ if $x$ is even and $y$ is odd or $x$ is odd and $y$ is even. So:

(3)

\begin{align} \quad R = \{ (1, 2), (3, 2), (4, 1), (4, 3), (4, 5), (6, 1), (6, 3), (6,5), (7,1), (7,3), (7,5) \} \end{align}

The graph below illustrates this relation.

Classifying Relations

We will now look at some important classifications of relations for binary relations on a set $X$ to itself.

Definition: A relation $R$ is said to be Reflexive if for all $x \in X$ we have $x \: R \: x$ and $R$ is said to be Irreflexive if for all $x \in X$ we have $x \: \not R \: x$.

Definition: A relation $R$ is said to be Symmetric if for all $x, y \in X$ we have that $x \: R \: y$ implies that $y \: R \: x$ and $R$ is said to be Antisymmetric if for all $x, y \in X$ where $x \neq y$ we have that $x \: R \: y$ implies that $y \: \not R \: x$.

Definition: A relation $R$ is said to be Transitive if for all $x, y, z \in X$ we have that whenever $x \: R \: y$ and $y \: R \: z$ then $x \: R \: z$.

Recall the first example from earlier that is the relation $<$ of strict inequality on $X \times X$ where $X = \{1, 2, ..., 10 \}$. This relation is irreflexive since for all $x \in X$ we have that $x \not < x$. Furthermore, this relation is antisymmetric since for all $x, y \in X$ where $x \neq y$ we have that whenever $x < y$ that then $y \neq x$. This relation is also transitive since for all $x, y, z \in X$ we have that if $x < y$ and $y < z$ then $x < z$.

For the second example from earlier, i.e., the relation $\subset$ of containment on $X \times X$ where $X$ is a set of all subsets of $E = \{x, y, z \}$. This set is reflexive since for all $A \in X$ we have that $A \subseteq A$. This relation is antisymmetric since for all $A, B \in X$ and $A \neq B$ we have that $A \subseteq B$ implies that $B \not \subseteq A$. Lastly, this relation is transitive since for all $A, B, C \in X$ we have that if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$.