1. What is a function

What is a function?

Function

Let $A$ and $B$ be any sets. A function from $A$ to $B$ is a rule $f$ that associates each element of $A$ with exactly one element of $B$.

If $f$ associates $x\in A$ with $y\in B$, then we write $\boxed{f(x)=y}$ and say ”$f$ of $x$ is $y$” or ”$f$ maps $x$ to $y$” or the “value of $f$ at $x$ is $y$”.

If $y$ is a function from $A$ to $B$, then we write: $\boxed{f:A\to B}$.

Function Rules

We call $A$ the domain of $f$ and $B$ the codomain of $f$.

• every element of the domain has to be mapped somewhere in the codomain (but this does not have to apply in reverse)
• one element cannot be mapped to 2 different places (but it can happen that $2$ different elements are mapped to the same place)

Link to original

Example 1

Let $H$ be the set of all humans, alive or dead. Making $H\to H$ associations, are the following functions or not:

• $\boxed{f(x)\text{ is a parent of }x}$ Not a function: people have two parents
• $f(x)\text{ is the mother of }x$ Function: each person has exactly one mother
• $f(x)\text{ is the oldest child of }x$ Not a function: some people have no children
• $f(x)\text{ is the set of all children of }x$ This is a function but it is not a $H\to H$ function because each person is associated with a set of people. This $f$ is a $H\to P(H)$ function.

Link to original

2. Different ways of describing functions

Different ways of describing functions

• 7. Describing functions by recursion

By associations

Let $A=\{a,b,c\}$ and $B=\{1,2,3\}$. We can describe a function $f:A\to B$ by listing all its associations:

• $f(a)=1$
• $f(b)=1$
• $f(c)=2$

We can describe it by using points and arrows:

We can describe the same $f$ by drawing its graph:

A function is a rule, sometimes we can describe it by a single formula, let $A=B=\mathbb{Z}$, for every $x\in \mathbb{Z}$, let:

$$\boxed{f(x)=6x+28}$$

Hence, for example $f(2)=6\times 2+28=40$.

By case distinction

Sometimes the rule can only be described by case distinction, let $A=B=\mathbb{N}$, for every $n\in \mathbb{N}$, let:

$$g(n)=\{\begin{array}{ll}{2}^n,& \text{if }n\text{ is odd}\\ 3n^2+n+1,& \text{if }n\text{ is even}\end{array}$$

Hence, for example $g(4)=3\times 4^2+4+1=53$ and $g(3)=2^3=8$.

Without any formula

The rule may be described without any mathematical formula.

Let $A=\{E|E\text{ is a healthy African elephant}\}$. Let $B=\{e|e\text{ is an elephant ear}\}$.

For every $E\in A$, let $l(E)=E\text{’s left ear}$.

Tuples

From topic 3. Some useful functions.

A tuple can be thought of as a function. For example, the 5-tuple $(22,14,55,1,700)$ can be thought of as a listing of the values of the function $f:\{0,1,2,3,4\}\to \mathbb{N}$ defined by:

$$f(0)=22,f(1)=14,f(2)=5,f(3)=1,f(4)=700$$

Infinite Sequence

An infinite sequence of objects can be thought of as a function.

For example, take $(b_0,b_1,...,b_n)$ is an infinite sequnce of objects from a set $S$. This sequence can be thought of as a listing of the values of the function $f:\mathbb{N}\to S$ defined by:

$$f(n)=b_n$$Link to original

3. Some useful functions

Useful functions

Floor function

Floor function

The floor function, $\lfloor \rfloor :\mathbb{R}\to \mathbb{Z}$, assigns any real number $x$ to the largest integer that is less than or equal to $x$.

Examples:

• $\lfloor \frac{1}{2}\rfloor =0$
• $\lfloor -\frac{3}{2}\rfloor =-2$
• $\lfloor 2.3\rfloor =3$

Link to original

Ceiling function

Ceiling function

The ceiling function, $\lceil \rceil :\mathbb{R}\to \mathbb{Z}$, assigns any real number $x$ to the smallest integer that is greater than or equal to $x$.

Examples:

• $\lceil \frac{1}{3}\rceil =1$
• $\lceil -\frac{5}{4}\rceil =-1$

Link to original

Properties of Floor and Ceil

Here are some simple properties of both floor and ceil functions.

$$\begin{array}{c}x-1<\lfloor x\rfloor \le x\le \lceil x\rceil <x+1\\ \lfloor -x\rfloor =-\lceil x\rceil \\ \lceil -x\rceil =-\lfloor x\rfloor \end{array}$$

Functions with multiple arguments

If the domain of a function $f$ is a Cartesian product $A_1\times ...\times A_n$, we can say that:

• $f$ has arity $n$

  Arity

  Arity is the number of arguments or operands taken by a function.

  Link to original

• $f$ is an $n$-ary function
• $f$ has $n$ arguments

In this case, for each $n$-tuple $(x_1,...,x_n)\in A_1\times ...\times A_n$, $\boxed{f(x_1,...,x_n)}$ denotes the value of $f$.

Binary function

A binary function $f$ has two arguments.

For binary functions, we may write either of:

• $f(x,y)=z$ $+(4,5)=9$
• $xfy=z$ $4+5=9$

Link to original

Link to original

4. Functions and relations

Functions and relations

Functions are special binary relations.

A function $f:A\to B$ can be considered as a relation from $A$ to $B$:

$$\{(a,b)\in A\times B|f(a)=b\}$$

Relations that are also functions have two special properties, following from function rules:

• For every element $a\in A$, there is some $b\in A$ with $(a,b)$ being in the relation.
• No two ordered pairs in the relation have the same first element.

For example:

• Not a function: $\{(x,y)\in \mathbb{N}\times \mathbb{N}|y=x-1\}$ $0$ is not mapped.
• Function: $\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|y=x-1\}$ $f(n)=n-1$
• Not a function: $\{(x,y)\in \mathbb{N}\times \mathbb{R}|x=y^2\}$ $(25,5)$ and $(25,-5)$ are both present in the relation.
• Not a function: $\{(x,y)\in \mathbb{N}\times \mathbb{N}|x=y^2\}$ $2$ is not mapped.
• Function: $\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|y=x^2\}$ $f(n)=n^2$

Link to original

5-6. Properties of functions

Properties of functions

Injective function

Injective function

A function $f:A\to B$ is called a one-to-one or injective function if it maps distinct elements of $A$ to distinct elements of $B$.

Example of a Injective mapping

Alternatively: $f$ is one-to-one if for all elements $x,y$ in $A$, if $x\ne y$ then $f(x)\ne f(y)$.

Link to original

Surjective function

Surjective function

A function $f:A\to B$ is called onto or a surjective function if every element $b$ in $B$ can be obtained as $b = f(a)$ for some $a$ in $A$. To summarise, the entire codomain must be mapped to the domain.

Example of a Surjective mapping

In general, this might not be the case. If $f$ is an $A\to B$ function, we know that for every $a\in A$, we have $f(a)\in B$. If the range of $f$ can be a proper subset of $B$ (which is the codomain), then it is not onto.

Link to original

Bijection

Bijection (function)

A function is called a bijection if it is both an [[Injective function|injective]] and [[Surjective function|surjective]] function.

Example of a Bijection mapping	Example of neither injective or surjective mapping

Link to original

Inverse Functions

Inverse (function)

Bijections always come in pairs, if $f:A\to B$ is a bijection, then there is a function $\boxed{f^{-1}:B\to A}$, it is called the inverse of $f$, defined by:

$$f^{-1}(b)=a\text{ whenever }f(a)=b$$

This also means $f^{-1}$ is also a bijection, so we have:

$$\begin{array}{rl}{f}^{-1}(f(a))& =a\text{ for every }a\in A\\ f^{-1}(f(b))& =b\text{ for every }b\in B\end{array}$$

For example, let Odd and Even be the sets of odd and even natural numbers, respectively. Define a function $f:\text{Odd }\to \text{ Even}$ by $f(n)=n-1$. Then $f$ is a bijection and its inverse $f^{-1}:\text{Even }\to \text{ Odd}$ is defined as $f^{-1}(n)=n+1$.

Link to original

Identity Function

Identity function

For every set $A$, its identity function ${\text{id}}_A:A\to A$ is defined for all $a\in A$ as: $$ \text{id}_A(a) = a $$

${\text{id}}_A$ is also a bijection and its inverse is itself.

Link to original

Characteristic function

Characteristic function

Let $S$ be a set. For every subset $A\subseteq S$, its characteristic function, $f_A:S\to \{0,1\}$ is defined for all $x\in S$ by: $$ f_A(x) = \begin{cases} 1, &\text{if } x \in A, \\ 0, &\text{if } x \notin A \end{cases} $$

If $A\subseteq \mathbb{N}$ then $f_a:\mathbb{N}\to \{0,1\}$ can be represented by an infinite 0-1 sequence.

For example, given $\text{Odd }\subseteq \mathbb{N}$, $f_{\text{odd}}=0101010101[..]$.

Link to original

Link to original

7. Describing functions by recursion

Describing $N\to N$ functions by recursion

Factorial

Factorial

The factorial function, $\boxed{n!}$, defined recursively is: ?

• Basis step: $f(0)=1$ and $f(1)=1$.
• Recursive step: If $n>1$ then $f(n)=f(n-1)\times n$.

Link to original

Fibonacci

Fibonacci function

Leonardo Fibonacci asked in 1202: Let’s start with a pair of rabbits that needs one month to mature, and assume that every month each pair produces a new pair that becomes productive after one month. How many new pairs are produced each month?

The Fibonacci function, defined recursively is:

• Basis step: $f(0)=1$ and $f(1)=1$.
• Recursive step: If $n>1$ then $f(n)=f(n-2)+f(n-1)$.

This generates a series of integers: $0,1,1,2,3,5,8,13,21,[...]$

Link to original

Link to original

8. Function composition

Function composition

Composition of functions

Let $g:A\to B$ and $f:B\to C$ be functions. The composition of $f$ and $g$ is the function $\boxed{ (f \circ g): A \rightarrow C }$, can also define this for all $a \in A$ as: $$ (f \circ g)(a) = f(g(a)) $$

We only define the composition $f\circ g$ when the codomain of $g$ is equal to the domain of $f$.

Link to original

title: Example
Let $X = \{ a,b,c \}$ and $Y = \{ 1,2,3 \}$.
Let the function $g: X \rightarrow X$ be defined by:
 
$$
	g(a) = b, \hspace{12px} g(b) = c, \hspace{12px} g(c) = a
$$
 
Let the function $f: X \rightarrow Y$ be defined by:
 
$$
	f(a) = 3, \hspace{12px} f(b) = 2, \hspace{12px} f(c) = 1
$$
 
Then:
- $(f \circ g)(a) = f(g(a)) = f(b) = 2$
- $(f \circ g)(b) = 1$
- $(f \circ g)(c) = 3$
- $(g \circ g)(a) = c$
- $(g \circ g)(b) = a$
- $(g \circ g)(c) = b$

Properties of composition

• Even if both $f$ and $g$ are defined, $f\circ g$ and $g\circ f$ can differ. Let $f$ and $g$ be both $\mathbb{Z}\to \mathbb{Z}$ functions, defined by $f(x)=2x+3$ and $g(x)=3x+2$, then:
  • $(f\circ g)(x)=6x+7$
  • $(g\circ f)(x)=6x+11$
• $\circ$ is associative: $\boxed{f\circ (g\circ h)=(f\circ g)\circ h}$
• If $f:A\to B$ is a bijection then $\boxed{f^{-1}\circ f={\text{id}}_A}$ and $\boxed{f\circ f^{-1}={\text{id}}_B}$
• For any function $f:A\to B$, $\boxed{f\circ {\text{id}}_A={\text{id}}_B\circ f=f}$

Link to original

9. Countable sets

Countable sets

For finite sets, we can simply count the number of elements in each. If finite sets have the same number of elements, then there is always a bijection between them.

Two infinite sets have the same size if there is a bijection between them.

Countable set

We can call a set $A$ countable if it is either finite or there is a [[Bijection (function)|bijection]] between $A$ and $\mathbb N$.

For example:

• ${\text{id}}_N:\mathbb{N}\to \mathbb{N}$ is a bijection hence $N$ is countable.
• Given Odd is the set of odd natural numbers, we find that even if $\text{Odd}\subset \mathbb{N}$, it still has the same size as $\mathbb{N}$. The function $f:\mathbb{N}\to \text{Odd}$ defined by $\boxed{f(x)=2x+1}$ is a bijection.

Link to original

$\mathbb{N}\times \mathbb{N}$ is countable

title: Not in exam.

We need to describe a bijection between $\mathbb{N}\times \mathbb{N}$ and $\mathbb{N}$. We arrange the ordered pairs in $\mathbb{N}\times \mathbb{N}$ in such a way that they can be easily counted:

$$\begin{array}{rl}(0,0)& ⟺0,\\ (0,1),(1,0)& ⟺1,2,\\ (0,2),(1,1),(2,0)& ⟺3,4,5,\\ (0,3),(1,2),(2,1),(3,0)& ⟺6,7,8,9,\\ & [...]\end{array}$$

We can describe this $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ bijection by

$$(m,n)⟺(1+2+...+(m+n))+m$$Link to original

10. Not all sets are countable

Not all sets are countable

title: Not in exam.

The power set $P(\mathbb{N})$ of $\mathbb{N}$ is not countable:

$$\neg \exists f(f\text{ is a bijection between }\mathbb{N}\text{ and }P(\mathbb{N}))$$

There are more subsets of numbers than numbers.

We can show that $\forall f(\text{if }f:\mathbb{N}\to P(\mathbb{N})\text{ then }f\text{ is not onto})$:

• Let $f:\mathbb{N}\to P(\mathbb{N})$ be an arbitrary function.
• Then, for every $n\in \mathbb{N}$, $f(n)$ is a subset of $\mathbb{N}$.
• Now take the following subset $D_f$ of $\mathbb{N}$: $\boxed{D_f=\{n\in \mathbb{N}|n\notin f(n)\}}$

We show that $D_f$ is not in the range of $f$, that is, for every $n\in \mathbb{N}$, $D_f\ne f(n)$: Take an arbitrary $n\in \mathbb{N}$, then there are two cases, either $n\in D_f$ or $n\notin D_f$.

• If $n\in D_f$, then $n$ shoudl have the property describing $D_f$, so $n\notin f(n)⇝\boxed{D_f⊈f(n)}$
• If $n\notin D_f$, then the property describing $D_f$ does not hold for $n$, so $n\in f(n)⇝\boxed{f(n)\notin D_f}$

Link to original