Functions

So, a binary relation is a set of ordered pairs, any such set. A binary relation on a set $X$ is a binary relation which is a subset of $X\times X$. A binary relation between sets $X$ and $Y$ is a binary relation which is a subset of $X\times Y$. Now, I want to say what is a function: a function will be a special kind of a binary relation.

Let us fix a binary relation $R$. This just means that $R$ is a set of ordered pairs. Two natural sets assigned to $R$ are its domain and its range: 

$$\mathrm{dom}(R):=\{x:\mathrm{\exists }y,⟨x,y⟩\in R\},$$

$$\mathrm{ran}(R):=\{y:\mathrm{\exists }x,⟨x,y⟩\in R\}.$$

Of course, it's not immediate that these are sets, but there is no doubt that they are classes. In order for a class to be a set, it suffices for it to be contained in a set. More precisely, if a class $C$ is contained in a set $X$, then $C$ is equal to the intersection $X\cap C$. The intersection of a set and a class is a set by Axiom of Comprehension. Hence, $C$ is a set. Back to the case of $R$, in order to show that $\mathrm{dom}(R)$ is a set, we just need to pinpoint one of its supersets. Here's what works:

$$\mathrm{dom}(R)\subseteq \bigcup \bigcup R.$$

To understand this, you'll just need to remind yourself of the definition of an ordered pair. The reasoning here is similar to the one that we had with $\times$. We can see in a similar fashion that $\mathrm{ran}(R)$ is a set.

Now, these two sets are very special when the relation $R$ is concerned. To begin with,

$$R\subseteq \mathrm{dom}(R)\times \mathrm{ran}(R),$$

or in other words, $R$ is a binary relation between $\mathrm{dom}(R)$ and $\mathrm{ran}(R)$. However, more is true: if $A$ and $B$ are any sets and if it is true that $R$ is a binary relation between $A$ and $B$, then we necessarily have that $\mathrm{dom}(R)\subseteq A$ and $\mathrm{ran}(R)\subseteq B$. Said differently, $\mathrm{dom}(R)$ and $\mathrm{ran}(R)$ are the least sets $A$ and $B$ such that $R$ is a binary relation between $A$ and $B$.

If $x\in \mathrm{dom}(R)$, then by definition, there exists $y$ such that $⟨x,y⟩\in R$. Of course, there can be more then one such $y$. For example, if $R=<$ is the standard order of natural numbers, then $0\in \mathrm{dom}(<)$ because $⟨0,1⟩\in <$. However, it is also true that $⟨0,2⟩\in <$. This means that if $x=0$ we can take both $y=1$ and $y=2$ and get $⟨x,y⟩\in <$.

Functions are a special kind of binary relations where this doesn't happen. More precisely, $R$ is a function if and only if $R$ is a binary relation and in addition, for every $x\in \mathrm{dom}(R)$, there exists a unique $y$ such that $⟨x,y⟩\in R$.

Here is an example of a function. Let us define that $⟨x,y⟩\in S$ if and only if $x$ is a natural number and $y=x\cup \{x\}$. If $n$ is a natural number, then we said that $n\cup \{n\}$ is its successor. So, $xSy$ just means "$x$ and $y$ are two consecutive natural numbers (in that order)". However, since every natural number has a unique successor, the relation $S$ meets the requirement to be a function!

A function will very often be denoted by $f$. We also frequently write 

$$f:A⟶B,$$

by which we mean "$f$ is a function, $\mathrm{dom}(f)=A$, and $\mathrm{ran}(f)\subseteq B$". For the set $A$ we require it to be exactly equal to the domain of $f$, while for the set $B$ we just require that all the points in the range of $f$ are contained in it. For example, 

$$S:\omega ⟶\omega ,$$

while $\mathrm{ran}(S)=\omega -\{0\}$ ($0$ is not a successor of anything!).

One more piece of standard notation. So, if $f$ is a function and $x\in \mathrm{dom}(f)$, then there is a unique $y$ such that $⟨x,y⟩\in f$. Thus, it makes sense to name this unique $y$: we name it $f(x)$. Here are examples:

$$S(0)=1,S(2)=3,S(S(3))=5.$$