Relations

In this topic, we will learn about the concept of relations, which at a first glance it is hard to see how it is connected to mathematics, but we will learn how it is formalized and applied. Relations are a fundamental mathematical concept and many other concepts are based on them. We will see that many real-world situations such as hierarchy in a company or just a comparison of numbers can be described using the language of relations. Relations are especially useful for database theory.

What is a relation?

In our everyday life, the word "relation" means some sort of connection between people, countries, or any other object. For example, how are writer J. R. R. Tolkien and the book "The Lord of the Rings" connected? The former is the author of the latter. The same relation exists between Leo Tolstoy and "War and Peace". On the other hand, Agatha Christie is not the author of "Alice in Wonderland".

Similarly, we can tell two countries are neighbors if they have a common border. It's a relation, too. Looking at the map, we see that France and Italy are neighbors, but Italy and India are not.

How can we formalize such examples? In both cases, a pair of objects is presented to us and we can (at least theoretically!) say whether they are connected in the way we are interested in. And when we hear the word "pair" in math, we immediately think about the Cartesian product.

Definition. A binary relation $R$ over sets $A$ and $B$ is a subset of the Cartesian product $A \times B$.

That means that $R$ is some set containing pairs with first elements from $A$ and second elements from $B$ (but not necessarily all such pairs).

In our first example, $A$ is the set of all writers in the world and $B$ the set of all books. In the second example, the role of both $A$ and $B$ is played by the set of countries.

Note that we defined not just "relations", but "binary relations". This means we consider pairs of objects. If we considered triples, the relation would be called ternary. The general case is an $n$-ary relation, a subset of the Cartesian product $A_{1} \times A_{2} \times \ldots \times A_{n}$ (its elements are $n$-tuples $(a_{1}, a_{2}, \ldots, a_{n})$, where $a_{i} \in A_{i}$).

An example of a ternary relation is Pythagorean triples, which are triples of elements that satisfy $a^2+b^2=c^2$. So a triple like $(3,4,5)$ would satisfy such ternary relation.

Often the sets $A$ and $B$ for our binary relation coincide. In this case, we say $R$ is a relation on $A$.

A relation where $A=B$ is often called a homogenous relation or an endorelation.

An inverse relation

Suppose we have some relation $R$ over sets $A$ and $B$. For every pair $(a, b) \in R$, we may swap its elements, obtaining pair $(b, a)$. The set of all such pairs $R' =\{ (b, a) \mid (a, b) \in R \}$ is a subset of $B \times A$ and is itself a relation over $B$ and $A$. We call it the inverse relation of the relation $R$ and sometimes denote by $R^{-1}$.

For example, if $A = B = \mathbb{Z}$ (the set of integers), we may consider a relation "is less than":

$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a < b\}$In other words, $R$ is the set of all pairs of integers such that the first integer is less than the second one. The inverse relation is $R^{-1} = \{(b, a) \in \mathbb{Z} \times \mathbb{Z} \mid b > a\}$Using words instead of formulas, we can say that this inverse relationship is the relation "is greater than".

Properties of relations

Now we will study several important properties of the relation $R$ on the set $A$. A little later, using these properties, we will distinguish two important types among all binary relations: equivalence relations and order relations.

• $R$ is called a reflexive relation if for any $a \in A$, $(a, a) \in R$ (so, any element of $A$ is related to itself).

  As an example of a reflexive relation, we can look no further than equality. If we take any number, say $a$, we will have $a =a$, and so the relation satisfies reflexivity. On the contrary, if we take $<$, it would not satisfy reflexivity as for any $a$, it does not hold such that $a<a$.

• $R$ is called a symmetric relation if for any $a, b \in A$, if $(a, b) \in R$, then also $(b, a) \in R$

  If we again compare $=$ to $<$, we will quickly see that the former is a symmetric relation, while the latter isn't. As if $a=b$ is true, then $b=a$ is also true. On the other hand, if $a<b$ is true, then $b<a$ is false.

• $R$ is an anti-symmetric relation if from $(a, b) \in R$ and $(b, a) \in R$ it follows that $a = b$

  Looking at a set $A$ that contains elements $x$ and $y$. We can define an anti-symmetric relation $R$ requiring $y$ to be divisible by $x$ and $x$ to be divisible by $y$. Thus we have that $(7, 21)\notin R$, as $21$ is divisible by $7$, but not the other way around. But if we have $(7, 7)\in R$, as $7$ is divisible by $7$ and the other way around, so it must be that $a=b$.

• $R$ is a transitive relation if from $(a, b) \in R$ and $(b, c) \in R$ it follows that $(a, c) \in R$

  Going back to our beloved inequality sign. It is transitive as if we have that $a<b$ and $b<c$, it must be true that $a<c$. While a simple example of a non-transitive relation is being someone's child. If Carl has a daughter named Sarah, and Sarah has a son named Bob, it is not true that Carl has a child named Bob, he instead has a grandchild named Bob.

Let's continue with some real-world examples. Suppose our $A$ is a set of users in some social network, and a pair of users $a$ and $b$ belong to relation $R$, if $a$ can comment on $b$'s posts. This relation is reflexive (everyone can comment on their own posts), but in a typical network, it's neither a symmetric nor an anti-symmetric one. Suppose $a$ and $b$ aren't friends, and they chose different settings for their profiles: only friends can comment on $a$'s posts, but everyone can comment on $b$'s posts. Then $(a, b) \in R$, but $(b, a) \not \in R$, so the relation can't be symmetric. But obviously, there will be a lot of pairs where each person can comment on each other's posts, so it's not an anti-symmetric relation too. You can easily invent a counter-example for transitivity, too.

There are a lot of examples of symmetric relations in our everyday life. Having the same year of birth or at least one common parent are symmetric relations, but the first one is transitive while the second one is not. Also, you might have already noticed that the word "transitive" resembles the word "transit". It's not a mere coincidence. Suppose $A$ is a set of cities and two cities are related if you can travel from one to the other by plane, possibly by connecting flights. Obviously, this relation is transitive.

Conclusion

Now we know about relations and some of their main properties. Now let's quickly go through what we have learned:

• Relations describe the connection between objects from sets, be it countries, people, or numbers.

• If there is a relation between elements of sets, for example, "less than" for real numbers, then "greater than" would be an inverse relation.

• A relation is reflexive if, for any element of a set, this element relates to itself.

• A relation is symmetric if for any $a, b \in A$ if $a$ relates to $b$, then $b$ relates to $a$.

• In a transitive relation if there is a relationship between $a$ and $b$ and there is a relationship between $b$ and $c$ then there will be the same relationship between $a$ and $c$.