19.1. Introduction to Connectivity Relation

Imagine you are given a relation R over a set which may or may not be finite. So, your R is a subset of A x A. And I define this relation R*, which I call as the connectivity relation and this is basically defined to be the union of different powers of your relation R. It turns out that, as per my definition of R*, an element, a_i will be related to a in this relation R* provided there exists some path of any length of it may be j of length 1, it may be of length 2, it may be of length 3.

A connectivity relation captures how elements in a set relate to each other based on the paths that connect them. In mathematical terms, if we have a set A and a relation R which consists of pairs of elements (a_i, a_j), then for R* to include a_i and a, there just needs to be one valid path—regardless of how many 'hops' it requires through other elements—to connect the two. This path could involve several intermediary elements and their relationships defined by R. As a result, R* serves as a summary that shows how connected the elements in A are.

Think of a network of roads in a city. Each intersection represents an element from set A, and a road between two intersections represents a relationship in R. If you can drive from intersection A to intersection B using various roads and intersections, then in terms of connectivity relation, A is connected to B, which would mean (A, B) is in R*. Even if there are many roads between them, what matters is that at least one path exists.

The guarantee is that there exists at least one path from the node a_i to the node a in the directed graph of your relation R. And why so, because recall in the last lecture. We proved this statement by induction. The statement states that if you have element a_i related to element a in the nth power of your relation R. Then that is possible only if you have a path of length n, from the node a to the node a in the directed graph of your relation R.

To understand how connections work, we use the concept of paths within the graph representing the relation R. If we have a_i related to a through nth power of R, it means there is a sequence (or path) that takes us from a_i to a using exactly n steps. This forms the basis of how we define 'connectivity' in larger sets of connections, as it allows us to track how we can traverse through nodes (or elements) in our set.

Imagine you are sending a message to a friend through several mutual friends in a relay system. If you send the message to your friend, and the message passes through four other friends before reaching its destination, we say the message has taken a path of length 4. Similarly, in connectivity relations, if a_i can reach a through paths of varying lengths, each path represents a way we can connect the two nodes.

My claim here is that R* is nothing but the union of R, R^2 and up to R^n because you do not need to take the union of higher powers of R. Any higher powers of R will be subsumed in the union of the first n powers of R provided your relation R is defined over a finite set consisting of n elements.

In a finite set, there's a limit to the number of distinct paths that can be formed between any two elements. If we think of nodes as being interconnected, once we reach n steps, we can't create new unique paths using distinct nodes without repeating. Hence, the connectivity relation R* can effectively be captured simply by the first n powers of R. This means that when analyzing paths, it's sufficient just to check these limited powers to understand the broader connectivity.

Consider a small town where there are four intersection points (A, B, C, D). You can only drive so far without revisiting intersections, so once you’ve tried every possible route to connect to another intersection, extra routes beyond a single loop through all intersections don’t add new information about connectivity; hence, only the first few connections matter to determine if you can reach a destination.

So, now we are going to see a relationship between the transitive closure and the connectivity relationship. So, remember in the last lecture we saw an example where we constructed the transitive closure of a relation. And there we had iteratively applied the process, the rule that if you have (a, b) and (b, c) in the expanded relation R or in the original relation R, then you add the element (a, c) and keep on doing this process till we do not need to add any extra elements of the form (a, c).

The connection between transitive properties and connectivity is that if one can traverse from A to B, and from B to C, then it must also be possible to traverse directly from A to C. This is a fundamental property in mathematics known as transitivity, which forms the backbone of how we expand R into R*. The iterative process allows us to conclusively understand all elements connected indirectly through others in a structured way.

Imagine you know a teacher who knows another teacher through mutual connections. If you hear about a project from the first teacher and the second teacher mentions it, you can infer that you also know about the project due to the shared knowledge, regardless of how many 'hops' it took. This is transitivity, where the knowledge shared connects indirectly through relationships.

--