## Introduction

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

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.

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

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.

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.

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

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

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

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.

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

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

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.

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

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

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

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

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

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.

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.

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.

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

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.

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

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

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

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

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

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.

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.

Let your friends, followers, and colleagues know about this resource you discovered.

Stay up to date with new material ** for free**.