Binary Relations, Relational Images, Inverse Relations and Images. Why do we need them in Computer Science?

Binary Relations

Binary relations define relations between two objects.

Well, we say "relation, relation" everytime, but what is the relation actually?

There are 5 types of binary relations:

Relational Images

The idea of the image of a set under a function extends directly to relations.

Formal definition: Given a relation R between two sets A (the domain) and B (the codomain), and a subset S⊆A. The image of S under R is the set

R(S) = {b∈B ∣ ∃a∈S such that (a,b)∈R}

Example: A = {1, 2, 3}, B = {a, b, c} and subset S = {1, 3}. Relation between A and B is R = {(1, a), (2, b), (1, c), (3, a)}. So the image of S under relation R becomes:

R(S) = {a, c}

Which means, the elements of the subset S is related to only these elements in a set B.

❓ Why we need this in Computer Science?

This concept is fundamental and very crucial in Computer Science due to its broad applicability to various fields like databases, graph theory and algorithms. Let's consider each:

1. Database management

In relational databases, the relationships between different tables (relations) are essential. For example, consider a database with tables for Users and Orders. The relationship can be represented by a relation R where each user is linked to their orders. If S is a set of users, R(S) would yield all orders related to these users.

Users = {Alice, Bob, Charlie}
Orders = {Order1, Order2, Order3, Order4}
R = {(Alice, Order1), (Bob, Order2), (Charlie, Order3), (Alice, Order4)}
S={Alice}
R(S)={Order1,Order4} - Image of S under relation R.

This is exactly the thing which finding all orders made by Alice.

2. Graph Theory

The image of a set under a relation in graph terms describes adjacency. Let's say we have a graph with some nodes and edges (relations). We can find all nodes which are directly reachable from some node (in this case A) using images:

Nodes = {A, B, C, D}
Edges (relation) = {(A, B), (A, C), (B, D), (C, B)}
S={A}
R(S)={B,C} - Nodes directly reachable from node A.

3. Algorithms

Many algorithms involve mapping elements from one set to another to identify properties or solve problems. For instance, in sorting algorithms, the relation might define how elements compare to each other, and understanding the image of a set under this relation can help optimize sorting.

array = {3, 1, 4, 1, 5, 9, 2}
Relation R based on '<'
S = {4}
R(S) = {5, 9} - elements greater than 4

Here, we have a relation "greater than" and we filtered the array for greater that 4.

Inverse Relation

Consider the relation R = {(1, a), (2, b), (3, a)} from set A = {1, 2, 3} to set B = {a, b}. The inverse relation becomes

R^(-1) = {(a, 1), (a, 3), (b, 2)}

Inverse Image

To understand this concept clearly, I'll give an example in relational databases.

Consider a database with two tables, Employees and Departments. Each employee is assigned to one department, establishing a relation R from Employees to Departments. The inverse relation R^{-1} can be used to find all employees in a specific department. If you know the department ID, you can easily retrieve all employees linked to that department, effectively using R^{-1}.

R = {(Sam, Development), (Tom, HR), (Martin, Development)}
R^(-1) = querying for the "Department" retrieves "Sam" and "Martin".

Finite Cardinality

We can then redefine the binary relations in finite sets:

1. If A surjective B, then |A| >= |B|
2. If A injective B, then |A| <= |B|
3. If A bijective B, then |A| = |B|

❓ How many subsets of a finite set?

✅ There are 2^n subsets in a n-element set.