# Functions

These lecture notes are mainly based on Rosen's (2011) *Discrete Mathematics and its Applications 7th Edition*.

Another fundamental structure in mathematics important to Computer Science is the function. Most programing language has the canonical type functions which can be called to transform inputs into the suitable function. CS also uses functions to create recursive algorithms and use functions to analyze algorithms.

##### Definition from Rosen (2011)

> Let $A$ and $B$ be non-empty sets. A **function** $f$ from $A$ to $B$ is an assignment of exactly one element of $B$ to each element of $A$. We write $f(a)=b$ if $b$ is the unique element of $B$ assigned by the function $f$ to the element $a$ of $A$. If $f$ is a function from $A$ to $B$, we write $f:A \to B$. Functions are also called **mappings** or **transformations**.


Describing Functions

##### Stating Assignments

Functions can be described by stating assignments from one set to the other. For example is a function that describes the transformation of numerical grades to letter grades can be described like this.
$$
\begin{align*}
f(1.00)&=``\text{A+}" \\
f(1.25)&=``\text{A}" \\
f(1.5)&=``\text{A}-" \\
f(1.75)&=``\text{B+}" \\
f(2)&=``\text{B}" \\
&\vdots
\end{align*}
$$

##### Formulas

Functions can also be defined using a formula
$$
f(x)=x^2
$$

##### Relations

A relation is some subset of the Cartesian product $A \times B$. A function can be defined in terms of a relation. Every ordered pair $(a,b)$ from $A \times B$ represents a transformation between two elements $a$ and $b$ or that $f(a)=b$.

### Friends of a function

##### Domain of $f$

Given a function $f$ such that $f: A \to B$, the set $A$ is called the **domain** of $f$. The The set $A$ is also called the **preimage** of $f$. For each pair of elements $a$ and $b$ such that $f(a)=b$, $a$ is called the preimage of $b$.

##### Range of $f$

Given a function $f$ such that $f: A \to B$, the set $B$ is called the **range** or the **codomain** of $f$. The The set $B$ is also called the **image** of $f$. For each pair of elements $a$ and $b$ such that $f(a)=b$, $b$ is called the image of $a$.

Two sets are said to be **equal** if they share the same domain, codomain, and mappings.

### Function operations

##### Definition from Rosen (2011)

>Let $f_1$ and $f_2$ be functions from $A$ to $\mathbb{R}$. Then, $f_1 +f_2$ and $f_1f_2$ are also functions from$A$ to $\mathbb{R}$ defined for all $x \in A$ by
>$$
>\begin{align*}
>(f_1+f_2)(x)&=f_1(x)+f_2(x) \\
>(f_1f_2)(x)&=f_1(x)f_2(x)
>\end{align*}
>$$
>

### Image of a Subset

##### Definition from Rosen (2011)

> Let $f$ be a function from $A$ to $B$ and let $S$ be a subset of $A$. The **image** of $S$ under the function $f$ is the subset of $B$ that consists of the images of $S$. The image of $S$ is denoted by $f(S)$, therefore
> $$
> f(S)=\{f(s)~|~s\in S\}
> $$
>


### One-to-One Functions

>A function $f$, such that $f: A \to B$, is said to be **one-to-one** or an **injunction**, if and only if
>$$
>\forall (a\in A) \forall (b \in B)(f(a)=f(b) \to a=b)
>$$
>

A function is **injective** if it is one-to-one

### Onto functions

> A function $f$, such that $f:A \to B$ is called **onto** or a **surjection**, if and only if
> $$
> \forall (b\in B) \exists (a \in A)(f(a)=b)
> $$
>

A function is **surjective** if it is onto.

A function is a **one-to-one correspondence** or **bijective** if it is both injective and surjective.

> An injunction but not a surjection

> A surjection but not an injunction

> Neither an injunction nor a surjection

> A bijection

> Not a function

### Proving the Properties of functions

Given a function $f$ such that $f:A \to B$

**The function $f$ can be shown to be injective** by demonstrating that for arbitrary elements of the domain $a_1,a_2 \in A$, $f(a_1)=f(a_2) \to a_1=a_2$.

**The function $f$ can be shown to be not injective** by demonstrating that for some specific elements of the domain $a_1,a_2 \in A$ , $a_1 \neq a_2 \land f(a_1)=f(a_2)$.

**The function $f$ can be shown to be surjective** by demonstrating that for an arbitrary element $b\in B$ you can construct some element $a \in A$ where $f(a)=b$.

**The function $f$ can be shown to be not surjective** by demonstrating that for some specific elements $b \in B$ and for an arbitrary $a \in A$, $f(a) \neq b$.

### Inverse of a function

> Let $f$ be a bijection such that $f: A \to B$. The **inverse function** denoted by $f^{-1}$ is the function that assigns some element $b \in B$ to the unique element $a \in A$ such that $f(a) = b$. Therefore $f^{-1}(b)=a$.


A function should be bijective so that it has an inverse. If a function is not injective, It's inverse will not be a function since some elements $a_1,a_2\in A$, and $b\in B$ (such that $a_1\neq a_2$) will satisfy $f(a_1)=f(a_2)=b$, therefore $f^{-1}(b)=a_1\land f^{-1}(b)=a_2 $ which is a contradiction since $a_1 \neq a_2$. If a function is not surjective, some elements $b \in B$ will have no assignment from $A$ ($\neg \exists (a \in A)(f(a)=b)$ ). Therefore there will be no value that satisfies $f^{-1}(b)$. This means that for a function is **invertible** if and only if it is bijective.

### Composition of Functions

> Let $f$ be a function such that $f:A \to B$ and let $g$ be a function such that $g: B \to C$. The composition of $g$ and $f$ denoted by $(g \circ f)(a)=g(f(a))$.


To get the value of $(g \circ f)(x)$ first you need to find the value $x$ of $f$ and apply that value ($f(x)$) to $g$ to get $g(f(x))$.

### Graphs of functions

> Let $f$ be a function such that $f: A \to B$. The **graph** of $f$ is the set of ordered pairs
> $$
> \{(a,f(a))~|~a\in A\}
> $$
>

From these ordered pairs, you can represent the graph as a set of points into a plane


Graph of the function $f(x)=x^2$

### Floor and Ceiling Functions

> The **floor function** denoted by $\lfloor x \rfloor$ is a function that maps a real number $x$ to the largest integer less than or equal to $x$. The **ceiling function** denoted by $\lceil x \rceil$ maps a real number $x$ to the smallest integer greater than or equal to $x$.


Floor Function


Ceiling Function