3. Functions

More on relations

Given a relation r\subseteq A\times B, the set of those elements of A which appear on the left side is called its left-side domain, in other words it is the set \{a\in A\colon \exists_{b\in B} a r b\}. Similarly its right-side domain is \{b\in B\colon \exists_{a\in A} a r b\}. Therefore if, for example, r=\{\left<n,5n\right>\colon n\in\mathbb{N}\}, \mathbb{N} is the left-side domain of r the set of natural numbers divisible by 5 is the right-side domain.

The field of a relation is the union of its left- and right-side domains. In the above example the whole set of natural numbers is the field of r.

The inverse of a relation r is the relation r^{-1}=\{\left<b,a\right>\in B\times A\colon \left<a,b\right>\in r\}.


A relation f\subseteq A\times B will be called a function, if for every argument a\in A it assigns at most one element (value) from B, in other words if:

    \[\forall_{a\in A} \forall_{b,b'\in B}\left<a,b\right>,\left<a,b'\right>\in f\rightarrow b=b'.\]

Sometimes we additionally request that every element of A is used:

    \[\forall_{a\in A}\exists_{b\in B} \left<a,b\right>\in f\]

and then relations which satisfy the first condition but may not satisfy the second are called partial functions. But often (especially when studying mathematical analysis) we ignore the second condition and call all relations satisfying the first condition functions and studying instead their domains.

If f is a function and \left<a,b\right>\in f, we write f(a)=b. The set of all functions f\colon A\to B will be denoted B^A.

E.g. F=\{\left<x,y\right>\colon y^3=x^2\} is a function, because if \left<x,y'\right>,\left<x,y\right>\in F, then y=\sqrt[3]{x^2}=y'.

Meanwhile: F=\{\left<x,y\right>\colon y^2=x\} is not a function, because \left<1,1\right>,\left<1,-1\right>\in F.

One-to-one functions and onto functions

A function is one-to-one (or monomorphism, injection), if different argument always give different values:

    \[\forall_{a,a'\in A} f(a)=f(a')\rightarrow a=a'.\]

A function f\colon A\to B is onto (or epimorphism, surjection), if every value is used:

    \[\forall_{b\in B}\exists_{a\in A} f(a)=b.\]

A bijection is a function which is both onto and one-to-one.

E.g. function f\colon \mathbb{R}\to\mathbb{R}, f(x)=x^2 is not one-to-one, because f(-1)=f(1). It is also not onto, because there does not exist r\in\mathbb{R} such that f(r)=-1.

On the other hand function F\colon\mathbb{N}\to\mathcal{P}{\mathbb{N}}, F(n)=\{n\} is one-to one, because if \{n\}=\{n'\}, then n=n'. It is not onto, because there does not exist n such that F(n)=\{1,2\}.

Function g\colon\mathbb{Z}\to\mathbb{N}, g(a)=|a| is not one-to-one, because g(-1)=g(1). It is onto, since for any n\in\mathbb{N}, we have g(n)=n.

Function G\colon\mathbb{N}^2\to\mathbb{N}^2, G(\left<n,m\right>)=\left<m,n\right> is one-to-one, because if G(\left<n,m\right>)=G(\left<n',m'\right>), then \left<m,n\right>=\left<m',n'\right>, so n=n',m=m'. It is also onto, because for any \left<n,m\right>\in\mathbb{N}^2 we have G(\left<m,n\right>)=\left<n,m\right>. Therefore G is a bijection.

Reverse function

If a function f\colon X\to Y is a bijection, then its reverse relation is also a function, called the reverse function f^{-1}\colon Y\to X. We can also consider the reverse function for a 1-1 function, but it will be defined on its image only.

Function g\colon Y\to X is the reverse function of f\colon X\to Y, if and only if f\circ g =id_Y and g\circ f=id_X. It is if for all y\in Y, f(g(y))=y and for all x\in X, g(f(x))=x.

E.g.: let f\colon [0,\infty)\to [0,\infty), f(x)=x^2. Then f^{-1}=g, where g\colon [0,\infty)\to [0,\infty), g(y)=\sqrt{y}.