0.3: Functions

 

Definition: Cartesian Product

Let \(A\) and \(B\) be  sets. Then \(A \times B= \{(a, b)| a \in A \) and \( b \in B \} \) is the Cartesian product of \(A\) and \(B\).

Example \(\PageIndex{1}\)

If \(A =B= \mathbb{R}\) then this is the Cartesian plane -  Like \(\{(x,y): x,y \in A\}\).

Definition: Function

Let \(A\) and \(B\) be sets. A function \(f\) is a subset (symbol is \(\subseteq\)) of \(A \times B\) such that for every \(a \in A\) there exists a unique \(b \in B\) such that \(f(a)=b\). 

Denoted by \(f: A \rightarrow B\) or \(A \xrightarrow{f} B\).

\(A\) is the domain of the function \(f\).  

\(B\) is the co-domain of the function \(f\).

The range of \(f\) is \(f(A)=\big{\{}f(x): x \in A \big{\}} \subseteq B = Im(f)\), the image of \(f.\)

A well-defined function is one that for every value of \(A\), there is one and only one value of \(B\).

 

Definition: 

Let \(A\) and \(B\) be sets. Let \(f\) be a function from \(A \rightarrow B\).

1. \(f\) is called onto (surjective) if \(f(A)=B\).

2. \(f\) is called one to one (injective) if \(f(x_1)=f(x_2), x_1,x_2 \in A \) then \(x_1=x_2\).

3. \(f\) is bijective if it is surjective and injective.

4. A function can be injective, surjective, bijective (both injective & surjective), or neither.

 Note: 

Let \(A\) and \(B\) be a sets. Let \(f: A \rightarrow B\).  If \(f\) is 1-1 and onto then \(f\) is a bijection from \(A \rightarrow B.\) 

If there is a bijection between two finite sets, the number of elements in each set is the same.  Notationally:  |A| = |B|.

Example \(\PageIndex{2}\)

Example \(\PageIndex{3}\)

Consider the mapping:

Is this mapping 

a) Well-defined?

b) Is it surjective? 

c) Is it injective? 

d) Is it bijective?

Solution

The function is well-defined. Not injective. Not surjective, not bijective.

 

Example \(\PageIndex{4}\)

Consider the mapping:

Is this mapping 

a) well-defined?

b) Is it surjective? 

c) Is it injective? 

d) Is it bijective?

Solution

This is a well-defined bijective function.

Example \(\PageIndex{5}\)

Given \(f: \mathbb{Q} \rightarrow \mathbb{Z}\) where \(\mathbb{Q}=\{\frac{a}{b}:a,b \in \mathbb{Z}, b \ne 0 \}\) and \(f(\frac{a}{b})=a\).  Is this a well-defined function?  

Solution

Let \(A\) and \(B\) be sets such that \(A=\{\frac{a}{b}:a,b \in \mathbb{Z}, a \ne 0\}\) and \(B=\mathbb{Z}\).

Using a counterexample, \(f(\frac{a}{b})\) is not a well-defined function since \(f(\frac{1}{2})=1\) and \(f(\frac{2}{4})=2\), but \(\frac{1}{2}=\frac{2}{4}\).  This is an example of an element in \(A\) that maps to more than one element in \(B\).

Example \(\PageIndex{6}\)

Let  \(\mathbb{Q}=\big{\{}\frac{a}{b}: b> 0,\text{and } gcd(a,b)=1 \big{\}}\)

and \(f: \mathbb{Q} \rightarrow \mathbb{Z}\) that is defined by

 \(f(\frac{a}{b})=a.\)

 a) Is \(f\) a well-defined function? b)  Is it surjective?  c) Is it injective?  d) Is it bijective?

Solution

1. The function is well-defined.

Let \(A\) and \(B\) be set.

Let \(a \in A\).

We need to show that if \(f(a)=b\) then \(b\in B\) and if \(f(a)=b_1\) that \(b=b_1\).

We are given \(f: \mathbb{Q} \rightarrow \mathbb{Z}\), which means that this is a function thus \(f(a)\) will map to one and only one element of \(B\).  Thus if \(f(a)=b\) and if \(f(a)=b_1\) then \(b=b_1\).

In b) below, we have shown that the function is surjective, thus \(f(a)=b\),

 

2. The function is surjective

   Proof:

We shall show that \(f(\mathbb{Q})=\mathbb{Z}\) by showing that  \(f(\mathbb{Q}) \subseteq \mathbb{Z}\) and  \(\mathbb{Z} \subseteq f(\mathbb{Q})\).

Since we are given \(f: \mathbb{Q} \rightarrow \mathbb{Z}\),  \(f(\mathbb{Q}) \subseteq \mathbb{Z}\).

Next, we shall show that \(\mathbb{Z} \subseteq f(\mathbb{Q})\).

Let \(n \in \mathbb{Z}\), then \(\frac{n}{1} \in \mathbb{Q}\) and \(f\big(\frac{n}{1}\big)=n\).

Hence \(n \in f(\mathbb{Q})\).

Hence \(\mathbb{Z} \subseteq f(\mathbb{Q})\).

Since \(\mathbb{Z} \subseteq f(\mathbb{Q})\) and \(f(\mathbb{Q}) \subseteq \mathbb{Z}, f(\mathbb{Q})=\mathbb{Z}\).◻

 

3. The function is not injective.

   Counterexample:

Let \(A=\big{\{}\frac{a}{b}: b> 0,\text{and } gcd(a,b)=1 \big{\}}\) and \(B=\mathbb{Z}\).

Note \(\frac{1}{4},  \frac{1}{3} \in A\) and that \(f(\frac{1}{4}),  f(\frac{1}{3}) \in B\) and that \(f(\frac{1}{4})=f(\frac{1}{3})=1\). 

Since \(\frac{1}{4} \ne \frac{1}{3}\) , the function is not injective.

 

4. The function is not bijective, as it is neither injective nor surjective.

 

Operation on functions: Composition

 

Definition: Composition of functions

Let \(A\) and \(B\) be  sets. Let \(f: A \rightarrow B\) and \(g: B \rightarrow C\). Then the composition functions of \(g\) and \(f\), \(g \circ f: A \to C \), defined by 

\((g \circ f)(a)=g(f(a)), \; \forall a \in A\).

Definition: Identity function

Let \(A\) be a set. Identity function \(id_A: A \rightarrow A\) defined by \(id_A(x)=x, \forall x \in A\).

Definition: Inverse of a function

Let \(A\) and \(B\) be  sets. Let \(f: A \rightarrow B\) then \(f\) has an inverse \(g: B \rightarrow A\) if \((f \circ g)= id_B\) and \((g \circ f)=id_A\).  Note the domain of \(f \circ g\) is the domain of \(g\).

Let \(A\) and \(B\) be sets and let \(f:A \rightarrow B\) be a bijection.  Then the inverse of \(f\), denoted by \(f^{-1}:B \rightarrow A\) defined by \(f^{-1}(b)=a\) if \(f(a)=b\) if \(a \in A\) and \(b \in B\). In this case, \(f \circ f^{-1}=id_B, \) and \(f^{-1}\circ f =id_A.\)

 

 

Example \(\PageIndex{7}\)

Let \(f: A \rightarrow B\) and \(g: B \rightarrow C\). Then \(g \circ f: A \to C.\) 

1. If \(f\) and \(g\) are surjective, then \(g \circ f\) is surjective.

Proof:

We will show that \(g \circ f\) is surjective.

Let \(c \in C\) . Since g is surjective, there exists \(b \in B\)  such that \(g(b)=c.\)

Since f is surjective, there exists \(a \in A\) such that \(f(a) = b \).

Hence there exists \(a \in A\) such that \(g(f(a))=c.\)

Therefore, if \(f\) and \(g\) are surjective, then \(g \circ f\)  is surjective.◻

(better proof) If \(f\) is onto and \(g\) is onto, then \(g \circ f\) is onto.

Proof:

We shall show that \((g \circ f)(A)=C\).

Since \(f\) and \(g\) are onto, by definition of a function, \((g \circ f)(A) \subseteq C\).

Now we need to show that \(C \subseteq (g \circ f)(A)\).

Let \(c \in C\).

Since \(g\) is onto \(\exists b \in B\) s.t. \(c=g(b)\).

Since \(f\) is onto, \(\exists a \in A\) s.t. \(b=f(a)\).

Consider \((g \circ f)(a)=g(f(a))\) (by definition)

        \(=g(b)\)

        \(=c\).

Therefore \(c \in (g \circ f)(A)\).

Hence \(C \subseteq (g \circ f)(A)\).

Since \((g \circ f)(A) \subseteq C\) and \(C \subseteq (g \circ f)(A)\), then \(g \circ f\) is onto. \(\square\)

 

Example \(\PageIndex{8}\)

1. If \(f\) and \(g\) are injective, then \(g \circ f\) is injective. That is,

If \(f\) is 1-1 and \(g\) is 1-1 then \(g \circ f\) is 1-1.

Proof:

Let   \(a_1,a_2 \in A\)  such that \(g \circ f (a_1)= g\circ f(a_2).\)  Then \(g(f(a_1))=g(f(a_2)).\)

Since  \(g\) is 1-1, \(f(a_1)=f(a_2)\).

Since,  \(f\) is 1-1, \(a_1=a_2.\)

 

Hence \(g \circ f\) is injective.

 

Theorem \(\PageIndex{1}\)

Let Let \(f:A\to B\) and \(g:B\to C\). 

1.  If \(g\circ f\) is injective, then \(f\) is injective.
2.  If \(g\circ f\) is surjective, then \(g\) is surjective.

Proof

1. Let \(a_1,a_2\in A\). Suppose \(f(a_1)=f(a_2)\). Applying \(g\) gives
\((g\circ f)(a_1)=(g\circ f)(a_2).\)
Since \(g\circ f\) is injective, \(a_1=a_2\). Thus \(f\) is injective.

2. let \(c\in C\). Since \(g\circ f\) is surjective, there exists \(a\in A\) such that \(g(f(a))=c.\)
Let \(b=f(a)\in B\). Then \(g(b)=c\). Hence \(g\) is surjective.

 

Example \(\PageIndex{9}\)

Surjective composition does not force injectivity:
Let \(A=\{1,2\},\qquad B=\{3\},\qquad C=\{4\}.\)
Define \(f(1)=3,\qquad f(2)=3,\) and \(g(3)=4.\)
Then \(g\circ f:A\to C\) is surjective, but \(f\) is not injective because \(f(1)=f(2).\)

Example \(\PageIndex{10}\)

Surjective composition does not force surjectivity of the first function:
Let \(A=\{1\},\qquad B=\{2,3\},\qquad C=\{4\}.\)
Define \(f(1)=2,\) and \( g(2)=4,\qquad g(3)=4.\)
Then \(g\circ f:A\to C\) is surjective, but \(f\) is not surjective because \(3\notin \text{Im}(f)\).

Example \(\PageIndex{11}\)

Given \(A\) is a matrix and \(T_A:\mathbb{R}^2 \rightarrow \mathbb{R}^2\) defined by \(T_A \begin{bmatrix} x\\
y\end{bmatrix} = \begin{bmatrix} 1 &1\\
0 & 1\end{bmatrix} \begin{bmatrix} x\\
y\end{bmatrix}\).  Note that this is a linear matrix transformation.

1. Is \(T_A\) 1-1?

Yes, \(T_A\) is 1-1.

Proof:

Let \(\begin{bmatrix} x_1\\
y_1\end{bmatrix}\)and \(\begin{bmatrix} x_2\\
y_2\end{bmatrix} \in \mathbb{R}^2\) s.t. \(T_A \begin{bmatrix} x_1\\
y_1\end{bmatrix} =T_A \begin{bmatrix} x_2\\
y_2\end{bmatrix}\).

We will show that \(\begin{bmatrix} x_1\\
y_1\end{bmatrix} =\begin{bmatrix} x_2\\
y_2\end{bmatrix}\).

\(T_A \begin{bmatrix} x\\
y\end{bmatrix} =\begin{bmatrix} x+y\\
y\end{bmatrix}\).

Thus  \(\begin{bmatrix} x_1 +y_1\\
y_1\end{bmatrix} =\begin{bmatrix} x_2+y_2\\
y_2\end{bmatrix}\).

Thus \(x_1+y_1=x_2+y_2\) and \(y_1=y_2\).

Thus \(x_1=x_2\) and \(y_1=y_2\).

Hence \(\begin{bmatrix} x_1\\
y_1\end{bmatrix} =\begin{bmatrix} x_2\\
y_2\end{bmatrix}\).

Thus \(T_A\) is 1-1.◻

 

2. Is \(T_A \begin{bmatrix} x\\
   y\end{bmatrix} \) onto?

Yes, \(T_A \begin{bmatrix} x\\
y\end{bmatrix} \) is onto.

Proof:

We know by definition that \(T_A \begin{bmatrix} x\\
y\end{bmatrix} \subseteq \mathbb{R}^2\).

We need to show that \(\mathbb{R}^2 \subseteq T_A \begin{bmatrix} x\\
y\end{bmatrix}\).

Let \( \begin{bmatrix} a\\
b\end{bmatrix} \in \mathbb{R}^2\).

Find \( \begin{bmatrix} x\\
y\end{bmatrix} \in \mathbb{R}^2\) s.t. \(\begin{bmatrix} 1 &1\\
0 & 1\end{bmatrix} \begin{bmatrix} x\\
y\end{bmatrix}=\begin{bmatrix} a\\
b\end{bmatrix}\).

\(\begin{bmatrix} x+y\\
y\end{bmatrix} =\begin{bmatrix} a\\
b\end{bmatrix}\).

Thus \(y=b\) and \(x=a-b\).

Thus \(T_A \begin{bmatrix} a-b\\
b\end{bmatrix} =\begin{bmatrix} a\\
b\end{bmatrix}\).

Thus \(T_A\) is onto.◻

 

3. Does \(T_A\) have an inverse?  If so, what is it?

a) Yes \(T_A\) has an inverse since it is a bijection (1-1 and onto) ∴ \(T_A^{-1}\) exists.

Proof:  By definition?  Obvious?

b) \(T_A^{-1}: \mathbb{R}^2 \rightarrow \mathbb{R}^2\).

\(T_A^{-1} \begin{bmatrix} x\\
y\end{bmatrix} =\begin{bmatrix} 1 & -1\\
0 & 1\end{bmatrix} \begin{bmatrix} x\\
y\end{bmatrix}\)

    \(=\begin{bmatrix} x-y\\
y\end{bmatrix} \).

Check: \( T_A^{-1} \cdot T_A=\begin{bmatrix} 1 & -1\\
0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1\\
0 & 1\end{bmatrix} =\begin{bmatrix} 1 & 0\\
0 & 1 \end{bmatrix}\).

Example \(\PageIndex{12}\)

Let \(f: A \rightarrow B\) and \(g: B \rightarrow C\). Then \(g \circ f:A \to C\). Given \(g \circ f\) is injective and \(f\) is surjective, prove that \( g\) is injective.

Proof:

Assume \(g \circ f\) is injective.  (by definition)

Let \(x_1, x_2 \in B\) s.t. \(g(x_1)=g(x_2)\).

We shall show that \(x_1=x_2\).

Let \(a_1, a_2 \in A\).

Since \(f\) is surjective (by definition), we know that \(f(a_1)=x_1\) and \(f(a_2)=x_2\).

Since \(x_1 \in B\) and \(f\) is surjective, \(\exists a_1 \in A\) s.t. \(f(a_1)=x_1\).

Since \(x_2 \in B\) and \(f\) is surjective, \(\exists a_2 \in A\) s.t. \(f(a_2)=x_2\).

Since \(g(x_1)=g(x_2)\), then \(g(f(a_1))=g(f(a_2))\) and \(g \circ f)(a_1)=(g \circ f)(a_2)\).

Since \(g \circ f)\) is injective, \(a_1=a_2\).

Thus \(f(a_1)=f(a_2)\) since \(f\) is a function.

Therefore, \(x_1=x_2\).

Hence \(g\) is injective.

Example \(\PageIndex{13}\)

Consider the mapping \(\alpha\):

 

 

Find \(\alpha^2\) , \(\alpha^3\) and \(\alpha^{-1}\).

Answer

From the diagram, the mapping \(\alpha: \{1, 2, 3\} \to \{1, 2, 3\}\) is defined by: \[ \alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2 \] In two-row notation, \(\alpha\) is written as: \[ \alpha = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \] In disjoint cycle notation, \(\alpha\) forms a single 3-cycle: \[ \alpha = (1 \ 3 \ 2) \]

Computation of \(\alpha^2\):

Applying \(\alpha\) twice: \begin{align*} \alpha^2(1) &= \alpha(\alpha(1)) = \alpha(3) = 2 \\ \alpha^2(2) &= \alpha(\alpha(2)) = \alpha(1) = 3 \\ \alpha^2(3) &= \alpha(\alpha(3)) = \alpha(2) = 1 \end{align*}

Thus, in two-row and cycle notation: \[ \alpha^2 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = (1 \ 2 \ 3) \]

Computation of \(\alpha^3\): 

Applying \(\alpha\) three times: \begin{align*} \alpha^3(1) &= \alpha(\alpha^2(1)) = \alpha(2) = 1 \\ \alpha^3(2) &= \alpha(\alpha^2(2)) = \alpha(3) = 2 \\ \alpha^3(3) &= \alpha(\alpha^2(3)) = \alpha(1) = 3 \end{align*}

Thus, \(\alpha^3\) is the identity permutation \(\varepsilon\): \[ \alpha^3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = (1)(2)(3) = \varepsilon \]

Computation of \(\alpha^{-1}\):

The inverse mapping reverses the direction of the arrows (\(\alpha^{-1}(x) = y \iff \alpha(y) = x\)): \[ \alpha^{-1}(3) = 1, \quad \alpha^{-1}(1) = 2, \quad \alpha^{-1}(2) = 3 \] Thus, in two-row and cycle notation: \[ \alpha^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = (1 \ 2 \ 3) \] Note that since \(\alpha^3 = \varepsilon\),  \(\alpha^{-1} = \alpha^2 = (1 \ 2 \ 3)\). (We will learn this later!)