Unit 2 – Relations and Functions | DM SPPU 2024 Pattern

Introduction to Relations in Discrete Mathematics

In discrete mathematics, a relation establishes a connection between elements of two or more sets. It is a fundamental concept used extensively in computer science, specifically in database management systems (RDBMS), network topology, and algorithm design.

To understand relations, we first need to understand the Cartesian product. If we have two sets, A and B, their Cartesian product (written as A x B) is the set of all possible ordered pairs where the first element comes from A and the second element comes from B. A relation is simply any subset of this Cartesian product.

For example, if A = {1, 2} and B = {a, b}, the Cartesian product is A x B = {(1, a), (1, b), (2, a), (2, b)}. A relation R could be just {(1, a), (2, b)}.

Hinglish Explanation: Relation ka matlab simple terms mein ek connection ya rishta hota hai. Agar hamare paas do sets hain, toh unke elements ke beech ke possible connections ke subset ko hum mathematical relation kehte hain.

Properties of Relations

When a relation R is defined on a single set A (meaning R is a subset of A x A), it can have specific properties. Understanding these properties is crucial for analyzing data structures.

• Reflexive Relation: A relation R on set A is reflexive if every element in A is related to itself.

  • Condition: (a, a) belongs to R for every element 'a' in A.

• Symmetric Relation: A relation is symmetric if, whenever 'a' is related to 'b', 'b' is also related to 'a'.

  • Condition: If (a, b) belongs to R, then (b, a) must belong to R.

• Transitive Relation: A relation is transitive if 'a' is related to 'b', and 'b' is related to 'c', then 'a' must be related to 'c'.

  • Condition: If (a, b) and (b, c) belong to R, then (a, c) must belong to R.

• Antisymmetric Relation: A relation is antisymmetric if 'a' is related to 'b', and 'b' is related to 'a', then 'a' must be exactly equal to 'b'.

  • Condition: If (a, b) belongs to R and (b, a) belongs to R, then a = b.

Representation of Relations

Relations can be represented mathematically as sets of ordered pairs, but in computer science, we need structures that algorithms can easily process. The two most common representations are Matrices and Digraphs.

1. Representation using Matrices (Zero-One Matrix)

A relation between finite sets can be represented using a matrix containing only 0s and 1s. This is highly useful for boolean matrix operations in programming.

• Let set A have 'm' elements and set B have 'n' elements. The matrix will be of size m x n.

• If an element from row 'i' is related to an element from column 'j', we place a 1 in that position.

• If they are not related, we place a 0.

2. Representation using Digraphs (Directed Graphs)

A directed graph (digraph) is a visual way to represent a relation on a single set A.

• Vertices (Nodes): Each element of the set is drawn as a circle or node.

• Edges (Arrows): If (a, b) is in the relation, we draw an arrow pointing from node 'a' to node 'b'.

• Self-loops: If (a, a) is in the relation (reflexive), we draw an arrow from node 'a' that loops back to itself.

Equivalence Relations and Partitions

Equivalence Relation

A relation R on a set A is called an Equivalence Relation if it perfectly satisfies three specific properties simultaneously:

1. It is Reflexive.

2. It is Symmetric.

3. It is Transitive.

An everyday example of an equivalence relation is the "is equal to" operator (=). A number is equal to itself (reflexive), if x = y then y = x (symmetric), and if x = y and y = z, then x = z (transitive).

Partitions and Equivalence Classes

When an equivalence relation is applied to a set, it divides the set into distinct, non-overlapping subsets. This division is called a Partition.

• Each subset in the partition is called an Equivalence Class.

• All elements within the same equivalence class are related to each other.

• No element can belong to two different equivalence classes. The intersection of any two different equivalence classes is always empty.

Hinglish Explanation: Equivalence relation ek set ko alag-alag tukdon (partitions) mein baant deta hai. Har tukde ko equivalence class kehte hain. Ek tukde (class) ke saare elements ek doosre se related hote hain, aur koi bhi element do alag classes mein nahi ja sakta.

Partial Orderings and Hasse Diagrams

Partial Ordering (POSET)

A relation R on a set A is called a Partial Order if it satisfies these three properties:

1. Reflexive

2. Antisymmetric

3. Transitive

A set combined with a partial order relation is called a Partially Ordered Set, or POSET. A common example is the "less than or equal to" (<=) relation on numbers.

Hasse Diagram

A Hasse diagram is a simplified visual representation of a POSET. Since a POSET is always reflexive and transitive, drawing every single arrow in a digraph makes it messy. A Hasse diagram removes unnecessary clutter using these steps:

1. Remove self-loops: Since POSET is reflexive, every node has a loop. We delete them to save space.

2. Remove transitive edges: If there is a path from A to B, and B to C, we know A connects to C because of transitivity. So, we delete the direct arrow from A to C.

3. Draw bottom-up: We arrange the nodes so that all arrows point upwards. Because of this, we can remove the arrowheads entirely.

Hinglish Explanation: Hasse diagram ek clean map hai. Kyunki hume pehle se pata hai ki POSET reflexive aur transitive hota hai, hum extra arrows aur loops hata dete hain. Hum diagram ko neeche se upar (bottom-up) banate hain taaki arrows draw karne ki zaroorat hi na pade.

Lattices, Chains, and Anti-Chains

Lattices

A Lattice is a special type of POSET. In a lattice, every pair of elements must have two things:

1. Least Upper Bound (LUB): The smallest element that is greater than or equal to both elements. (Also called Supremum or Join).

2. Greatest Lower Bound (GLB): The largest element that is less than or equal to both elements. (Also called Infimum or Meet).

If every possible pair of elements in the POSET has a unique LUB and GLB, the POSET qualifies as a Lattice.

Chains and Anti-Chains

• Chain: In a POSET, if every pair of elements can be compared to each other (i.e., either a <= b or b <= a), that subset is called a Chain. It represents a totally ordered set. In a Hasse diagram, a chain looks like a straight vertical line.

• Anti-Chain: If no two elements in a subset are related or comparable to each other, it is called an Anti-chain. In a Hasse diagram, these appear as nodes on the same horizontal level with no lines connecting them.

Transitive Closure and Warshall’s Algorithm

What is Transitive Closure?

If we have a relation R that is not transitive, we can make it transitive by adding the minimum necessary ordered pairs. The new, expanded relation is called the Transitive Closure of R. In graph theory, it helps answer the question: "Is there any path from node A to node B?"

Warshall’s Algorithm

Finding the transitive closure manually is slow for large datasets. Warshall’s algorithm is a highly efficient computational method used to find the transitive closure of a relation using boolean matrices.

Working of Warshall's Algorithm:

1. Start with the initial boolean matrix of the relation, let's call it W0.

2. The algorithm processes the matrix in 'n' steps (where n is the number of elements).

3. In each step 'k', it checks if a path exists between node 'i' and node 'j' by routing through an intermediate node 'k'.

4. The formula used is: W_k[i, j] = W_k-1[i, j] OR (W_k-1[i, k] AND W_k-1[k, j]).

5. After 'n' iterations, the final matrix W_n represents the transitive closure.

Hinglish Explanation: Warshall’s algorithm computer ko ye batata hai ki kya node A se node B tak koi direct ya indirect rasta hai. Ye ek-ek karke sabhi nodes ko intermediate (beech ka) point banakar check karta hai aur matrix ko update karta hai. Ye algorithm networks aur routing mein bahut kaam aata hai.

Introduction to Functions

A function is a special type of relation. Let A and B be two non-empty sets. A function 'f' from set A to set B is an assignment where exactly one element of set B is assigned to each element of set A.

• Domain: The set A (all possible input values).

• Codomain: The set B (the set containing all potential output values).

• Range: The actual set of output values produced by the function. The range is always a subset of the codomain.

Notation: f(a) = b. Here, 'b' is the image of 'a', and 'a' is the pre-image of 'b'.

Types of Functions

Depending on how elements are mapped from Domain to Codomain, functions are classified into three main types.

1. Injective Function (One-to-One)

A function is injective if every distinct element in the domain maps to a unique and distinct element in the codomain. No two different inputs can produce the same output.

• Condition: If f(x) = f(y), then x must be equal to y.

2. Surjective Function (Onto)

A function is surjective if every element in the codomain is mapped by at least one element in the domain. This means the Range is exactly equal to the Codomain. No element in the output set is left unmapped.

3. Bijective Function (One-to-One Correspondence)

A function is bijective if it is BOTH injective (one-to-one) and surjective (onto).

• Feature: Bijective functions establish a perfect pairing between set A and set B. Every input has a unique output, and every output has exactly one corresponding input.

Hinglish Explanation: Injective ka matlab hai har input ka apna alag output hona chahiye (no sharing). Surjective ka matlab hai output set (codomain) ka koi bhi element khali nahi chhutna chahiye. Aur jab ek function ye dono rules follow karta hai, toh use Bijective kehte hain.

Composition and Inverse of Functions

Composition of Functions

If we have two functions, f: A -> B and g: B -> C, we can combine them to form a new function that maps directly from A to C. This is called function composition, denoted by (g o f).

• Formula: (g o f)(x) = g(f(x)).

• Working: First, apply function 'f' to input 'x' to get an intermediate result. Then, use that result as the input for function 'g'.

Inverse of a Function

The inverse of a function 'f', denoted by f^-1, reverses the mapping. If f(a) = b, then f^-1(b) = a.

• Important Condition: A function can only have an inverse if it is Bijective. If it is not one-to-one, reversing it would assign multiple outputs to one input (which violates the definition of a function). If it is not onto, some inputs in the reverse function would have no output.

Recursive Functions and Applications in Algorithms

What is a Recursive Function?

In computer science and discrete math, a recursive function is a function that defines its values based on its previous values. Simply put, it is a function that calls itself to solve smaller instances of the same problem.

A well-defined recursive function must have two parts:

1. Base Condition (or Basis Step): The stopping point. It defines the value of the function for the initial input (usually 0 or 1) so the recursion does not run infinitely.

2. Recursive Step: The rule that computes the current value using one or more previous values.

Applications in Algorithms

Recursion is deeply embedded in algorithmic design.

• Factorial Function: n! = n * (n-1)!. The base case is 0! = 1. This is heavily used in counting and probability.

• Fibonacci Sequence: F(n) = F(n-1) + F(n-2). Base cases are F(0) = 0 and F(1) = 1. Used in dynamic programming and data structure analysis.

• Tree Traversals: Algorithms like searching through a Binary Search Tree (BST) use recursive functions to visit left and right child nodes naturally.

Hinglish Explanation: Recursion ek aisi technique hai jisme function apne aap ko tab tak call karta rehta hai jab tak ek final stopping point (base case) na aa jaye. Ye bade complex problems ko chhote aur aasan steps mein todne ka sabse best tarika hai.

Counting Functions and Growth of Functions

Counting Functions

Discrete mathematics often requires us to count how many functions can exist between two finite sets. Let Set A have 'm' elements and Set B have 'n' elements.

• Total Number of Functions: Since each of the 'm' elements in A can map to any of the 'n' elements in B, the total number of possible functions is n^m.

• Total Number of Injective Functions: To create a one-to-one function, the first element has 'n' choices, the second has 'n-1' choices, and so on. This is a permutation. The formula is P(n, m). Note: Injective functions are only possible if n >= m.

Growth of Functions

In algorithm analysis, it is essential to measure how the execution time or space requirements of a function increase as the input size grows. This is studied under the Growth of Functions.

• Big-O Notation (O): Represents the upper bound or worst-case scenario. It guarantees that the function will not grow faster than a certain rate.

• Big-Omega Notation (Ω): Represents the lower bound or best-case scenario.

• Big-Theta Notation (Θ): Represents the tight bound or average-case scenario.

Understanding function growth (like linear O(n), quadratic O(n^2), or exponential O(2^n)) is critical for optimizing computer code.

Summary and Key Takeaways

• Relations are subsets of a Cartesian product. Key properties include Reflexive, Symmetric, Transitive, and Antisymmetric.

• An Equivalence Relation partitions a set into distinct, non-overlapping equivalence classes.

• A POSET (Partial Order) is reflexive, antisymmetric, and transitive. It can be visually simplified using a Hasse Diagram.

• Warshall’s Algorithm is an efficient matrix-based method to compute the transitive closure of a relation.

• A Function is a strict relation where each input has exactly one output. They can be Injective (One-to-One), Surjective (Onto), or Bijective.

• Only Bijective functions can have an Inverse.

• Recursive Functions solve complex problems by breaking them down into base cases and recursive steps, widely used in algorithms like Fibonacci and tree traversals.

• Analyzing the Growth of Functions using Big-O notation is essential for evaluating algorithmic efficiency.

SEO Keywords Section

Search keywords related to this topic:

Discrete Mathematics Relations and Functions, Properties of Relations Reflexive Symmetric Transitive, Representation of Relations Matrices Digraphs, Equivalence Relations and Partitions, Partial Orderings POSET, How to draw Hasse Diagram, Lattices Chains and Anti-Chains, Transitive closure and Warshall algorithm, Types of Functions Injective Surjective Bijective, Composition and Inverse of Functions, Recursive Functions in Algorithms, Counting Functions formula, Growth of Functions Big-O notation, Computer Engineering Discrete Math notes, Diploma engineering mathematics basics.