2 Sets and functions 2.4 De Morgan’s laws 2.6 Function composition

2.5 Functions

2.5.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$ . A ‘rule’ here could be some kind of mathematical formula, but that isn’t necessary — it could simply be a list specifying the output $f(x)$ for each input $x\in X$ .

Definition 2.5.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.

2.5.2 When are two functions equal?

Definition 2.5.2.

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.5.1.

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.5.3.

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.