1. Function Definitions

Definition 4.1: Function

Let A and B be non-empty sets. A function f from A to B, denoted $f: A \to B$ , is a rule that assigns to each element $x \in A$ exactly one element $y \in B$ .

We write $y = f(x)$ and say that y is the image of x under f.

A is called the domain of f
B is called the codomain of f
The set $\{f(x) \mid x \in A\}$ is called the range or image of f

Remark

Key Requirements for a Function:

Every element in the domain must be mapped to something
Each element in the domain maps to exactly one element in the codomain
The range is a subset of the codomain: $ext{range}(f) subseteq B$

Example: Functions and Non-Functions

Let $A = {1, 2, 3}$ and $B = {a, b, c}$ . Which of the following are functions from A to B?

1. $f_1 = {(1,a), (2,b), (3,c)}$

✓ This is a function. Every element in A is mapped to exactly one element in B.

2. $f_2 = {(1,a), (2,b)}$

✗ Not a function. Element 3 is not mapped to anything.

3. $f_3 = {(1,a), (1,b), (2,c), (3,a)}$

✗ Not a function. Element 1 is mapped to both a and b.

4. $f_4 = {(1,a), (2,a), (3,a)}$

✓ This is a function. Multiple elements can map to the same output (this is a constant function).

Definition 4.2: Function Equality

Two functions $f: A \to B$ and $g: A \to B$ are equal, written $f = g$ , if $f(x) = g(x)$ for all $x \in A$ .

Definition 4.3: Special Functions

Identity Function:

The identity function $I_A: A \to A$ is defined by $I_A(x) = x$ for all $x \in A$ .

Constant Function:

A constant function $f: A \to B$ maps all elements of A to a single element $c \in B$ : $f(x) = c$ for all $x \in A$ .

Inclusion Function:

If $A \subseteq B$ , the inclusion function $i: A \to B$ is defined by $i(x) = x$ for all $x \in A$ .

Example: Functions on Real Numbers

$f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$

Domain: $\mathbb{R}$ (all real numbers)
Codomain: $\mathbb{R}$
Range: $[0, \infty)$ (non-negative real numbers)

Definition 4.4: Graph of a Function

The graph of a function $f: A \to B$ is the set of ordered pairs:

\text{graph}(f) = \{(x, f(x)) \mid x \in A\} \subseteq A \times B

A relation $R \subseteq A \times B$ is the graph of a function if and only if for each $a \in A$ , there is exactly one $b \in B$ such that $(a,b) \in R$ .

2. Injective Functions

Definition 4.5: Injective Function (One-to-One)

A function $f: A \to B$ is injective (or one-to-one) if different inputs always produce different outputs.

Formally, f is injective if:

\forall x_1, x_2 \in A, \; f(x_1) = f(x_2) \implies x_1 = x_2

Equivalently (contrapositive):

\forall x_1, x_2 \in A, \; x_1 \neq x_2 \implies f(x_1) \neq f(x_2)

Example: Testing for Injectivity

Example 1: Is $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 3$ injective?

Proof of f is injective

Assume $f(x_1) = f(x_2)$

Then $2x_1 + 3 = 2x_2 + 3$

Subtracting 3: $2x_1 = 2x_2$

Dividing by 2: $x_1 = x_2$

Therefore, f is injective.

∎

Example 2: Is $g: \mathbb{R} \to \mathbb{R}$ defined by $g(x) = x^2$ injective?

No! Consider $x_1 = 2$ and $x_2 = -2$ :

$g(2) = 4$ and $g(-2) = 4$

We have $g(x_1) = g(x_2)$ but $x_1 \neq x_2$ , so g is not injective.

Example 3: Is $h: [0, \infty) \to \mathbb{R}$ defined by $h(x) = x^2$ injective?

Proof of h is injective

Assume $h(x_1) = h(x_2)$ where $x_1, x_2 \geq 0$

Then $x_1^2 = x_2^2$

Taking square roots (both sides non-negative): $x_1 = x_2$

Therefore, h is injective on the restricted domain $[0, \infty)$ .

∎

Theorem 4.1: Properties of Injective Functions

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

If f is injective and finite, then $|A| \leq |B|$
If $f: A \to B$ and $g: B \to C$ are both injective, then $g \circ f: A \to C$ is injective
A function has a left inverse if and only if it is injective

Proof of Composition of Injections

Suppose f and g are injective. We prove $g \circ f$ is injective.

Let $x_1, x_2 \in A$ and assume $(g \circ f)(x_1) = (g \circ f)(x_2)$

Then $g(f(x_1)) = g(f(x_2))$

Since g is injective, $f(x_1) = f(x_2)$

Since f is injective, $x_1 = x_2$

Therefore, $g \circ f$ is injective.

∎

3. Surjective Functions

Definition 4.6: Surjective Function (Onto)

A function $f: A \to B$ is surjective (or onto) if every element of the codomain B is the image of at least one element in the domain A.

Formally, f is surjective if:

\forall y \in B, \; \exists x \in A \text{ such that } f(x) = y

Equivalently, the range of f equals the codomain: $\text{range}(f) = B$

Example: Testing for Surjectivity

Example 1: Is $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 3$ surjective?

Proof of f is surjective

Let $y \in \mathbb{R}$ be arbitrary. We need to find $x \in \mathbb{R}$ such that $f(x) = y$

We need $2x + 3 = y$

Solving for x: $x = \frac{y - 3}{2}$

This value of x is real for any real y, so every $y \in \mathbb{R}$ has a pre-image.

Therefore, f is surjective.

∎

Example 2: Is $g: \mathbb{R} \to \mathbb{R}$ defined by $g(x) = x^2$ surjective?

No! Consider $y = -1 \in \mathbb{R}$ :

We need $x^2 = -1$ , but no real number x satisfies this equation.

Since -1 (and all negative numbers) have no pre-image, g is not surjective.

Example 3: Is $h: \mathbb{R} \to [0, \infty)$ defined by $h(x) = x^2$ surjective?

Proof of h is surjective

Let $y \in [0, \infty)$ . We need to find $x \in \mathbb{R}$ such that $x^2 = y$

Choose $x = \sqrt{y}$ (well-defined since $y \geq 0$ )

Then $h(x) = (\sqrt{y})^2 = y$

Therefore, h is surjective with the restricted codomain.

∎

Theorem 4.2: Properties of Surjective Functions

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

If f is surjective and finite, then $|A| \geq |B|$
If $f: A \to B$ and $g: B \to C$ are both surjective, then $g \circ f: A \to C$ is surjective
A function has a right inverse if and only if it is surjective

Proof of Composition of Surjections

Suppose f and g are surjective. We prove $g \circ f$ is surjective.

Let $z \in C$ be arbitrary.

Since g is surjective, there exists $y \in B$ such that $g(y) = z$

Since f is surjective, there exists $x \in A$ such that $f(x) = y$

Therefore, $(g \circ f)(x) = g(f(x)) = g(y) = z$

Since z was arbitrary, $g \circ f$ is surjective.

∎

4. Bijective Functions

Definition 4.7: Bijective Function (One-to-One Correspondence)

A function $f: A \to B$ is bijective (or a one-to-one correspondence) if it is both injective and surjective.

A bijection establishes a perfect pairing between elements of A and elements of B.

Theorem 4.3: Bijection and Cardinality

If there exists a bijection $f: A \to B$ between finite sets A and B, then $|A| = |B|$ .

Proof of Bijection implies equal cardinality

Since f is injective, $|A| \leq |B|$

Since f is surjective, $|A| \geq |B|$

Therefore, $|A| = |B|$ .

∎

Example: Bijective Functions

Example 1: $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 3$

This is bijective (we proved it's both injective and surjective earlier).

Example 2: $g: {1,2,3} o {a,b,c}$ defined by $g(1)=b, g(2)=c, g(3)=a$

This is bijective:

Injective: Different inputs map to different outputs
Surjective: Every element in {a,b,c} is mapped to

Example 3: $h: [0, \infty) \to [0, \infty)$ defined by $h(x) = x^2$

This is bijective on the restricted domain and codomain (check both properties).

Theorem 4.4: Properties of Bijections

The composition of two bijections is a bijection
Every bijection has an inverse function
The inverse of a bijection is also a bijection
The identity function is a bijection

Remark

Summary Table:

Property	Injective	Surjective	Bijective
One-to-one	✓	✗	✓
Onto	✗	✓	✓
Has inverse	Left	Right	Two-sided
Cardinality (finite)	$\|A\| \leq \|B\|$	$\|A\| \geq \|B\|$	$\|A\| = \|B\|$

5. Inverse Functions

Definition 4.8: Inverse Function

Let $f: A \to B$ be a bijection. The inverse function of f, denoted $f^-1: B \to A$ , is defined by:

f^-1(y) = x \iff f(x) = y

In other words, $f^-1$ "undoes" what f does.

Theorem 4.5: Existence of Inverse

A function $f: A \to B$ has an inverse function if and only if f is bijective.

Proof of Inverse exists iff bijective

(⟹) Suppose $f^-1$ exists.

To show f is injective: If $f(x_1) = f(x_2)$ , then $f^-1(f(x_1)) = f^-1(f(x_2))$ , so $x_1 = x_2$ .

To show f is surjective: For any $y \in B$ , let $x = f^-1(y)$ . Then $f(x) = y$ .

(⟸) Suppose f is bijective.

For each $y \in B$ , there exists a unique $x \in A$ such that $f(x) = y$ (surjective ensures existence, injective ensures uniqueness). Define $f^-1(y) = x$ .

∎

Theorem 4.6: Properties of Inverse Functions

If $f: A \to B$ is bijective with inverse $f^-1: B \to A$ , then:

$f^-1(f(x)) = x$ for all $x \in A$
$f(f^-1(y)) = y$ for all $y \in B$
$(f^-1)^-1 = f$
$f^-1$ is also bijective

Example: Finding Inverse Functions

Example 1: Find the inverse of $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 3x - 5$

Solution:

Let $y = f(x) = 3x - 5$

Solve for x in terms of y:

$y = 3x - 5$

$y + 5 = 3x$

$x = \frac{y + 5}{3}$

Therefore, $f^{-1}(y) = \frac{y + 5}{3}$ , or $f^{-1}(x) = \frac{x + 5}{3}$

Verification: $f(f^{-1}(x)) = f(\frac{x+5}{3}) = 3(\frac{x+5}{3}) - 5 = x + 5 - 5 = x$ ✓

Example 2: Does $g: \mathbb{R} \to \mathbb{R}$ defined by $g(x) = x^2$ have an inverse?

No! We showed earlier that g is not injective (since $g(2) = g(-2) = 4$ ).

Therefore, by Theorem 4.5, g does not have an inverse function.

Example 3: Find the inverse of $h: [0, \infty) \to [0, \infty)$ defined by $h(x) = x^2$

On this restricted domain, h is bijective, so it has an inverse.

Let $y = x^2$ . Solving for x (with $x \geq 0$ ): $x = \sqrt{y}$

Therefore, $h^{-1}(x) = \sqrt{x}$ for $x \geq 0$

6. Function Composition

Definition 4.9: Function Composition

Let $f: A \to B$ and $g: B \to C$ be functions. The composition of g and f, denoted $g \circ f$ (read "g composed with f" or "g circle f"), is the function $g \circ f: A \to C$ defined by:

(g \circ f)(x) = g(f(x))

Note: Apply f first, then apply g to the result. The order matters!

Remark

Important:

For $g \circ f$ to be defined, the codomain of f must match the domain of g
In general, $g \circ f \neq f \circ g$ (composition is not commutative)
Composition is associative: $(h \circ g) \circ f = h \circ (g \circ f)$

Example: Function Composition

Example 1: Let $f(x) = x + 1$ and $g(x) = 2x$ . Find $(g \circ f)(x)$ and $(f \circ g)(x)$ .

$(g \circ f)(x) = g(f(x)) = g(x + 1) = 2(x + 1) = 2x + 2$

$(f \circ g)(x) = f(g(x)) = f(2x) = 2x + 1$

Note: $g \circ f \neq f \circ g$ (they give different results)

Example 2: Let $f(x) = x^2$ and $g(x) = \sqrt{x}$ for $x \geq 0$ . Compute $(g \circ f)(x)$ and $(f \circ g)(x)$ .

$(g \circ f)(x) = g(f(x)) = g(x^2) = \sqrt{x^2} = |x|$

$(f \circ g)(x) = f(g(x)) = f(\sqrt{x}) = (\sqrt{x})^2 = x$ for $x \geq 0$

Note: $f \circ g = I$ (identity), but $g \circ f \neq I$ on all of $\mathbb{R}$

Theorem 4.7: Properties of Composition

Let f, g, and h be functions where composition is defined:

Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$
Identity: $f \circ I_A = f$ and $I_B \circ f = f$ where $f: A \to B$
Inverse: If f is bijective, then $f^-1 \circ f = I_A$ and $f \circ f^-1 = I_B$
Inverse of Composition: If f and g are bijective, then $(g \circ f)^-1 = f^-1 \circ g^-1$

Proof of Inverse of Composition

We show $(g \circ f) \circ (f^-1 \circ g^-1) = I$ and $(f^-1 \circ g^-1) \circ (g \circ f) = I$

For any $x \in A$ :

$((f^-1 \circ g^-1) \circ (g \circ f))(x)$

$= (f^-1 \circ g^-1)(g(f(x)))$

$= f^-1(g^-1(g(f(x))))$

$= f^-1(f(x))$

$= x$

Similarly for the other direction. Therefore $(g \circ f)^-1 = f^-1 \circ g^-1$ .

∎

Note

Think of Function Composition Like Putting on Clothes:

If $f$ = "put on socks" and $g$ = "put on shoes", then:

$(g \circ f)$ = "put on socks, then shoes" (correct order)
$(f \circ g)$ = "put on shoes, then socks" (incorrect order)

Similarly, to undo $(g \circ f)$ , you must first undo g, then undo f: $(g \circ f)^-1 = f^-1 \circ g^-1$

Practice Quiz

Functions Quiz

10

Questions

0

Correct

0%

Accuracy

1

Which of the following relations from

A = \{1, 2, 3\}

to

B = \{a, b\}

is NOT a function?

Easy

Not attempted

2

Let

f: \mathbb{R} \to \mathbb{R}

be defined by

f(x) = 2x + 1

. What is

f^{-1}(5)

?

Easy

Not attempted

3

Which property makes a function one-to-one (injective)?

Medium

Not attempted

4

Let

f: \{1,2,3\} \to \{a,b,c,d\}

be defined by

f(1)=a, f(2)=b, f(3)=c

. Is f surjective?

Medium

Not attempted

5

If

f: A \to B

is bijective, which statement is always true?

Medium

Not attempted

6

Let

f(x) = x^2

from

\mathbb{R}

to

\mathbb{R}

. Which is true?

Hard

Not attempted

7

If

f: A \to B

and

g: B \to C

are both bijections, what can we say about

g \circ f

?

Hard

Not attempted

8

What is the identity function

I_A: A \to A

?

Easy

Not attempted

9

If

f: A \to B

is injective and

|A| = 5

, what is the minimum possible value of

|B|

?

Medium

Not attempted

10

Given

f(x) = 3x - 2

and

g(x) = x^2

, what is

(f \circ g)(x)

?

Hard

Not attempted

Frequently Asked Questions

What's the difference between codomain and range?

The codomain is the set that you specify as the target when defining a function.

The range (or image) is the set of actual output values that the function produces.

Example: For f: ℝ → ℝ defined by f(x) = x²:

Codomain = ℝ (all real numbers)
Range = [0, ∞) (only non-negative real numbers)

The function is surjective if and only if range = codomain.

How do I prove a function is injective?

Method 1 (Direct): Assume f(x₁) = f(x₂) and prove that x₁ = x₂.

Method 2 (Contrapositive): Assume x₁ ≠ x₂ and prove that f(x₁) ≠ f(x₂).

Method 3 (Horizontal Line Test): For functions on real numbers, if every horizontal line intersects the graph at most once, the function is injective.

Most commonly, we use Method 1 in formal proofs.

Why can't every function have an inverse?

An inverse function must "undo" what the original function does. For this to work:

Injective required: If two inputs map to the same output, the inverse wouldn't know which input to return
Surjective required: Every output must come from some input, otherwise the inverse wouldn't be defined everywhere

Example: f(x) = x² on ℝ fails both:

Not injective: f(2) = f(-2) = 4 (which input should f⁻¹(4) return?)
Not surjective: No input gives -1 (what should f⁻¹(-1) be?)

What does f⁻¹ mean if f is not bijective?

If f is not bijective, then f⁻¹ as an inverse function does not exist.

However, f⁻¹ can still denote the inverse image (or preimage) of a set:

$f^{-1}(B) = \{x \in A \mid f(x) \in B\}$ (the set of inputs that map into B)

This is a different concept! The inverse image is always defined, even when the inverse function is not.

Why is (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ and not g⁻¹ ∘ f⁻¹?

Think about the order of operations. When you apply g ∘ f, you:

First apply f
Then apply g to the result

To undo this, you must:

First undo g (apply g⁻¹)
Then undo f (apply f⁻¹)

You undo operations in reverse order! Like putting on shoes and socks: to undo, you remove shoes first, then socks.

What's the practical importance of functions in computer science?

Functions are fundamental to CS:

Programming: Functions/methods are the building blocks of programs
Data structures: Hash functions (should be injective for perfect hashing)
Cryptography: Encryption functions (should be bijective to allow decryption)
Databases: Functional dependencies determine database design
Algorithms: Algorithm complexity is described as a function of input size
Type theory: Types in programming languages are sets, functions map values between types