學海無涯，思境無維；數乃六藝，理之始也。
或有一得足矣 愚千慮

$$$$

Function

Function/mapping/map/transformation

$$f:\underset{domain}{\underbrace{A}}\to \underset{codomain}{\underbrace{B}}$$

Function. A function from a set A into a set B is a relation from A into B such that each element of A is related to exactly one element of the set B. The set A is called the domain of the function and the set B is called the codomain.

• one-to-one or many-to-one
• one-to-many is not allowed
  $⟺\mathrm{\forall }(a,b),(a,c)\in f,b=c$

Functions between two sets (domain and codomain)

$$f:A\to B$$

There are

$B^A$ different possible functions between A(domain) and B(codomain).

$$\begin{gathered} f:A\to B \\ f(x)=x^2⟺f=\{(x,x^2)\mid x\in A,x^2\in B\} \end{gathered}$$

Image of an element of the domain

$$\begin{gathered} f:A\to B \\ a\in A⟹f(a)\in B \end{gathered}$$

$f(a)$ is called the image of the

$a$ elment in

$A$ under the function

$f$.

Range of a function

$$\begin{gathered} f:X\to Y \\ f(X)⟺\text{ the range of }f \end{gathered}$$

The range of a function is the set of images of it's codomain.

$$f(X)=\{y\mid \mathrm{\exists }x\in X,y=f(x)\}$$

Characteristic Function

$$\begin{gathered} S\subseteq A,x\in A \\ {\chi }_S(x)=\{\begin{array}{l}1,x\in S\\ 0,x\notin S\end{array} \end{gathered}$$

Kernel

$$\begin{gathered} f:A\to B \\ K\subseteq A\times A \\ K=\{(x,y)\mid x,y\in A,f(x)=f(y)\} \end{gathered}$$

Kernel is an equivalence relation.

• reflexive
  
  $$\begin{gathered} \mathrm{\forall }x\in A,f(x)=f(x) \\ \therefore (x,x)\in K \end{gathered}$$
• symmetric
  
  $$\begin{gathered} \mathrm{\forall }x,y\in A,f(x)=f(y)⟹f(y)=f(x) \\ \therefore (x,y)\in K⟹(y,x)\in K \end{gathered}$$
• transitive
  
  $$\begin{gathered} \mathrm{\forall }x,y,z\in A,f(x)=f(y),f(y)=f(z),f(x)=f(z) \\ \therefore (x,y)\in K,(y,z)\in K⟹(x,z)\in K \end{gathered}$$

Properties of Functions

Injection (one-to-one)

$$\begin{gathered} f:A\to B \\ \mathrm{\forall }a,b\in A,a\ne b,f(a)\ne f(b) \\ \Updownarrow \\ \mathrm{\forall }a,b\in A,f(a)=f(b)⟹a=b \end{gathered}$$

Surjection (onto)

$$\begin{gathered} f:A\to B \\ \mathrm{\forall }b\in B,\mathrm{\exists }a\in A,b=f(a) \end{gathered}$$

Bijection (one-to-one and onto)

A function is a bijection if it's one-to-one and onto.

Counting

Cardinality

Two sets have the same cardinality

$⟺$ exists a bijection

$f$ between the two sets.

Cardinality = the number of elements in a set

Countable Set

If a set is finite or has the same cardinality as the set of positive integers, it is called a countable set.

countablly infinite

The Pigeonhole Principle

$$\begin{gathered} \{\begin{array}{l}X,Y\in finiteset\\ f:X\to Y\end{array} \\ |X|>n|Y|,n\ge 1⟹\mathrm{\exists }b\in Y,n+1\text{ elements }\in \text{ X are mapped to }b \end{gathered}$$

Function Composition

$$\{\begin{array}{l}f:A\to B\\ g:B\to C\end{array}⟹\{\begin{array}{l}g\circ f:A\to C\\ g\circ f(x)=g(f(x))\end{array}$$

Function Composition is associative

$$\begin{gathered} \{\begin{array}{l}f:A\to B\\ g:B\to C\\ h:C\to D\end{array} \\ h\circ (g\circ f)=(h\circ g)\circ f \end{gathered}$$

Powers of Functions

$$\begin{gathered} f:A\to B \\ {f}^1=f(a) \\ {f}^{n+1}=f(f^n(x)) \end{gathered}$$

The composition of injections is an injection

$$\{\begin{array}{l}f:A\to B\\ g:B\to C\\ f,g\in injection\end{array}⟹g\circ f\in injection$$

The composition of surjections is a surjection

$$\{\begin{array}{l}f:A\to B\\ g:B\to C\\ f,g\in surjection\end{array}⟹g\circ f\in surjection$$

Indentity Function

$$i_A:A\to A,\mathrm{\forall }a\in A,i(a)=a$$

Inverse Functions

$$\begin{gathered} f:A\to A \\ g:A\to A \\ g\circ f=f\circ g=i_A⟺g=f^{-1},f=g^{-1} \end{gathered}$$

$f^{-1}$ undo what

$f$ does.

Bijections have inverses

$$\begin{gathered} f:A\to B \\ \mathrm{\exists }{f}^{-1}⟺f\text{ is a bijection} \end{gathered}$$

Permutaion

A bijection of a set into itself is called a permuation of a.

Inverse of a function

$$\begin{gathered} \{\begin{array}{l}f:A\to B\\ g:B\to A\end{array} \\ g\circ f=i_A,f\circ g=i_B \end{gathered}$$

tags: math function