Operations on relations

Because relations are really sets, we can carry out the usual set operations on them.

Set operations

In the previous article we defined relations as a set. With sets we can carry out operations such as union, intersection or difference. Let us see what this means for relations.

First we have to introduce a condition, because we cannot carry out these operations between arbitrary relations. If we have the relations “less than” and “being an even number”, these operations will make no sense, because the first relation is binary while the second is unary. So that after applying a set operation we again get a relation, all the relations involved must have the same arity, that is, they must all be n-ary for some n.

Union

Take the relations “less than” and “equality”. What happens if we take the union of these relations? In the relation less than we have all the pairs (a, b) for which a < b. In the relation of equality we have all the pairs (a, b) for which a = b. In the relation < ∪ = there will therefore be all the pairs (a, b) for which a < b or a = b. The number a is either less than the number b or equal to it. We know such a relation and call it “less than or equal to”, written ≤.

If we have relations R₁ and R₂, then their union gives the relation R = R₁ ∪ R₂, for which the following holds: an element r is in the relation R if it is in the relation R₁ or in the relation R₂. In other words, it will be in the resulting relation if it was in at least one of the relations being united.

Intersection

With the union we got a new relation whose elements were elements of at least one of the relations being united. The intersection is similar, except that the elements must be members of both relations.

If we take the relations less than and equality again (over the real numbers) and take their intersection, what do we get? We should get the elements that are in the relation less than and are also equal. But such a case cannot occur, because if a < b, then a = b never holds. We would get the empty relation.

Take these two relations: “divisibility without remainder” and the binary relation containing pairs of elements (a, b) where a is an odd number and b is an even number. Let us work over the positive integers. In the first relation there would be pairs of numbers such as (5, 15), (6, 30), (3, 123) – the second number must always be divisible by the first. In the second relation there will be pairs of numbers where the first number is odd and the second even: (1, 4), (5, 14), (3, 24) and so on. The intersection of these relations gives a new relation R, containing the pairs (a, b) for which b is divisible by a and at the same time a is odd and b is an even number. For example: (5, 30) or (3, 24).

Difference

If we have two relations R₁ and R₂, then the difference R₁ − R₂ gives a new relation containing the elements that are in R₁ but not in R₂. We can go back to the relations less than or equal to and equality. If the relation R₁ is less than or equal to and the relation R₂ is equality, then the difference R₁ − R₂ gives the elements that are in the relation less than or equal to but not in the relation of equality. So we get the pairs (a, b) for which a ≤ b and at the same time a = b does not hold. In other words we get the relation less than: <.

The complement of a relation

For every relation we can find the complement of the relation. The elements of the complement of a relation R are all the elements that do not belong to the original relation R. For example, the complement of the relation of equality (that is, =) is the relation of inequality. In the first relation we have all the pairs of elements that are equal (e.g. 5 = 5), and in the complement of the relation we have all the pairs of numbers that are not equal (e.g. 5 ≠ 6).

The only thing you must watch out for when finding the complement of a relation is the ground set – the set the relation belongs to. We can define the relation of equality on the positive integers, the integers, the real numbers or even on the set of all people on Earth.

If we have a binary relation R from the sets M₁ and M₂, so that R ⊆ M₁ × M₂, then the complement of the relation, let us call it S, is equal to S = (M₁ × M₂) ∖ R: these are the elements that are in the Cartesian product of the ground sets but not in the relation R. It is similar for relations of other arities.