Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Relations and Functions

Functions as Special Relations

See a function as a relation where each input has exactly one output, with domain, codomain, range, images, preimages and composition in Python.

You have met functions as formulas such as f(x) = xยฒ. Set theory gives a more general and more precise definition: a function is a relation with one special feature, that every input has exactly one output. This definition removes any need for a formula, so it covers rules given by tables, by cases, or by no rule at all.

Definition

A function f from A to B, written f : A โ†’ B, is a relation f โІ A ร— B such that

Text
for every a โˆˆ A there is exactly one b โˆˆ B with (a, b) โˆˆ f

We write f(a) = b for (a, b) โˆˆ f. Here A is the domain, B is the codomain, and the range (or image) is the set of outputs that actually occur:

Text
ran(f) = { f(a) : a โˆˆ A } โІ B

The requirement has two halves:

  • Every input has an output (the function is defined on all of A).
  • At most one output per input (the function is well-defined: no input points to two outputs).

Example. A = {1, 2, 3}, B = {a, b}.

  • f = {(1, a), (2, a), (3, b)} is a function. Two inputs may share an output.
  • g = {(1, a), (2, b)} is not a function from A to B: the input 3 has no output.
  • h = {(1, a), (1, b), (2, a), (3, b)} is not a function: the input 1 has two outputs.

Think of the arrow diagram: a function has exactly one arrow leaving every element of the domain. Several arrows may arrive at the same element of the codomain, and some codomain elements may receive none.

flowchart LR
    one["1"] --> a["a"]
    two["2"] --> a
    three["3"] --> b["b"]

The function f: every input has exactly one arrow out. Both 1 and 2 map to a.

Two functions are equal only if they have the same domain, the same codomain and the same pairs. The functions f : โ„ โ†’ โ„, f(x) = xยฒ and g : โ„ โ†’ [0, โˆž), g(x) = xยฒ have the same rule but different codomains, which matters for surjectivity in the next lesson.

Checking the definition in code

For finite sets we can test directly whether a relation is a function.

Python Is this relation a function?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows a general counting rule: there are |B|^|A| functions from A to B, since each of the |A| inputs independently chooses one of |B| outputs. This is why the set of all functions from A to B is written Bแดฌ, and why P(A) can be written 2^A: a subset is a function from A to {0, 1} (the indicator function).

Images and preimages

A function acts on single elements, but also on subsets.

  • The image of a subset S โІ A is f[S] = { f(a) : a โˆˆ S }.
  • The preimage (or inverse image) of a subset T โІ B is fโปยน[T] = { a โˆˆ A : f(a) โˆˆ T }.

The preimage notation does not require f to have an inverse function; it is simply the set of inputs landing inside T. For f(x) = xยฒ on โ„, the preimage of is {โˆ’2, 2} and the preimage of {โˆ’1} is โˆ….

Some facts that are easy to prove with double inclusion:

  • fโปยน[Tโ‚ โˆช Tโ‚‚] = fโปยน[Tโ‚] โˆช fโปยน[Tโ‚‚] and likewise for โˆฉ (preimages are very well behaved).
  • f[Sโ‚ โˆช Sโ‚‚] = f[Sโ‚] โˆช f[Sโ‚‚], but f[Sโ‚ โˆฉ Sโ‚‚] โІ f[Sโ‚] โˆฉ f[Sโ‚‚] with equality only in special cases. For f(x) = xยฒ, take Sโ‚ = {1} and Sโ‚‚ = {โˆ’1}: the left side is f[โˆ…] = โˆ…, the right side is .
Python Images, preimages and a failed equality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

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)). It is the relational composition from the earlier lesson, and it is again a function. Composition is associative: h โˆ˜ (g โˆ˜ f) = (h โˆ˜ g) โˆ˜ f. It is usually not commutative: with f(x) = x + 1 and g(x) = 2x, g(f(x)) = 2x + 2 but f(g(x)) = 2x + 1.

The identity function idโ‚ : A โ†’ A, idโ‚(a) = a, leaves everything unchanged: f โˆ˜ idโ‚ = f and id_B โˆ˜ f = f.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A relation f โІ A ร— B is a function from A to B when:

    A function assigns exactly one output to each element of its domain.
  2. 2. How many functions are there from a 3-element set to a 2-element set?

    Each of the 3 inputs picks one of 2 outputs: 2^3 = 8.
  3. 3. For f(x) = xยฒ on the real numbers, what is the preimage of {9}?

    Both 3 and -3 square to 9.
  4. 4. With f(x) = x + 1 and g(x) = 2x, which is g(f(x))?

    First add 1, then double: 2(x + 1) = 2x + 2.

Summary

  • A function f : A โ†’ B is a relation in which every a โˆˆ A has exactly one b โˆˆ B with (a, b) โˆˆ f.
  • Domain A, codomain B, range ran(f) โІ B; a function is determined by domain, codomain and pairs.
  • There are |B|^|A| functions from A to B.
  • Images f[S] and preimages fโปยน[T] work on subsets; preimages respect unions and intersections.
  • Composition is associative but not commutative.

Next: Injective, Surjective and Bijective Functions