# 14 Relations

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

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

The definition mentions that must be a subset of if it is a relation from to . The elements of are of the form , where is in and is in . So, if is a relation from to , the elements of will be of the form . Similarly, if is a relation from to , the elements of will be of the form where and are elements of .

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 from to is the set

The range of the relation is the set

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

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 be a set and be a relation on .

• is reflexive on if for all , .
• is symmetric if for all and , if , .
• is transitive if for all , and , if and , then .

The reflexive property simply means that every in must be related to itself. The symmetric property says that for each and in , must be related to if is related to . Transitive simply means that for each , and in , if is related to and is related to , then must be related to . 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 defined as on is an equivalence relation.

Solution

1. For all , . Thus, , and is reflexive.
2. For all , if and , then . So, if and , then . Thus, is transitive.
3. However, there exists such that if , then . Thus, is not symmetric.

Therefore, the relation 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 be a relation on a set . Then,

• is antisymmetric if for all , if and , then .
• is irreflexive on if is not related to for all .
• has the comparability property if for all , either or .

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

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 and in where [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 defined as if on is.

Solution

1. For all , . Thus, is irreflexive.
2. For all ,

Thus, is antisymmetric.

3. There exists and in such that and but . Thus, is not transitive.
4. There exists in such that and . Thus, the comparability property does not hold for .

Therefore, 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 and , where .

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