Functions

Definition

A function $f$ from $A$ to $B$, written $f: A \to B$, is a relation where each element of $A$ is related to exactly one element of $B$.

• Domain: $A$ (input set)
• Codomain: $B$ (output set)
• Range/Image: $\{f(a) \mid a \in A\} \subseteq B$ (actual outputs)

Notation

• $f(a) = b$ means $f$ maps $a$ to $b$
• $a \mapsto f(a)$ describes the mapping

Types of Functions

Injective (One-to-One)

Different inputs give different outputs: $\forall a_1, a_2 \in A: f(a_1) = f(a_2) \rightarrow a_1 = a_2$

Equivalently: $\forall a_1, a_2 \in A: a_1 \neq a_2 \rightarrow f(a_1) \neq f(a_2)$

Example: $f(x) = 2x$ on $\mathbb{R}$ is injective. Non-example: $f(x) = x^2$ on $\mathbb{R}$ is not injective ($f(-1) = f(1)$).

Surjective (Onto)

Every element in the codomain is mapped to: $\forall b \in B: \exists a \in A: f(a) = b$

Equivalently: $\text{range}(f) = B$

Example: $f(x) = x^3$ from $\mathbb{R}$ to $\mathbb{R}$ is surjective. Non-example: $f(x) = x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not surjective ($-1$ is not in range).

Bijective (One-to-One Correspondence)

Both injective AND surjective.

$f: A \to B \text{ is bijective} \iff |A| = |B| \text{ and } f \text{ is injective}$

Example: $f(x) = 2x + 1$ from $\mathbb{R}$ to $\mathbb{R}$ is bijective.

Cardinality Conditions

For finite sets $A$ and $B$ with $|A| = m$ and $|B| = n$:

Condition	Possible if
$f: A \to B$ injective	$m \leq n$
$f: A \to B$ surjective	$m \geq n$
$f: A \to B$ bijective	$m = n$

Counting Functions

Type	Count
All functions $A \to B$	$n^m$
Injective functions	$n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}$
Bijective functions	$n!$ (when $m = n$)

Function Composition

If $f: A \to B$ and $g: B \to C$, then $g \circ f: A \to C$: $(g \circ f)(a) = g(f(a))$

Properties

• Associative: $(h \circ g) \circ f = h \circ (g \circ f)$
• NOT commutative: $g \circ f \neq f \circ g$ in general
• $f \circ g$ injective $\Rightarrow$ $g$ injective
• $f \circ g$ surjective $\Rightarrow$ $f$ surjective
• $f, g$ bijective $\Rightarrow$ $g \circ f$ bijective

Inverse Functions

If $f: A \to B$ is bijective, its inverse $f^{-1}: B \to A$ satisfies: $f^{-1}(f(a)) = a \text{ for all } a \in A$ $f(f^{-1}(b)) = b \text{ for all } b \in B$

Properties

• $(f^{-1})^{-1} = f$
• $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$
• $f \circ f^{-1} = I_B$ and $f^{-1} \circ f = I_A$

Identity Function

$I_A: A \to A, \quad I_A(a) = a$

For any $f: A \to B$: $f \circ I_A = f = I_B \circ f$

Important Functions

Floor and Ceiling

$\lfloor x \rfloor = \text{largest integer } \leq x$ $\lceil x \rceil = \text{smallest integer } \geq x$

Properties:

• $\lfloor x \rfloor \leq x < \lfloor x \rfloor + 1$
• $\lceil x \rceil - 1 < x \leq \lceil x \rceil$
• $\lfloor x \rfloor = \lceil x \rceil$ iff $x \in \mathbb{Z}$
• $\lfloor -x \rfloor = -\lceil x \rceil$

Modulo Function

$a \mod n = a - n\lfloor a/n \rfloor$

The remainder when $a$ is divided by $n$.

Function Growth

Big-O Notation

$f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that: $|f(n)| \leq c \cdot |g(n)| \text{ for all } n \geq n_0$

Common Growth Rates

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

Other Notations

• $f(n) = \Omega(g(n))$: $f$ grows at least as fast as $g$
• $f(n) = \Theta(g(n))$: $f$ grows at the same rate as $g$
• $f(n) = o(g(n))$: $f$ grows strictly slower than $g$

Cardinality of Infinite Sets

Two sets have the same cardinality if there exists a bijection between them.

• Countably infinite: Same cardinality as $\mathbb{N}$ (e.g., $\mathbb{Z}$, $\mathbb{Q}$)
• Uncountable: Larger than $\mathbb{N}$ (e.g., $\mathbb{R}$, $\mathcal{P}(\mathbb{N})$)

$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$ $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} = \mathfrak{c}$