Introduction to Relations

 Introduction of relations: when the word relation comes to our mind then we discuss the relations with our family, friends, and colleagues but here we are going to discuss the relation in mathematics. We have to understand that relations in sets are very important and we use these relations in our daily life. 

The only way to learn mathematics is to do mathematics - Paul Halmos

Introduction

In our daily life, we come across many patterns that characterize relations such as brother and sister, father and son, teacher and student. In mathematics also, we come across many relations such as number `m` is less than number `n`, line `l` is parallel to line `m`, set `A` is a subset of set `B`. In all these, we notice that a relation involves pairs of objects in certain order. Cartesian Product Given two non-empty sets `S` and `T`. The Cartesian product `S \times T` is the set of all ordered pairs of elements from `S` and `T`, such that `S \times T=\{(s, t): s \in S, t \in T\}` Let us consider an example: `S= \{PB, HR\}` represents Punjab, Harayana and `T= \{11, 21, 31\}` representing codes for the registered number plates of vehicles issued by PB, HR. If the two states, Punjab and Haryana were making codes for the registered number plates of vehicles, with the restriction that the code begins with an element from set `S`, which are the pairs available from these sets and how many such pairs will there be? `S \times T= \{(PB, 11), (PB, 21), (PB, 31), (HR, 11), (HR, 21), (HR, 31)\}` It can easily be seen that there will be `6` such pairs in the Cartesian product, since there are `2` elements in the sets `S` and `3` elements in the set `T`. This gives us `6` possible codes.

 Let us take one more example, 

`A=\{1, 2, 3, 4\}` and `B=\{a, b, c, d, e\}`, then

 `A \times B` = `\{(1, a), (1, b), (1, c)`, (1, d), (1, e), (2, a), (2, b), (2, c), (2, d), (2, e), (3, a), (3, b), 

(3, c), (3, d), (3, e), (4, a), (4, b),` (4, c), (4, d), (4, e)\}` 

The `20` ordered pairs thus formed can represent the position of points in the plane if `A` and `B` are subsets of the set of real numbers and it is obvious that the point in the position `(1, c)` will be distinct from the point in the position `(c, 1)`. 

REMARK: 

1. If there are `m_1` elements in `S` and `m_2` elements in `T`, then there will be `mn` elements in `S \times T`, i.e., if `n(S) = m_1` and `n(T) = m_2`, then `n(S \times T) = m_1 m_2`. 

2. If `S` and `T` are non-empty sets and either `S` or `T` is an infinite set, then so is `S \times T`. 

3. If `S` and `T` are non-empty sets such that ` S \times T \not = T \times S`. 

4. `S \times S \times S= \{(x, y, z): x, y, z \in S\}`. `(x, y, z)` is called an ordered triplet. Relation} 

Definition: A relation `R` from a non-empty set `S` to a non-empty set `T` is a subset of the Cartesian product `S \times T`. The subset is derived by describing a relationship between the first element and the second element of the ordered pairs in `S \times T`. The second element is called the image of the first element. 

Definition: The set of all first elements of the ordered pairs in a relation `R` from a set `S` to a set `T` is called the domain of the relation `R`. 

Definition: The set of all second elements of the ordered pairs in a relation `R` from a set `S` to a set `T` is called the range of the relation `R`. 

Definition: The whole set `T` is called the codomain of the relation `R`. 

Note that range is the subset of codomain. 

Note: A visual representation of the relation `R` is called an arrow diagram. 

Example: Consider the relation `R` from `A \times A` by `R= \{(x, y): y= x+2\}`, where `A=\{1, 2, 3, 4, 5\}`. 

1. Depict this relation using an arrow diagram. 

2. Write down the domain, range and codomain of `R`. 

Solution: 1. The arrow diagram from `A \times A`. Thus, `R=\{(1, 3), (2, 4), (3, 5)\}`. 

2. Domain `= \{1, 2, 3\}`, that is, the set of all first elements of the ordered pairs in a relation `R`.

 Range `= \{3, 4, 5\}`, , that is, the set of all second elements of the ordered pairs in a relation `R`. Codomain `= \{1, 2, 3, 4, 5\}`, that is, the set of all elements of the set `A`. 

Example: Let `P=\{2, 3, 4\}` and `Q=\{3, 4, 5\}`. List the elements of relation `R` defined below and domain, range and codomain. `R=\{(p, q): p \in P, \; q \in Q,\; \text{iff} \; p \; \text{and} \; q \; \text{both are odd numbers}\}` 

Solution: In set `P` only odd number is `3` and in set `Q` we have two odd numbers, that is, `3, 5`. Thus relation is `R=\{(3, 3), (3, 5)\}` Domain `= \{3\}`, Range `= \{3, 5\}` and codomain `=\{3, 4, 5\}`. 

Total Number of Distinct Relation From Set `P` to Set `Q` 

The total number of relations that can be defined from a set `P` to a set `Q` is the number of possible subsets of `P \times Q` If `n(P ) = p` and `n(Q) = q`, then `n (P \times Q) = pq` and the total number of relations is `2^{pq}`. Among these `2^{pq}` relations the void relation `\phi` and the universal relation are trivial relations from `P \times Q`. 

Example: Find the number of relations from `A= \{a, b, c\}` to `B=\{1, 2\}`. 

Solution: Here, `A= \{a, b, c\}`, `B=\{1, 2\}`. Number of elements in set `A` is `3` and in set `B` is `2`. Thus, total number of relations from `A` to `B` is `2^{3 \times 2}= 2^6=64`.

References

[1]    B. S. Grewal, Higher Engineering Mathematics, Khanna Publishers, 40^th Edition.

[2]    H. Rosen Kenneth, Discrete Mathematics and its Applications, McGraw-Hill.

Here's a concise summary of the current page:

Mathematical Relations: The page discusses the concept of relations in mathematics, which involve ordered pairs of objects.

Cartesian Product: It explains the cartesian product of two sets, providing examples with sets representing states and vehicle codes.

Relation Definition: Various definitions related to relations such as domain, range, and codomain are provided in 2.

Examples: The page includes examples to illustrate the concepts, like the relation R from set A to A, where R is defined by a specific condition.

The page also contains references for further reading on the topic.

How can relations be used in programming?

Programming requires the use of relations and sets, particularly when working with data structures and algorithms. Let's examine some possible uses for these ideas:

Networks and Graphs: Graphs are a popular type of data structure that is used to show the relationships between objects. Adjacency lists and matrices are two programming tools that can be used to create graphs. 

Think of a social network, for instance, in which friends are the edges and users are the nodes. This can be represented as a graph on which you can run operations such as shortest paths and friends-of-friends finding.

SQL and databases: Relations, or tables, are used by relational databases (like MySQL and PostgreSQL) to store and manage data. Relationship procedures including selecting rows, joining tables, and conditionally filtering data are all part of SQL queries.

Key-value stores and hash tables: Keys and values are correlated in hash tables (dictionaries, maps). There is a linkage between the key-value pairs. Dictionary storage with fast lookup times is possible in Python.

Functional Programming: The focus of functional programming languages, such as Scala and Haskell, is on functions and immutability. Relationships between the values of the input and output are what define functions.

Operate Sets: In programming, set operations (union, intersection, and difference) are helpful.

Set operations, for example, can be used to locate common elements or unique values when working with lists or arrays.

Graph Formulas: Graphs are the working medium for algorithms such as depth-first search (DFS) and breadth-first search (BFS).

These algorithms investigate the connections between a graph's nodes.

Recall that creating successful models of real-world events, designing efficient algorithms, and data organization all benefit from a grasp of relations and sets. Please feel free to ask any questions.