Relations

Abigail Huettig

14 Relations

A relation is simply a set of ordered pairs $(a,b)$ where $a$ and $b$ are related in some way [23]. Smith et al. provides us with the following formal definition [23].

Definition III.2
Let $A$ and $B$ be sets. $R$ is a relation from $A$ to $B$ if $R$ is a subset of $A \times B$ . A relation from $A$ to $A$ is called a relation on $A$ . If $(a,b) \in R$ , we say $a$ is $R$ -related (or simply related) to $b$ and write $a\, R \,b$ .

The definition mentions that $R$ must be a subset of $A \times B$ if it is a relation from $A$ to $B$ . The elements of $A \times B$ are of the form $(a,b)$ , where $a$ is in $A$ and $b$ is in $B$ . So, if $R$ is a relation from $A$ to $B$ , the elements of $R$ will be of the form $(a,b)$ . Similarly, if $R$ is a relation from $A$ to $A$ , the elements of $R$ will be of the form $(a,c)$ where $a$ and $c$ are elements of $A$ .

Domain and range are terms that we will be using many times in the coming sections so it is important to understand what these terms are referring to. The following definition comes from Smith et al.[23].

Definition III.3
The domain of the relation $R$ from $A$ to $B$ is the set

$Dom(R)=\{x\in A:\text{there exists}\, y\in B \,\text{such that} \,x\, R\, y\}.$

The range of the relation $R$ is the set

$Rng(R)=\{y\in B:\text{there exists}\, x\in A \,\text{such that} \,x\, R\, y\}.$

In other words, for a relation from $A$ to $B$ , the domain of the relation is the set of all $a$ in $A$ that are related to at least one $b$ in $B$ . Similarly, the range of the relation is the set of all $b$ in $B$ that are related to at least one $a$ in $A$ .

There are many different properties that can be used to describe a relation, and we can categorize relations based on the properties they possess. These categories include equivalence relations and ordering relations.

Equivalence Relations

An equivalence relation is a special type of relation that is reflexive, symmetric, and transitive [23]. Smith et al. provides the following definition [23].

Definition III.4
Let $A$ be a set and $R$ be a relation on $A$ .

$R$ is reflexive on $A$ if for all $x\in A$ , $x\, R\, x$ .
$R$ is symmetric if for all $x$ and $y \in A$ , if $x\, R\, y$ , $y\,R\,x$ .
$R$ is transitive if for all $x, y$ , and $z \in A$ , if $x\,R\,y$ and $y\,R\,z$ , then $x\,R\,z$ .

The reflexive property simply means that every $x$ in $A$ must be related to itself. The symmetric property says that for each $x$ and $y$ in $A$ , $y$ must be related to $x$ if $x$ is related to $y$ . Transitive simply means that for each $x, y$ , and $z$ in $A$ , if $x$ is related to $y$ and $y$ is related to $z$ , then $x$ must be related to $z$ . Let’s look at an example to see what these properties look like for a specific relation. The following exercise is a homework problem from Smith et al. that I completed for this paper [23].

Example 29
Determine whether the relation $R$ defined as $\leq$ on $\mathbb{N}$ is an equivalence relation.

Solution

For all $x \in \mathbb{N}$ , $x\leq x$ . Thus, $x\, R\, x$ , and $R$ is reflexive.
For all $x, y, z \in \mathbb{N}$ , if $x\leq y$ and $y\leq z$ , then $x\leq z$ . So, if $x\,R\,y$ and $y\,R\,z$ , then $x\,R\,z$ . Thus, $R$ is transitive.
However, there exists $4,5 \in \mathbb{N}$ such that if $4 \leq 5$ , then $5 \nleq 4$ . Thus, $R$ is not symmetric.

Therefore, the relation $R$ is not an equivalence relation.

Ordering Relations

We will start this section by defining three more properties of relations. The following definition comes from Smith et al. [23].

Definition III.5
Let $R$ be a relation on a set $A$ . Then,

$R$ is antisymmetric if for all $x,y\in A$ , if $x \,R\,y$ and $y\,R\,x$ , then $x=y$ .
$R$ is irreflexive on $A$ if $x$ is not related to $x$ for all $x\in A$ .
$R$ has the comparability property if for all $x,y\in A$ , either $x\,R\, y$ or $y\,R\,x$ .

Antisymmetric means that for each $x$ and $y$ in $A$ where $x\neq y$ , the symmetric property cannot hold. Similarly, the irreflexive property means that for each $x$ in $A$ the reflexive property cannot hold. That is, $x$ is not related to itself. Finally, the comparability property says that for each $x$ and $y$ in $A$ , it must be true that either $x$ is related to $y$ or $y$ is related to $x$ .

Using these additional properties, we have more categories that we can organize relations into. These categories are given by Smith et al. A relation is a partial order or partial ordering if it is reflexive, antisymmetric, and transitive. A relation is a strict partial order or strict partial ordering if it is irreflexive, antisymmetric, and transitive. A partial ordering is called a linear order or total order if the comparability property holds for all $x$ and $y$ in $A$ where $x\neq y$ [23]. We will now look at a homework problem from Smith et al. that I completed for this paper [23].

Example 30
Determine what kind of relation $S$ defined as $x\,S\,y$ if $y=x-1$ on $\mathbb{R}\times \mathbb{R}$ is.

Solution

For all $(x,x) \in \mathbb{R}\times \mathbb{R}$ , $x\neq x-1$ . Thus, $S$ is irreflexive.
For all $(x,y)\in \mathbb{R}\times \mathbb{R}$ ,
$\begin{align*} y&=x-1\\ x&=y+1\\ &\neq y-1 \end{align*}$

Thus, $S$ is antisymmetric.
There exists $(5,4)$ and $(4,3)$ in $\mathbb{R}\times\mathbb{R}$ such that $4=5-1$ and $3=4-1$ but $3\neq 5-1$ . Thus, $S$ is not transitive.
There exists $(5,10)$ in $\mathbb{R}\times\mathbb{R}$ such that $10\neq 5-1$ and $5\neq 10-1$ . Thus, the comparability property does not hold for $S$ .

Therefore, $S$ is not an equivalence relation because it is not reflexive, symmetric, or transitive. It is not a partial ordering because it is not reflexive or transitive. It is also not a strict partial ordering since it is not transitive, and it is not a linear order since it is not a partial ordering and the comparability property does not hold for all $x$ and $y$ , where $x\neq y$ .

Up to this point, we have discussed types of relations from $A$ to $A$ , where $A$ is a set. In our next section, we will discuss another type of relation, known as a function, which may be a relation from $A$ to $A$ or from $A$ to $B$ , where $A$ and $B$ are distinct sets.

14 Relations

Equivalence Relations

Ordering Relations

License

Share This Book