MA5.101 - Discrete Structures | DS Lecture 14

Functions

Definition:

A binary function is defined by two sets say $X$ and $Y$ A binary relation $f$ from $X \rightarrow Y$ is called a function if each element in $X$ maps to exactly one element in $Y$.
Do note: every element in $X$ has to be mapped to an element.

• The set $X$ is the domain and the set $Y$ is the co-domain
• The image of $y \in Y$ of an element $x \in X$ is denoted by $y = f(x)$
• For aa function $f: X\rightarrow Y$ , if $y\in Y$ then the pre-image of $y$ is an element $x\in X$ for which $f(x) = y$
• The set of all elemenets in $Y$ which have atleast one pre-image is called the image of $f$ and is denoted by $Im(f)$

Partial Functions

A partial function $f: X \rightarrow Y$ is defined every element $x \in D$ ($D \subset X$) maps to one element in $Y$.
Do note that strictly speaking a Partial function is not a function.

Type of functions

One-to-one or injective function

• A function $f: X \rightarrow Y$ is 1-1 or injective if each element in co-domain is the image of at most one element in the the domain.
• In other words, $f: X \rightarrow Y$ is 1-1 if $a, b \in X$ such that $a \not= b \implies f(a) \not=f(b)$
• contrapositive (and therefore implied): $f(a) = f(b) \implies a = b$
• If a function is note one-to-one it is called many-one.

Onto function or surjective

• for $f: X \rightarrow Y$ , if each element of co-domain Y is the image of atleast one element in in $X$
• In other words $f: X \rightarrow Y$ is onto iff $Im(f) = Y$.

Bijective or one-one correspondence

• If a function is both injective and surjective

Theorem: If a function $f: X \rightarrow Y$ is injective, then $f: X \rightarrow Im(f)$ is a bijection.
Proof: The definition of surjection implies that the co-domain of a surjective function is equal to $Im(f)$. Thus $f: X \rightarrow Im(f)$ is surjective (i). Given that $f: X \rightarrow Y$ is injective $\implies$ every element $y \in Y$ has at most one pre-image. $z \in Im(f) \implies z \in Y, \forall z \in Im(f)$ as $Im(f)\subseteq Y$ thus every element in $Im(f)$ has at most one pre-image in $X$ this $f: X \rightarrow Im(f)$ is also injective (ii) By (i) and (ii) the function is bijective

Theorem: If a function $f: X \rightarrow Y$ is injective, and $X, Y$ are finite sets of the same size then $f: X \rightarrow Y$ is a bijection.

Let $f: X \rightarrow Y$ is a function with $|X| = m, |Y| = n$ then:

• Total number of functions from $X \rightarrow Y$ is $n^m$ reasoning: every element in $X$ needs to have an image in $Y$ and thus has $n$ choices thus $n^m$
• The total number of injective functions $X \rightarrow Y$ with $m \leq n$ is ${n \choose m} m!$ . reasoning: we choose m eleents in $Y$ and then all possible rearrangements of these will yield the total number of mappings.
• The total number of surjective functions from $X \rightarrow Y$ with $m \geq n$ is $n! S(m, n)$ where S refers to the Stirling number of second kind resoning: Stirling number of second kind gives you the number of ways to partition a particular set of $m$ elements into $n$ non-empty sets. Thus what we’re doing is partitioning the $X$ into $n$ subsets, and then we can associate each sub-set with an element of $Y$ (a subset for each element). For each partition there are $n!$ possible mappings.
• Total number of bijective functions from $X \rightarrow Y$ with $m = n$ is $n!$

Inverse functions

A function is bijective $f: X \rightarrow Y$ then we define $g: Y \rightarrow X$ such that $g(y) = x \forall y \in Y, x\in X$ The $g$ is the inverse of $f$

One-way function

A function $f: X \rightarrow Y$ is called a one-way function if $f(x)$ is easy to compute $\forall x \in X$ but it is generally infeasible to compute $x \in X | f(x) = y, y \in Y$ Note: emphasis has been given to “generally” because there may be some values $y \in Y$ for which is it is easy to find $x \in X$ such that $y = f(x)$ Such a function may or may not be bijective.

Trap-door one-way function

Iti s a one-way function $f: X \rightarrow Y$ with the additional property that given some extra information it becomes feasible to get $x \in X$ such that $f(x) = y, y \in Im(f)$

Involutions

Definition: let $f$ be a bijection on a set $S$ this $f: S \rightarrow S$ then the function $f$ is set to be an involution iff $f = f^-1$ or equivalently $f(f(x)) = x$

Composition of function

Definition: Let $f: A \rightarrow B$ and $g: B \rightarrow C$ be two functions. The composition of $f$ by $g$ be the function $(g \circ f)(a) = g[f(a)] \forall a \in A$
$g \circ f: A \rightarrow C$
Such a composition can also be described for $f: A \rightarrow B$ , $g: C \rightarrow D$ if $C \subseteq B$
Lemma: Let $f: A \rightarrow B$ , $g: B \rightarrow C$ and $h: C \rightarrow D$ then whenever the compositions involved are defined we can say: \((f \circ g) \circ h = f \circ (g \circ h)\) associacitivity

Identity function

The identity function $I_s: S \rightarrow S$ such that $I_s(x) = x \forall x \in S$ . This can also be represented by $1_s$
Theorem: Let $f: S \rightarrow T$ and $1_s$ and $1_t$ then: \((f \circ 1_s) = (1_t \circ f) = f\)

Proof:
Given:
\(1_s: S \rightarrow S | 1_S(s) = s \forall s \in S \\ 1_t: T \rightarrow T | 1_T(t) = t \forall t \in T \\ \text{Therefore}, \\ (f \circ 1_S): S \rightarrow T\\ (f \circ 1_S)(s) = f(1_S(s)) = f(s) \forall s \in S [\textrm{By definition of } 1_s] \\ Similarly, \\ (1_T \circ f): S \rightarrow T \\ (1_T \circ f)(t) = i_T(f(s)) = f(s) \forall s \in S [\textrm{By definition of } 1_t] \\ \textrm{thus, }\\ (f \circ 1_S) = (1_T \circ f) = f\)

Characteristic function

Any set $S|S \subseteq U$ can be associated with a characteristic function $e_S$ such that \(e_S: U \rightarrow {0, 1} \\ e_s(x) = \begin{array}{cc} \Bigg\{ & \begin{array}{cc} 1 & x \in S \\ 0 & x \notin S \end{array} \end{array}\)

Inverses of functions

Let $f: S \rightarrow T$ and $g: T \rightarrow S$ be two mappings. if $g \circ f = 1_S$ then $g$ is the left inverse of $f$ if $f \circ g = 1_T$ then $g$ is the right inverse of $f$

A function which has a two-sided inverse is called invertible Theorem:

• A function is left invertible iff it is injective.
• A function is right invertible iff it is surjective.
• And thus a function is invertible iff it is bijective Corollary
• A function $f: A \rightarrow B$ is bijective iff it has both: a left inverse and a right inverse. Corollary
• If $g \circ f$ is defined, and both f and g have left inverse then $g \circ f$ has a left inverse.

Doubt: can a bijective function have a left inverse which is different from it’s right inverse?

Idempotent functions

Let for all $f: S \rightarrow S$ $f^2 = f \circ f$ if $f^2 = f$ then $f$ is said to be idempotent or a projection.

Theorems:
For the following function definitions:
\(f: A \rightarrow B \\ g: B \rightarrow C \\ g \circ f: A \rightarrow c\)

1. If $f$ and $g$ are both injective then $g \circ f$ and are injective as well
2. If $f$ and $g$ are both surjective then $g \circ f$ and are surjective as well.
3. and therefore if $f$ and $g$ are bijective then so are $f \circ g$ and $g \circ f$
4. and also $(f \circ g)^{-1} = f^{-1} \circ g^{-1}$
5. if $g \circ f$ is injective, $f$ is injective
6. if $g \circ f$ is surjective, $g$ is surjective too.

Proofs
\(\text{for all proofs that are to follow: } \\ f: A \rightarrow B \\ g: B \rightarrow C \\ \text{thus} \\ g \circ f: A \rightarrow C\)

for (1.) \(\text{Given } f \text{ and } g \text{ are both injective} \\ f(x_1) = f(x_2) \implies x_1 = x_2, \text{ for arbitrary } x_1 \text{ and } x_2 \\ g(x_1) = g(x_2) \implies x_1 = x_2, \text{ for arbitrary } x_1 \text{ and } x_2 \\ \text{let} g \circ f (x_1) = g \circ f(x_2) \\ \implies g(f(x_1)) = g(f(x_2)) \\ \implies g(x_1) = g(x_2) \text{ as f is injective } \\ \implies x_1 = x_2 \text{ as g is injective} \\\)

Theorem: If $X$ and $Y$ are two non-empty sets and $f$ is a mapping of $X$ into $Y$. Then, for any sub-sets $A, B \subseteq X$ then: $f(A \cup B) = f(A) \cup f(B)$ Proof RTP:

1. $f(A \cup B) \subseteq f(A) \cup f(B)$
2. $f(A) \cup f(B) \subseteq f(A \cup B)$

Let $y$ be an arbitrary element such that $y \in f(A \cup B)$

$\text{thus proved } f(A \cup B) \subseteq f(A) \cup f(B)…..(\text{i})$

$\text{Let } y \in f(A) \cup f(B) \text{ be an arbitrary variable}$

Thus, $f(A) \cup f(B) \subseteq f(A \cup B)……..(\text{ii})$

$\text{ by i and ii, } f(A) \cup f(B) = f(A \cup B)$

Theorem
If $X$ and $Y$ are two non-empty sets and $f$ be a bijective function such that $f: X \rightarrow Y$ then for $A, B \subseteq Y$ $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$

Theorem
if $f: X \rightarrow Y$ be a mapping anf $A, B \subseteq X$ then $f(A \cap B) \subseteq f(A) \cup f(B)$
Note: The equality holds in the case of $f$ being a bijection