Functions#
Informally, a function is a rule that assigns a possible output for each element in a set \(D\) of possible inputs called the domain.
Formally, a function \(f\) is a (in)finite set of pairs \((a, b)\) no two of which share the same first entry. The domain itself can consist of pairs of numbers.
The output \(f(q)\) is called the image of the input \(q\) under the function \(f\).
The input \(q\) is called the pre-image of the output \(f(q)\).
If \(r = f(q)\) then we say that \(q\) maps to \(r\) under \(f\).
\(q\) maps to \(r\) is denoted \(q \mapsto r\).
The set \(D\) of possible inputs is called the domain of the function.
The co-domain is a set from which the function’s output values are chosen (i.e., the co-domain is a set of possible outputs). There is freedom in choosing the co-dimain because not all its members need to be outputs.
A function \(f\) with domain \(D\) and co-domain \(F\) is denoted \(f : D \to F\) and is pronounced “a function from \(D\) to \(F\)” or “a function that maps \(D\) to \(F\)”.
The image of a function \(f\) is called the range and it is defined as the set of images of all of the function’s domain elements (i.e., the set of values of the co-domain which actually occur as function outputs).
Let \(D\) and \(F\) be sets. \(F^D\) denotes the set of all functions from \(D\) to \(F\).
For example, the set of functions from the set \(W\) of words to the set \(\mathbb{R}\) of real numbers is denoted \(\mathbb{R}^W\).
For any finite sets \(D\) and \(F\) it is the case that \(|F^D| = |F|^{|D|}\).
For any domain \(D\) there is a function \(\text{id}_D : D \to D\) called the identity function for \(D\) and is defined by \(\text{id}_D(d) = d\) for every \(d \in D\).
Function composition is an operation that combines two functions and produces a new function.
Let \(f : A \to B\) and \(g : B \to C\) be two functions. The function \(g \circ f\) called the composition of \(g\) and \(f\) is a function whose domain is \(A\) and whose co-domain is \(C\) defined by \((g \circ f)(x) = g(f(x))\) for every \(x \in A\).
If the image of \(f\) is not contained in the domain of \(g\) then \(g \circ f\) is not a legal expression.
For example
\( \begin{aligned} f &: \mathbb{R} \to \mathbb{R} & f(x) &= x + 1 \\ g &: \mathbb{R} \to \mathbb{R} & g(x) &= y^2 \\ g \circ f &: \mathbb{R} \to \mathbb{R} & (g \circ f)(x) &= (x + 1)^2 \\ \end {aligned} \)
Some examples#
\( \begin{aligned} D &= \{ 1, 2, 3, \dots \} \\ f &= \{ (1, 2), (2, 4), (3, 6), \dots \} \\ f &: \mathbb{P} \to \mathbb{E} \\ f &: \mathbb{P} \to \mathbb{P} \\ f &: \mathbb{P} \to \mathbb{Z} \\ \end {aligned} \)
\( \begin{aligned} D &= \{ 1, 2, 3, \dots \} \times \{ 2 \} = \{ (1, 2), (2, 2), (3, 2), \dots \} \\ f &= \{ ((1, 2), 2), ((2, 2), 4), ((3, 2), 6), \dots \} \\ f &: \mathbb{P} \times \{ 2 \} \to \mathbb{E} \\ f &: \mathbb{P} \times \{ 2 \} \to \mathbb{P} \\ f &: \mathbb{P} \times \{ 2 \} \to \mathbb{Z} \\ \end {aligned} \)
\( \begin{aligned} D &= \{ 1, 2, 3, \dots \} \times \{ 1, 2, 3, \dots \} = \{ (1, 1), (1, 2), (1, 3), \dots, (2, 1), (2, 2), (2, 3), \dots \} \\ f &= \{ ((1, 1), 1), ((1, 2), 2), ((1, 3), 3), \dots, ((2, 1), 2), ((2, 2), 4), ((2, 3), 6), \dots \} \\ f &: \mathbb{P} \times \mathbb{P} \to \mathbb{P} \\ f &: \mathbb{P} \times \mathbb{P} \to \mathbb{Z} \\ \end {aligned} \)
Let \(\Sigma = \{ a, \dots, z \}\) and \(0 \le k \lt 26\).
The Caesar Cipher is just the shift cipher with \(k = 3\).
The process of encrypting a single character according to the shift cipher with key \(k\) may be defined as the composition of the following three functions.
\( \begin{aligned} \text{Encode} &:& \Sigma &\to \{ 0, \dots, 25 \} &\text{Encode} &= \{ (a, 0), \dots, (z, 25) \} \\ \text{Enc}_k &:& \{ 0, \dots, 25 \} &\to \{ 0, \dots, 25 \} &\text{Enc}_k(x) &= (x + k) \mod 26 \\ \text{Decode} &:& \{ 0, \dots, 25 \} &\to \Sigma &\text{Decode} &= \{ (0, a), \dots, (25, z) \} \\ \text{Decode} \circ \text{Enc}_k \circ \text{Encode} &:& \Sigma &\to \Sigma \\ \end{aligned} \)
Let \(p = p_1 \dots p_x\) be a string of arbitrary length \(x \in \mathbb{P}\).
\( \begin{aligned} \text{Encode} &:& p &= p_1 \dots p_x &\to&& m &= m_1 \dots m_x \\ \text{Enc}_k &:& m &= m_1 \dots m_x &\to&& c &= c_1 \dots c_x \\ \text{Decode} &:& c &= c_1 \dots c_x &\to&& p &= p_1 \dots p_x \\ \text{Decode} \circ (\text{Enc}_k \circ \text{Encode}) &:& p &= p_1 \dots p_x &\to&& p &= p_1 \dots p_x \\ \end{aligned} \)
\(\text{Enc}_k(m_1 \dots m_x) = c_1 \dots c_x \,\,\text{where}\,\, c_i = (m_i + k) \mod 26\)
Properties of function composition#
Associativity of function composition#
Let \(f,g,h\) be functions.
\( h\circ(g\circ f)=(h\circ g)\circ f \)
if the compositions are legal.
Proof
Let \(x\) be any member of the domain of \(f\).
\( \begin{aligned} (h\circ(g\circ f))(x) &=h((g\circ f)(x))\\ &=h(g(f(x)))\\ &=(h\circ g)(f(x))\\ &=((h\circ g)\circ f)(x)\\ \end{aligned}\\ \blacksquare \)
Associativity of function composition means that parentheses in composition expressions aren’t necessary.
\(h\circ(g\circ f)=(h\circ g)\circ f=h\circ g\circ f\)
Inverse Function#
Let \(f,g\) be functions.
\(f\) and \(g\) are called functional inverses of each other if both \(f\circ g\) is defined and is the identity function on the domain of \(g\) and \(g\circ f\) is defined and is the identity function on the domain of \(f\).
Not every function has an inverse. A function that has an inverse is called invertible.
Example of Inverse Function: Caesar Cipher#
\( \begin{aligned} h\circ f&:\{a,...,z\}\rightarrow\{a,...,z\}=\text{id}_{\{a,...,z\}}\\ f\circ h&:\{0,...,25\}\rightarrow\{0,...,25\}=\text{id}_{\{0,...,25\}}\\ \end{aligned} \)
Injection (one-to-one)#
Let \(f:D\rightarrow F\) be a function.
\(f\) is one-to-one if for every \(x,y\in D\), \(f(x)=f(y)\implies x=y\).
Lemma: an invertible function is one-to-one#
Lemma
An invertible function is one-to-one.
Proof by Contradiction
Suppose \(f\) is not one-to-one.
Let \(x_1,x_2\) be distinct elements of the domain such that \(f(x_1)=f(x_2)\).
Let \(y=f(x_1)\).
Assume \(f\) is invertible.
Then \(f^{-1}(y)=x_1\) and \(f^{-1}(y)=x_2\).
But both cannot be true.
Contradiction.
\(\blacksquare\)
Surjection (onto)#
Let \(f:D\rightarrow F\) be a function.
\(f\) is onto if for every \(z\in F\), there exists \(x\in D\) such that \(f(x)=z\).
Lemma: an invertible function is onto#
Lemma
An invertible function is onto.
Proof by Contradiction
Suppose \(f\) is not onto.
Let \(\hat{y}\) be an element of the codomain such that \(\hat{y}\) is not the image of any domain element.
Assume \(f\) is invertible.
Then \(\hat{y}\) has an image \(\hat{x}\) under \(f^{-1}\).
But the definition of inverse implies that \(f(\hat{x})=\hat{y}\).
Contradiction.
\(\blacksquare\)
Bijection (one-to-one correspondence)#
A function is a one-to-one correspondence iff it is both one-to-one and onto.
Function Invertibility Theorem#
A function is invertible iff it is one-to-one and onto.
First direction
If a function if invertible, then it is both one-to-one and onto.
Proof
By the above lemmas.
\(\blacksquare\)
Second direction
If a function is both one-to-one and onto, then it is invertible.
Proof
Let \(f\) be both one-to-one and onto.
Let \(g\) be a function whose domain is the codomain of \(f\) such that for each element \(\hat{y}\) of the codomain of \(f\), since \(f\) is onto, \(f\)’s domain contains some element \(\hat{x}\) for which \(f(\hat{x})=\hat{y}\), and so \(g(\hat{y})=\hat{x}\).
It is claimed that \(g\circ f\) is the identity function on \(f\)’s domain.
Let \(\hat{x}\) be any element of \(f\)’s domain, and let \(\hat{y}=f(\hat{x})\).
Since \(f\) is one-to-one, \(\hat{x}\) is the only element of \(f\)’s domain whose image under \(f\) is \(\hat{y}\). So \(g(\hat{y})=\hat{x}\).
This shows that \(g\circ f\) is the identity function.
It is also claimed that \(f\circ g\) is the identity function on \(g\)’s domain.
Let \(\hat{y}\) be any element of \(g\)’s domain.
By the definition of \(g\), \(f(g(\hat{y}))=\hat{y}\).
\(\blacksquare\)
Lemma: every function has at most one functional inverse#
Lemma
Every function has at most one functional inverse.
Proof
Let \(f:U\rightarrow V\) be an invertible function.
Let \(g_1,g_2\) be inverses of \(f\).
Show that for every element \(v\in V,g_1(v)=g_2(v)\) so that \(g_1\) and \(g_2\) are the same function.
Let \(v\in V\) be any element of the codomain of \(f\).
Since \(f\) is onto, there is some element \(u\in U\) such that \(v=f(u)\).
By the definition of inverse, \(g_1(v)=u\) and \(g_2(v)=u\).
Therefore, \(g_1(v)=g_2(v)\).
\(\blacksquare\)
Lemma: invertibility of the composition of invertible functions#
Lemma
If \(f\) and \(g\) are invertible functions and \(f\circ g\) exists, then \(f\circ g\) is invertible and \((f\circ g)^{-1}=g^{-1}\circ f^{-1}\).
The converse is not necessarily true.
Proof
Converse of Lemma
FALSE: If \(f\) and \(g\) are functions and \(f\circ g\) is invertible, then \(f\) and \(g\) are invertible.
Operations#
DEFINITION
Let \(A\) be a non-empty set.
A nullary operation on \(A\) is a constant \(a \in A\).
A unary operation on \(A\) is a function from \(A\) to \(A\).
A binary operation on \(A\) is a function from \(A \times A\) to \(A\).
A ternary operation on \(A\) is a function from \(A \times A \times A\) to \(A\).
In general, an \(n\) -ary operation on \(A\) is a function from \(\underbrace{A \times A \times \dots \times A}_{n \,\text{times}}\) to \(A\).
Notation: Binary Operations
Infix notation is standard in integer arithmetic
Prefix notation places the operation before its operands
Function notation is a special form of prefix notation
Operations, Functions, Computations, Procedures#
Procedures#
A procedure is a precise description of a computation.
A procedure accepts inputs called arguments and produces an output called the return value.
def mul (p : float,
q : float) -> float:
return p * q
Computations#
A computational problem is an input-output specification that a procedure might be required to satisfy.
[Example]
input: a pair \((p,q)\) of integers greater than \(1\)
output: the product \(pq\)
[Example]
input: an integer \(m\) greater than \(1\)
output: a pair \((p,q)\) of integers whose product is \(m\)
Operations vs Functions vs Computations vs Procedures#
Unlike a procedure, a function or computational problem does not specify how to compute the output from the input. There are often many different procedures that satisfy the same input-output specification, or that implement the same function.
[Example]
Integer Multiplication
long multiplication
Karatsuba algorithm (used by Python for long-integer multiplication)
Schönhage-Strassen algorithm (uses the FFT)
Fürer algorithm
Sometimes the same procedure can be used for different functions.
[Example]
Python procedure mul
multiplication of negative integers
multiplication of numbers that are not integers
Unlike a function, a computational problem need not specify a unique output for every input.
For each function \(f\), there is a corresponding computational problem.
[FORWARD PROBLEM]
Given an element \(a\) of \(f\)’s domain, compute \(f(a)\), the image of \(a\) under \(f\).
[BACKWARD PROBLEM]
Given an element \(r\) of the codomain of the function, compute any preimage (or report that none exists).
Theorem#
Let \(A\) be a nonempty set and let \(\mathscr{F}\) be the set of all bijections \(A \rightarrow A\).
The tuple \((\mathscr{F}, \circ)\) where \(\circ\) is function composition is a structure such that
\(\circ\) is associative
the identity function \(I_A\) is the identity element
every element in \(\mathscr{F}\) has an inverse \(f^{-1}\)
Proof
\(\mathscr{F}\) is closed under \(\circ\) (proved elsewhere).
\(\circ\) is associative on \(\mathscr{F}\) (proved elsewhere).
\(I_A\) is the identity element (proved elsewhere).
If \(f \in \mathscr{F}\), then \(f^{-1} \in \mathscr{F}\) (proved elsewhere).
\(f^{-1}\) is the inverse of \(f\) (proved elsewhere)