Functions

Definition

A 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 to each element \(x \in A\) a unique 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 sometimes say that \(y\) is the output of \(f\) when the input is \(x\).

The set \(A\) is called domain of \(f\). The set \(\{y \in B : \exists x \in A \text{ with } y = f(x)\}\) is called the range of \(f\).

ExampleDirichlet's unruly indicator function for rational numbers

\[\begin{split}g(x) = \left\{ \begin{array}{ll} 1 & \mbox{if $x \in \QQ$};\\ 0 & \mbox{if $x \notin \QQ$}. \end{array} \right.\end{split}\]

This function is not continuous anywhere on the real line.

ExampleAbsolute value function

\[\begin{split}| x | = \left\{ \begin{array}{ll} x & \mbox{if $x \geq 0$};\\ -x & \mbox{if $x < 0$}. \end{array} \right.\end{split}\]

This function is continuous but not differentiable at \(x=0\).

Definition

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

Definition

A function \(f : A \to B\) is called onto or surjective if the range of \(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

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

Definition

Let \(f : X \to Y\) be 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 : \exists x \in A \text{ such that } y = f(x)\}.\]

Definition

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\}.\]

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:

\[\begin{split}& f ( \cup_{i \in I} A_i) = \cup_{i \in I} f(A_i)\\ & f (\cap_{i \in I} A_i) \subseteq \cap_{i \in I} f(A_i) \\ & f^{-1} (\cup_{i \in I} B_i) = \cup_{i \in I}f^{-1} (B_i)\\ & f^{-1} (\cap_{i \in I} B_i) = \cap_{i \in I}f^{-1} (B_i)\\ & f^{-1}(B^c) = (f^{-1}(B))^c\end{split}\]

Definition

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)) \quad \forall x \in X.\]

Theorem

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 X\). We need to show that \(g(f(x_1)) = g(f(x_2)) \implies x_1 = x_2\). Since \(g\) is one-one, hence \(g(f(x_1)) = g(f(x_2)) \implies f(x_1) = f(x_2)\). Further, since \(f\) is one-one, hence \(f(x_1) = f(x_2) \implies x_1 = x_2\).

Theorem

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

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 here and here.

Definition

If a function \(f : X \to Y\) is one-one and onto, 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 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\).

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

Also \((f^{-1} \circ f) (x) = x\) for all \(x \in X\).

Definition

We define an identity function on a set \(X\) as

\[\begin{split}\begin{aligned} I_X : &X \to X\\ & I_X(x) = x \quad \forall x \in X \end{aligned}\end{split}\]

Remark

Identify function is bijective.

Thus we have:

\[\begin{split}& f \circ f^{-1} = I_Y.\\ & f^{-1} \circ f = I_X.\end{split}\]

If \(f : X \to Y\) is one-one, then we can define a function \(g : X \to f(Y)\) given by \(g(x) = f(x)\). This function is one-one and onto. Thus \(g^{-1}\) exists. We will use this idea to define an inverse function for a one-one function \(f\) as \(f^{-1} : f(X) \to X\) given by \(f^{-1}(y) = x \Forall y \in f(X)\). Clearly \(f^{-1}\) so defined is one-one and onto between \(X\) and \(f(X)\).

Theorem

Given two one-one functions \(f : X \to Y\) and \(g : Y \to X\), there exists a one-one onto 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.

Sequence

Definition

Any function \(x : \Nat \to X\), where \(\Nat = \{1,2,3,\dots\}\) is the set of natural numbers, is called a sequence of \(X\).

We say that \(x(n)\) denoted by \(x_n\) is the \(n^{\text{th}}\) term in the sequence.

We denote the sequence by \(\{ x_n \}\).

Note that sequence may have repeated elements and the order of elements in a sequence is important.

Definition

A subsequence of a sequence \(\{ x_n \}\) is a sequence \(\{ y_n \}\) for which there exists a strictly increasing sequence \(\{ k_n \}\) of natural numbers (i.e. \(1 \leq k_1 < k_2 < k_3 < \ldots)\) such that \(y_n = x_{k_n}\) holds for each \(n\).

Cartesian product

Definition

Let \(\{ A_i \}_{i \in I}\) be a family of sets. Then the Cartesian product \(\prod_{i \in I} A_i\) or \(\prod A_i\) is defined to be the set consisting of all functions \(f : I \to \cup_{i \in I}A_i\) such that \(x_i = f(i) \in A_i\) for each \(i \in I\).

Such a function is called a choice function and often denoted by \((x_i)_{i \in I}\) or simply by \((x_i)\).

If a family consists of two sets, say \(A\) and \(B\), then the Cartesian product of the sets \(A\) and \(B\) is designated by \(A \times B\). The members of \(A \times B\) are denoted as ordered pairs.

\[A \times B = \{ (a, b) : a \in A \text{ and } b \in B \}.\]

Similarly the Cartesian product of a finite family of sets \(\{ A_1, \dots, A_n\}\) is written as \(A_1 \times \dots \times A_n\) and its members are denoted as \(n\)-tuples, i.e.:

\[A_1 \times \dots \times A_n = \{(a_1, \dots, a_n) : a_i \in A_i \forall i = 1,\dots,n\}.\]

Note that \((a_1,\dots, a_n) = (b_1,\dots,b_n)\) if and only if \(a_i = b_i \forall i = 1,\dots,n\).

If \(A_1 = A_2 = \dots = A_n = A\), then it is standard to write \(A_1 \times \dots \times A_n\) as \(A^n\).

Example:math:`A^n`

Let \(A = \{ 0, +1, -1\}\).

Then \(A^2\) is

\[\begin{split}\{\\ &(0,0), (0,+1), (0,-1),\\ &(+1,0), (+1,+1), (+1,-1),\\ &(-1,0), (-1,+1), (-1,-1)\\ \}.\end{split}\]

And \(A^3\) is given by

\[\begin{split} \{\\ &(0,0,0), (0,0,+1), (0,0,-1),\\ &(0,+1,0), (0,+1,+1), (0,+1,-1),\\ &(0,-1,0), (0,-1,+1), (0,-1,-1),\\ &(+1,0,0), (+1,0,+1), (+1,0,-1),\\ &(+1,+1,0), (+1,+1,+1), (+1,+1,-1),\\ &(+1,-1,0), (+1,-1,+1), (+1,-1,-1),\\ &(-1,0,0), (-1,0,+1), (-1,0,-1),\\ &(-1,+1,0), (-1,+1,+1), (-1,+1,-1),\\ &(-1,-1,0), (-1,-1,+1), (-1,-1,-1)\\ &\}.\end{split}\]

If the family of sets \(\{A_i\}_{i \in I}\) satisfies \(A_i = A \forall i \in I\), then \(\prod_{i \in I} A_i\) is written as \(A^I\).

\[A^I = \{ f | f : I \to A\}.\]

i.e. \(A^I\) is the set of all functions from \(I\) to \(A\).

Example

• Let \(A = \{0, 1\}\). \(A^{\RR}\) is a set of all functions on \(\RR\) which can take only one of the two values \(0\) or \(1\). \(A^{\Nat}\) is a set of all sequences of zeros and ones.
• \(\RR^\RR\) is a set of all functions from \(\RR\) to \(\RR\).

Axiom of choice

If a Cartesian product is non-empty, then each \(A_i\) must be non-empty.

We can therefore ask: If each :math:`A_i` is non-empty, is then the Cartesian product :math:`prod A_i` nonempty?

An affirmative answer cannot be proven within the usual axioms of set theory.

This requires us to introduce the axiom of choice.

Axiom

Axiom of choice. If \(\{A_i\}_{i \in I}\) is a nonempty family of sets such that \(A_i\) is nonempty for each \(i \in I\), then \(\prod A_i\) is nonempty.

Another way to state the axiom of choice is:

Axiom

If \(\{A_i\}_{i \in I}\) is a nonempty family of pairwise disjoint sets such that \(A_i \neq \EmptySet\) for each \(i \in I\), then there exists a set \(E \subseteq \cup_{i \in I} A_i\) such that \(E \cap A_i\) consists of precisely one element for each \(i \in I\).