2 Sets and functions 2.6 Function composition 2.8 Invertibility

2.7 Function properties

2.7.1 Image of a function

We need to extend our set builder notation a little. If $f:X\to Y$ is a function, we write $\{f(x):x\in X\}$ for the subset of $Y$ consisting of all elements $f(x)$ for $x\in X$ . This set has a special name.

Definition 2.7.1.

Let $f:X\to Y$ . Then the image of $f$ , written $\operatorname{im}(f)$ , is defined to be $\{f(x):x\in X\}$ .

Don’t confuse codomain and image. $Y$ is the codomain of $f$ and the image $\operatorname{im}(f)$ is a subset of $Y$ , but it need not equal $Y$ .

Some people use the word range to refer to one of these two concepts, but since different people use it for different things we will only use the terms image and codomain in MATH0005.

Example 2.7.1.

•

Let $f:\mathbb{R}\to\mathbb{R}$ be the function $f(x)=x^{2}$ . Every element $f(x)$ of the image of $f$ is a nonnegative number, and every nonnegative number is the square of some real number, so $\operatorname{im}(f)=[0,\infty)$ .
•

Let $g:\mathbb{Z}\to\mathbb{Z}$ be defined by $g(z)=3z$ . Then $\operatorname{im}(g)=\{g(z):z\in\mathbb{Z}\}=\{3z:z\in\mathbb{Z}\}$ .

2.7.2 Injection, surjection, bijection

Definition 2.7.2.

Let $f:X\to Y$ be a function.

•

We say $f$ is injective or one-to-one if and only if for all $a,b\in X$ , if $f(a)=f(b)$ then $a=b$ .
•

We say $f$ is surjective or onto if and only if for all $y\in Y$ there is at least one $x\in X$ such that $f(x)=y$ .
•

We say $f$ is a bijection if and only if it is injective and surjective.

Another way to write the definition of surjective would be that a function is surjective if and only if its image equals its codomain.

As an example, here’s a picture of a function $f:\{1,2,3,4,5,6\}\to\{1,2,3,4,5\}$ . There is an arrow from $x$ to $f(x)$ for each $x$ in the domain of $f$ .

Figure 2.9: Drawing of a function from

\{1,2,3,4,5,6\}

\{1,2,3,4,5\}

such that

f(1)=f(2)=1,f(3)=5,f(4)=3,f(5)=1,f(6)=2

The function $f$ shown in Figure 2.9 is not onto because $\operatorname{im}(f)$ is a proper subset of the codomain, specifically, the codomain contains 4 but $\operatorname{im}(f)$ does not. $f$ is not one-to-one because $f(1)=f(2)$ but $1\neq 2$ .

Example 2.7.2.

Here are some more examples to illustrate the injective, surjective, and bijective properties.

•

$f:\mathbb{R}\to\mathbb{R},f(x)=x^{2}$ . It isn’t injective as $f(-1)=f(1)$ and it isn’t surjective as $-1$ is in the codomain, but there’s no element $x$ in the domain such that $f(x)=-1$ .
•

$g:\mathbb{R}\to[0,\infty),g(x)=x^{2}$ . This is not injective for the same reason as before, but this time it is surjective: for each $y\geqslant 0$ we can find an element of the domain which $g$ sends to $y$ : for example. $g(\sqrt{y})=y$ .
•

$h:[0,\infty)\to\mathbb{R},h(x)=x^{2}$ . Not surjective, for the same reason $f$ isn’t surjective (the codomain contains negative numbers, but the image doesn’t contain any negative numbers, so the image doesn’t equal the codomain). But $h$ is injective: if $x$ and $y$ are in the domain of $h$ and $h(x)=h(y)$ then $x^{2}=y^{2}$ , so $x=\pm y$ . Since elements of the domain of $h$ are nonnegative, it must be that $x=y$ .
•

$j:(-\infty,0]\to[0,\infty),j(x)=x^{2}$ . This is injective (for a similar reason to $h$ ) and surjective (for a similar reason to $g$ ), so it is a bijection.

All of these functions had their rules described in the same way, but their properties differed. This shows how important it is to specify the domain and codomain when you talk about a function. A question like “is the function $f(x)=x^{2}$ injective?” doesn’t make any sense unless you do this.

2.7.3 Bijections and sizes of sets

How do we know when two sets have the same size? If you see an alien creature with an apple in each of its hundreds of hands you know it has the same number of apples as it does hands, even if you haven’t counted either the apples or the hands.

You know that because you can pair each apple with the hand holding it. Every apple is held by one hand, and every hand holds one apple.

Suppose there is a bijection $f$ between two sets $X$ and $Y$ . This gives us a way to pair up elements of $X$ and elements of $Y$ such that every element of $X$ is paired with exactly one element of $Y$ .

Consider the pairs $(x,f(x))$ for $x$ in $X$ . Every element of $Y$ appears in exactly one of these pairs (at least one pair because $f$ is onto, at most one pair because $f$ is one-to-one). So a bijection pairs up each element of $X$ with a unique element $f(x)$ of $Y$ .

Figure 2.10: Picture of a bijection

f

from

\{1,2,3\}

\{a,b,c\}

such that

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

The picture shows a bijection $f:\{1,2,3\}\to\{a,b,c\}$ . If we pair each element $x$ of the domain with its image $f(x)$ we get the pairs $\langle 1,c\rangle,\langle 2,b\rangle,\langle 3,a\rangle$ . Because $f$ is a bijection, every element of the domain is paired with exactly one element of the domain and every element of the codomain is paired with exactly one element of the domain. This leads us to make the definition that two sets have the same size (or the same cardinality) if and only if there is a bijection between them.

This definition works even for infinite sets — though it sometimes provides some counter-intuitive results. The set of integers $\mathbb{Z}$ and the set of even integers $2\mathbb{Z}=\{\ldots-4,-2,0,2,4,6,\ldots\}$ have the same size since there is a bijection

	$\displaystyle f:\mathbb{Z}$	$\displaystyle\to 2\mathbb{Z}$
	$\displaystyle f(z)$	$\displaystyle=2z$

even though one is a proper subset of the other.