Functions

Functions in Discrete Mathematics

In discrete mathematics, a function is a fundamental concept used to describe the relationship between two sets, where each element from the first set is associated with exactly one element from the second set. Functions are widely used in areas such as algorithms, number theory, computer science, and graph theory.

---

Definition of a Function

A function $f$ from set $A$ to set $B$, denoted by $f: A \to B$, is a rule that assigns each element $a \in A$ to exactly one element $b \in B$. In other words, for every $a \in A$, there exists a unique $b \in B$ such that $f(a) = b$.

• Domain: The set $A$ is called the domain of the function, which consists of all the possible inputs.
• Codomain: The set $B$ is called the codomain of the function, which contains all possible outputs (though not every element in the codomain has to be an output).
• Range: The range of the function is the set of all outputs $f(a)$ for $a \in A$. It is a subset of the codomain.

---

Types of Functions

Functions can be classified in various ways based on their properties. Some important types include:

1. Injective Function (One-to-One)

A function $f: A \to B$ is injective (or one-to-one) if every element in the domain $A$ maps to a distinct element in the codomain $B$. In other words, if $f(a_1) = f(a_2)$, then $a_1 = a_2$.

• Example: Let $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$, with the function $f(1) = a$, $f(2) = b$, and $f(3) = c$. This function is injective because each element in $A$ maps to a unique element in $B$.

2. Surjective Function (Onto)

A function $f: A \to B$ is surjective (or onto) if for every element $b \in B$, there exists at least one element $a \in A$ such that $f(a) = b$. In other words, the range of the function is equal to the entire codomain.

• Example: Let $A = \{1, 2\}$ and $B = \{a, b\}$, with the function $f(1) = a$ and $f(2) = b$. This function is surjective because every element of $B$ is covered by the function.

3. Bijective Function (One-to-One and Onto)

A function $f: A \to B$ is bijective if it is both injective (one-to-one) and surjective (onto). This means that each element in the domain maps to a distinct element in the codomain, and every element in the codomain is covered.

• Example: Let $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$, with the function $f(1) = a$, $f(2) = b$, and $f(3) = c$. This function is bijective because it is both injective and surjective.

---

Function Notation

Function notation is a way of representing the relationship between elements of the domain and the codomain.

• $f: A \to B$ means that $f$ is a function from set $A$ to set $B$.
• $f(a) = b$ means that the function $f$ maps the element $a$ in the domain $A$ to the element $b$ in the codomain $B$.

---

Operations on Functions

There are several important operations that can be performed on functions, such as composition and inverse functions.

1. Function Composition

Given two functions $f: A \to B$ and $g: B \to C$, the composition of $f$ and $g$, denoted $g \circ f$, is a function from $A$ to $C$ defined by:

$$(g \circ f)(a) = g(f(a))$$

In words, we first apply $f$ to an element $a \in A$ and then apply $g$ to the result.

• Example: If $f: \{1, 2, 3\} \to \{a, b, c\}$ and $g: \{a, b, c\} \to \{x, y, z\}$, with $f(1) = a$, $f(2) = b$, and $f(3) = c$, and $g(a) = x$, $g(b) = y$, and $g(c) = z$, then $g \circ f(1) = g(f(1)) = g(a) = x$.

2. Inverse Function

A function $f: A \to B$ has an inverse function, denoted $f^{-1}: B \to A$, if and only if $f$ is bijective. The inverse function reverses the mapping, so for every element $b \in B$, $f^{-1}(b) = a$ where $f(a) = b$.

• Example: If $f: A \to B$ is bijective, then $f^{-1}(f(a)) = a$ for all $a \in A$, and $f(f^{-1}(b)) = b$ for all $b \in B$.

---

Types of Functions Based on Structure

1. Identity Function

The identity function $I_A$ on a set $A$ is a function that maps every element of $A$ to itself. For all $a \in A$, $I_A(a) = a$.

• Example: If $A = \{1, 2, 3\}$, then the identity function $I_A$ is $I_A(1) = 1$, $I_A(2) = 2$, and $I_A(3) = 3$.

2. Constant Function

A constant function is a function where every element in the domain is mapped to the same element in the codomain. For all $a \in A$, $f(a) = c$, where $c$ is a fixed element in $B$.

• Example: If $A = \{1, 2, 3\}$ and $B = \{a, b\}$, and $f(1) = f(2) = f(3) = a$, then $f$ is a constant function.

3. Polynomial Function

A polynomial function is a function that can be expressed as $f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$, where $a_n, a_{n-1}, \dots, a_1, a_0$ are constants, and $n$ is a non-negative integer.

• Example: The function $f(x) = 3x^2 + 2x + 1$ is a polynomial function.

4. Piecewise Function

A piecewise function is a function defined by different expressions based on the input value. It is a combination of several functions, each of which applies to a specific part of the domain.

• Example: The function $f(x)$ defined as: $$f(x) = \begin{cases} x^2 & \text{if } x \geq 0 \\ -x & \text{if } x < 0 \end{cases}$$ is a piecewise function.

---

Conclusion

Functions are one of the most fundamental concepts in mathematics and computer science. They establish relationships between elements of sets and are essential for modeling and solving problems across many fields. Understanding the properties and operations of functions, such as injectivity, surjectivity, and composition, is crucial for designing algorithms, analyzing data, and understanding mathematical structures.