Functions

  • A function between two sets is a relation $f \subseteq A \times B$ such that for every $a \in A$
    • There is some $b \in B$ such that $(a, b) \in f$
    • If $(a, b) \in f$ and $(a, c) \in f$ then $b = c$
  • Equivalently, for every $a \in A$ - there is exactly one $b \in B$ such that $(a, b) \in f$
    • We write $b = f(a)$ and $f: A \rightarrow B$

In effect, the function defines a mapping between set A and set B.

A function must define a mapping for every element of $A$ but does NOT need to do so for set $B$.

Terminology

Let $f: A \rightarrow B$ be a function:

  • $A$ is the domain of $f$
  • $B$ is the codomain of $f$
  • For every $a \in A$ then $f(a)$ is the image of $a$.
  • The set $f(A) = {f(a) | a \in A}$ is the image of $A$
  • The image may not contain every element of $B$ depending on the type of function (see below)

Invertible Functions

A function $f: A \rightarrow B$ is invertible if the relation $f^{-1}$ is a function (which is then called its inverse)

If $f:A \rightarrow B$ is invertible, then for every $a \in A$…

\[ f^{-1}\left(f(a)\right) = a \]

Function Example - ECC

Assume two sets of bits.

  • Domain: $A = {0, 1}^n$
  • Codomain: $B \subseteq {0, 1}^{n+1}$
    • $B$ contains all the bit strings of length $n+1$ where sum of bits is even
  • bitParity can be a function $A \rightarrow B$
    • $bitParity(b_1, b_2, …, b_n) = (b_1, b_2, …, b_n, n_{n+1})$, where $b_{n+1} = b_1 + b_2 + … + b_n \textrm{ mod } 2$
  • If the emessage is not in $B$ then there was an error
  • Otherwise, $bitparity$ is invertible, $bitparity^1: B \rightarrow A$

Injective Functions

An injective function can be thought of as a “one-to-one” relation, wherein each element that is mapped to, is only mapped to once at most.

Formal definition:

\[ \textrm{For every } a_1, a_2 \in A\\ f(a_1)=f(a_2) \textrm{ implies } a_1 = a_2 \]

If $f: A \rightarrow B$ is injective, then $f$ defines a bijection between $A$ and $f(A)$

Non-injective Functions

Non-injective functions can be one-to-many or many-to-one.
That is to say, there will be a solution for the following constraint:

\[ f(a_1) = f(a_2) \textrm{ where } a_1 \neq a_2 \]

Surjective Functions

A surjective function is a function that has a mapping for every element of $A$ and $B$, that is to say:

\[ \textrm{For every } b \in B \textrm{ there is } a \in A \textrm{ such that} b=f(a) \]

It can also be said that “f is onto”

A non-surjective function may have elements of $B$ that are left without a mapping from $A$
If $f$ is surjective, then $f(A) = B$ (image and codomain are the same)

Bijective Functions

A function $f: A \rightarrow B$ is bijective (a bijection) if it is both injective and surjective.

That is to say, it is a one-to-one mapping wherein every element in both sets $A$ and $B$ have mappings or are mapped onto.

Formally:

\[ \textrm{For every } a_1, a_2 \in A\\ f(a_1)=f(a_2) \textrm{ implies } a_1 = a_2\\ \textrm{Furthermore, for every } b \in B \textrm{ there is } a \in A \textrm{ such that } b = f(a) \]
A function is only invertible if and only if it is bijective!!!

Example

\[ f(x) = x^2 + 2 \left(\textrm{as } f : \mathbb{Z} \rightarrow \mathbb{N}\right) \]

The above function is not an injection. (see: $x = 3$ and $x = -3$)
The above function is also not a surjection. ($f(x) = 7$, therefore $x^2 + 2 = 7$, then $x = \pm\sqrt{5}$ which is not in the domain)