Notes@HKU by Jax

Functions

Introduction

Definition of functions

For non-empty sets AA and BB, a "function ff from AA to BB" is a relation from AA to BB such that for each a∈Aa \in A, there is exactly one b∈Bb \in B such that (a,b)∈f(a, b) \in f.

We write f:A→Bf: A \to B to denote that ff is a function from AA to BB.

Terminologies

For f:A→B,f(a)=bf: A \to B, \quad f(a) = b:

  • Domain: AA

  • Codomain: BB

  • bb is the image of aa under ff

  • aa is a preimage of bb under ff

  • The Range is the specific set of codomains that were assigned. It is always a subset of the codomain.

  • f:A→Rf: A \to \mathbb{R} is a real-valued function

  • f:A→Zf: A \to \mathbb{Z} is an integer-valued function

Combining functions

Combination of functions by addition or multiplication retain the same domain and codomain, i.e. f1,f2:A→B  ⟹  (f1+f2),(f1⋅f2):A→Bf_1,f_2: A \to B \implies (f_1 + f_2), (f_1 \cdot f_2): A \to B

Functions of a Subset

For f:A→B,S⊆Af: A\to B, \quad S \subseteq A, the image of S under f is:

f(S)={y ∣ ∃x∈S,f(x)=y}f(S) = \{y\ |\ \exists x \in S, f(x) = y\}

Characteristics of functions

CharacteristicDefinition
Injection / One-to-onef:R,f(x1)=f(x2)→x1=x2f: \mathbb{R},\quad f(x_1) = f(x_2) \to x_1 = x_2
Surjection / Onto∀y∃x:f(x)=y\forall y \exists x : f(x)=y
Bijection / One-to-one CorrespondenceBoth one-to-one and onto
Total∀x∈A∃y∈B:f(x)=y\forall x \in A \exists y \in B : f(x)=y
PartialNot total

Inverse functions

The inverse function f−1f^{-1} will inverse the mapping: f(a)=b→f−1(b)=af(a)=b\to f^{-1}(b) = a.

Only Bijection function can have an inverse function.

Composition of functions

The composition of functions f(g(x))f(g(x)) can be written as (f∘g)(x)(f \circ g)(x). The order is important.

The composition of function and its inverse will produce the input: (f∘f−1)(x)=(f−1∘f)(x)=x(f \circ f^{-1})(x) = (f^{-1}\circ f)(x) = x

Special functions

Ceiling and Floor functions

  • Ceiling function: ⌈x⌉=min⁡{n∈Z ∣ n≥x}\lceil x \rceil = \min\{n \in \mathbb{Z}\ |\ n \geq x\} (round up)
  • Floor function: ⌊x⌋=max⁡{n∈Z ∣ n≤x}\lfloor x \rfloor = \max\{n \in \mathbb{Z}\ |\ n \leq x\} (round down)

Other functions

You should be familiar with the exponential, logarithmic and factorial functions already.

Graph of functions

Graph of functions

The formal defintion of a graph is:

Graph(f)={(x,f(x)) ∣ x∈A}⊆A×B\text{Graph}(f) = \{(x, f(x))\ |\ x \in A\} \subseteq A \times B

Vertical line test

A relation is a function if and only if no vertical line intersects the graph at more than one point.

Growth of functions

Big O notation simplifies a function to its growth rate in respect to the input size.

Definitions of Big Notation

T(n)∈A(g(n)) iff ∃ c>0:T(n) \in A(g(n))\ \text{iff}\ \exists\ c > 0: T(n)≃c⋅g(n) ∀ n≥n0>0T(n) \simeq c\cdot g(n)\ \forall\ n \geq n_0 > 0
NotationConditionAsymptotic boundaryName
O(g)O(g)T(n)≤c⋅g(n)T(n) \leq c\cdot g(n)UpperBig O
Ω(g)\Omega(g)T(n)≥c⋅g(n)T(n) \geq c\cdot g(n)LowerBig Omega
Θ(g)\Theta(g)c1⋅g(n≤T(n)≤c2⋅g(n) c_1\cdot g(n\leq T(n) \leq c_2\cdot g(n)TightBig Theta / Order of growth

Identifying growth rates

Identify the term with the highest growth rate in T(n)T(n) would be g(n)g(n).

The following gives the common growth rate functions (increasing order of growth):

1<log⁡n<n<n<nlog⁡n<n2<n3<2n<n!<nn1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < 2^n < n! < n^n
Edit on GitHub

Previous

Sets and relations

Next

Counting

On this page