Functions

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Functions
        Foundations of mathematics
      

Introduction

Functions are the most studied relation of all. They appear commonly in most advanced topics such as calculus.

Prerequisites

To understand functions, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Functions

Let $ A $ and $ B $ be nonempty sets. A function $ f: A \to B $ is a relation from the set $ A $ to the set $ B $ such that every element $ a \in A $ is the first coordinate of exactly one ordered pair in $ f $.

Note that the cardinality of $ f $ is the same as that of $ A $ since every element of $ A $ appears exactly once as the first coordinate of $ f $.

Thus, every function is a relation but every relation is not a function. This is because in a relation an element in the set $ A $ may be the first coordinate of more than one ordered pair.

Examples

Consider the sets $ A = \lbrace 1, 2, 3 \rbrace $ and $ B = \lbrace x, y \rbrace $.

The relation $ R_1 = \lbrace (1,x), (2,y), (3,x) \rbrace $ is a function
The relation $ R_2 = \lbrace (1,x), (2,y) \rbrace $ is not a function, because the element $ 3 $ in $ A $ is not part of the relation.
The relation $ R_3 = \lbrace (1,x), (2,y), (1,y), (3,x) \rbrace $ is not a function, because the element $ 1 $ in $ A $ appears multiple times in the relation.

An injective function — Relation but not a function

Image of a function

Consider a function $ f $. If $ (a,b) \in f $, then we write this relationship as $ b = f(a) $ and refer to $ b $ as the image of $ a $. It is also said that $ f $ maps $ a $ into $ b $. Thus, functions are sometimes called mappings.

Pre-image of a function

Consider a function $ f $. If $ (a,b) \in f $, then we write this relationship as $ b = f(a) $ and refer to $ a $ as the pre-image of $ f(a) $.

Domain and Codomain of a function

Consider a function $ f: A \to B $.

The set $ A $ is known as the domain of $ f $ and the set $ B $ is known as the codomain of $ f $.

Range of a function

Consider a function $ f: A \to B $.

The subset of $ B $ consisting of elements which appear as second coordinates in $ f $ is known as the range of $ f $.

$$ \text{range}(f) = \lbrace f(x): x \in A \rbrace $$

Note that the range is a subset of the codomain, but they may not always be equal.

Example

Consider the sets $ A = \lbrace 1, 2, 3 \rbrace $ and $ B = \lbrace x, y, z \rbrace $. Consider the function $ f: A \to B $, $ f = \lbrace (1,x), (2,y), (3,x) \rbrace $

The range of the function is $ \text{range}(f) = \lbrace x, y \rbrace $. Note also that $ \text{range}(f) \subset B $.

Equality of functions

Two function $ f: A \to B $ and $ g: A \to B $ are said to be equal if $ f(a) = g(a) $ for all $ a \in A $.

Inverse image of a function

For a function $ f: A \to B $ and a subset $ D $ of $ B $, the inverse image $ \inv{f}(D) $ of $ D $ is defined as

$$ \inv{f}(D) = \lbrace a \in A: f(a) \in D \rbrace $$

Thus, $ \inv{f}(D) \subseteq A $ for each subset $ D $ of $ B $.

Note that the inverse image of the range of a function is its domain.

Example

Consider the sets $ A = \lbrace 1, 2, 3 \rbrace $ and $ B = \lbrace x, y, z \rbrace $. Consider the function $ f: A \to B $, $ f = \lbrace (1,x), (2,y), (3,z) \rbrace $

Consider a set $ D = \lbrace x, y \rbrace $. Note that $ D \subset B $. The inverse image of the function $ f $ on the set $ D $ is

$$ \inv{f}(D) = \lbrace 1, 2 \rbrace $$

One-to-one function

A function $ f: A \to B $ is said to be a one-to-one function if no two elements of $ A $ have the same image in $ B $. One-to-one functions are also known as injective functions.

Mathematically, if $ f: A \to B $ is a one-to-one function, then for any $ x, y \in A $ such that $ x \ne y $, it is the case that $ f(x) \ne f(y) $.

Thus, in the case of injective functions from set $ A $ to set $ B $, it is always the case that the codomain has at least as many elements as the domain, $ |A| \le |B| $.

Example

Consider the sets $ A = \lbrace 1,2,3 \rbrace $ and $ B = \lbrace w,x,y,z \rbrace $. Then,

$ f_1 = \lbrace (1,w), (2,x), (3,y) \rbrace $ is a one-to-one function
$ f_2 = \lbrace (1,x), (2,x), (3,y) \rbrace $ is not a one-to-one function, because the elements $ 1 $ and $ 2 $ in $ A $ have the same image $ x $ in $ B $.

Not an injective function — A function that is not one-to-one

Onto function

A function $f: A \to B $ is said to be an onto function if every element of the codomain $ B $ is the image of some element of the domain $ A $. Onto functions are also known as surjective functions.

Thus, in the case of onto functions, the codomain is also the range of the function.

Note that in the case of surjective functions, the domain has at least as many elements as the codomain, $ |A| \ge |B| $.

Example

Consider the sets $ A = \lbrace 1,2,3,4 \rbrace $ and $ B = \lbrace x,y,z \rbrace $. Then,

$ f_1 = \lbrace (1,x), (2,y), (3,z), (4,x) \rbrace $ is an onto function
$ f_2 = \lbrace (1,x), (2,y), (3,y), (4,x) \rbrace $ is not an onto function since $ z $ is not an image of any element of $ A $.

Bijective functions

A function is said to be a bijective or a one-to-one correspondence if it is both one-to-one and onto.

Note that in the case of functions of the form $ f: A \to B $, it is always the case that

$ |A| \le |B| $ if they are one-to-one.
$ |A| \ge |B| $ if they are onto.

Thus, in the case of bijective functions, $ |A| = |B| $. So, if the cardinality of $ A $ and $ B $ is $ n $, then there are $ n! $ possible bijective functions of the form $ f: A \to B $ between them.

Example

Consider the sets $ A = \lbrace 1,2,3 \rbrace $ and $ B = \lbrace x,y,z \rbrace $. Then,

$ f_1 = \lbrace (1,x), (2,y), (3,z) \rbrace $ is a bijective function.
$ f_2 = \lbrace (1,x), (2,x), (3,z) \rbrace $ is not a bijective function.

Identity function is bijective

The identity function maps an element to itself. It is defined as $ i_A: A \to A $ such that $ a = i_A(a), \forall a \in A $.

Note that every element in $ A $ has a distinct image in $ A $, itself, so it is a one-to-one function. Moreover, every element in $ A $ is the image of some element, itself, so it is also onto.

Hence, it is a bijective function.

Inverse function

Let $ f: A \to B $ be a function. The inverse function is defined as

$$ \inv{f} = \lbrace (b,a): (a,b) \in f \rbrace $$

To be considered a function, the inverse must satisfy the definition of a function.

Every element $ b \in B $ must be in $ \inv{f} $. This implies that every element $ b \in B $ must also be in $ f $. This means, $ f $ should be an onto function.
Each element $ b \in B $ must occur only once in $ \inv{f} $. This implies that every $ b \in B $ is the image of exactly one element of $ A $. This means, $ f $ should be a one-to-one function.

Thus, to have an inverse function, the original function $ f $ must be bijective, both onto and one-to-one.

Moreover, if $ f $ is bijective, then so is $ \inv{f} $.

Preimage of an inverse function

Let $ f: A \to B $ be a function and $ \inv{f} $ be its inverse.

The preimage of a subset $ Y \subseteq B $ is the set $ \inv{f}(Y) = \lbrace x \in A: f(x) \in Y \rbrace $.

The preimage is a concept is analogous to the image of a function, but applied to the inverse.

Example

Consider the function $ f = \lbrace (p,1), (q,2), (r,3) \rbrace $ and its inverse $ \inv{f} = \lbrace (1,p), (2,q), (3,r) \rbrace $.

The preimage of the set $ Y = \lbrace 1,2 \rbrace $ is the set $ X = \lbrace p,q \rbrace $.

Composition of functions

The composition $ g \circ f $ of the functions $ f: A \to B $ and $ g: B \to C$ is a function from $ A $ to $ C $ such that

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

Example

Consider the functions $ f = \lbrace (x,1), (y,2), (z,2) \rbrace $ and $ g = \lbrace (1,p), (2,q) \rbrace $.

The composite function $ (g \circ f)(a) = \lbrace (x,p), (y,q), (z,q) \rbrace $.

Properties of composite functions

Following are some interesting properties of compositions.

If $ f $ and $ g $ are injective (one-to-one), then so is $ g \circ f $.
If $ f $ and $ g $ are surjective (onto), then so is $ g \circ f $.
Thus, if $ f $ and $ g $ are bijective, then so is $ g \circ f $.

Associative composite function

A composition of functions $f, g, $ and $ h $ is said to be associative if $ h \circ (g \circ f) = (h \circ g) \circ f $

The Pigeonhole Principle

Consider the function $ f: A \to B $ between two finite sets $ A $ and $ B $. Then,

If $ |A| > |B| $, then $ f $ is not injective, because multiple elements in $ A $ will map to the same element in $ B $.
If $ |A| < |B| $, then $ f $ is not surjective, because there are elements in $ B $ that are not the image of any element in $ A $.

This observation is known as the pigeonhole principle in Mathematics and comes from the idea that if $ n $ objects (pigeons) are put into $ m $ containers (pigeon-holes), such that $ n > m $, then some containers will end up containing more than one object.

Next-article

With a thorough understanding of functions, we continue our journey through mathematical foundations with an introduction to logic, an important concept in understanding and developing mathematical proofs.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Subscribe for article updates

Stay up to date with new material for free.