Functions and Relations

Definition 53: Relation

A relation $𝑅$ from a set $𝐴$ to a set $𝐵$ is a subset of the Cartesian product $𝐴 \times 𝐵$ :

𝑅 is a relation from 𝐴 to 𝐵 iff 𝑅 \subseteq 𝐴 \times 𝐵 .

If $(𝑎, 𝑏) \in 𝑅$ , we say that $𝑎$ is related to $𝑏$ by $𝑅$ , and we write $𝑎 𝑅 𝑏$ .

Definition 54: Function

A relation $𝑅 \subseteq 𝐴 \times 𝐵$ is a function iff the following two conditions hold:

Totality. $\forall 𝑎 \in 𝐴, \exists 𝑏 \in 𝐵 such that (𝑎, 𝑏) \in 𝑅$ .
Uniqueness. $\forall 𝑎 \in 𝐴, \forall 𝑏_{1}, 𝑏_{2} \in 𝐵, [(𝑎, 𝑏_{1}) \in 𝑅 and (𝑎, 𝑏_{2}) \in 𝑅] \Rightarrow 𝑏_{1} = 𝑏_{2}$ .

Terminology: Domain, Codomain, Range

For a function $𝑓 : 𝐴 \to 𝐵$ , the set $𝐴$ is called the domain of $𝑓$ , the set $𝐵$ is called the codomain of $𝑓$ , and the set $𝑓 (𝐴) = {𝑓 (𝑎) | 𝑎 \in 𝐴}$ is called the range of $𝑓$ .

Notation

Denoting $𝑎 \mapsto 𝑏$ under $𝑓$ asserts that $𝑓$ maps $𝑎$ to $𝑏$ , i.e. that $𝑓 (𝑎) = 𝑏$ .

Definition 55: Graph of a Function

The graph $Gr (𝑓)$ of a function $𝑓 : 𝐴 \to 𝐵$ is the set of ordered pairs $(𝑎, 𝑓 (𝑎))$ for all $𝑎 \in 𝐴$ :

Gr (𝑓) = {(𝑎, 𝑓 (𝑎)) | 𝑎 \in 𝐴} .

Terminology: Partial Function

A partial function from $𝐴$ to $𝐵$ is a relation $𝑅 \subseteq 𝐴 \times 𝐵$ that satisfies the uniqueness condition of functions but not necessarily the totality condition. In other words, a partial function may not be defined for every element of $𝐴$ .

Terminology: Endofunction

An endofunction or square function over a set $𝐴$ is a function from $𝐴$ to itself, i.e. a function $𝑓 : 𝐴 \to 𝐴$ .

Definition 56: Identity Function

For any set $𝐴$ , the identity function on $𝐴$ , denoted ${id}_{𝐴}$ , is the endofunction from $𝐴$ to $𝐴$ defined by $𝑥 \mapsto 𝑥$ for all $𝑥 \in 𝐴$ .

Functions with Multiple Arguments

Definition 57: $𝑛$ -ary Function

An $𝒏$ -ary function is a function that takes $𝑛$ arguments. Formally, an $𝑛$ -ary function from sets $𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}$ to a set $𝐵$ is a function $𝑓 : 𝐴_{1} \times 𝐴_{2} \times \dots \times 𝐴_{𝑛} \to 𝐵$ .

Terminology: Unary, Binary, Ternary Functions

In Definition 57, when $𝑛 = 1$ , we call $𝑓$ a unary function; when $𝑛 = 2$ , we call $𝑓$ a binary function; and when $𝑛 = 3$ , we call $𝑓$ a ternary function. Also, when $𝑛 = 0$ , we call $𝑓$ a nullary function, which is just a constant element of $𝐵$ .

Function Composition and Iteration

Definition 58: Composition of Functions

Let $𝑓 : 𝐴 \to 𝐵$ and $𝑔 : 𝐵 \to 𝐶$ be functions. The composition of $𝑔$ and $𝑓$ , denoted $𝑔 \circ 𝑓$ , is the function from $𝐴$ to $𝐶$ defined by $(𝑔 \circ 𝑓) (𝑥) = 𝑔 (𝑓 (𝑥))$ for all $𝑥 \in 𝐴$ .

Theorem 13: Compositions Involving the Identity Function

Let $𝑓 : 𝐴 \to 𝐵$ be a function. Then ${id}_{𝐵} \circ 𝑓 = 𝑓 \circ {id}_{𝐴} = 𝑓$ .

Definition 59: Idempotent Function

A endofunction $𝑓 : 𝐴 \to 𝐴$ is idempotent if $𝑓 \circ 𝑓 = 𝑓$ .

Iteration, Transients, and Periods

Definition 60: Iterated Function

Let $𝑓 : 𝐴 \to 𝐴$ be an endofunction. The $𝒏$ ^th iterate of $𝑓$ , denoted $𝑓^{𝑛}$ , is defined recursively as follows:

𝑓^{0} = {id}_{𝐴}, 𝑓^{𝑛 + 1} = 𝑓 \circ 𝑓^{𝑛} for 𝑛 \geq 0 .

Definition 61: Trajectory of an Element under a Function

Let $𝑓 : 𝐴 \to 𝐴$ be an endofunction and let $𝑥 \in 𝐴$ . The trajectory of $𝑥$ under $𝑓$ , denoted ${traj}_{𝑓} (𝑥)$ , is the sequence of elements obtained by iteratively applying $𝑓$ to $𝑥$ :

{traj}_{𝑓} (𝑥) = (𝑥, 𝑓 (𝑥), 𝑓^{2} (𝑥), 𝑓^{3} (𝑥), \dots)

Example.

Let $𝑓 : ℕ \to ℕ$ be defined by $𝑥 \mapsto 𝑥^{2}$ . Then the trajectory of $2$ under $𝑓$ is:

{traj}_{𝑓} (2) = (2, 4, 16, 256, \dots, 2^{2^{𝑛}}, \dots)

Remark

While we are currently using $𝑓^{𝑛}$ to denote the $𝑛$ ^th iterate of a function, the notation $𝑓^{𝑛}$ may also be used to denote the $𝑛$ ^th power of a function in the context of function algebras, which is a different concept.

Definition 62: Periodic Element under a Function

Let $𝑓 : 𝐴 \to 𝐴$ be an endofunction and let $𝑥 \in 𝐴$ . We say that $𝑥$ is periodic under $𝑓$ if there exists a positive integer $𝑛$ such that $𝑓^{𝑛} (𝑥) = 𝑥$ . The smallest such positive integer $𝑛$ is called the period of $𝑥$ under $𝑓$ .

Theorem 14: Periodicity of Endofunctions with Finite Domains

Classification of Functions

Definition 63: Injective Function

A function $𝑓 : 𝐴 \to 𝐵$ is injective or one-to-one if no two distinct elements in $𝐴$ map to the same element in $𝐵$ . Formally:

𝑓 is injective iff \forall 𝑥_{1}, 𝑥_{2} \in 𝐴, 𝑓 (𝑥_{1}) = 𝑓 (𝑥_{2}) \Rightarrow 𝑥_{1} = 𝑥_{2} .

Definition 64: Surjective Function

A function $𝑓 : 𝐴 \to 𝐵$ is surjective or onto if every element in $𝐵$ is the image of at least one element in $𝐴$ . Formally:

𝑓 is surjective iff \forall 𝑦 \in 𝐵, \exists 𝑥 \in 𝐴 such that 𝑓 (𝑥) = 𝑦 .

Theorem 15: Alternative Characterization of Surjectivity

A function $𝑓 : 𝐴 \to 𝐵$ is surjective iff the range of $𝑓$ equal to its codomain $𝐵$ .

Definition 65: Bijection

A function $𝑓 : 𝐴 \to 𝐵$ is bijective if it is both injective and surjective. In other words, a bijection is a function that establishes a one-to-one correspondence between the elements of $𝐴$ and the elements of $𝐵$ .

Theorem 16: Inverse of a Bijection

Let $𝑓 : 𝐴 \to 𝐵$ be a bijection. Then there exists a unique function $𝑓^{- 1} : 𝐵 \to 𝐴$ such that $𝑓^{- 1} \circ 𝑓 = {id}_{𝐴}$ and $𝑓 \circ 𝑓^{- 1} = {id}_{𝐵}$ . The function $𝑓^{- 1}$ is called the inverse of $𝑓$ .

For this reason, bijective functions are also called invertible functions.

Exercises

Exercise 9.