Chapter 09 of 30

Functions

On this page

Every roll number in your college maps to exactly one student. Every key in a hash table is sent to exactly one bucket. Every program, given an input, produces one output. These are all functions: rules that assign to each element of one set exactly one element of another.

In the Sets & Set Operations chapter we learned to build and combine sets. In this chapter we connect sets with functions. We will define functions precisely, study the three key properties (one-to-one, onto, bijective), count how many functions of each kind exist (a GATE favourite), compose and invert functions, meet the floor and ceiling functions that appear in every algorithm analysis, and finally use bijections to compare the sizes of infinite sets, which leads to the surprising fact that some problems cannot be solved by any program.


Definition of a Function

A function f from a set A to a set B, written f : A → B, assigns to each element a ∈ A exactly one element f(a) ∈ B.

  • A is the domain and B is the codomain.

  • If f(a) = b, then b is the image of a, and a is a preimage of b.

  • The range (or image of f) is the set of all values actually taken: f(A) = { f(a) | a ∈ A }. It is a subset of the codomain, and may be smaller.

Two conditions are packed into "each element … exactly one":

  1. Every element of A has an image (no element is left out).

  2. No element of A has two images.

In terms of sets, a function is a special subset of A × B (a special relation, see the next chapters): for every a ∈ A there is exactly one pair (a, b) in it.

Function or not?

Let A = {1, 2, 3} and B = {x, y, z}.

Rule

Function A → B?

Reason

{(1, x), (2, x), (3, z)}

Yes

Each of 1, 2, 3 has exactly one image. Two inputs sharing an image is fine.

{(1, x), (2, y)}

No

3 has no image.

{(1, x), (1, y), (2, z), (3, z)}

No

1 has two images.

f(n) = 1/n from ℤ to ℝ

No

f(0) is undefined.

f(x) = √x from ℝ to ℝ

No

Negative x have no real square root (it is a function on [0, ∞)).

Two functions are equal if they have the same domain, the same codomain, and agree on every element. So f(x) = x² as a function ℝ → ℝ and as a function ℝ → [0, ∞) are, strictly speaking, different functions, and as we will see, they have different properties.

Arrow diagram

   A              B
 +---+          +---+
 | 1 |--------->| x |       f(1) = x
 |   |      +-->|   |       f(2) = x
 | 2 |------+   | y |       f(3) = z
 |   |          |   |
 | 3 |--------->| z |       range f(A) = {x, z}, codomain B = {x, y, z}
 +---+          +---+

In an arrow diagram of a function, every element on the left has exactly one arrow leaving it. Elements on the right may receive any number of arrows, including none (like y here).

Image and preimage of a set

For S ⊆ A, the image is f(S) = { f(s) | s ∈ S }. For T ⊆ B, the preimage (inverse image) is f−1(T) = { a ∈ A | f(a) ∈ T }. The preimage always exists, even when f has no inverse function.

Example: f : ℤ → ℤ, f(x) = x². Then f({−2, 1, 2}) = {1, 4} and f−1({4, 5, 9}) = {−3, −2, 2, 3} (nothing maps to 5).


One-to-One, Onto and Bijective

Injective (one-to-one)

f : A → B is injective (one-to-one) if different inputs always give different outputs: for all a1, a2 ∈ A, f(a1) = f(a2) → a1 = a2.

The form "f(a1) = f(a2) → a1 = a2" is the contrapositive of "a1 ≠ a2 → f(a1) ≠ f(a2)", and it is the one used in proofs because it starts from an equation you can manipulate.

Example. f : ℤ → ℤ, f(x) = 2x + 1 is injective. Proof: if 2a + 1 = 2b + 1, then 2a = 2b, so a = b. ∎

Non-example. g : ℤ → ℤ, g(x) = x² is not injective: g(−2) = g(2) = 4. One counterexample is enough.

Surjective (onto)

f : A → B is surjective (onto) if every element of the codomain is hit: for every b ∈ B there is some a ∈ A with f(a) = b. Equivalently, range = codomain.

To prove onto, take an arbitrary b and solve f(a) = b for a, then check that a really is in the domain.

Example. h : ℝ → ℝ, h(x) = 3x − 7 is onto. Given any real y, take x = (y + 7)/3, which is real, and h(x) = (y + 7) − 7 = y. ∎

Non-example. f : ℤ → ℤ, f(x) = 2x + 1 is not onto: f(x) is always odd, so 2 has no preimage. (Solving 2x + 1 = 2 gives x = 1/2, which is not in the domain ℤ.)

Bijective (one-to-one correspondence)

f is bijective if it is both injective and surjective. Then every element of B is the image of exactly one element of A.

h(x) = 3x − 7 on ℝ is bijective: injective since 3a − 7 = 3b − 7 gives a = b, and onto as shown above.

Same formula, different domain and codomain

Whether a function is injective or surjective depends on the domain and codomain, not just the formula. Look at f(x) = x²:

f(x) = x² as a map

Injective?

Surjective?

Why

ℝ → ℝ

No

No

f(−1) = f(1); −1 is never hit

ℝ → [0, ∞)

No

Yes

every y ≥ 0 equals (√y)²

[0, ∞) → ℝ

Yes

No

on non-negatives, a² = b² gives a = b

[0, ∞) → [0, ∞)

Yes

Yes

bijective; inverse is √y

Arrow-diagram tests

Property

In the arrow diagram

Needs (finite sets)

Function

Every left element has exactly one outgoing arrow

—

Injective

Every right element has at most one incoming arrow

|A| ≤ |B|

Surjective

Every right element has at least one incoming arrow

|A| ≥ |B|

Bijective

Every right element has exactly one incoming arrow

|A| = |B|

The condition |A| ≤ |B| for injections is the pigeonhole principle in disguise: if more than |B| pigeons (inputs) go into |B| holes (outputs), two must share a hole. That is why every hash function from long strings to 64-bit values must have collisions.

Theorem (finite sets of equal size). If |A| = |B| is finite, then f : A → B is injective ⟺ f is surjective ⟺ f is bijective.

Proof. If f is injective, the |A| elements of A have |A| distinct images, so the range has |A| = |B| elements; a subset of B with |B| elements is B itself, so f is onto. Conversely, if f is onto, the range has |B| = |A| elements; if two elements of A shared an image, the range would have at most |A| − 1 elements. So f is injective. ∎

This fails for infinite sets: f : ℕ → ℕ, f(n) = n + 1 is injective but not onto (0 is never hit).


Counting Functions (GATE Favourite)

Let |A| = m and |B| = n.

Kind of function A → B

Number

Reasoning

All functions

nm

each of the m inputs independently chooses one of n outputs

Injective (needs m ≤ n)

n(n − 1)(n − 2)⋯(n − m + 1) = n!/(n − m)!

first input has n choices, the next n − 1 (cannot reuse), and so on

Bijective (needs m = n)

n!

injective count with m = n

Surjective (needs m ≥ n)

∑k=0n (−1)k C(n, k)(n − k)m

derived in the Inclusion-Exclusion Principle chapter; for n = 2 it is 2m − 2

Partial functions (some inputs may be undefined)

(n + 1)m

each input chooses one of n outputs or "undefined"

The onto count for n = 2 is easy to see directly: of the 2m functions into {a, b}, only the two constant functions (everything to a, everything to b) miss an element. So 2m − 2 are onto. For m = 3 that is 6; for m = 5 it is 30.

Example: A = {1, 2, 3, 4}, B = {a, b, c}

  • All functions: 34 = 81.

  • Injective: 0, because 4 > 3 (pigeonhole).

  • Surjective: 34 − 3 · 24 + 3 · 14 − 0 = 81 − 48 + 3 = 36. Another way: exactly one output must receive two inputs. Choose the 2 inputs that share an output, C(4, 2) = 6 ways, then assign the 3 resulting groups to a, b, c bijectively, 3! = 6 ways. 6 × 6 = 36.

Let us confirm all of these by brute force: generate every function and classify it.

from itertools import product

def classify_all(A, B):
    """Count all functions A -> B, and how many are injective / surjective / bijective."""
    total = inj = surj = bij = 0
    for values in product(B, repeat=len(A)):   # values[i] = f(A[i])
        f = dict(zip(A, values))
        image = set(f.values())
        is_inj = len(image) == len(A)
        is_surj = image == set(B)
        total += 1
        inj += is_inj
        surj += is_surj
        bij += is_inj and is_surj
    return total, inj, surj, bij

for A, B in [([1, 2, 3], ['a', 'b']),
             ([1, 2, 3], ['a', 'b', 'c']),
             ([1, 2, 3, 4], ['a', 'b', 'c']),
             ([1, 2, 3], ['a', 'b', 'c', 'd'])]:
    t, i, s, b = classify_all(A, B)
    print(f"|A|={len(A)}, |B|={len(B)}: total={t}, injective={i}, surjective={s}, bijective={b}")

Output:

|A|=3, |B|=2: total=8, injective=0, surjective=6, bijective=0
|A|=3, |B|=3: total=27, injective=6, surjective=6, bijective=6
|A|=4, |B|=3: total=81, injective=0, surjective=36, bijective=0
|A|=3, |B|=4: total=64, injective=24, surjective=0, bijective=0

Every number matches the formulas: 23 − 2 = 6, 3! = 6, 36, and 4 · 3 · 2 = 24. Note the row |A| = |B| = 3: injective, surjective and bijective counts are all equal, exactly as the theorem for equal-size finite sets predicts.


Composition of Functions

If f : A → B and g : B → C, the composition g ∘ f : A → C is defined by (g ∘ f)(a) = g(f(a)).

Read g ∘ f as "g after f": apply f first, then g. It only makes sense when the range of f lies inside the domain of g.

Example. f, g : ℝ → ℝ with f(x) = x + 1 and g(x) = x².

(g ∘ f)(x) = g(f(x)) = g(x + 1) = (x + 1)²
(f ∘ g)(x) = f(g(x)) = f(x²)    = x² + 1

At x = 2:  (g ∘ f)(2) = 9,   (f ∘ g)(2) = 5

So composition is not commutative. It is associative: h ∘ (g ∘ f) = (h ∘ g) ∘ f, because both send a to h(g(f(a))). In code, composition is just nested calls, and Unix pipes (cat file | sort | uniq) are compositions read left to right.

How properties pass through composition

Theorem 1. If f and g are both injective, then g ∘ f is injective.

Proof. Suppose g(f(a1)) = g(f(a2)). Since g is injective, f(a1) = f(a2). Since f is injective, a1 = a2. ∎

Theorem 2. If f and g are both surjective, then g ∘ f is surjective.

Proof. Let c ∈ C. g is onto, so c = g(b) for some b ∈ B. f is onto, so b = f(a) for some a ∈ A. Then (g ∘ f)(a) = c. ∎

So a composition of bijections is a bijection.

Theorem 3 (the reverse direction, often asked).

  • If g ∘ f is injective, then f is injective (but g need not be).

  • If g ∘ f is surjective, then g is surjective (but f need not be).

Proof of the first part. If f(a1) = f(a2), then applying g gives (g ∘ f)(a1) = (g ∘ f)(a2), so a1 = a2 by injectivity of g ∘ f. Second part. For c ∈ C there is a with g(f(a)) = c, so b = f(a) is a preimage of c under g. ∎

Counterexample showing g need not be injective: A = {1}, B = {1, 2}, C = {1}, f(1) = 1, g(1) = g(2) = 1. Then g ∘ f is injective (and even bijective), but g is not injective and f is not onto.


Inverse Functions

If f : A → B is a bijection, its inverse f−1 : B → A is defined by f−1(b) = a exactly when f(a) = b.

Why must f be bijective? If f were not onto, some b would have no a to send back to. If f were not one-to-one, some b would have two candidates, so f−1(b) would not be well defined. A function is invertible if and only if it is a bijection.

The inverse "undoes" f:

f⁻¹(f(a)) = a  for every a ∈ A,     i.e.  f⁻¹ ∘ f = identity on A
f(f⁻¹(b)) = b  for every b ∈ B,     i.e.  f ∘ f⁻¹ = identity on B

Finding an inverse

For h(x) = 3x − 7 on ℝ: write y = 3x − 7 and solve for x: x = (y + 7)/3. So h−1(y) = (y + 7)/3. Check: h−1(h(x)) = (3x − 7 + 7)/3 = x. ✓

Inverse of a composition

If f and g are bijections, then (g ∘ f)−1 = f−1 ∘ g−1. The order reverses, just like taking off socks and shoes: you put on socks then shoes, and take off shoes then socks.

Notation warning: f−1(x) means the inverse function, not 1/f(x). And f−1(T) for a set T is the preimage, which exists for every function.


Important Functions in Computer Science

Identity, constant and characteristic functions

  • Identity ιA : A → A, ιA(a) = a. A bijection; it plays the role of 1 in composition.

  • Constant function: every input goes to the same value c. Injective only if |A| ≤ 1.

  • Characteristic function of S ⊆ U: χS(x) = 1 if x ∈ S, else 0. This is the bit vector representation of a set from the Sets chapter. There is a bijection between P(U) and the set of functions U → {0, 1}, which is another way to see |P(U)| = 2|U|.

Floor and ceiling

⌊x⌋ (floor) is the largest integer ≤ x. ⌈x⌉ (ceiling) is the smallest integer ≥ x.

x

3.5

−3.5

4

100/7 ≈ 14.29

⌊x⌋

3

−4

4

14

⌈x⌉

4

−3

4

15

Note ⌊−3.5⌋ = −4, not −3: floor always goes down the number line. (In C and C++, integer division truncates toward zero, so -7 / 2 is −3, while ⌊−7/2⌋ = −4. Python's // is a true floor: -7 // 2 is −4.)

Useful facts (n an integer, x real):

  • ⌊x⌋ = n ⟺ n ≤ x < n + 1; ⌈x⌉ = n ⟺ n − 1 < x ≤ n.

  • ⌊x + n⌋ = ⌊x⌋ + n and ⌈x + n⌉ = ⌈x⌉ + n.

  • ⌈x⌉ − ⌊x⌋ is 0 if x is an integer and 1 otherwise. Also ⌈x⌉ = −⌊−x⌋.

  • ⌊n/2⌋ + ⌈n/2⌉ = n. (Merge sort splits n items into halves of these sizes.)

  • A positive integer n has ⌊log2 n⌋ + 1 bits. For n = 1000 that is 9 + 1 = 10 bits.

  • Packing: 100 items into boxes of 7 needs ⌈100/7⌉ = 15 boxes.

Floor maps ℝ → ℤ; it is onto but not one-to-one (⌊1.2⌋ = ⌊1.7⌋ = 1).

Hash functions and the mod function

f(k) = k mod m maps ℤ onto {0, 1, …, m − 1}. It is onto but not one-to-one; keys that differ by a multiple of m collide. Hash tables live with collisions because a one-to-one hash from a large key space into a small table is impossible (pigeonhole).


Cardinality of Infinite Sets

For finite sets we count elements. For infinite sets, we use bijections, an idea due to Georg Cantor.

Sets A and B have the same cardinality, |A| = |B|, if there is a bijection between them. A set is countably infinite if it has the same cardinality as ℕ; it is countable if it is finite or countably infinite. A set that is not countable is uncountable.

A set is countably infinite exactly when its elements can be listed as a sequence a0, a1, a2, … in which every element appears exactly once.

ℤ is countable

List the integers by zig-zagging: 0, −1, 1, −2, 2, −3, 3, … The bijection f : ℕ → ℤ is

f(n) =  n/2          if n is even
f(n) = −(n + 1)/2    if n is odd

n    : 0   1   2   3   4   5   6   7   8
f(n) : 0  −1   1  −2   2  −3   3  −4   4

So ℤ, which "looks twice as big" as ℕ, has the same cardinality. Infinite sets can be in bijection with proper subsets of themselves; finite sets never can.

ℚ is countable

Arrange positive fractions p/q in a grid (row p, column q) and walk along the diagonals p + q = 2, 3, 4, …, skipping fractions not in lowest terms:

1/1  1/2  1/3  1/4 ...
2/1  2/2  2/3  2/4 ...       order: 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, ...
3/1  3/2  3/3  3/4 ...       (2/2, 2/4, 4/2, 3/3 ... skipped: not in lowest terms)
4/1  4/2  4/3  4/4 ...

Each diagonal is finite, so every positive rational appears after finitely many steps. Interleaving 0 and the negatives (as for ℤ) lists all of ℚ.

ℝ is uncountable: Cantor's diagonal argument

Theorem. The real numbers in (0, 1) cannot be listed. So ℝ is uncountable.

Proof (contradiction). Suppose r1, r2, r3, … lists all reals in (0, 1). Write each as a decimal (choosing the expansion that does not end in all 9s):

r1 = 0. d11 d12 d13 d14 ...
r2 = 0. d21 d22 d23 d24 ...
r3 = 0. d31 d32 d33 d34 ...
r4 = 0. d41 d42 d43 d44 ...
...

Build x = 0.e1e2e3… where ei = 5 if dii ≠ 5 and ei = 4 if dii = 5. Then x is in (0, 1) and its expansion contains no 0s or 9s, so it is its only decimal expansion. But x differs from ri in the i-th digit, for every i, so x is not in the list. Contradiction. ∎

The same diagonal idea proves Cantor's theorem: for every set A, there is no surjection from A onto P(A); since a ↦ {a} is an injection from A into P(A), this gives |A| < |P(A)|. (Given f : A → P(A), the set D = { a ∈ A | a ∉ f(a) } differs from every f(a) in whether it contains a.) In particular P(ℕ) is uncountable.

Why this matters for programmers

Every program is a finite string over a finite alphabet, and the set of all finite strings is countable (list them by length, then alphabetically). So there are only countably many programs. But the set of functions ℕ → {0, 1} is in bijection with P(ℕ), which is uncountable. Therefore most functions from ℕ to {0, 1} cannot be computed by any program. The halting problem is a concrete example, and its proof uses the very same diagonal trick.


Common Mistakes

  • Calling something a function when an input has no image or two images.

  • Ignoring the domain and codomain when judging injective or onto (see the x² table).

  • Confusing range with codomain. Onto means they are equal.

  • Proving onto without checking the domain: solving 2x + 1 = 2 gives x = 1/2, which is not an integer.

  • Getting composition order wrong: g ∘ f applies f first.

  • Reading f−1(x) as 1/f(x), or claiming an inverse exists for a non-bijection.

  • Mixing up the injective and onto counts. Injective counts are n!/(n − m)! (ordered choices without repetition); onto counts need inclusion-exclusion and are 0 when m < n.

  • Assuming "injective ⟺ onto" for infinite sets. It only holds for finite sets of equal size.


Interview and GATE-Style Questions

Q1. How many functions, injective functions and bijections are there from a 4-element set to a 6-element set?

Functions: 64 = 1296. Injective: 6 · 5 · 4 · 3 = 360. Bijections: 0, since the sizes differ.

Q2. How many onto functions are there from a 5-element set to a 2-element set? From a 5-element set to a 3-element set?

To 2 elements: 25 − 2 = 30. To 3 elements: 35 − 3 · 25 + 3 · 15 = 243 − 96 + 3 = 150.

Q3. f : A → B and g : B → C, and g ∘ f is onto. Which must be true: (a) f onto (b) g onto (c) f one-to-one (d) g one-to-one?

Only (b). Every c ∈ C is g(f(a)) for some a, so it is hit by g. The counterexample after Theorem 3 (f(1) = 1 into B = {1, 2}, g(1) = g(2) = 1) shows that f need not be onto and g need not be one-to-one. For f not one-to-one, take A = {1, 2}, B = C = {1}, f constant and g the identity: g ∘ f is onto but f(1) = f(2).

Q4. Is f : ℤ → ℤ, f(n) = n + (−1)n a bijection?

Yes. It sends each even n to n + 1 and each odd n to n − 1, i.e. it swaps 0↔1, 2↔3, −2↔−1, and so on. Applying it twice gives n back, so f ∘ f is the identity and f is its own inverse. A function with an inverse is a bijection.

Q5. What is ⌊−2.3⌋ + ⌈−2.3⌉ + ⌊2.3⌋ + ⌈2.3⌉?

−3 + (−2) + 2 + 3 = 0.

Q6. Which of these sets are countable: ℤ × ℤ, the set of all C programs, P(ℕ), the set of finite subsets of ℕ?

ℤ × ℤ: countable (list pairs by |a| + |b|, like the ℚ grid). C programs: countable (finite strings). P(ℕ): uncountable (Cantor). Finite subsets of ℕ: countable (each is described by a finite string, e.g. its sorted list of elements, or equivalently by a natural number whose binary digits mark its members).

Q7. Let |A| = m. How many functions A → A are bijections, and what fraction of all functions is that for m = 3?

m! bijections out of mm functions. For m = 3: 6/27 = 2/9.


Summary

  • A function f : A → B gives every element of A exactly one image in B. Range ⊆ codomain.

  • Injective: f(a1) = f(a2) → a1 = a2. Surjective: range = codomain. Bijective: both.

  • Counts for |A| = m, |B| = n: nm functions, n!/(n − m)! injections, n! bijections (m = n), 2m − 2 onto maps when n = 2.

  • g ∘ f means f first. Composition is associative, not commutative, and preserves injectivity and surjectivity.

  • Only bijections have inverses; (g ∘ f)−1 = f−1 ∘ g−1.

  • Floor and ceiling appear in every algorithm analysis; know their identities.

  • Bijections define cardinality for infinite sets: ℕ, ℤ, ℚ are countable; ℝ and P(ℕ) are not. There are more problems than programs.

A function is a relation with a promise: exactly one output for every input. In the next chapter, Relations, we drop that promise and study connections between elements in full generality.