Relations (Recursions)

Relations and Recursions in Discrete Mathematics

In discrete mathematics, relations and recursions are key concepts that help describe and analyze relationships between elements within a set and how sequences or functions behave and evolve step by step. Let’s explore these two topics in detail.

---

Relations

Definition of a Relation

A relation is a way to express a relationship between elements of two sets. More formally, a relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$, meaning $R \subseteq A \times B$. This means that for every element $a \in A$ and $b \in B$, a relation $R$ relates $a$ to $b$ if and only if $(a, b) \in R$.

For example, if $A = \{1, 2, 3\}$ and $B = \{x, y, z\}$, a relation $R$ might be $R = \{(1, x), (2, y)\}$, meaning that element 1 from set $A$ is related to $x$ in set $B$, and element 2 is related to $y$.

Types of Relations

Relations have several important properties, which can be used to classify them:

1. Reflexive Relation: A relation $R$ on set $A$ is reflexive if every element in $A$ is related to itself. That is, for every $a \in A$, $(a, a) \in R$.

   • Example: If $A = \{1, 2, 3\}$, the relation $R = \{(1, 1), (2, 2), (3, 3)\}$ is reflexive.

2. Symmetric Relation: A relation $R$ is symmetric if whenever $(a, b) \in R$, it follows that $(b, a) \in R$.

   • Example: If $R = \{(1, 2), (2, 1)\}$, then $R$ is symmetric because $(1, 2) \in R$ and $(2, 1) \in R$.

3. Transitive Relation: A relation $R$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$, it follows that $(a, c) \in R$.

   • Example: If $R = \{(1, 2), (2, 3), (1, 3)\}$, then $R$ is transitive because $(1, 2)$ and $(2, 3)$ imply $(1, 3)$.

4. Antisymmetric Relation: A relation $R$ is antisymmetric if whenever $(a, b) \in R$ and $(b, a) \in R$, it must follow that $a = b$.

   • Example: If $R = \{(1, 2), (2, 1)\}$, then the relation is not antisymmetric because $(1, 2) \in R$ and $(2, 1) \in R$ but $1 \neq 2$.

Equivalence Relation

A relation that is reflexive, symmetric, and transitive is called an equivalence relation. Equivalence relations divide the set into equivalence classes, where elements within each class are considered "equivalent" to one another.

• Example: The congruence modulo relation is an equivalence relation on the set of integers. Two integers $a$ and $b$ are related if their difference is divisible by a fixed integer $n$, i.e., $a \equiv b \pmod{n}$.

Partial Order and Total Order

• Partial Order: A relation $R$ on a set $A$ is a partial order if it is reflexive, antisymmetric, and transitive. Not every pair of elements in $A$ is comparable in a partial order.

  • Example: The subset relation $\subseteq$ on the power set of a set is a partial order.

• Total Order: A relation $R$ on a set $A$ is a total order if it is a partial order and, for every pair of elements $a, b \in A$, either $a \leq b$ or $b \leq a$ holds.

  • Example: The relation $\leq$ on the set of integers is a total order because for any two integers $a$ and $b$, one of $a \leq b$ or $b \leq a$ must hold.

---

Recursions

Definition of Recursion

A recursion is a process where a function or a sequence is defined in terms of itself. In mathematics and computer science, recursions are used to define sequences, algorithms, and structures in a compact and efficient way.

A recursive definition typically includes two parts:

1. Base Case(s): Defines the initial values or conditions that terminate the recursion.
2. Recursive Step: Defines the relationship between the current case and previous cases (often the recursive step involves the same function or sequence applied to smaller instances).

Example of a Recursive Sequence

Consider the Fibonacci sequence, which is defined as:

$$F(0) = 0, \quad F(1) = 1$$ $$F(n) = F(n-1) + F(n-2) \quad \text{for} \quad n \geq 2$$

Here:

• The base cases are $F(0) = 0$ and $F(1) = 1$.
• The recursive step defines $F(n)$ as the sum of the two previous values, $F(n-1)$ and $F(n-2)$.

Calculation of Fibonacci Numbers:

$$F(2) = F(1) + F(0) = 1 + 0 = 1$$ $$F(3) = F(2) + F(1) = 1 + 1 = 2$$ $$F(4) = F(3) + F(2) = 2 + 1 = 3$$

And so on...

Recursive Functions in Algorithms

Many algorithms in computer science are defined recursively. For example, the merge sort algorithm is defined recursively as follows:

• Base case: If the list contains 0 or 1 elements, it is already sorted.
• Recursive step: Otherwise, divide the list into two halves, recursively sort each half, and then merge the two sorted halves.

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    middle = len(arr) // 2
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left)
    result.extend(right)
    return result

Recursion Trees

A recursion tree is a tree-like diagram that represents the recursive calls made by a recursive function. It is often used to visualize the time complexity of recursive algorithms.

Example: Recursive Call Tree for Fibonacci Sequence

For calculating $F(4)$, the recursive calls would look like this:

$$F(4) \rightarrow F(3) + F(2)$$ $$F(3) \rightarrow F(2) + F(1), \quad F(2) \rightarrow F(1) + F(0)$$

This process continues recursively, with overlapping subproblems, which is why a more efficient approach like dynamic programming (or memoization) can be used to store intermediate results and avoid redundant calculations.

---

Conclusion

• Relations are a fundamental concept used to describe relationships between elements in sets, with various types like reflexive, symmetric, transitive, and equivalence relations. They also provide ways to organize and order elements through partial or total orders.

• Recursions define processes or sequences in terms of themselves, allowing complex problems to be broken down into simpler subproblems. Recursive definitions are widely used in mathematics and computer science, especially for defining sequences, algorithms, and functions. Understanding both relations and recursions is key to solving problems in discrete mathematics and computer science.