{%hackmd @RintarouTW/About %}

# Function

:::info
**Function**/**mapping**/**map**/**transformation**

$$
f:\underbrace{A}_{domain}\rightarrow \underbrace{B}_{codomain}
$$

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 $\iff\forall (a,b),(a,c)\in f, b=c$
:::

### Functions between two sets (domain and codomain)

$$
f: A\rightarrow B
$$

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

:::info
$$
f: A\rightarrow B\\
f(x)=x^2 \iff f=\{(x,x^2)\mid x\in A, x^2\in B\}
$$
:::

### Image of an element of the domain

$$
f:A\rightarrow B\\
a\in A\implies f(a)\in B
$$

$f(a)$ is called the **image** of the $a$ elment in $A$ under the function $f$.

### Range of a function

$$
f:X\rightarrow Y\\
f(X)\iff \text{ the range of }f
$$

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

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

### Characteristic Function

$$
S\subseteq A, x\in A\\
\chi_S(x)=\cases{1,x\in S\\0,x\not\in S}
$$

### Kernel

:::info
$$
f:A\rightarrow B\\
K\subseteq A\times A\\
K=\{(x,y)\mid x,y\in A, f(x)=f(y)\}
$$
:::

Kernel is an equivalence relation.

- reflexive
$$
\forall x\in A,f(x)=f(x)\\
\therefore (x,x)\in K
$$
- symmetric
$$
\forall x,y\in A,f(x)=f(y)\implies f(y)=f(x)\\
\therefore (x,y)\in K\implies (y,x)\in K
$$
- transitive
$$
\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\implies (x,z)\in K
$$

## Properties of Functions

### Injection (one-to-one)

:::info
$$
f:A\rightarrow B\\
\forall a,b\in A,a\neq b,f(a)\neq f(b)\\
\Updownarrow\\
\forall a,b\in A,f(a)=f(b)\implies a=b
$$
:::

### Surjection (onto)

:::info
$$
f:A\rightarrow B\\
\forall b\in B,\exists a\in A, b=f(a)
$$
:::

### Bijection (one-to-one and onto)

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

## Counting

### Cardinality

Two sets have the same cardinality $\iff$ 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

:::info
$$
\cases{
X,Y\in finite\ set\\
f:X\rightarrow Y\\
}\\
|X|>n|Y|, n\geq 1\implies \exists b\in Y, n+1 \text{ elements $\in$ X are mapped to } b
$$
:::

## Function Composition

:::info
$$
\cases{
f:A\rightarrow B\\
g:B\rightarrow C
}\implies
\cases{
g\circ f:A\rightarrow C\\
g\circ f(x)=g(f(x))
}
$$
:::

### Function Composition is associative

:::info
$$
\cases{
f:A\rightarrow B\\
g:B\rightarrow C\\
h:C\rightarrow D\\
}\\
h\circ (g\circ f)=(h\circ g)\circ f
$$
:::

### Powers of Functions

$$
f:A\rightarrow B\\
f^1=f(a)\\
f^{n+1}=f(f^n(x))
$$

### The composition of injections is an injection

$$
\cases{
f:A\rightarrow B\\
g:B\rightarrow C\\
f,g\in injection
}
\implies g\circ f\in injection
$$

### The composition of surjections is a surjection

$$
\cases{
f:A\rightarrow B\\
g:B\rightarrow C\\
f,g\in surjection
}
\implies g\circ f\in surjection
$$

### Indentity Function

$$
i_A: A\rightarrow A, \forall a\in A, i(a)=a
$$

## Inverse Functions

:::info
$$
f:A\rightarrow A\\
g:A\rightarrow A\\
g\circ f=f\circ g=i_A\iff g=f^{-1}, f=g^{-1}
$$
$f^{-1}$ **undo** what $f$ does.
:::

### Bijections have inverses

$$
f:A\rightarrow B\\
\exists f^{-1}\iff f\text{ is a bijection}
$$

### Permutaion

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

### Inverse of a function

$$
\cases{
f:A\rightarrow B\\
g:B\rightarrow A\\
}\\
g\circ f=i_A, f\circ g=i_B
$$

###### tags: `math` `function`