18.5. Powers of a Relation

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.

In this chunk, we are defining the concept of powers of a relation. A relation R going from set A to set B is defined as a subset of the Cartesian product of A and B, denoted A x B. Here, R1, which is the first power of R, is simply R itself. To find the power Rn+1, we take the composition of R with Rn, which indicates the order of operations matters. The construction builds on itself, recursively defining higher powers of the relation. This means that the nth power relates to how many times we can 'chain' connections through the relation R itself.

Imagine a party where you are connecting people through mutual friends. The first connection (R1) is simply the individuals at the party. The second connection (R2) represents direct friendships between those at the party, while R3 could represent friends of friends. Each step in composition broadens your understanding of how interconnected your social network is!

So again, I stress here the order matters here, the n + 1th power is defined to be the composition of Rn with R that means you have to apply the relation R first and then you have to apply the relation Rn. It need not be equal to the composition of R with the nth power of R that may or may not be the case because in general the composition of two relations need not be commutative.

This chunk emphasizes the importance of order in defining the powers of a relation. Specifically, for the (n + 1)th power, we first apply R, then apply the previous power Rn. This is crucial as the direction or order of operations can lead to different results, known as non-commutativity in mathematics. Because of this characteristic, Rn+1 is not necessarily the same as R combined with Rn.

Think about following a recipe step by step. If you mix flour and sugar, then add eggs, you get a different mix than if you add eggs first and then mix in the sugar. The order in which ingredients or relational steps are combined matters, just like in our power relations!

Let me demonstrate the powers of a relation with an example. Here I have defined a relation R consisting of the pairs (1, 1), (2, 1), (3, 2) and (4, 3). So, R1 as per my definition will be the relation R itself.

In this example, the relation R is given explicitly with pairs such as (1, 1), (2, 1), (3, 2), and (4, 3). R1, reflecting the first power, is just the relation itself. As we explore further powers, we will look at how we build R2 by composing R with itself, cataloging which pairs can be 'reachably' combined both ways from R's existing pairs.

Consider a small map in a town where locations (1, 2, 3, 4) represent different people, and the pairs represent direct acquaintances. R1 captures that direct connection; as you apply transformations (or powers), you can navigate through the network to find indirect acquaintances, just like how you might trace who knows who on a social map!

Now, if I want to compute R3 then it will be the composition of R2 with relation R. So, I will take this R2 here first and compose it with the original relation R that means the relation R has to be applied first and then on top of that the relation R2 has to be applied.

In this chunk, we are moving on to calculating R3, which involves taking the result of the previous power R2 and composing it with the original relation R. This shows the iterative nature of calculating higher powers, building upon the previous results to discover new connections available through R.

Continuing with our social map analogy, imagine you discover that connections among your friends can lead to a whole new set of acquaintances. If R2 contains people you can reach through one degree of separation, R3 reveals those who are two degrees away. Continuing this process maps a deeper layer of relationships among individuals in your network!

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 concept of interpreting powers of a relation through the lens of graph theory. In this context, the relation can be viewed as a directed graph G, where elements from the set A are represented as vertices. The edges between vertices (relationships) illustrate how elements are related, and the sequence of connections (or paths) from one vertex to another reveals the powers of that relation.

Imagine a city where places are intersections and roads are the directed edges of your graph. If you start at one intersection (A) and want to explore how to return to A via a series of roads (representing powers of the relation), each layer tells you what newer routes exist based on how many roads you traverse, expanding your understanding of the city layout!

So, the claim here is the following the ordered pair (a, a) will be present in the mth power of the relation if and only if, there is a directed path of length m from the node a to the node a in the digraph of your relation.

In this chunk, we are asserting a key result regarding directed paths in graphs. Specifically, an ordered pair (a, a) exists in the mth power of the relation if and only if there is a directed path of length m that starts and ends at a. This shows a direct relationship between the powers of a relation and the paths in a corresponding graph.

Think of a round trip from home (A) to an amusement park (B) and back. If you can make a round trip in M different ways by following a series of routes (the edges of our graph), this reflects how many ways you can reach back home as defined by the mth power of the relation. Each route represents a collection of steps you take!

--