[Discrete Mathematics] lecture 4 - Functions

Overview

---

This lecture covers the basics of functions in discrete mathematics, defining them as relations where each input has a unique output. Key terms like domain, codomain, and range are introduced. It explores composite functions, operators, restrictions, and extensions.

Different types of functions are discussed: injective (one-to-one), surjective (onto), bijective (both), along with their properties and behavior under composition. The lecture also explains inverse functions, including left and right inverses, and ends with the concept of permutations as ordered arrangements of elements.

Introduction to Functions

---

Definition 1 (fuction)
Let $A$ and $B$ be two sets. A relation $f$ from $A$ to $B$ is called a fuction if $\forall x \in A$, there is a unique $y \in B$ such that $\left<x,y\right> \in f$.

It could be also written as $f: A \to B$ and $\left<x,y\right> \in f$ as $f(x) = y$.

Terminology: $f: A \to B$ and $f(a) = b$

• domain: $A$
• codomain: $B$
• image: $b$ is the image of $a$ under $f$
• preimage: $a$ is the preimage of $b$ under $f$
• range: the set of all outputs ($R = \left\{b | (a,b) \in f : \text{for some} : a\right\}$)

Definition 2 (image)
Let $f: A \to B$ be a function. The image of $f$ is the set $\left\{f(x) | x \in A\right\} $.

Operators

Definition 3 (n-ary operator)
An n-ary operator is a function $O_n: S^n \to S$ where $S^n = S \times S \times \cdots \times S$ ($n$ times).

Definition 4
Given any binary operator $\bullet: B\times B \to B$ and two functions $f: A \to B$ and $g: A \to B$, the function $(f \bullet g) : A \to B$, is defined to be such that $\forall x \in A$, $(f \bullet g)(x) = f(x) \bullet g(x)$.

Think of this definition as a generalization of operators. For example, if $f$ and $g$ are both functions from $A$ to $\mathbb{R}$, then $(f + g)(x) = f(x) + g(x)$ is a function from $A$ to $\mathbb{R}$.
Recall that we can add $f=2x$ and $g=3x$ to get $f+g=5x$.
What we are doing is just generalizing the notation with the idea of a operator acting on two functions. (Still, we are not adding the functions, but the values of the functions at a point $x$.)

Restriction and Extension

Definition 5 (composite)
Let $f: A \to B$ and $g: B \to C$ be two functions. The composite function $g \circ f: A \to C$ is defined to be such that $\forall x \in A$, $(g \circ f)(x) = g(f(x))$.

Theorem 1
Composite functions are associative but not commutative.

Definition 6 (restriction and extension)
Let $f: X \to Y$ be a function and $A \subseteq X$.
The restriction of $f$ to $A$ is the function is $f/A = f \cap (A \times Y)$.
If $g$ is a restriction of $f$, then $f$ is an extension of $g$.

Type of Functions

Definition 7 (partial function)
Let $X$ and $Y$ be two sets. A partial function from $X$ to $Y$ is a relation $f \subseteq X \times Y$ such that $f$ is any function from $X'$ to $Y$ where $X' \subseteq X$. The subset $X'$ is called the domain of definition of $f$.

Definition 8 (injective function)
A function $f: A \to B$ is called injective if $\forall a_1, a_2 \in A$, $f(a_1) = f(a_2) \implies a_1 = a_2$.
Also called one-to-one function.

Definition 9 (surjective function)
A function $f: A \to B$ is called surjective if $\forall b \in B$, $\exists a \in A$ such that $f(a) = b$.
Also called onto function.

Definition 10 (bijective function)
A function $f: A \to B$ is called bijective if it is both injective and surjective.

Theorem 2
Let $f \circ g: A \to C$ be a composite function where $g: A \to B$ and $f: B \to C$.
‣ If $f$ and $g$ are surjective, then $f \circ g$ is surjective.
‣ If $f$ and $g$ are injective, then $f \circ g$ is injective.
‣ If $f$ and $g$ are bijective, then $f \circ g$ is bijective.
‣ If $f \circ g$ is surjective, then $f$ is surjective.
‣ If $f \circ g$ is injective, then $g$ is injective.
‣ If $f \circ g$ is bijective, then $f$ is surjective and $g$ is injective.

Definition 11 (constant function)
A function $f: X \to Y$ is called a constant function if there exists a $y \in Y$ such that $\forall x \in X$, $f(x) = y$.

Definition 12 (identity function)
The identity function on a set $X$ is the function $I_X: X \to X$ such that $\forall x \in X$, $I_X(x) = x$.

Definition 13 (inverse function)
Let $f: A \to B$ be a bijective function. The inverse function is the inverse relation of $f$, denoted as $f^{-1}$

Theorem 3
Let $f: X \to Y$ be a bijective function. Then $f^{-1}: Y \to X$ is a bijective function.
If $f$ is bijective, then $(f^{-1})^{-1} = f$

Definition 14 (left/right inverse)
Let $h: A \to B$ and $g: B \to A$ be a function. If $g \circ h = I_A$, then $g$ is a left inverse of $h$ and $h$ is a right inverse of $g$.

Theorem 4
Let $f: A \to B$ with $A \neq \empty$
‣ $f$ has a left inverse if and only if $f$ is injective.
‣ $f$ has a right inverse if and only if $f$ is surjective.
‣ $f$ has a left and a right inverse if and only if $f$ is bijective.
‣ If $f$ is bijective, then the left and the right inverse are equal.

Let's take a look at the proof of the theorem 4 but only the first statement.

($f$ has a left inverse if and only if $f$ is injective.)
(only if $\Rightarrow$) Let $g: B \rightarrow A$ be a left inverse of $f$. What we need to show is

$$(g \circ f = I_A) \wedge (f(x_1) = f(x_2)) \implies (x_1 = x_2)$$

Suppose $y = f(x_1) = f(x_2)$. Using $g \circ f = I_A$, we have $g(y) = g(f(x_1)) = I_A(x_1) = x_1$ and $g(y) = g(f(x_2)) = I_A(x_2) = x_2$. So we have $x_1 = x_2$.
(Note: To be more rigorous, you have to introduce $u$, $v$ to represent the intermediate value of the composite function. The definition of the function will tell you that $u=v=y$.)

(if $\Rightarrow$) We need to show that left inverse $g$ exists if $f$ is injective.
It could be shown directly by constructing a function $g$.
Let $f: A \to B$. For any $y \in B$, it is either $y \in f(A)$ or $y \notin f(A)$. So construct $y$ as follows:

$$g(y) =\begin{cases}x & \text{if} : y = f(x) : \text{for some} : x \in A \\ z & \text{if} : y \notin f(A) : \text{for some} : z \in A \end{cases}$$

Since injectivity gives the uniqueness to the pre-image of $y \in f(A)$, $g$ and $g \circ f$ are valid functions
Then $\forall a \in A$, $g(f(a)) = a$ and thus $g \circ f = I_A$ where g is a left inverse of $f$ $\blacksquare $

Definition 15 (permutation)
A permutation of a set $A$ is an ordered arrangement of the elements of $A$