Relations

A relation is the mathematical counterpart of the ordinary idea of a “relationship”. In everyday life, for example, Olivia is in a relationship with Emily, namely the relationship “mother – daughter”. Another such relationship is “country – capital city of that country”. We can take Egypt – Cairo as an example.

More examples of relations

Let us look at some more examples. In the introduction we mentioned the relations (relationships) “being the mother of a daughter” and “being the capital city of a country”. Let us look at others: “being an even number”. The numbers 2, 4, 8, 18, 58, 66 and many more are in this relation. The numbers 1, 3, −7, 19 are not in the relation “being an even number”. A relation from the everyday world could be “being a man”. Oliver, George, Jack or Noah are in the relation “being a man”.

Another example is the relation “less than”. For instance, the number three is “less than” the number five. In maths we can write this as 3<5. Or the relation of equality: the number three “is equal to” the number three, in maths 3 = 3.

We can also have more complicated examples: “a father and a mother are the parents of a child”. This relation contains a triple of people: the father Daniel, the mother Lily and the child Isla. In maths we could invent a relation with three elements like this: the sum of the first two numbers is equal to the third number. For example, these numbers, in this order, are in the relation: 3, 4, 7, because 3 + 4 = 7. These numbers are not in the relation: 3, 5, 12, because 3 + 5 ≠ 12.

The arity of a relation

Arity is a strange-sounding term, but it simply says how many elements we have in the relation. In the previous examples we worked with different numbers of elements. For the relation “being a man” one element was enough, so we can say: “Harry is a man”. One name, one element, is all we need. We say that such a relation is unary.

In the next example we had the relation “less than”. It worked with two numbers, two elements. We said that the number three is less than five. We used two elements, so the relation is binary.

In the last example we used three elements altogether: the sum of two numbers was to equal the third. So we had numbers a, b, c and it had to hold that a + b = c. This relation would be ternary.

For higher arities we can use the term n-ary relation. But we can also use it for lower arities: we can describe a binary relation as a 2-ary relation. The elements of the relation are then written as ordered n-tuples. For a binary relation we write them as pairs, usually with either round brackets or square brackets. So if we want to write that the numbers three and five are in the relation “less than”, we have to write the numbers as a pair: (3, 5), or alternatively [3, 5]. Note that we have to keep to the order; the other way round it would not hold: (3, 5) ≠ (5, 3) – five is not less than three.

A family example

Before we get on to the mathematical definitions, let us try one more typical example with a family. Take these members of one family:

• Max: paternal grandfather;
• Oliver: father;
• Amelia: mother;
• Isla: daughter;
• Harry: son.

First we look for all the members of the family who fit the relation “being a man”. This is a 1-ary, or unary, relation. So there will always be just one element in the relation, one member of the family. Now we must list all the members of the family who are male. The order does not matter here. The relation “being a man” therefore contains these elements: {(Max), (Oliver), (Harry)}. Notice that even though this is a unary relation, we used round brackets. This is not necessary in any way, and the notation would be readable without them, but for the sake of consistency I kept the brackets. The collection of all the elements of the relation is then an ordinary set, hence the curly brackets.

Now let us find all the “father – son” relations. This is clearly a binary relation, so the result will contain ordered pairs of elements. The resulting set looks like this: {(Oliver, Harry), (Max, Oliver)}. The father Oliver is the father of the son Harry, and the grandfather Max is the father of the father Oliver. Notice that the order really matters: Oliver appears twice, but once in first place as the father and once in second place as the son.

Let us try another relation: “parent – child”. There will be more in this one, because in first place there can be either parent, the father or the mother, and in second place there can be either child, the son or the daughter. We must also take into account that the grandfather Max is a parent of Oliver, but not a parent of Amelia. Oliver and Amelia are, however, both parents of Isla and Harry. Isla and Harry are not parents of anyone, because they are only nineteen and thirteen years old. In the end the ordered pairs will be: {(Max, Oliver), (Oliver, Isla), (Oliver, Harry), (Amelia, Isla), (Amelia, Harry)}. Notice that Oliver and Amelia each appear twice – once as parents of the daughter Isla and once as parents of Harry.

One last catch with binary relations. Take the relation “sibling – sibling”. Here we have to remember that order matters in relations, so if we wrote only “Isla – Harry” as the result for this relation, it would be wrong, because that is a completely different ordered pair from “Harry – Isla”. So the correct result is: {(Isla, Harry), (Harry, Isla)}.

And one very short example on a ternary relation: write down all the ordered triples of this relation: “grandfather – father – child”. In the question we have only one grandfather and one father, but two children. It is not enough to write only the version with Isla or with Harry; we have to list both. It would be different if “son” were given at the end instead of “child”. The correct result is: {(Max, Oliver, Isla), (Max, Oliver, Harry)}.

The definition of a unary relation

Let us explore the simplest relations, the unary ones. By a unary relation we mean some set of elements. The set {2, 3} can represent a relation. For example the relation “being a prime number less than five” or “being a non-trivial factor of the number six”, depending on our interpretation.

The sharper-eyed readers will have noticed that the second relation is defined a little strangely. It says that the relation should contain the non-trivial factors of the number six, and in the resulting set we have the numbers 2 and 3. Are we not missing some? The numbers 1 and 6 are trivial factors, so they do not interest us. But the negative numbers should be there too, that is −2 and −3. The set of all non-trivial factors of the number 6 looks like this: {−3, −2, 2, 3}.

Just as with functions we specify the domain, with a relation we specify the ground set – the set from which we choose the elements of the relation. In the previous examples, for instance, we specified a family that included Grandad Max and so on. We did not choose fathers and children from all the families in the world. If we specify the set of positive integers as the ground set, then our relation will be fine.

Now we can get on with the definition of a relation. If our ground set is the positive integers, what elements can our unary relation contain? Again only positive integers. Either all of them or just some part. So we can say that the relation will be a subset of the set of positive integers. More generally, if we have a unary relation R and a ground set M, then R ⊆ M, that is, the relation R is a subset of the set M.

The definition of a binary relation

What will it look like for a binary relation? In a binary relation the elements of the relation R are ordered pairs. Each element of the pair can come from a different set. We can have the relation “parent – number of children”. The parent will be chosen from the set of people, say in Europe, and the number of children will be chosen from the set of non-negative integers.

How do we get from two sets the set of all possible pairs? By the Cartesian product. If we have the sets A = {a, b, c}, B = {1, 2}, then the Cartesian product gives us:

$$A\times B=\{(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)\}$$

This is the set of all possible pairs that we can get by putting an element of the set A in first place and an element of the set B in second place. So if we have a binary relation R between the sets A and B, we can define this relation as R ⊆ A × B.

If we kept the previous sets A and B and defined a relation R between them like this: “letter – position of the letter in the alphabet”, then this relation will look like this: R = {(a, 1), (b, 2)}. The letter c will not be there, because the pair (c, 3) does not occur in the Cartesian product A × B.

The definition of an n-ary relation

Finally we define a general n-ary relation R between the sets M₁, M₂, …, M_n:

$$R\subseteq M_1\times M_2\times \dots \times M_n$$

A relation is thus a subset of the ordered n-tuples. An example of a binary relation is the relation “less than”, that is <. We can define it between some number systems, for example between the positive integers. Then the relation will look like this:

$$<\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$$

(Do not be alarmed that the symbol < sits so oddly on the left-hand side. It is just the name of the relation. There could again be an R there, where R would represent the relation less than.)

Specifically, the relation would look like this:

$$\begin{array}{rcl}<=& & (1,2),(1,3),(1,4),(1,5),\dots \\ & & (2,3),(2,4),(2,5),(2,6),\dots \\ & & (3,4),(3,5),(3,6),(3,7),\dots \\ & & (4,5),(4,6),(4,7),(4,8),\dots \\ & & \dots \\ & & \end{array}$$

It is the set of ordered pairs such that the positive integer in first place is less than the positive integer in second place.

Writing relations

We usually name relations with capital letters R, S and so on, or with established symbols: <, ⊆, = and so on. From the previous definitions we can see that a relation is really a set. After all, almost everything in maths is really a set :-). So if we want to say that an element r belongs to the relation R, we can write it as r ∈ R.

For example we can write (1, 3) ∈ <, which means that the pair of numbers one and three belongs to the relation less than. With binary relations we often meet a more pleasant notation that you know from primary school. Instead of using the operator “is an element of” ∈, we simply write 1 < 3. Similarly, we do not usually write (5, 5) ∈ =, but 5 = 5.