Unit 4: Relations and Functions

Introduction to Relations and Functions

In the study of mathematics and computer science, relations and functions are fundamental concepts that describe the associations between elements of sets. These concepts are crucial for structuring data, solving problems, and understanding connections between various mathematical objects. Additionally, recurrence relations provide a powerful method for defining sequences and solving problems that exhibit a recursive nature. This unit delves into properties of relations, different types of functions, and their applications, with a specific focus on recurrence relations and their role in problem-solving.

Relations

Definition of a Relation

A relation is a subset of a Cartesian product of two sets. If $A$ and $B$ are sets, a relation $R$ from $A$ to $B$ is a subset of the Cartesian product $A \times B$ . For instance, if $A = \{1, 2\}$ and $B = \{a, b\}$ , the relation $R = \{(1, a), (2, b)\}$ defines a connection between the elements of $A$ and $B$ .

Properties of Binary Relations

Binary relations exhibit several key properties, which help classify them and understand their structure. Some of the important properties of binary relations include:

Reflexive: A relation $R$ on a set $A$ is reflexive if every element is related to itself. Formally, $\forall a \in A, (a, a) \in R$ . For example, the relation "is equal to" is reflexive since every element is equal to itself.
Symmetric: A relation $R$ is symmetric if for every $(a, b) \in R$ , $(b, a) \in R$ . An example of a symmetric relation is "is a sibling of," where if $a$ is a sibling of $b$ , then $b$ is a sibling of $a$ .
Transitive: A relation $R$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$ , then $(a, c) \in R$ . An example of a transitive relation is "is an ancestor of," where if $a$ is an ancestor of $b$ , and $b$ is an ancestor of $c$ , then $a$ is an ancestor of $c$ .
Antisymmetric: A relation $R$ is antisymmetric if for all $(a, b) \in R$ and $(b, a) \in R$ , we must have $a = b$ . For example, "less than or equal to" ( $\leq$ ) is antisymmetric since if $a \leq b$ and $b \leq a$ , then $a = b$ .

Closure of Relations

The closure of a relation refers to the process of extending a relation to include missing elements so that it satisfies certain properties. For instance, the reflexive closure of a relation $R$ adds all pairs $(a, a)$ to $R$ for every element $a$ in the set.

Reflexive closure: Adds the pairs necessary to make a relation reflexive.
Symmetric closure: Adds pairs to make a relation symmetric.
Transitive closure: Adds pairs to make a relation transitive.

Warshall’s Algorithm

Warshall’s algorithm is a method used to compute the transitive closure of a binary relation. Given a relation represented as a matrix, the algorithm identifies all the indirect connections between elements and ensures that the relation satisfies transitivity. This algorithm is particularly useful in graph theory, where the transitive closure can represent all possible paths between vertices.

The algorithm works by iterating over each pair of vertices and checking if an intermediate vertex can provide a path between them, updating the matrix accordingly.

Equivalence Relations

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations are used to partition sets into disjoint subsets, called equivalence classes, where all the elements in an equivalence class are related to each other.

For example, consider the set of all integers with the relation "congruent modulo $n$ ." This relation is reflexive, symmetric, and transitive, and it partitions the set of integers into equivalence classes based on their remainders when divided by $n$ .

Partitions

A partition of a set is a division of the set into non-overlapping, non-empty subsets, such that the union of these subsets is equal to the original set. Each equivalence relation induces a partition, and conversely, each partition defines an equivalence relation. For example, the set of natural numbers can be partitioned into even and odd numbers, which forms two equivalence classes under the relation "has the same parity."

Partial Ordering Relations

A partial ordering is a relation that is reflexive, antisymmetric, and transitive. Unlike a total ordering, where every pair of elements is comparable, in a partial ordering, some pairs may not be related. For example, the subset relation $\subseteq$ on sets is a partial ordering because not every pair of sets is related.

Lattices

A lattice is a partially ordered set where every pair of elements has a least upper bound (supremum) and a greatest lower bound (infimum). Lattices are important in various branches of mathematics and computer science, including algebra and formal logic. In lattice theory, these bounds are referred to as the join (supremum) and meet (infimum).

Chains and Antichains

In a partially ordered set, a chain is a subset in which every pair of elements is comparable. Conversely, an antichain is a subset where no pair of elements is comparable. Chains represent sequences of elements that follow the ordering relation, while antichains represent elements that are independent of each other.

Functions

Definition of a Function

A function is a special kind of relation that maps each element in one set, called the domain, to exactly one element in another set, called the codomain. Formally, a function $f: A \rightarrow B$ is defined as a relation where for every $a \in A$ , there is exactly one $b \in B$ such that $(a, b) \in f$ .

Composition of Functions

The composition of two functions $f: A \rightarrow B$ and $g: B \rightarrow C$ is a function that maps elements of $A$ to elements of $C$ . The composition is denoted as $(g \circ f)(a) = g(f(a))$ . Function composition is associative, meaning $(h \circ (g \circ f)) = ((h \circ g) \circ f)$ .

Invertible Functions

A function $f: A \rightarrow B$ is invertible if there exists a function $g: B \rightarrow A$ such that $g(f(a)) = a$ for all $a \in A$ and $f(g(b)) = b$ for all $b \in B$ . Invertible functions are also called bijective functions because they are both injective (one-to-one) and surjective (onto).

Pigeonhole Principle

The Pigeonhole Principle states that if $n$ items are placed into $m$ containers, where $n > m$ , then at least one container must contain more than one item. This principle is often used in combinatorics and computer science to prove the existence of solutions or demonstrate that certain constraints cannot be satisfied.

For example, if you have 11 socks and 10 drawers, at least one drawer must contain more than one sock.

Discrete Numeric Functions

Discrete numeric functions are functions that map integers to integers. These functions arise in many areas of computer science and mathematics, particularly in the analysis of algorithms and recurrence relations.

Recurrence Relations

Recurrence Relation

A recurrence relation defines a sequence in terms of previous values in the sequence. It provides a way to describe sequences that evolve based on their earlier values. Recurrence relations are widely used in algorithm analysis, particularly for recursive algorithms.

For example, the Fibonacci sequence is defined by the recurrence relation:

F(n) = F(n-1) + F(n-2), \text{ with } F(0) = 0 \text{ and } F(1) = 1.

Linear Recurrence Relations with Constant Coefficients

A linear recurrence relation is a recurrence relation in which each term is a linear combination of previous terms with constant coefficients. For example, the general form of a linear recurrence relation is:

a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}.

The Fibonacci sequence is an example of a second-order linear recurrence relation with constant coefficients.

Total Solutions

The total solution of a recurrence relation includes both the homogeneous solution and the particular solution. The homogeneous solution solves the corresponding homogeneous recurrence relation, where all terms on the right-hand side are zero, while the particular solution solves the non-homogeneous recurrence relation.

Applications of Relations and Functions

Relations and functions are critical in various fields, including:

Graph theory: Relations are used to represent edges between vertices in a graph, while functions can describe paths, flows, and other properties of graphs.
Database theory: Relations form the basis of relational databases, where data is organized into tables (relations) with functional dependencies between fields.
Algorithms: Recurrence relations are

used to analyze the time complexity of recursive algorithms and dynamic programming problems.

Unit-03 Unit-05