.md .pdf

repository open issue

Contents

1.3. Functions

Definition 1.47 (Function)

A partial function (or simply function) from a set $A$ to a set $B$, in symbols $f:A\to B$ (or $A\stackrel{f}{\to }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 [10], 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.

Definition 1.48 (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$.

Definition 1.49 (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 $\mathrm{dom}f$.

$$\mathrm{dom}f\triangleq \{x\in A|\mathrm{\exists }y\in B\text{ such that }y=f(x)\}.$$

Definition 1.50 (Total function)

A function $f:A\to B$ is called a total function if $\mathrm{dom}f=A$.

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

Definition 1.51 (Range of a function)

The set $\{y\in B|\mathrm{\exists }x\in A\text{ such that }y=f(x)\}$ is called the range of $f$ denoted by $\mathrm{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$.

Definition 1.52 (Equality of functions)

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

In words, they map the same elements of $A$ to same elements of $B$.

Definition 1.53 (Surjective function)

A function $f:A\to B$ is called onto or surjective if $\mathrm{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)$.

Definition 1.54 (Injective function)

A function $f:A\to B$ is called one-one or injective if $x_1\ne x_2⟹f(x_1)\ne f(x_2)$.

Definition 1.55 (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 $\mathrm{dom}f=A$, $\mathrm{range}f=B$, the elements of $A$ and $B$ are in one-to-one mapping.

Example 1.10 (Square root)

Let $f:\mathbb{R}\to \mathbb{R}$ be defined as:

$$f(x)=\sqrt{x}.$$

$\mathrm{dom}f=[0,\mathrm{\infty })$. $\mathrm{range}f=[0,\mathrm{\infty })$.

$f$ is partial and injective. It is neither surjective nor bijective.

Example 1.11 (Logarithm)

Let $f:\mathbb{R}\to \mathbb{R}$ be defined as:

$$f(x)=\log (x).$$

$\mathrm{dom}f=(0,\mathrm{\infty })$. $\mathrm{range}f=(-\mathrm{\infty },\mathrm{\infty })=\mathbb{R}$.

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

Example 1.12 (Exponential)

Let $f:\mathbb{R}\to \mathbb{R}$ be defined as:

$$f(x)=e^x.$$

$\mathrm{dom}f=(-\mathrm{\infty },\mathrm{\infty })=\mathbb{R}$. $\mathrm{range}f=(0,\mathrm{\infty })=\mathbb{R}$.

$f$ is total and injective but not surjective.

Example 1.13 (Extended value extension of exponential)

Let $f:\mathbb{R}\cup \{-\mathrm{\infty },\mathrm{\infty }\}\to \mathbb{R}\cup \{-\mathrm{\infty },\mathrm{\infty }\}$ be defined as:

$$\begin{array}{r}f(x)=\{\begin{array}{ll}{e}^x& x\in \mathbb{R}\\ 0& x=-\mathrm{\infty }\\ \mathrm{\infty }& x=\mathrm{\infty }\end{array}.\end{array}$$

$\mathrm{dom}f=[-\mathrm{\infty },\mathrm{\infty }]$. $\mathrm{range}f=[0,\mathrm{\infty }]=\mathbb{R}$.

$f$ is total and injective but not surjective.

Example 1.14 (Dirichlet’s unruly indicator function for rational numbers)

Let $g:\mathbb{R}\to \mathbb{R}$ be defined as:

$$\begin{array}{r}g(x)\triangleq \{\begin{array}{ll}1& \text{if }x\in \mathbb{Q};\\ 0& \text{if }x\notin \mathbb{Q}.\end{array}\end{array}$$

$\mathrm{dom}g=\mathbb{R}$, $\mathrm{range}g=${0, 1 }$.

Example 1.15 (Absolute value function)

$$\begin{array}{r}f(x)=|x|=\{\begin{array}{ll}x& \text{if }x\ge 0;\\ -x& \text{if }x<0.\end{array}\end{array}$$

The domain is $\mathbb{R}$ and the range is ${\mathbb{R}}_{+}=[0,\mathrm{\infty })$.

$f$ is total. It is not injective. It is not surjective.

Example 1.16 (Logarithm of the determinant)

The set of $n\times n$ real symmetric matrices is denoted by ${\mathbb{S}}^n$. The set of positive semidefinite symmetric matrices is denoted by ${\mathbb{S}}_{+}^n$. The set of positive definite symmetric matrices is denoted by ${\mathbb{S}}_{++}^n$.

Consider the function $f:{\mathbb{S}}^n\to \mathbb{R}$ given by

$$f(X)=\log det(X).$$

The domain of the function is $\mathrm{dom}f={\mathbb{S}}_{++}^n$. The function is not defined for matrices which are not positive definite.

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

• If $\mathrm{dom}f=A$ then, the function is total.

• If $\mathrm{range}f=B$ then, the function is surjective.

• If $f(x_1)=f(x_2)⟹x_1=x_2$, then the function is injective.

• If $f$ is total, injective and surjective, then it is bijective.

1.3.1. Image under a function

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

Definition 1.56 (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

$$f(A)=\{y\in Y|\mathrm{\exists }x\in A\text{ such that }y=f(x)\}.$$

Note that the definition is valid even if some elements of the subset $A$ may not belong to $\mathrm{dom}f$.

Definition 1.57 (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

$$f^{-1}(B)=\{x\in X|f(x)\in B\}.$$

Remark 1.5

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

Proposition 1.7

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$.

$$f({\cup }_{i\in I}{A}_i)={\cup }_{i\in I}f(A_i).$$

Image of the intersection of $A_i$ is a subset of the intersection of the images of $A_i$.

$$f({\cap }_{i\in I}{A}_i)\subseteq {\cap }_{i\in I}f(A_i).$$

Inverse image of the union of $B_i$ is the union of the inverse images of $B_i$.

$$f^{-1}({\cup }_{i\in I}{B}_i)={\cup }_{i\in I}{f}^{-1}(B_i).$$

Inverse image of the intersection of $B_i$ is the intersection of the inverse images of $B_i$.

$$f^{-1}({\cap }_{i\in I}{B}_i)={\cap }_{i\in I}{f}^{-1}(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$.

$$f^{-1}(Y\setminus B)=\mathrm{dom}f\setminus f^{-1}(B)\subseteq X\setminus f^{-1}(B).$$

1.3.2. Function Composition

Definition 1.58 (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

$$(g\circ f)(x)=g(f(x))\mathrm{\forall }x\in \mathrm{dom}f\text{ such that }f(x)\in \mathrm{dom}g.$$

Remark 1.6

$$\mathrm{dom}g\circ f\subseteq \mathrm{dom}f\subseteq X.$$

The domain of the composition may be smaller than the domain of $f$ as $g$ may not be defined for every $y$ in $\mathrm{range}f$.

Theorem 1.1

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 \mathrm{dom}g\circ f$. We need to show that $g(f(x_1))=g(f(x_2))⟹x_1=x_2$. Since $g$ is one-one, hence

$$g(f(x_1))=g(f(x_2))⟹f(x_1)=f(x_2).$$

Further, since $f$ is one-one, hence

$$f(x_1)=f(x_2)⟹x_1=x_2.$$

Theorem 1.2

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))$.

Theorem 1.3

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.

Corollary 1.1

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

Definition 1.59 (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

$$(g\circ f)(x)=g(f(x))\mathrm{\forall }x\in X.$$

Since $\mathrm{dom}f=X$ and $\mathrm{dom}g=Y$, hence composition is well defined over all of $X$.

1.3.3. Inverse Function

Definition 1.60 (Inverse function)

If a function $f:X\to Y$ is one-one, then for every $y$ in $\mathrm{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

$$f^{-1}(y)=x\text{ whenever }f(x)=y.$$

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 $\mathrm{dom}{f}^{-1}$ to be a subset of $Y$ (which happens to be $\mathrm{range}f$).

Remark 1.7

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

$$\mathrm{dom}{f}^{-1}=\mathrm{range}f.$$

$$\mathrm{dom}f=\mathrm{range}{f}^{-1}.$$

Remark 1.8

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

Definition 1.61 (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

$$f^{-1}(y)=x\text{ whenever }f(x)=y.$$

The total function $f^{-1}$ is called the inverse of $f$.

Remark 1.9

The inverse of a bijective function is bijective.

Definition 1.62 (Identity function)

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

$$I_X(x)=x\mathrm{\forall }x\in X$$

Remark 1.10

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

Remark 1.11 (Composition of a total function with its inverse)

For a total function $f:X\to Y$:

$$\begin{array}{rl}& f\circ f^{-1}=I_Y.\\ & f^{-1}\circ f=I_X.\end{array}$$

1.3.4. Schröder-Bernstein Theorem

Theorem 1.4 (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

$$\dots ,f^{-1}(g^{-1}(x)),g^{-1}(x),x,f(x),g(f(x)),f(g(f(x))),\dots .$$

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.3.5. Restriction and Extension

Definition 1.63 (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

$$f{|}_C(x)=f(x)\mathrm{\forall }x\in C\cap \mathrm{dom}f.$$

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

Remark 1.12

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.

Definition 1.64 (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 $\mathrm{dom}f\subset \mathrm{dom}g$.

1.3.6. Graph

Definition 1.65 (Graph of a function)

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

$$\mathrm{gra}f\triangleq \{(x,f(x))|x\in X\}$$

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

1.3.7. Set Valued Functions

For a set $X$, the notation $2^X$ denotes the power set of $X$.

Definition 1.66 (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.

Observation 1.1

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

If $f:X\to Y$ is a partial function with $\mathrm{dom}f\subseteq X$, then, the corresponding set valued function $A:X\to 2^Y$ is:

$$\begin{array}{r}A(x)=\{\begin{array}{ll}\{f(x)\}& \text{ if }x\in \mathrm{dom}f\\ \varnothing & \text{ if }x\notin \mathrm{dom}f\end{array}.\end{array}$$

Remark 1.13

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

$$\mathrm{gra}A=\{(x,y)\in X\times Y|y\in A(x)\}.$$

Definition 1.67 (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:

$$A(C)\triangleq \bigcup _{x\in C}A(x).$$

Definition 1.68 (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:

$$(B\circ A)(x)\triangleq B(A(x))=\bigcup _{y\in A(x)}B(y).$$

Definition 1.69 (Domain of a set valued function)

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

$$\mathrm{dom}A\triangleq \{x\in X|A(x)\ne \varnothing \}.$$

Definition 1.70 (Range of a set valued function)

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

$$\mathrm{range}A\triangleq A(X)=\bigcup _{x\in X}A(x).$$

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

Remark 1.14

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

1. partial if $\mathrm{dom}A\ne X$.

2. total if $\mathrm{dom}A=X$.

3. onto if $\mathrm{range}A=Y$.

Definition 1.71 (Inverse of a set valued function)

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

$$\mathrm{gra}{A}^{-1}=\{(y,x)\in Y\times X|(x,y)\in \mathrm{gra}A\}.$$

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

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

Definition 1.72 (Single valued function)

Let $A:X\to 2^Y$ be a set valued function. If for every $x\in \mathrm{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.

Definition 1.73 (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 \mathrm{dom}A$.

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

previous

1.2. Relations

next

1.4. Cardinality