Functions

Instructor

Li Hui

Basic Concepts

Definition: Let \(A\) and \(B\) be any two given sets, and let \(f\) be a binary relation from \(A\) to \(B\).

If for every \(x{\in}A\), there exists a unique \(y{\in}B\) such that \({\langle}x, y{\rangle}{\in}f\), then the relation \(f\) is called a function from \(A\) to \(B\), denoted \(f:A{\rightarrow}B\).

If \({\langle}x, y{\rangle}{\in}f\), then \(x\) is called the preimage (or independent variable, source), and \(y\) is called the image (function value, image point) of \(x\) under \(f\). We generally write \(y=f(x)\) to denote \({\langle}x, y{\rangle}{\in}f\).

Clearly, the domain of \(f\): \(D(f)=A\), and the range: \(V(f){\subseteq}B\). Moreover: \(V(f)=\{y|y{\in}B{\wedge}{\exists}x{\in}A, y=f(x)\}\)

Example: Let \(X=\{a, b, c, d\}\), \(Y=\{1, 2, 3, 4, 5\}\), \(f=\{{\langle}a, 1{\rangle}, {\langle}b, 3{\rangle}, {\langle}c, 4{\rangle}, {\langle}d, 4{\rangle}\}\), then \(f\) is a function from \(X\) to \(Y\), and \[D(f)=\{a, b, c, d\},\,\,V(f)=\{1, 3, 4\}\] \[f(a)=1, f(b)=3, f(c)=4, f(d)=4.\]

The differences between binary relations and functions are as follows:

  1. The domain of a function must equal \(A\). The domain of a relation can be \(A\) or a proper subset of \(A\).

  2. As a binary relation, a single \(x\) can correspond to multiple different \(y\) values. As a function, a single \(x\) can only correspond to one \(y\).

Therefore, every function is a binary relation, but not every binary relation is a function.

Example: Let \(X=\{1, 2, 3, 4\}, Y=\{a, b, c, d\}\). Which of the following relations are functions? Which are not?

\[f_1=\{{\langle}1, a{\rangle}, {\langle}2, c{\rangle}, {\langle}3, b{\rangle}, {\langle}4, d{\rangle}\}\] \[f_2=\{{\langle}1, a{\rangle}, {\langle}2, b{\rangle}, {\langle}3, d{\rangle}, {\langle}4, b{\rangle}\}\] \[f_3=\{{\langle}1, a{\rangle}, {\langle}3, b{\rangle}, {\langle}4, d{\rangle}\}\] \[f_4=\{{\langle}1, a{\rangle}, {\langle}1, b{\rangle}, {\langle}2, b{\rangle}, {\langle}3, c{\rangle}, {\langle}4, d{\rangle}\}\]

Solution: \(f_1\) and \(f_2\) are both functions; \(f_3\) is not, because \(2{\in}X\) but has no corresponding \(y\) value; \(f_4\) is not either, because 1 corresponds to two different values \(a\) and \(b\).

Theorem: Let \(A\) and \(B\) both be finite sets with \(|A|=m\) and \(|B|=n\). Then there are \(n^m\) distinct functions from \(A\) to \(B\).

Proof: For any function \(f\) from \(A\) to \(B\), its domain is \(A\), so \(f\) contains exactly \(m\) ordered pairs;

In addition, for any \(x{\in}A\), it can correspond to any one of the \(n\) elements of \(B\).

Therefore, there are \(n^m\) distinct functions from \(A\) to \(B\).

The set of all distinct functions from \(A\) to \(B\) is commonly denoted \(B^A\), i.e.: \[B^A =\{f|f:A{\rightarrow}B\}.\]

Example: Let \(A=\{a, b, c\}, B=\{0, 1\}\). Find \(B^A\).

Solution: There are \(2^3=8\) distinct functions from \(A\) to \(B\). Therefore, \(B^A =\{f_0, f_1, f_2, f_3, f_4, f_5, f_6, f_7\}\).

Where: \[f_0=\{{\langle}a, 0{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 0{\rangle}\}\]

\[f_1=\{{\langle}a, 0{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 1{\rangle}\}\]

\[f_2=\{{\langle}a, 0{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 0{\rangle}\}\]

\[f_3=\{{\langle}a, 0{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 1{\rangle}\}\]

\[f_4=\{{\langle}a, 1{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 0{\rangle}\}\]

\[f_5=\{{\langle}a, 1{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 1{\rangle}\}\]

\[f_6=\{{\langle}a, 1{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 0{\rangle}\}\]

\[f_7=\{{\langle}a, 1{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 1{\rangle}\}\]

Definition: Let \(f\) and \(g\) both be functions from \(A\) to \(B\), with the same domain and codomain, and for every \(x{\in}A\): \[f(x)=g(x)\] Then functions \(f\) and \(g\) are said to be equal, denoted \(f=g\).

Special Functions

Definition: Given a function \(f:X{\rightarrow}Y\)

  1. If \(V(f)=Y\), then \(f\) is called surjective (onto);

  2. For any \(x_1, x_2{\in}X\), when \(x_1{\neq}x_2\) implies \(f(x_1){\neq}f(x_2)\) (equivalently, \(f(x_1)=f(x_2)\) implies \(x_1=x_2\)), then \(f\) is called injective (one-to-one);

  3. If \(f\) is both surjective and injective, then \(f\) is called bijective (a one-to-one correspondence).

Functions with the above properties are called surjective functions, injective functions, and bijective functions, respectively.

Example: Consider the following 4 functions:

\[f_1: \{a, b, c, d\} {\rightarrow}\{1, 2, 3\}, f_1=\{{\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}, {\langle}c, 3{\rangle}, {\langle}d, 3{\rangle}\}\] \[f_2: \{a, b, c\}{\rightarrow}\{1, 2, 3, 4\}, f_2=\{{\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}, {\langle}c, 3{\rangle}\}\] \[f_3: \{a, b, c\} {\rightarrow}\{1, 2, 3\}, f_3=\{{\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}, {\langle}c, 3{\rangle}\}\] \[f_4: \{a, b, c\} {\rightarrow}\{1, 2, 3\}, f_4=\{{\langle}a, 1{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 3{\rangle}\}\]

Then: \(f_1\) is surjective; \(f_2\) is injective; \(f_3\) is bijective; \(f_4\) is neither surjective nor injective.

 

Example: Let \(f_1:Z{\rightarrow}Z\) with \(f(x)=x+4\); \(f_2:N{\rightarrow}N\) with \(f(x)=x+4\).

Determine the type of each function.

Solution: \(f_1\) is a bijective function; \(f_2\) is an injective function.

Example: For given sets \(A\) and \(B\), construct a bijective function \(f\) from \(A\) to \(B\).

(1)\(f: R{\rightarrow}R\), (2)\(g:[0, 1]{\rightarrow}[a, b]\).

Solution:

  1. Let \(f:R{\rightarrow}R\), \(f(x)=x\). (2) Let \(f:[0, 1]{\rightarrow}[a, b]\), \(f(x)=(b-a)x+a\).

 

Let \(f:A{\rightarrow}B\), where \(A\) and \(B\) are both finite sets:

  1. A necessary condition for \(f\) to be surjective is \(|B|{\leq}|A|\);

  2. A necessary condition for \(f\) to be injective is \(|A|{\leq}|B|\);

  3. A necessary condition for \(f\) to be bijective is \(|A|=|B|\).

Definition: Let \(f:A{\rightarrow}B\) be a function. If there exists some \(c{\in}B\) such that for every \(x{\in}A\), \(f(x)=c\), i.e., \(V(f)=\{c\}\), then \(f\) is called a constant function.

A constant function is generally not injective.

 

Example: Let \(A=\{a, b, c\}, B=\{0, 1\}\).

Function \(f:A{\rightarrow}B\) defined by: \(f(a)=f(b)=f(c)=1\). That is: \(f=\{{\langle}a, 1{\rangle}, {\langle}b, 1{\rangle}, {\langle}c, 1{\rangle}\}\)

Function \(g:A{\rightarrow}B\) defined by: \(g(a)=g(b)=g(c)=0\). That is: \(g=\{{\langle}a, 0{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 0{\rangle}\}\).

Then \(f\) and \(g\) are both constant functions.

Example: Let \(f:N{\rightarrow}N\) be defined by \(f(x)=2\). Then \(f\) is a constant function.

Definition: A function \(f:A{\rightarrow}A\) is called an identity function if for every \(x{\in}A\): \(f(x)=x\), i.e.: \(f =\{{\langle}x, x{\rangle}|x{\in}A\}\). It is denoted \(I_A\).

The identity function is a bijective function.

Example: Let \(A=\{a, b, c\}, B=\{1, 2, 3\}\). Which of the following functions are identity functions? \[f_1=\{{\langle}a, b{\rangle}, {\langle}b, c{\rangle}, {\langle}c, c{\rangle}\}\] \[f_2=\{{\langle}a, a{\rangle}, {\langle}b, b{\rangle}, {\langle}c, c{\rangle}\}\] \[f_3=\{{\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}, {\langle}c, 3{\rangle}\}\] \[f_4=\{{\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}, {\langle}3, 3{\rangle}\}\] \[f_5=\{{\langle}1, a{\rangle}, {\langle}2, a{\rangle}, {\langle}3, a{\rangle}\}\] \[f_6=\{{\langle}1, 2{\rangle}, {\langle}2, 1{\rangle}, {\langle}3, 3{\rangle}\}\]

Solution: \(f_2\) and \(f_4\) are both identity functions.

Operations on Functions

Definition: Let \(f:X{\rightarrow}Y\) and \(g:Y{\rightarrow}Z\) be functions. Then \[f{\cdot}g=\{{\langle}x, z{\rangle}|x{\in}X{\wedge}z{\in}Z{\wedge}{\exists}y{\in}Y, y=f(x){\wedge}z=g(y)\}\] is called the composite function (composition) of \(f\) and \(g\).

Clearly, \(D(f{\cdot}g)=X, V(f{\cdot}g){\subseteq}Z\).

Theorem: Let \(f:X{\rightarrow}Y\) and \(g:Y{\rightarrow}Z\) be two functions. Then \(f{\cdot}g\) is a function from \(X{\rightarrow}Z\), and for every \(x{\in}X\): \[(f{\cdot}g)(x)=g(f(x))\]

Example: Let \(X=\{a, b, c\}, Y=\{\alpha, \beta\}, Z=\{0, 1\}\), function \(f:X{\rightarrow}Y\) defined by: \(f=\{{\langle}a, \alpha{\rangle}, {\langle}b, \alpha{\rangle}, {\langle}c, \beta{\rangle}\}\), function \(g:Y{\rightarrow}Z\) defined by: \(g=\{{\langle}\alpha, 0{\rangle}, {\langle}\beta, 1{\rangle}\}\). Find the composite function \(f{\cdot}g\).

Solution: \(f{\cdot}g =\{{\langle}a, 0{\rangle}, {\langle}b, 0{\rangle}, {\langle}c, 1{\rangle}\}\).

Example: Let \(A=\{1, 2, 3\}, B=\{p, q\}, C=\{a, b\}\),

function \(f:A{\rightarrow}B\) defined by: \(f=\{{\langle}1, p{\rangle}, {\langle}2, p{\rangle}, {\langle}3, q{\rangle}\}\), function \(g:B{\rightarrow}C\) defined by: \(g=\{{\langle}p, b{\rangle}, {\langle}q, b{\rangle}\}\), Find the composite function \(f{\cdot}g\).

Solution: \[D(f{\cdot}g)=A, V(f{\cdot}g)\subseteq C, f{\cdot}g:A{\rightarrow}C\]

\[(f{\cdot}g)(1)=g{\cdot}(f(1))=g(p)=b\]

\[(f{\cdot}g)(2)=g{\cdot}(f(2))=g(p)=b\]

\[(f{\cdot}g)(3)=g{\cdot}(f(3))=g(q)=b\]

Therefore: \(f{\cdot}g =\{{\langle}1, b{\rangle}, {\langle}2, b{\rangle}, {\langle}3, b{\rangle}\}.\)

Example: Let \(X=\{1, 2, 3\}\), and let \(f\) and \(g\) both be functions defined on \(X\), where: \[f=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 1{\rangle}\}\] \[g=\{{\langle}1, 2{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 3{\rangle}\}\] Find the composite functions \(f{\cdot}g\) and \(g{\cdot}f\).

Solution: \[f{\cdot}g =\{{\langle}1, 3{\rangle}, {\langle}2, 3{\rangle}, {\langle}3, 2{\rangle}\}\] \[g{\cdot}f =\{{\langle}1, 3{\rangle}, {\langle}2, 1{\rangle}, {\langle}3, 1{\rangle}\}\] Clearly \(f{\cdot}g{\neq}g{\cdot}f\).

Function composition does not satisfy the commutative law.

Theorem: Function composition satisfies the associative law. That is, if

\[f:X{\rightarrow}Y, g:Y{\rightarrow}Z, h:Z{\rightarrow}W\]are functions, then: \[f{\cdot}(g{\cdot}h)=(f{\cdot}g){\cdot}h\]

Proof: For any \(x{\in}X\), by the definition of composite functions: \[f{\cdot}(g{\cdot}h)(x)=(g{\cdot}h)(f(x))\] \[=h(g(f(x)))\] \[=h{\cdot}((f{\cdot}g)(x))\] \[=(f{\cdot}g){\cdot}h(x)\] Therefore \(f{\cdot}(g{\cdot}h)=(f{\cdot}g){\cdot}h\)

Since function composition satisfies the associative law, when composing multiple functions, parentheses are often omitted for brevity. For example: \(f{\cdot}(g{\cdot}h)\) or \((f{\cdot}g){\cdot}h\) is written simply as \(f{\cdot}g{\cdot}h\).

In particular, when \(f\) is a function defined on a set \(X\), \(f\) can be composed with itself any number of times. This is defined inductively as follows:

  1. \(f^0(x)=x, f^0=I_x\)

  2. \(f^{n+1}(x)= f^n {\cdot} f(x)= f(f^n(x))=f^n(f(x))\)

Example: Let \(f:Z{\rightarrow}Z\) be defined by: \(f(i) =2 i+1\) Find \(f^3\).

Solution: \[f^3(i)=f^2(f(i))=f^2(2i+1)= f(f(2i+1))= f(2(2i+1)+1) = f(4i+3)=2(4i+3)+1=8i+7\] Therefore: \[f^3 =\{{\langle}i, j{\rangle}|i {\in}Z {\wedge}j=8i+7\}\]

Definition: Given a function \(f:X{\rightarrow}X\), if \(f^2=f\), then \(f\) is called an idempotent function.

Example: Let \(A=\{0, 1, 2, 3\}\), and let \(f:A{\rightarrow}A\) be defined by: \[f(i) = i (\mod 2)\] Is \(f\) an idempotent function?

Solution: \[f=\{{\langle}0, 0{\rangle}, {\langle}1, 1{\rangle}, {\langle}2, 0{\rangle}, {\langle}3, 1{\rangle}\}, \] \[f^2 =\{{\langle}0, 0{\rangle}, {\langle}1, 1{\rangle}, {\langle}2, 0{\rangle}, {\langle}3, 1{\rangle}\} = f, \] so \(f\) is an idempotent function.

If \(f\) is an idempotent function, then \(f^n=f\) for every positive integer \(n\).

Theorem: Let \(f:X{\rightarrow}Y\) and \(g:Y{\rightarrow}Z\) be functions.

  1. If both \(f\) and \(g\) are surjective, then \(f{\cdot}g\) is also surjective;

  2. If both \(f\) and \(g\) are injective, then \(f{\cdot}g\) is also injective;

  3. If both \(f\) and \(g\) are bijective, then \(f{\cdot}g\) is also bijective.

Theorem: Let \(f:X{\rightarrow}Y\) be a function, \(I_X\) the identity function on \(X\), and \(I_Y\) the identity function on \(Y\). Then \(f =I_X{\cdot}f=f{\cdot}I_Y\).

Proof: For any \(x{\in}X\), since \(I_X(x)=x\), we have: \((I_X{\cdot}f)(x)=f(I_X(x))=f(x)\), so \(I_X{\cdot}f=f\).

Similarly, for any \(y{\in}Y\), since \(I_Y(y)=y\), we have: for any \(x{\in}X\), \((f{\cdot}I_Y)(x)=I_Y(f(x))=f(x)\), so \(f{\cdot}I_Y=f\).

Inverse Functions

Example: Let \(A=\{a, b\}, B=\{c, d, e\}\), and define: \(f:A{\rightarrow}B, f=\{{\langle}a, c{\rangle}, {\langle}b, d{\rangle}\}\) (injective but not surjective) Then \(f^{-1}\) is a relation from \(B\) to \(A\), \[f^{-1}=\{{\langle}c, a{\rangle}, {\langle}d, b{\rangle}\}, \,\,D(f^{-1})=\{c, d\} {\neq}B, \] so \(f^{-1}\) is not a function.

Example: Let \(A=\{0, 1, 2, 3, 4\}, B=\{p, q, r, s\}\), and define \(f:A{\rightarrow}B\), \(f=\{{\langle}0, p{\rangle}, {\langle}1, q{\rangle}, {\langle}2, r{\rangle}, {\langle}3, r{\rangle}, {\langle}4, s{\rangle}\}\)

(surjective but not injective)

Then \(f^{-1}\) is a relation from \(B\) to \(A\): \(f^{-1}=\{{\langle}p, 0{\rangle}, {\langle}q, 1{\rangle}, {\langle}r, 2{\rangle}, {\langle}r, 3{\rangle}, {\langle}s, 4{\rangle}\}\).

Since \({\langle}r, 2{\rangle}, {\langle}r, 3{\rangle}{\in}f^{-1}\), \(f^{-1}\) is not a function.

Definition: Let \(f:X{\rightarrow}Y\) be a bijective function. The inverse relation of \(f\) is called the inverse function of \(f\), denoted \(f^{-1}\).

If the inverse function \(f^{-1}\) of \(f\) exists, then \(f\) is said to be invertible.

Example: Let \(A=\{a, b, c\}\), \(B=\{1, 2, 3\}\), \[f:A{\rightarrow}B, f=\{{\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}, {\langle}c, 3{\rangle}\}\] \[g:A{\rightarrow}B, g=\{{\langle}a, 2{\rangle}, {\langle}b, 3{\rangle}, {\langle}c, 2{\rangle}\}\] \[h:A{\rightarrow}B, h=\{{\langle}a, 3{\rangle}, {\langle}b, 3{\rangle}, {\langle}c, 1{\rangle}\}\] Are functions \(f\), \(g\), and \(h\) invertible? If so, find the inverse function.

Solution: \(f\) is a bijective function and is invertible. \(f^{-1}:B{\rightarrow}A, f^{-1}=\{{\langle}1, a{\rangle}, {\langle}2, b{\rangle}, {\langle}3, c{\rangle}\}\)

Since neither \(g\) nor \(h\) is bijective, neither has an inverse function.

Example: Let \(A=\{0, 1, 2\}\), \(B=\{a, b, c\}\), \(f:A{\rightarrow}B, f=\{{\langle}0, c{\rangle}, {\langle}1, a{\rangle}, {\langle}2, b{\rangle}\}\). Find: \(f{\cdot}f^{-1}, f^{-1}{\cdot}f, (f^{-1})^{-1}\).

Solution:

\[f^{-1}=\{{\langle}c, 0{\rangle}, {\langle}a, 1{\rangle}, {\langle}b, 2{\rangle}\}\]

\[f^{-1}{\cdot}f=\{{\langle}a, a{\rangle}, {\langle}b, b{\rangle}, {\langle}c, c{\rangle}\}\]

\[f{\cdot}f^{-1} =\{{\langle}0, 0{\rangle}, {\langle}1, 1{\rangle}, {\langle}2, 2{\rangle}\}\]

\[(f^{-1})^{-1}=\{{\langle}0, c{\rangle}, {\langle}1, a{\rangle}, {\langle}2, b{\rangle}\}= f\]

Theorem: If \(f:X{\rightarrow}Y\) is a bijective function, then the inverse function \(f^{-1}:Y{\rightarrow}X\) is also bijective.

Theorem: If a function \(f:X{\rightarrow}Y\) is invertible, then:

  1. \(f{\cdot}f^{-1}=I_X\)

  2. \(f^{-1}{\cdot}f=I_Y\)

  3. \((f^{-1})^{-1}=f\)

Theorem: If \(f:X{\rightarrow}Y\) and \(g:Y{\rightarrow}Z\) are both invertible functions, then \(f{\cdot}g\) is also invertible, and

\((f{\cdot}g)^{-1}=g^{-1}{\cdot}f^{-1}\).