16.2. Mathematical Interpretation of Relations

So, what is a relation? So, let me begin with this example, you consider this table and people who are familiar with databases, they very well know what is a table. Table basically consist of several columns and each column have some entries. So, I call this table T which has two columns, column number 1 and column number 2. In column number 1, you have some countries and in column number 2, you have some cities listed. Now if your general knowledge is good then it turns out that the elements you can spot here that elements of the first column and the second column they are related by some relationship. And the relationship here is that, in the first column I have listed some of the countries and in the second column I have listed the capital of the corresponding countries.

A relation is a connection between two sets where elements of one set are associated with elements of another set. For example, in the context of a table consisting of countries and their capitals, each country (from the first column) is related directly to its capital (from the second column). This relationship can be viewed as a way of organizing and displaying data, similar to a database table, making it easier to identify connections.

Think of a library database where each book is associated with its author. If you have a list of books (set A) and a list of authors (set B), a relation can be created where each pair consists of a book and its author. Just like recognizing that 'Harry Potter' is by 'J.K. Rowling', this relationship helps us understand which books belong to which authors.

Now how do we mathematically interpret this table? Is there any mathematical interpretation or mathematical abstraction by which you can define this table? Well the way I can mathematically interpret this table T is as follows. I can imagine that I have a set A which is defined to be the set of all countries in the world. Well I do not know right now how many exact numbers of countries in the world definitely it is more than 200. So, A has more than 200 elements. Whereas B is another set, which is defined to be the set of all cities in the world. Again this is a well defined set because we know the list of all cities in this world, so both these sets are well defined.

To mathematically define the relationship seen in our example with countries and capitals, we can establish two sets: Set A contains all countries, while Set B contains all cities. The relationship can be seen as a subset of the Cartesian product of these two sets, meaning each country in set A can be paired with the corresponding capital in set B. In our case, this makes the table a visual representation of specific pairings from this larger set of all possible country-city pairs.

Imagine you have a set of all students in a school (Set A) and another set of all classes offered (Set B). The relations here could represent which student is enrolled in which class. Each specific student-class pair makes it easier to look up who is attending which class, similar to how country-capital pairs help us see which capital belongs to which country.

So, that is a loose definition of a relation. A relation here is basically a subset of A x B, if I am considering two sets A and B and of course whatever I have discussed here can be extended where I have multiple sets. What do I mean by that? In this example I had only two columns. And C was having entries from set A and C was having some entries from B. What if I have a database consisting of 3 columns? Say there is a third column as well, where the third column denotes population. So, those entries will be coming from a set C, what if I have a fourth column which denotes another feature of the table, say the climate or the temperature of the respective countries.

A relation is formally defined as a subset of the Cartesian product of two sets, A and B. In addition, this concept can be extended to more than two sets by including more columns in the representation. For instance, if we add a third set for populations and a fourth set for climate data, we can create more complex relations that show how these different attributes are connected, enhancing our understanding of the data's interplay.

Consider a restaurant menu where we have dishes (Set A), their prices (Set B), and the preparation time (Set C). A relation formed from these sets helps us see which dish has what price and preparation time, enabling customers to make informed choices based on their preferences.

So, that is how we are going to define a relation, so we will focus in mostly on binary relations and by binary relations I mean, we will be working with two sets A and B, but whatever we are discussing here can be generalized for extended for any number, it can be generalized for n-ary relations which are defined over n sets. But for this course and for most important cases, we will be focusing on binary relations.

In mathematics, binary relations specifically deal with pairs from two sets, labeled A and B, and we often focus on these because they are sufficient for many practical applications. While we can discuss relations involving multiple sets (n-ary relations), binary relations provide a clear foundation and are commonly used in databases and theoretical mathematics, making them crucial for our understanding.

If you think of relationships in social networks, each user (Set A) may be connected to another user (Set B) through friendships. Each unique friendship can be represented as a pair, illustrating the binary nature of these connections.

So, how do we define a binary relation? So, we are given two sets here, call them A and B and they need not be different, I stress here, they can be the same, definition does not say that they have to be different sets, because we are defining a relation in an abstract fashion. Then a binary relation from A to B is a subset of A x B. So, I have highlighted the term from A to B by a different color because the order of the relation matters.

A binary relation is a subset of the Cartesian product of two sets A and B, indicating the connections between each element of A and each element of B. It's important to note that the order of these sets matters; a relation from A to B is not the same as one from B to A, as it changes the meaning of the relationship between the elements.

Imagine writing a love letter where you specify who loves whom. Here, A could represent people in love, and B could represent the recipients of those affections. When you say 'A loves B,' that’s different from saying 'B loves A,' illustrating how the order in relations is crucial for understanding the dynamics.

So, now an interesting question is that if you have a binary relation defined from the set A to B how many such binary relations can you define? Can I define any number of binary relations or is there an upper bound on the maximum number of binary relations that I can define?

The total number of binary relations that can be formed between two sets A and B is determined by the number of subsets of the Cartesian product A x B. If set A has m elements and set B has n elements, then the number of possible pairs (small subsets) is mn, leading to 2^(mn) total binary relations, as each element can either be included in a relation or not.

If you think of pairing socks from two different drawers (one with patterns and the other with colors), every combination you could possibly make forms a unique 'binary relation.' The more combinations you can create, the more relations you can establish, similar to how friends can have different connections based on shared interests.

Now the next question is how do we represent binary relations? So, there are some well known methods for representing binary relations, the first method is the matrix representation. So, since we are dealing with binary relations the matrix representation here will be an m x n matrix, m because there are m possible elements from the set A and n columns because I have n possible elements from the set B.

Binary relations can be represented in several ways, with one common method being the matrix representation. In this method, we create a Boolean matrix where each entry signifies whether a pair (a, b) is present in the relation or not. If the pair exists, it is marked as 1; if not, it is marked as 0. This matrix effectively summarizes the relationships between elements across both sets.

Think of a seating arrangement for a dinner party where a matrix can show which guests are sitting next to each other. A '1' in the matrix indicates that two guests are seated next to each other, whereas a '0' means they are not, allowing the party planner to visualize the seating relationships.

We have another representation which we call as the directed graph representation. So, what do we do in this representation, we draw a graph and by graph I mean a collection of vertices and edges. The vertices will be the nodes a , a , a , and b , b , b and it will be a directed graph that means the edges here will have a direction associated.

Another common representation of binary relations is through a directed graph. In this approach, we create nodes for each element in sets A and B, connecting them with directed edges that indicate a relation. If there is a relation from a to b, we draw an arrow from node a to node b. This visualizes which elements are related, making patterns and connections more intuitive to understand.

Picture a city transit map where stations (nodes) are connected by directed routes (edges) indicating which station leads to another. If a bus route can take you from Station A to Station B, that directed edge represents the relationship of those two stations in terms of travel routes.

--