Relations and Functions

Relations and Functions

In Discrete Structures, relations and functions are fundamental concepts used to describe how elements from one set are related to elements in another set (or the same set). These concepts are widely used in mathematics, computer science, and logic, particularly for modeling systems, algorithms, and databases.

1. Relations

A relation is a way to describe a connection or association between elements of two sets. It generalizes the concept of a function but is more flexible.

Definition of a Relation:

A relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product $A \times B$. This means that each relation $R$ consists of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. If $(a, b) \in R$, we say that $a$ is related to $b$ under $R$, and we write $a R b$.

• Notation: $a R b$ means that $a$ is related to $b$.
• Example: Consider the set $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$. A relation $R$ from $A$ to $B$ could be: $$R = \{(1, a), (2, b), (3, c)\}$$ This means that element $1$ in set $A$ is related to $a$ in set $B$, element $2$ in $A$ is related to $b$ in $B$, and so on.

Types of Relations:

Relations can have additional properties, such as:

• Reflexive: A relation $R$ on a set $A$ is reflexive if, for every element $a \in A$, $a R a$. In other words, each element is related to itself.

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

• Symmetric: A relation $R$ on a set $A$ is symmetric if, for all $a, b \in A$, whenever $a R b$, then $b R a$.

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

• Transitive: A relation $R$ on a set $A$ is transitive if, for all $a, b, c \in A$, whenever $a R b$ and $b R c$, then $a R c$.

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

• Anti-symmetric: A relation $R$ on a set $A$ is anti-symmetric if, for all $a, b \in A$, whenever $a R b$ and $b R a$, then $a = b$.

  • Example: $R = \{(1, 2), (2, 1)\}$ is not anti-symmetric because $1 \neq 2$, but $(1, 2)$ and $(2, 1)$ are in the relation. On the other hand, the relation $\{(1, 2), (2, 2)\}$ is anti-symmetric.

• Equivalence Relation: A relation that is reflexive, symmetric, and transitive is called an equivalence relation. An example of an equivalence relation is the "equals" relation on integers, where $a \equiv b$ modulo $n$.

• Partial Order: A relation that is reflexive, transitive, and anti-symmetric is a partial order. An example of a partial order is the subset relation on sets, $\subseteq$, where $A \subseteq B$ means $A$ is a subset of $B$.

2. Functions

A function is a special type of relation where each element in the domain (set $A$) is related to exactly one element in the codomain (set $B$).

Definition of a Function:

A function $f$ from a set $A$ to a set $B$ is a relation where each element $a \in A$ is associated with a unique element $b \in B$. This is written as:

If $f(a) = b$, then $a$ is mapped to $b$ under the function $f$.

• Notation: The notation $f(a) = b$ means that $f$ maps $a$ from set $A$ to $b$ in set $B$.
• Example: Let $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$, and define the function $f$ as: $$f = \{(1, a), (2, b), (3, c)\}$$ This means that $f(1) = a$, $f(2) = b$, and $f(3) = c$.

Types of Functions:

• Injective (One-to-One): A function $f: A \to B$ is injective (or one-to-one) if different elements in $A$ map to different elements in $B$. In other words, if $f(a_1) = f(a_2)$, then $a_1 = a_2$.

  • Example: The function $f(x) = 2x$ for $x \in \{1, 2, 3\}$ is injective because each $x$ maps to a unique value in the codomain.

• Surjective (Onto): A function $f: A \to B$ is surjective (or onto) if every element in $B$ is mapped to by at least one element in $A$. In other words, for every $b \in B$, there exists at least one $a \in A$ such that $f(a) = b$.

  • Example: The function $f(x) = x^2$ for $x \in \{1, 2, 3\}$ is surjective if the codomain is $\{1, 4, 9\}$.

• Bijective (One-to-One and Onto): A function $f: A \to B$ is bijective if it is both injective and surjective. This means each element in $A$ maps to a unique element in $B$, and every element in $B$ is mapped to by exactly one element in $A$.

  • Example: The function $f(x) = x + 1$ for $x \in \{1, 2, 3\}$ is bijective if the codomain is $\{2, 3, 4\}$.

• Identity Function: The identity function on a set $A$, denoted as $id_A$, is a function that maps each element of $A$ to itself:

  $$id_A(a) = a \quad \text{for all } a \in A$$

• Constant Function: A function is constant if all elements in the domain map to the same element in the codomain. For example, $f(x) = 5$ for all $x \in A$ is a constant function.

Function Composition:

If $f: A \to B$ and $g: B \to C$ are functions, their composition $g \circ f$ is defined as:

This means we first apply $f$, then apply $g$ to the result of $f$.

3. Relations and Functions in Computer Science

• Databases: Relations are fundamental to relational databases, where tables are used to represent sets, and rows in a table represent ordered pairs (tuples) that show relationships between different data elements.
• Computer Algorithms: Functions are used extensively in algorithms to define operations such as sorting, searching, and mapping.
• Programming: Functions are the building blocks of programs, allowing inputs to be mapped to outputs, and are essential for modularity, recursion, and lambda calculus.

Conclusion

Relations and functions