What Is a Function

I believe all programmers and computer scientists should take the time to appreciate the foundations of mathematics. If you currently attend a university, I highly encourage you to take a foundations course. Learning math foundations expands your mind, and gives you a greater understanding of the concepts we programmers implement every single day. For those of you who do not have the ability or desire to invest in a foundations of mathematics course, but still appreciate the complexities and origins of our field of work, I will very briefly describe what a function really is.

Set Theory

Set theory is an extremely important branch of mathematics. Without set theory, we would not have computability theory.

Definition of Set

The definition of a set is somewhat circular, namely a collection of objects that are known as elements of the set. Sets are denoted using curly braces, and elements of the set are separated by a comma. Examples: {a,b,c,...,z} {1,3,5,7} It's important to note that sets do not take order into account. That is, {a,b,c} = {c,b,a}. Additionally, repeated entries can be ommitted. For example, {a,b,c,c} = {a,b,c}

Complex Sets

More complex sets can be described using the "|" symbol, which is read "such that" or "with the property that" {2x|x is an integer} (Also known as the set of even numbers) {2x+1|x is an integer} (Also known as the set of odd numbers}

Pre-defined Sets

In mathematics, some sets are referred to so much, we have them predefined and represented by symbols. Here is a table of the most commonly used sets.

Set	Symbol
Integers	Z
Real Numbers	R
Rational Numbers	Q

Elements and Subsets

Objects that are in the set are said to be elements of the set. This relationship is denoted element∈Set. For example, 2∈{2,4,6,8}. If every element of set A is also an element of set B, it is said that A is a subset of B, denoted A⊆B. Examples: {1,2,3}⊆{1,2,3,4,5} {2,4,6,...,8}⊆{2x|x∈Z}

Cartesian Product

The Cartesian Product of two sets A and B, denoted AXB, is defined as follows: AXB = {(a,b)|a∈A and b∈B} So AXB yields a set of ordered pairs. Example: A={1,2,3}, B={a,b,c} AXB = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)}

Relations

A relation R from set A to set B is any subset of AxB (defined above). Take our previous example: A={1,2,3}, B={a,b,c} AXB = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)} The following are relations. R1={(1,a),(3,b),(2,a)} R2={(2,b),(2,c),(3,b)}

Domain and Range

The domain and range of a relation R from set A to set B is as follows: Dom(R) = {a∈A|There exists a b∈B such that (a,b)∈R} So for the examples above, Dom(R1) = {1,3,2}, and Dom(R2)={2,3} Ran(R) = {b∈B|There exists an a∈A such that (a,b)∈R} So for the examples above, Ran(R1) = {a,b}, and Ran(R2) = {b,c}

Functions

Now we get to the fun! As a programmer, you already know the notion of a function. When you pass a set of values to a function, you get a value back. An obvious fact that you may not have taken the time to consider is that if you pass in the same input, a function will ALWAYS give you the same result back. Thus, the formal definition of a function is as follows:

A function f is a relation from A to B such that for x1,x2∈Dom(f)=A, x1=x2 implies f(x1)=f(x2).

In other words, in the event two values passed to a function are equal, the corresponding function values will be equal. Essentially, every value only yields one and only one output...just like in our programming functions!

But What About Random Functions?

You might think that random functions, such as PHP's rand(), nullify the concept of a function. It's true, calling rand() can yield multiple values. But upon examining the official documentation, we see the following:

"The random number generator is seeded automatically."

This means the rand() function is automatically passed a value, referred to here as a seed. The function returns an output based on that value. Randomness cannot simply "occur" and be "extracted by" a computer. The general solution is a Pseudorandom number generator, which is what every random function in every programming language uses. Usually the seed is some derivation of the current time, since time never remains constant. However, if your seed is based on a relatively slow unit of time, such as seconds or even minutes, the function will return the same value, guaranteed. This is echoed by a user's comment in the official rand documentation:

"Note that the automatic seeding seems to be done with the current number of seconds which means you can get the same results for several runs on a fast server. Either call srand() yourself with a more frequently changing seed or use mt_rand() which doesn't appear to suffer from the problem."

Are random functions useless? Not at all! Random functions in programming aim to be random enough for general use. Check out this awesome visual example of True Random vs PHP rand().

Further Reading

I hope you've enjoyed this very, VERY brief introduction to functions! Please, do not consider this summary complete in any form. I was mainly hoping to entice you to the beautiful overlap between mathematics and computer science. If you wish to further your ability to think abstractly, I highly recommend reading through Set Theory for Computer Science, a free textbook with excellent information regarding functions and proofs, along with applications for the field of computer science. March 23, 2011