The notion of a function is equally important in programming and in mathematics. Deepening our understanding of the concept will help in both disciplines. I remember how in my first course in programming (C++), the professor introduced functions and said that they are sort of like functions from mathematics, but not quite. Only now with a course on formal methods I start to understand what I think he meant. There are some obvious differences and some really subtle ones, but this post is not directly about this distinction. Instead I cover an insight about mathematical functions that I personally find helpful when thinking about functions in a programming context.

For the rest of this post I am talking about mathematical functions and will write function if I mean programming functions instead.

Starting from scratch (almost)

How is a function defined in terms of other things? At first it seems like this is such a fundamental concept that there is no way to build it from simpler ones. So let me just start from scratch and we will see that with a very small number of simple steps we can go from the notion of sets to the notion of functions.

Our starting point consists of two sets $$A, B$$. If you prefer thinking in examples, think of the natural numbers and a list of strings for example. From these we can build the cartesian product $$A \times B$$ to get a new set. It consists of all pairs that one can build from the elements in $$A$$ and $$B$$. The pairs $$(0,0), (17,3), (53,100)$$ for example are elements of the cartesian product of the natural numbers with themselves.

Pairs are closely related to a relation which is best illustrated with the natural numbers again. Intuitively, two natural numbers $$x, y$$ can relate in various ways to each other: $$x$$ can be greater than $$y$$, equal to $$y$$ or divisible by $$y$$ for example. You can think of many more, but they are all represented in a very simple way. A relation $$R$$ between elements of $$A$$ and $$B$$ is a subset of their cartesian product: $$R \subset A \times B$$. Or in plain English: A relation is described as the set of all pairs which satisfy the relation.

Functions are relations

A relation is a more general concept than a function, so what makes functions special? We can “apply” it to each input in the domain and get some output. Now think of some function $$f:A \rightarrow B$$ of your choice and consider the following set of pairs:

That is a relation on $$A \times B$$ with the special property that each $$a \in A$$ appears in exactly one pair. The point to meditate about is that we can go the other way around too. Consider an arbitrary relation with the same property:

This defines a function by mapping a given $$a$$ onto the $$b$$ such that $$(a,b) \in F$$. The property guarantees that exactly one such output for any given input exists. This relation is a function. And this is how a function is defined in terms of sets, because a relation is also just a set.

Mathematical functions in programming

A function in programming can behave like mathematical function, but it is not easy to see from our definition of a function as relation. This is usually called a pure function. However, from the point of view where a function is just a relation, there are far more obvious mathematical functions in code:

• An initialized array of length n is a function from $$\{0,\dots,n-1\}$$ to its type.
• An object instance is a function from the set of its attribute names to the union of all its attribute types.
• The binary plus operator for integers is a function from (int, int) to int.

There are some subtle points here if you dig really deep. My suggestion is just that this point of view can help (has helped me in the past) to write better code and understand others people code better.