2 Sets and functions 2.5 Cartesian products 2.7 Function composition

2.6 Functions

2.6.1 Definition of function, domain, codomain

Informally, given two sets $X$ and $Y$ a function or map $f$ from $X$ to $Y$ is a definite rule which associates to each $x\in X$ an element $f(x)\in Y$ .

Definition 2.6.1.

We write $f:X\to Y$ to mean that $f$ is a function from $X$ to $Y$ . $X$ is called the domain of $f$ and $Y$ is called the codomain of $f$ .

We refer to the element $f(x)$ of $Y$ as being the “output” or “value” of $f$ when it is given the “input” or “argument” $x$ .

This might seem vague: what is a definite rule? What does associates mean? Should we say that two functions with the same domain and codomain are equal if and only if they have the same rule, or should it be if and only if they have the same output for every input?²² 2 These concepts are called intensional and extensional equality, but that won’t be relevant in MATH0005.

The formal definition of a function is:

Definition 2.6.2.

A function consists of a domain $X$ , a codomain $Y$ , and a subset $f\subseteq X\times Y$ containing exactly one pair $\langle x,y\rangle$ for each $x\in X$ . We write $f(x)$ for the unique element of $Y$ such that $\langle x,f(x)\rangle$ is in $f$ .

In other words, the formal definition of a function is its set of $\langle$ input, output $\rangle$ pairs.

Example 2.6.1.

The function $f:\mathbb{N}\to\mathbb{N}$ such that $f(x)=x+1$ corresponds to $\{\langle 0,1\rangle,\langle 1,2\rangle,\langle 2,3\rangle\ldots\}\subseteq% \mathbb{N}\times\mathbb{N}$

We won’t use the formal definition in MATH0005.

2.6.2 When are two functions equal?

Definition 2.6.3.

Two functions $f$ and $g$ are said to be equal, and we write $f=g$ , if and only if

•

they have the same domain, say $X$ , and
•

they have the same codomain, and
•

for all $x\in X$ we have $f(x)=g(x)$ .

Sometimes the definition has slightly strange-looking consequences.

Example 2.6.2.

Let $f,g:\{0,1\}\to\{0,1\}$ . $f(x)=x^{2}$ . $g(x)=x$ . Are they equal?

(the answer is yes — they have the same domain, same codomain, and the same output for every input in their common domain).

Definition 2.6.4.

For any set $X$ , the identity function $\operatorname{id}_{X}:X\to X$ is defined by $\operatorname{id}_{X}(x)=x$ for all $x\in X$ .

Sometimes we just write $\operatorname{id}$ instead of $\operatorname{id}_{X}$ if it is clear which set we are talking about.