18. Operations on Relations

Hello everyone, welcome to this lecture on operations on relations. Just to recap in the last lecture we introduced the definition of relations and we saw various types of relations. The plan for this lecture is as follows. We will see various set theoretic operations which we can perform on relations. Specifically, we will be discussing on the powers of a relation and closure of a relation.

This chunk introduces the topic of operations on relations. The speaker explains that the previous lecture covered the definition and types of relations, and now they will explore how set theoretic operations can be applied to relations. Specifically, they will focus on operations like union, intersection, and the concepts of the powers of a relation and closure. Understanding these operations is crucial for analyzing and manipulating relations effectively.

Think of relations as social connections. If someone is connected to various friends (relations), just as we can combine friendships (like unions or intersections), we can analyze how these connections can lead to new connections (like powers of relations), or strengthen existing connections so that they meet specific criteria (closures).

So, it turns out that since relations are nothing but a set so we can perform various set theoretic operations like union, intersection, set difference on relations as well. So, to demonstrate this, let us consider two relations R1 and R2. You have a relation R1 which consists of all (x, y) pairs or all real numbers (x, y) where x < y. So, here my relation R1 is defined over the set of real numbers, my domain is that of real numbers.

So, R1 will have all tuples of the form (x, y) where real number x is less than real number y and similarly, relation R2 is another relation defined over the set of real numbers consisting of all (x, y) pairs where the real number x is greater than the real number y. Now, if I take the union of these two relations and the union of these two relations is well defined because both R1 and R2 are sets and we can perform the union of two sets.

This chunk explains that relations can be treated as sets, and various set-theoretic operations such as union and intersection can be applied to them. The speaker introduces two specific relations, R1 and R2. R1 contains all pairs of real numbers (x,y) where x < y, and R2 contains pairs where x > y. When examining the union of R1 and R2, the speaker explains that this union would contain all pairs where x is not equal to y, capturing both types of relations in a single set. This illustrates how union expands the notion of relationships by including more combinations.

Imagine two groups of people: Group R1 is comprised of people who prefer soccer over basketball, and Group R2 consists of people who prefer basketball over soccer. If we take the union of these groups, we have a complete list of all individuals who are either into soccer or basketball, which helps us understand everyone's preferences.

So, it turns out that the union of these two relations will have all pairs of the form (x, y) where the real number x is not equal to real number y because the union will have all the elements of R1 and a union also will have all the elements of R2. So, one way of describing the union of the two relations is that it has all (x, y) pairs where either x < y or x > y.

Whereas, if I take the intersection of these two relations R1 and R2 and it turns out to be an empty set, because you cannot have real numbers x and y, where x is simultaneously less than y as well as x is simultaneously greater than y.

This chunk describes the results of applying the intersection operation. The lecture explains that the intersection of the two relations R1 and R2 is empty, meaning there are no pairs (x,y) where x is both less than and greater than y at the same time. This emphasizes that the intersection represents shared elements between sets, which in this case, do not exist. The set difference operation is also briefly mentioned, illustrating how one can subtract elements from one relation to see what remains.

Think of two exclusive clubs: Club A is for people under 30 years old, while Club B is for those over 30. The intersection of these clubs (those who belong to both) is empty, as no one can be both under and over 30 at the same time. This simple example helps clarify the intersection concept effectively.

Now, we can perform another interesting operation on the relations which is called as composition of relations. So, imagine you are given two relations R and S, the relation R is from the set A to B. So, R is a subset of A x B. And your relation S is from the set B to C, so S is a subset of B x C. I am taking here three arbitrary sets A, B, C; A, B, C may be the same, they may be different there is no relationship.

The speaker describes the composition of two relations, R and S, which involves two sets A and B, and B and C respectively. They define how the composition combines elements through a shared connecting relation (from A through B to C). The notation S o R indicates that R is applied first, followed by S; the order affects the resulting composition, which creates a new relation from set A to set C. This is a fundamental concept that helps understand how different relations can interact and lead to new derivations.

Consider a taxi service (R) that connects your home to your local grocery store (B), and the grocery store has a delivery service (S) to bring products to your home (C). If R connects you to the store and S connects the store to your home, the composition of these two services effectively allows you to get groceries delivered without going out yourself.

So, once the definition of compositions of relations is given, we can define what we call as powers of a relation and how it is defined. So, imagine R is a relation from A to B that means R is a subset of A x B. Then the definition of powers of a relation is as follows; R1 is defined to be the relation R itself and then recursively I define the n + 1th power of R to be the composition of the relation which is nth power of R with the original relation R.

This chunk presents the concept of the powers of a relation, which denotes repeated applications of the composition operation. The first power, R1, is simply the original relation R. As the powers increase (R2, R3...), we keep composing the relations, implying that we are effectively extending the relation by one step further through the existing connections. This recursive definition emphasizes the significance of relation composition in growing the relational sets.

Imagine a chain of friends where R is one connection. If each of your friends (R) can also introduce you to their friends, R2 represents this second level of introductions, and going further, R3 could be the friends of your friends' friends, demonstrating how relationships grow geometrically through composition.

Now, next what we are going to discuss is a very nice interpretation of the powers of a relation in terms of a property in the corresponding graph. So, imagine you are given a relation over some set A consisting of n elements and suppose the relation is represented by a directed graph G.

This chunk introduces the closure of a relation, which pertains to enhancing a relation to ensure it meets certain properties (e.g., reflexivity, symmetry, transitivity). The closure can be interpreted as finding the least amount of new connections necessary to uphold a property, ensuring that the expanded relation still retains the original elements. This concept emphasizes not just what exists but what is needed to satisfy broader relational properties.

Envision a group of students forming study groups. Initially, some students may not connect directly. We can think of 'closure' as ensuring that every student can study with every other student by forming minimal new groups, thereby making sure no one is left out, effectively enhancing the study environment while maintaining original members.

--