Properties of functions

Remember that a function is a rule that maps one element of one set to only one element of another set?

In this topic, we will divide functions into three classes: injections, surjections, and bijections. This is important because functions of different classes are used in different situations: for example, any good cipher is an injective function. Why? Well, you'll have to read the topic and then come back to this question.

Injections

A function may send several elements of its domain to the same element of its codomain. In terms of arrow diagrams, this means that two or more arrows that start in the domain can point to the same element in the codomain. Some functions, though, associate a different element of its codomain to each element of its domain. They are called injective functions.

A function $f\colon X \to Y$ is called injective (or simply injection) if no two elements in the domain are mapped to the same element in the codomain, i.e.

$$\text{if} \ f(x_1) = f(x_2) \ \ \text{then} \ x_1 = x_2, \ \ \text{for all} \ \ x_1, x_2 \in X.$$For example:

What does it mean for a function not to be injective? It means there are two different elements $x_{1}, x_{2} \in X$such that $f(x_{1}) = f(x_{2})$.

Let's give some examples of injective and non-injective functions.

Suppose $f$ is a function from the set of integers $\mathbb{Z}$ to itself and for every integer $x$

$$f(x) = x + 1$$Is this function injective? Yes, because the equality $x_{1} + 1 = x_{2} + 1$ is possible only when $x_{1} = x_{2}$. You can also notice that $g: \mathbb{Z} \rightarrow \mathbb{Z}$ such that $g(x) = 3x$ is injective.

On the other hand, the function $h: \mathbb{Z} \rightarrow \mathbb{Z}$ such that$$h(x) = x^2$$won't be injective. Indeed, both 2 and -2 are mapped to 4, and a similar situation holds for all pairs of numbers with the same absolute value and different signs.

Surjections

There may be an element of the co-domain of a function that is not the image of any element in the domain. On the other hand, a function may have the property that every element of its co-domain is the image of some element of its domain. Such a function is called onto or surjective.

Definition. A function $f\colon X \to Y$ is a surjective function (or surjection) if the codomain of $f$ is equal to the range of $f$, i.e

$$\text{if} \ y \in Y \ \ \ \text{then exists} \ x \in X \ \ \text{such that} \ f(x) = y.$$For instance:

What does it mean for a function not to be surjective? It means there is an element $y \in Y$such that for any $x \in X$ , $f(x) \neq y$.

We know that both functions $g$ and $h$ from the previous section are functions from $\mathbb{Z}$ to $\mathbb{Z}$:

$$g(x) = 3x, \quad h(x) = x^2$$These functions are not surjective: their codomain $\mathbb{Z}$ contains elements which are not a multiple of 3 (and so cannot be an output of $g$) and negative elements which cannot be a square of some integer (and so an output of $h$). On the other hand, $f: \mathbb{Z} \rightarrow \mathbb{Z}$ defined by the formula $f(x) = x + 1$ is surjective: for any $y \in \mathbb{Z}$, there exists an integer $x$ such that $y = f(x)$. Namely,

$$y = f(y - 1)$$

Bijections

A function $f\colon X \to Y$ is bijective if it is both injective and surjective, i.e

$$\text{for every} \ y \in Y \ \ \text{there is \bf{exactly} one} \ x \in X \ \ \text{such that} \ f(x) = y.$$For example:

We've already seen that $f: \mathbb{Z} \rightarrow \mathbb{Z}$ defined by the formula $f(x) = x + 1$ is injective and surjective, so it is bijective.

Inverse function

If $f\colon X \to Y$ is bijective, there exists a function from $Y$ to $X$ that "undoes" the action of $f$ – that is, it sends each element of $Y$ back to the unique element of $X$ that it came from. This function is called the inverse function for $f$ and denoted by $f^{-1}$.

For example, if $f: \mathbb{R} \rightarrow \mathbb{R}$ maps a real number to its cube:

$$f(x) = x^{3}$$its inverse will be a cube root function :

$$f^{-1}(y) = \sqrt[3]{y}$$In the picture (arrow diagram) showing some function $f$, we can reverse all the arrows and obtain a picture of $f^{-1}$.

Conclusion

In this topic, you've learned about injections, surjections and bijections. Here is a brief summary:

• a function is injective if it associates a different element of its codomain to each element of its domain;
• a function is surjective if every element of its co-domain is the image of some element of its domain;
• a function is bijective if it is both injective and surjective, and every bijective function has an inverse.

All that said, let's get back to the cipher from the intro. Of course, you need an injection function – two different messages should have different encoded versions; otherwise you will never be able to understand what the author meant.