Functions

Function Notation

Definition

Functions are typically denoted by letters such as $f$, $g$, or $h$. If $f$ is a function and $x$ is an element of its domain, then $f(x)$ denotes the output value corresponding to the input $x$. The notation $f: A \to B$ indicates that $f$ is a function with domain $A$ and codomain $B$.

Function

Definition

A function is a collection of pairs of numbers with the following property: if $(a, b)$ and $(a, c)$ are both in the collection, then $b = c$; in other words, the collection must not contain two different pairs with the same first element.

Domain of a Function

Definition

If $f$ is a function, the domain of $f$ is the set of all $a$ for which there is some $b$ such that $(a, b)$ is in $f$. If $a$ is in the domain of $f$, it follows from the definition of a function that there is, in fact, a unique number $b$ such that $(a, b)$ is in $f$. This unique $b$ is denoted by $f(a)$.

Notation

The domain of a function $f$ is denoted by $\operatorname{dom}(f)$.

Range of a Function

Definition

The range of a function $f$ is the set of all values $f(x)$ where $x$ is in the domain of $f$. In other words, if $f: A \to B$ is a function, then the range is the set $\{f(x) : x \in A\}$.

Notation

The range of a function $f$ is denoted by $\operatorname{range}(f)$.

Function Uniqueness

Theorem

If $f$ is a function and $a$ is in the domain of $f$, then there exists exactly one $b$ such that $f(a) = b$.

Proof

By the definition of a function, for each $a$ in the domain, there exists at least one $b$ such that $(a, b)$ is in $f$. Suppose for contradiction that there exist two different values $b_1$ and $b_2$ such that both $(a, b_1)$ and $(a, b_2)$ are in $f$. This would violate the defining property of a function, which requires that if $(a, b)$ and $(a, c)$ are both in the function, then $b = c$. Therefore, there must be exactly one $b$ for each $a$ in the domain.

$\square$

Injective Functions, One-to-One Functions

Definition

A function $f: A \to B$ is called injective if different inputs always produce different outputs. Formally, $f$ is injective if for all $a_1, a_2 \in A$, $f(a_1) = f(a_2)$ implies $a_1 = a_2$.

Surjective Functions, Onto Functions

Definition

A function $f: A \to B$ is called surjective if every element in the codomain $B$ is the image of at least one element in the domain $A$. Formally, $f$ is surjective if for every $b \in B$, there exists an $a \in A$ such that $f(a) = b$.

Bijective Functions

Definition

A function $f: A \to B$ is called bijective if it is both injective and surjective. Bijective functions establish a perfect one-to-one correspondence between the elements of the domain and codomain.

Theorem

A function $f: A \to B$ is bijective if and only if there exists a function $f^{-1}: B \to A$ such that $f^{-1} \circ f = \text{id}_A$ and $f \circ f^{-1} = \text{id}_B$, where $\text{id}_A$ and $\text{id}_B$ are the identity functions on $A$ and $B$ respectively.

Proof

($\Rightarrow$) Suppose $f$ is bijective. Then for each $b \in B$, there exists a unique $a \in A$ such that $f(a) = b$. Define $f^{-1}(b) = a$. This is well-defined because $f$ is surjective (so such an $a$ exists) and injective (so it's unique). Then $f^{-1}(f(a)) = a$ for all $a \in A$ and $f(f^{-1}(b)) = b$ for all $b \in B$.

($\Leftarrow$) Suppose $f$ has an inverse $f^{-1}$. To show $f$ is injective, assume $f(a_1) = f(a_2)$. Then $f^{-1}(f(a_1)) = f^{-1}(f(a_2))$, so $a_1 = a_2$. To show $f$ is surjective, for any $b \in B$, let $a = f^{-1}(b)$. Then $f(a) = f(f^{-1}(b)) = b$, so $b$ is in the range of $f$.

$\square$

Inverse Functions

Definition

If $f: A \to B$ is a bijective function, then it has an inverse function $f^{-1}: B \to A$ defined by $f^{-1}(b) = a$ if and only if $f(a) = b$. The inverse function reverses the action of the original function.

Pigeonhole Principle

Theorems

If $A$ and $B$ are finite sets and $f: A \to B$ is a function, then:

  1. If $|A| > |B|$, then $f$ is not injective.

  2. If $|A| < |B|$, then $f$ is not surjective.

Proofs

  1. If $|A| > |B|$, then by the pigeonhole principle, at least two elements of $A$ must map to the same element of $B$, so $f$ cannot be injective.

  2. If $|A| < |B|$, then there are more elements in $B$ than in $A$, so it's impossible for every element of $B$ to be the image of some element of $A$. Therefore, $f$ cannot be surjective.

$\square$

Composition of Functions

Definition

If $f: A \to B$ and $g: B \to C$ are functions, then the composition $g \circ f$ is a function from $A$ to $C$ defined by $(g \circ f)(x) = g(f(x))$ for all $x \in A$.

Associativity of Composition Theorem

If $f: A \to B$, $g: B \to C$, and $h: C \to D$ are functions, then $(h \circ g) \circ f = h \circ (g \circ f)$.

Proof

For any $a \in A$, we have: $$((h \circ g) \circ f)(a) = (h \circ g)(f(a)) = h(g(f(a)))$$ and $$(h \circ (g \circ f))(a) = h((g \circ f)(a)) = h(g(f(a)))$$ Since both compositions give the same result for every $a \in A$, the functions are equal.

$\square$

Image of Intersection and Union

Theorems

Let $f: A \to B$ be a function, and let $X, Y \subseteq A$. Then:

  1. $f(X \cup Y) = f(X) \cup f(Y)$

  2. $f(X \cap Y) \subseteq f(X) \cap f(Y)$

Equality holds in 2. if $f$ is injective.

Proofs

  1. ($\subseteq$) If $b \in f(X \cup Y)$, then $b = f(a)$ for some $a \in X \cup Y$. So $a \in X$ or $a \in Y$, which means $b \in f(X)$ or $b \in f(Y)$, so $b \in f(X) \cup f(Y)$.

    ($\supseteq$) If $b \in f(X) \cup f(Y)$, then $b \in f(X)$ or $b \in f(Y)$. So there exists $a \in X$ or $a \in Y$ such that $b = f(a)$. Thus $a \in X \cup Y$, so $b \in f(X \cup Y)$.

  2. If $b \in f(X \cap Y)$, then $b = f(a)$ for some $a \in X \cap Y$. So $a \in X$ and $a \in Y$, which means $b \in f(X)$ and $b \in f(Y)$, so $b \in f(X) \cap f(Y)$.

    For the equality when $f$ is injective: If $b \in f(X) \cap f(Y)$, then $b \in f(X)$ and $b \in f(Y)$. So there exist $a_1 \in X$ and $a_2 \in Y$ such that $f(a_1) = b$ and $f(a_2) = b$. Since $f$ is injective, $a_1 = a_2$, so $a_1 \in X \cap Y$, and thus $b \in f(X \cap Y)$.

$\square$

Left and Right Inverses Theorems

Let $f: A \to B$ be a function.

  1. There exists $g: B \to A$ such that $g \circ f = I_A$ if and only if $f$ is injective.

  2. There exists $h: B \to A$ such that $f \circ h = I_B$ if and only if $f$ is surjective.

Proofs

  1. ($\Rightarrow$) If $g \circ f = I_A$ and $f(x) = f(y)$, then $x = g(f(x)) = g(f(y)) = y$, so $f$ is injective.

    ($\Leftarrow$) If $f$ is injective, for each $b$ in the range of $f$, there's a unique $a$ with $f(a) = b$. Define $g(b) = a$. For $b$ not in the range, define $g(b)$ arbitrarily.

  2. ($\Rightarrow$) If $f \circ h = I_B$, then for any $b \in B$, $a = h(b)$ satisfies $f(a) = f(h(b)) = b$, so $f$ is surjective.

    ($\Leftarrow$) If $f$ is surjective, for each $b \in B$, choose $a_b \in A$ with $f(a_b) = b$. Define $h(b) = a_b$. Then $f(h(b)) = f(a_b) = b$ for all $b \in B$.

$\square$

Definition

A function $f: \mathbb{R} \to \mathbb{R}$ is:

Properties

  1. The only function that is both even and odd is the zero function.

  2. Every function can be uniquely written as the sum of an even and an odd function.

Proof

(1) If $f$ is both even and odd, then $f(x) = f(-x) = -f(x)$, so $2f(x) = 0$, hence $f(x) = 0$.

(2) For any function $f$, define: $$E(x) = \frac{f(x) + f(-x)}{2}, \quad O(x) = \frac{f(x) - f(-x)}{2}$$ Then $E$ is even, $O$ is odd, and $f = E + O$. For uniqueness, if $f = E_1 + O_1 = E_2 + O_2$ with $E_1, E_2$ even and $O_1, O_2$ odd, then $E_1 - E_2 = O_2 - O_1$ is both even and odd, hence zero.

$\square$

Polynomial Functions

Definition

A polynomial is a function of the form: $$f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$$ where $a_0, a_1, \ldots, a_n$ are constants and $a_n \neq 0$. The number $n$ is called the degree of the polynomial.

Polynomial Division Theorem

For any polynomial $f$ and number $a$, there exist a polynomial $g$ and a number $b$ such that: $$f(x) = (x - a)g(x) + b$$

Proof

Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$. We can perform polynomial long division of $f(x)$ by $(x - a)$ to obtain quotient $g(x)$ and remainder $b$.

$\square$

Factor Theorem

If $f(a) = 0$, then $f(x) = (x - a)g(x)$ for some polynomial $g$.

Proof

By polynomial division, $f(x) = (x - a)g(x) + b$. Then $0 = f(a) = (a - a)g(a) + b = b$, so $f(x) = (x - a)g(x)$.

$\square$

Number of Roots Theorem

A degree $n$ polynomial has at most $n$ roots.

Proof

We proceed by induction. For $n = 0$, a nonzero constant polynomial has no roots. Assume the theorem holds for degree $n-1$. If a degree $n$ polynomial $f$ has a root $a$, then $f(x) = (x - a)g(x)$ where $g$ has degree $n-1$. By induction, $g$ has at most $n-1$ roots, so $f$ has at most $n$ roots.

$\square$

Characteristic Functions

Definition

For a set $A \subseteq \mathbb{R}$, the characteristic function $C_A: \mathbb{R} \to \{0,1\}$ is defined by: $$C_A(x) = \begin{cases} 1 & \text{if } x \in A \\ 0 & \text{if } x \notin A \end{cases}$$

Properties of Characteristic Functions Theorem

For sets $A, B \subseteq \mathbb{R}$:

  1. $C_{A \cap B}(x) = C_A(x) \cdot C_B(x)$

  2. $C_{A \cup B}(x) = C_A(x) + C_B(x) - C_A(x)C_B(x)$

  3. $C_{\mathbb{R} \setminus A}(x) = 1 - C_A(x)$

Characterization of Characteristic Functions Theorem

A function $f: \mathbb{R} \to \mathbb{R}$ satisfies $f = f^2$ if and only if $f = C_A$ for some set $A \subseteq \mathbb{R}$.

Proof

($\Leftarrow$) If $f = C_A$, then $f(x)^2 = C_A(x)^2 = C_A(x) = f(x)$ since $C_A(x) \in \{0,1\}$.

($\Rightarrow$) If $f = f^2$, then for each $x$, $f(x) = f(x)^2$, so $f(x) \in \{0,1\}$. Let $A = \{x \in \mathbb{R} : f(x) = 1\}$. Then $f = C_A$.

$\square$

Fixed Points and Iteration

Definition

A fixed point of a function $f$ is a value $x$ such that $f(x) = x$.

Definition

A function $f$ is idempotent if $f \circ f = f$, i.e., $f(f(x)) = f(x)$ for all $x$.

Properties of Idempotent Functions

If $f$ is idempotent, then:

  1. Every element in the range of $f$ is a fixed point.

  2. For any $x$, $f(x)$ is a fixed point.

Proofs

  1. If $y = f(x)$ is in the range, then $f(y) = f(f(x)) = f(x) = y$.

  2. $f(f(x)) = f(x)$ by idempotence, so $f(x)$ is a fixed point.

$\square$

Functional Equations

Cauchy's Functional Equation Theorem

If $f: \mathbb{R} \to \mathbb{R}$ satisfies $f(x + y) = f(x) + f(y)$ for all $x, y \in \mathbb{R}$, and $f$ is continuous, then $f(x) = cx$ for some constant $c$.

Proof

First, $f(0) = f(0 + 0) = f(0) + f(0)$, so $f(0) = 0$.

For natural numbers $n$, $f(nx) = nf(x)$ by induction.

For rational numbers $\frac{p}{q}$, $f(\frac{p}{q}) = \frac{p}{q}f(1)$.

By continuity, $f(x) = xf(1)$ for all $x \in \mathbb{R}$.

$\square$

Additive and Multiplicative Functions Theorem

If $f: \mathbb{R} \to \mathbb{R}$ satisfies:

  1. $f(x + y) = f(x) + f(y)$ for all $x, y$

  2. $f(xy) = f(x)f(y)$ for all $x, y$

  3. $f$ is not identically zero

Then $f(x) = x$ for all $x \in \mathbb{R}$.

Proof

First, $f(1) = f(1 \cdot 1) = f(1)^2$, so $f(1) = 0$ or $1$. If $f(1) = 0$, then $f(x) = f(x \cdot 1) = f(x)f(1) = 0$ for all $x$, contradicting (3). So $f(1) = 1$.

For rational $r = \frac{p}{q}$, $f(r) = r$ by the additive property.

If $x > 0$, then $x = y^2$ for some $y$, so $f(x) = f(y)^2 \geq 0$.

If $x > y$, then $f(x) - f(y) = f(x - y) > 0$ (since $x - y > 0$ and $f$ is not identically zero), so $f$ is strictly increasing.

Since $f$ agrees with the identity on rationals and is increasing, $f(x) = x$ for all $x \in \mathbb{R}$.

$\square$

Max, Min, and Absolute Value

Max-Min Formula Theorem

For any functions $f, g: \mathbb{R} \to \mathbb{R}$:

  1. $\max(f, g)(x) = \frac{f(x) + g(x) + |f(x) - g(x)|}{2}$
  2. $\min(f, g)(x) = \frac{f(x) + g(x) - |f(x) - g(x)|}{2}$
  3. $f(x) = \max(f, 0)(x) + \min(f, 0)(x)$

Proof

For any real numbers $a, b$: $$\max(a, b) = \frac{a + b + |a - b|}{2}$$ $$\min(a, b) = \frac{a + b - |a - b|}{2}$$ Applying these pointwise gives (1) and (2). For (3), note that $\max(f, 0) + \min(f, 0) = f$.

$\square$

Domain Determination

Domain of Composite Functions Theorem

For functions $f: A \to B$ and $g: B \to C$, the domain of $g \circ f$ is: $$\{x \in A : f(x) \in \text{domain of } g\}$$

Proof

The proof follows from the definition of function composition and the requirement that the output of $f$ must lie in the domain of $g$ for $g(f(x))$ to be defined.

$\square$

Domain of Algebraic Expressions Theorem

The domain of an expression is the set of all $x$ for which:

  1. Denominators are nonzero

  2. Arguments of square roots are nonnegative

  3. Arguments of logarithms are positive

  4. etc.

Proof

The proof follows from the definitions of the functions involved and the restrictions on their domains.

$\square$

Addition of Functions

Definition

If $f$ and $g$ are functions with the same domain, then their sum $f + g$ is defined by $(f + g)(x) = f(x) + g(x)$ for all $x$ in the domain.

Multiplication of Functions

Definition

If $f$ and $g$ are functions with the same domain, then their product $f \cdot g$ is defined by $(f \cdot g)(x) = f(x) \cdot g(x)$ for all $x$ in the domain.

Scalar Multiplication

Definition

If $f$ is a function and $c$ is a constant (scalar), then the scalar multiple $c \cdot f$ is defined by $(c \cdot f)(x) = c \cdot f(x)$ for all $x$ in the domain of $f$.