# Functions

## Contents

# 1.4. Functions#

(Function)

A *partial function* (or simply *function*)
from a set \(A\) to a set \(B\), in symbols \(f : A \to B\) (or \(A \xrightarrow{f} B\)
or \(x \mapsto f(x)\)) is a specific *rule* that assigns
a *unique* element \(y \in B\)
to an element \(x \in A\).

The rule need not be defined for every element in \(A\).

Note

Following [17],
our definition of functions is somewhat different from the
traditional definition. In particular, we don’t require that
\(f\) maps *each* element of \(A\) to an element of \(B\). It may
map only some elements of \(A\) to \(B\).

See also : total function below.

(Function value or image)

If \(f\) maps an element \(x \in A\) to an element \(y \in B\),
We say that the element \(y\) is the *value* of the function \(f\)
at \(x\) (or the *image* of \(x\) under \(f\))
and denote as \(f(x)\), that is, \(y = f(x)\).
We also say that \(f\) *attains* or *assumes* the value \(y\) at \(x\).
We also sometimes say that \(y\) is the *output* of \(f\) when the *input* is \(x\).

(Domain of a function)

For a function \(f: A \to B\) the *domain* of the
function is the subset of \(A\) for which the function
is defined. It is denoted by \(\dom f\).

(Total function)

A function \(f : A \to B\) is called a *total function* if \(\dom f = A\).

The normal set-theoretic definition of a function coincides with the
definition of *total function* above.

(Range of a function)

The set \(\{y \in B \ST \exists \; x \in A \text{ such that } y = f(x)\}\)
is called the *range* of \(f\) denoted by \(\range f\).

In other words, the set of values *attained* by \(f\) is called
its range.

The domain is a subset of \(A\) and the range is a subset of \(B\).

(Equality of functions)

Two functions \(f : A \to B\) and \(g : A \to B\) are said to be *equal*,
in symbols \(f = g\) if \(\dom f = \dom g\) and
\(f(x) = g(x) \quad \forall x \in \dom f\).

In words, they map the same elements of \(A\) to same elements of \(B\).

(Surjective function)

A function \(f : A \to B\) is called *onto* or *surjective* if \(\range f\) is
all of \(B\). i.e. for every \(y \in B\), there exists (at least one) \(x \in A\) such that
\( y = f(x)\).

(Injective function)

A function \(f : A \to B\) is called *one-one* or *injective* if \(x_1 \neq x_2 \implies f(x_1) \neq f(x_2)\).

(Bijective function)

A *total* function \(f : A \to B\) is called *one-one onto* or *bijective*
if it is injective as well as surjective.

For a bijective function \(\dom f = A\), \(\range f = B\), the elements of \(A\) and \(B\) are in one-to-one mapping.

(Square root)

Let \(f: \RR \to \RR\) be defined as:

\(\dom f = [0, \infty)\). \(\range f = [0, \infty)\).

\(f\) is partial and injective. It is neither surjective nor bijective.

(Logarithm)

Let \(f: \RR \to \RR\) be defined as:

\(\dom f = (0, \infty)\). \(\range f = (-\infty, \infty) = \RR\).

\(f\) is partial, injective and surjective (but not bijective).

(Exponential)

Let \(f: \RR \to \RR\) be defined as:

\(\dom f = (-\infty, \infty) = \RR\). \(\range f = (0, \infty) = \RR\).

\(f\) is total and injective but not surjective.

(Extended value extension of exponential)

Let \(f: \RR \cup \{-\infty, \infty \} \to \RR \cup \{-\infty, \infty \}\) be defined as:

\(\dom f = [-\infty, \infty]\). \(\range f = [0, \infty] = \RR\).

\(f\) is total and injective but not surjective.

(Dirichlet’s unruly indicator function for rational numbers)

Let \(g : \RR \to \RR\) be defined as:

\(\dom g = \RR\), \(\range g = \){0, 1 }$.

(Absolute value function)

The domain is \(\RR\) and the range is \(\RR_+ = [0, \infty)\).

\(f\) is total. It is not injective. It is not surjective.

(Logarithm of the determinant)

The set of \(n \times n\) real symmetric matrices is denoted by \(\SS^n\). The set of positive semidefinite symmetric matrices is denoted by \(\SS^n_+\). The set of positive definite symmetric matrices is denoted by \(\SS^n_{++}\).

Consider the function \(f : \SS^n \to \RR\) given by

The domain of the function is \(\dom f = \SS^n_{++}\). The function is not defined for matrices which are not positive definite.

In summary, for a function \(f : A \to B\):

If \(\dom f = A\) then, the function is total.

If \(\range f = B\) then, the function is surjective.

If \(f(x_1) = f(x_2) \implies x_1 = x_2\), then the function is injective.

If \(f\) is total, injective and surjective, then it is bijective.

## 1.4.1. Image under a function#

Let \(f : X \to Y\) be a (partial) function.

(Image of a set under a function)

If \(A \subseteq X\), then *image* of \(A\) under \(f\)
denoted as \(f(A)\) (a subset of \(Y\)) is defined by

Note that the definition is valid even if some elements of the subset \(A\) may not belong to \(\dom f\).

(Inverse image )

If \(B\) is a subset of \(Y\) then the *inverse image* \(f^{-1}(B)\) of \(B\) under \(f\)
is the subset of \(X\) defined by

If \(B \cap \range f = \EmptySet\) then \(f^{-1}(B) = \EmptySet\).

Let \(\{A_i\}_{i \in I}\) be a family of subsets of \(X\). Let \(\{B_i\}_{i \in I}\) be a family of subsets of \(Y\).

Then, the following results hold:

Image of the union of \(A_i\) is the union of the images of \(A_i\).

Image of the intersection of \(A_i\) is a subset of the intersection of the images of \(A_i\).

Inverse image of the union of \(B_i\) is the union of the inverse images of \(B_i\).

Inverse image of the intersection of \(B_i\) is the intersection of the inverse images of \(B_i\).

Let \(B \subseteq Y\). Inverse image of complement of \(B\) (w.r.t. \(Y\)) is the complement of the inverse image of \(B\) w.r.t. the domain of \(f\).

## 1.4.2. Function Composition#

(Composition)

Given two functions \(f : X \to Y\) and \(g : Y \to Z\), their *composition*
\(g \circ f\) is the function \(g \circ f : X \to Z\) defined by

The domain of the composition may be smaller than the domain of \(f\) as \(g\) may not be defined for every \(y\) in \(\range f\).

Given two one-one functions \(f : X \to Y\) and \(g : Y \to Z\), their composition \(g \circ f\) is one-one.

Proof. Let \(x_1, x_2 \in \dom g \circ f\). We need to show that \(g(f(x_1)) = g(f(x_2)) \implies x_1 = x_2\). Since \(g\) is one-one, hence

Further, since \(f\) is one-one, hence

Given two onto functions \(f : X \to Y\) and \(g : Y \to Z\), their composition \(g \circ f\) is onto.

Proof. Let \(z \in Z\). We need to show that there exists \(x \in X\) such that \(g(f(x)) = z\). Since \(g\) is on-to, hence for every \(z \in Z\), there exists \(y \in Y\) such that \(z = g(y)\). Further, since \(f\) is onto, for every \(y \in Y\), there exists \(x \in X\) such that \(y = f(x)\). Combining the two, for every \(z \in Z\), there exists \(x \in X\) such that \(z = g(f(x))\).

Given two one-one onto functions \(f : X \to Y\) and \(g : Y \to Z\), their composition \(g \circ f\) is one-one onto.

Proof. This is a direct result of combining Theorem 1.1 and Theorem 1.2.

Given two bijective (total) functions \(f : X \to Y\) and \(g : Y \to Z\), their composition \(g \circ f\) is bijective.

(Composition of total functions)

Given two total functions
\(f : X \to Y\) and \(g : Y \to Z\), their *composition*
\(g \circ f\) is the function \(g \circ f : X \to Z\) defined by

Since \(\dom f = X\) and \(\dom g = Y\), hence composition is well defined over all of \(X\).

## 1.4.3. Inverse Function#

(Inverse function)

If a function \(f : X \to Y\) is one-one, then for every \(y\) in \(\range f\),
there exists a unique \(x \in X\) such that \( y = f(x)\).

This unique element
is denoted by \(f^{-1}(y)\).
Thus, a function \(f^{-1} : Y \to X\) can be defined
by

The function \(f^{-1}\) is called the *inverse* of \(f\).

Note that we don’t require \(f\) to be *onto* since our
definition of a function allows \(\dom f^{-1}\) to be a
subset of \(Y\) (which happens to be \(\range f\)).

We can see that \((f \circ f^{-1})(y) = y\) for all \( y \in \range f\). Also \( (f^{-1} \circ f) (x) = x\) for all \( x \in \dom f\).

The inverse of an injective (partial) function is injective.

(Inverse of a total function)

If a total function \(f : X \to Y\) is bijective,
then for every \(y\) in \(Y\),
there exists a unique \(x \in X\) such that \(y = f(x)\).

This unique element
is denoted by \(f^{-1}(y)\).
Thus, a total function \(f^{-1} : Y \to X\) can be defined
by

The total function \(f^{-1}\) is called the *inverse* of \(f\).

The inverse of a bijective function is bijective.

(Identity function)

We define an *identity* function on a set \(X\) denoted by
\(I_X : X \to X\) as:

Identify function is one-one and onto. It is a total function and is bijective.

(Composition of a total function with its inverse)

For a total function \(f: X \to Y\):

## 1.4.4. Schröder-Bernstein Theorem#

(Schröder-Bernstein Theorem)

Given two one-one total functions \(f : X \to Y\) and \(g : Y \to X\), there exists a bijective total function \(h : X \to Y\).

Proof. Clearly, we can define a one-one onto function \(f^{-1} : f(X) \to X\) and another one-one onto function \(g^{-1} : g(Y) \to Y\). Let the two-sided sequence \(C_x\) be defined as

Note that the elements in the sequence alternate between \(X\) and \(Y\). On the left side, the sequence stops whenever \(f^{-1}(y)\) or \(g^{-1}(x)\) is not defined. On the right side the sequence goes on infinitely.

We call the sequence as \(X\) stopper if it stops at an element of \(X\) or as \(Y\) stopper if it stops at an element of \(Y\). If any element in the left side repeats, then the sequence on the left will keep on repeating. We call the sequence doubly infinite if all the elements (on the left) are distinct, or cyclic if the elements repeat. Define \(Z = X \cup Y\) If an element \(z \in Z\) occurs in two sequences, then the two sequences must be identical by definition. Otherwise, the two sequences must be disjoint. Thus the sequences form a partition on \(Z\). All elements within one equivalence class of \(Z\) are reachable from each other through one such sequence. The elements from different sequences are not reachable from each other at all. Thus, we need to define bijections between elements of \(X\) and \(Y\) which belong to same sequence separately.

For an \(X\)-stopper sequence \(C\), every element \(y \in C \cap Y\) is reachable from \(f\). Hence \(f\) serves as the bijection between elements of \(X\) and \(Y\). For an \(Y\)-stopper sequence \(C\), every element \(x \in C \cap X\) is reachable from \(g\). Hence \(g\) serves as the bijection between elements of \(X\) and \(Y\). For a cyclic or doubly infinite sequence \(C\), every element \(y \in C \cap Y\) is reachable from \(f\) and every element \(x \in C \cap X\) is reachable from \(g\). Thus either of \(f\) and \(g\) can serve as a bijection.

## 1.4.5. Restriction and Extension#

(Restriction of a function)

Let \(f : A \to B\) be a function. Let \(C\) be a subset of \(A\).
Then, the *restriction* of \(f\) to \(C\) is the function
\(f|_C : A \to B\) given by

In other words, the domain of \(f\) gets restricted to \(C \cap \dom f\) and \(f\) is no longer defined for any \(x \in \dom f \setminus C\).

For total functions, the convention is to change the signature from \(f : A \to B\) to \(f|_C : C \to B\). This way, the restriction \(f|_C\) is also a total function.

(Extension of a function)

An *extension* of a function \(f\) is any function \(g\) such that
\(f\) is a restriction of \(g\).

If \(g\) is an extension of \(f\) then \(\dom f \subset \dom g\).

## 1.4.6. Graph#

(Graph of a function)

Given a function \(f : X \to Y\),
the set of ordered pairs \((x, y)\) where
\(x \in \dom f\) and \(y = f(x)\),
is known as the *graph* of a function.

The graph of a function is the subset of the Cartesian product \(X \times Y\).

## 1.4.7. Set Valued Functions#

For a set \(X\), the notation \(2^X\) denotes the power set of \(X\).

(Set valued function/operator)

The notation \(A : X \to 2^Y\) means that
\(A\) maps every element of \(X\) to a subset of \(Y\).
In other words, \(A(x) \subseteq Y\).
\(A\) is a mapping from \(X\) to the power set of \(Y\).
Such a mapping \(A\) is called a *set valued function* or
*set valued operator*.

If \(A\) is not defined on some values of \(X\), we can simply say that \(A\) maps those values to \(\EmptySet\) which is a subset of \(Y\).

If \(f : X \to Y\) is a partial function with \(\dom f \subseteq X\), then, the corresponding set valued function \(A: X \to 2^Y\) is:

Let \(A : X \to 2^Y\) be a set valued function. Then, \(A\) is characterized by its graph

(Image of a subset under a set valued function)

Let \(A : X \to 2^Y\) be a set valued function and let \(C \subseteq X\). Then:

(Composition of set valued functions)

Let \(A : X \to 2^Y\) and \( B : Y \to 2^Z\) be set valued functions.

Then the composition \(B \circ A : X \to 2^Z\) is defined as:

(Domain of a set valued function)

The *domain* of a set valued function \(A: X \to 2^Y\) is defined as:

(Range of a set valued function)

The *range* of a set valued function \(A: X \to 2^Y\) is defined as:

Note that \(A(X) \subseteq Y\).

A set valued function \(A: X \to 2^Y\) is:

*partial*if \(\dom A \neq X\).*total*if \(\dom A = X\).*onto*if \(\range A = Y\).

(Inverse of a set valued function)

The *inverse* of a set valued function \(A: X \to 2^Y\) is defined
using its graph as:

For every \((x,y) \in X \times Y\), \(y \in A(x) \iff x \in A^{-1} (y)\).

The inverse of a set valued function is a set valued function and it always exists.

(Single valued function)

Let \(A : X \to 2^Y\) be a set valued function.
If for every \(x \in \dom A\), \(A(x)\) is a singleton,
then \(A\) is called an *at most single valued* function
from \(X\) to \(Y\).

This can be identified with a partial function.

(Selection of a set valued function)

Let \(A : X \to 2^Y\) be a set valued function.
A function \(f : X \to Y\) is called a *selection* of \(A\)
if \(f(x) \in A(x)\) for every \(x \in \dom A\).

In other words, for every \(x \in \dom A\), we select one value from the set \(A(x)\). Domain of a selection \(f\) is same as the domain of \(A\).