Function And Set Notation

In a recent post we talked about the definition and nature of functions and explored how the term function differs in meaning within the contexts of math and programming.

Most notably, we saw that functions in the mathematical sense are more akin to associative arrays in programming than they are to functions in programming.  This is because both are defined as having a set of keys, paired with a set of values in such a way that one and only one value is associated with each key.

Now that we have explored the definition of functions in both contexts, let’s compare the different types of notation that we use for functions and sets.

What Is A Set?

Since mathematical functions are essentially a mapping between two sets, it makes sense to explore the behaviors, terminology, and symbolic notation associated with sets.

While the word set does require a definition in a strict setting, here we are going to let it be a loosely-defined word that means “an unordered collection of items without redundancy.”  Assuming that “collection of items” needs no further explanation, let’s do some unpacking of the other key pieces of our working definition.

 

Ordered vs. Unordered

While some sets can be ordered (like the set of all real numbers), this is not a requirement for being a set.  Most importantly, different orderings of the same set do not constitute two different sets.  In other words, these two sets are equal:

(1) The set containing the numbers 1, 2, and 3
(2) The set containing the numbers 3, 2, and 1

 

Without Redundancy

The phrase without redundancy refers to the idea that, for example, the set containing the numbers 1, 2, and 3 is the same as the set containing the numbers 1, 1, 2, 2, 3, and 3.  Both sets are said to contain 3 elements and are considered equal no matter how many times each element is listed.

 

Set Notation

There are a lot of ways to notate a set; and the verbal method (as done in the examples above) is certainly one way.

Another common way to denote a set is to list out the elements with a comma between each one, and to place curly brackets around the element list.

 

Ex:

(a) If \(X\) is the set containing the first three positive integers, we can write \(X = \{ 1, 2, 3 \} \).

(b) If \(S\) is the set containing the first one hundred positive integers, we can write \(S = \{ 1, 2, 3, …, 100\}\).

Note that we can save some writing and use an implied pattern as we have done in (b), as long as the pattern is well-defined and not ambiguous.

 

Set Membership

One key idea we want to establish a notation for is that of set membership.

In particular, if \(x\) is an element of set \(X\), then we can write \(x \in X\); and if another item \(x_{1}\) is not in set \(X\), then we can write \(x_{1} \notin X\).

Verbally, we can read the notation \(x \in X\) in any of the following ways:

(1) \(x\) in \(X\)
(2) \(x\) is in \(X\)
(3) \(x\) belongs to \(X\)
(4) \(x\) is a member of \(X\)
(5) \(x\) is an element belonging to \(X\)

All of these phrasings convey the meaning that \(x\) is an item that enjoys membership in the set \(X\).

 

Ex:

(a) For the set of all integers \(\mathbb{Z}\), we have the following:

\(5 \in \mathbb{Z}\)

\(-1 \in \mathbb{Z}\)

\(0 \in \mathbb{Z}\)

\(1.5 \notin \mathbb{Z}\)

 

(b) For the set of all well-formed email addresses (let’s call the set \(E\)), we have:

\(\text{hello@mydomain.com} \in E\)

\(\text{hello@world} \notin E\)

 

(c) For the set of all strings (let’s call the set \(S\)), we have:

\(“7” \in S\)

\(7 \notin S\)

\(\text{“Hello World”} \in S\)

\([ \text{“foo”}, \text{“bar”} ] \notin S\)

 

Calling set elements into existence

Within a discussion about sets, it makes sense to say “let \(s \in S\).”  This is a short, convenient way to identify \(S\) as a set and to stipulate that \(s\) is an entity/item that has the defining characteristics of membership in \(S\).

Furthermore, we might say “suppose \(x \in X\) has property foo” and this provides a good amount of contextual information in an efficient way.

For example, using the set \(\mathbb{R}\) of all real numbers, the phrase “let \(x \in \mathbb{R}\) be positive” is an efficient way to introduce a number \(x\) into discourse, to indicate that it is a real number, and to specify that \(x>0\).

 

Function Notation

Let’s take a look at how to call a function into existence in programming and then how to do the same thing in math.

Creating a function in programming

To use JavaScript and PHP as examples, we can see many similarities.  There are important differences to note here, but those are outside the scope of this article, if you will.

What we are focusing on here is the underlying mechanism consisting of the function keyword, the inputs, and the output indicated by the return keyword.

In JavaScript, we might see a function defined this way:

And in PHP, we might see a function defined this way:

All possible differences and variations aside, it is worth mentioning that the following characteristics of the above examples fall directly in line with how we call a function into existence in mathematics:

(1) We give the function a name (in math sometimes just a symbol will suffice)
(2) We specify the input(s) and indicate which set(s) the inputs come from
(3) We return a value (which may or may not depend on the inputs) and indicate which set the return value comes from

It is true that programming sometimes allows for more flexibility with input types and return types than math.  For example, in PHP we don’t need to enforce that $my_param be an integer if we don’t want to.  In fact, the information regarding input and output types are strictly for documentation purposes and there is nothing in the code that actually enforces that the inputs and return values belong to a specific set (i.e. that they be of a certain type).

Most of the time, if our PHP function expects 7 but instead gets "7", it will still work. However, requiring that our inputs and outputs come from a pre-specified set aligns our thinking with mathematical functions and also makes for more stable code.

 

Creating a function in math

To call a function into existence in math, we invoke the function’s name (we usually default to \(f\) but this can be any letter or symbol) and then we indicate what the input and output sets are (again, \(X\) and \(Y\) are common names for the input and output sets, respectively, if we don’t have a specific context).  The most generic way to express a function in math (which achieves the above requirements in a compact way) is to use the notation \(f \colon X \rightarrow Y\).

To better understand this notation, consider how we would say it in words.  If we let \(f\) be a function and let \(X\) and \(Y\) be sets, then the following statements are all equivalent:

(1) \(f\) is a function whose input set (or domain) is \(X\) and whose output set (or codomain) is \(Y\)
(2) \(f\) takes elements from set \(X\) and assigns them each a value from set \(Y\).
(3) \(f\) maps \(X\) into \(Y\)
(4) \(f \colon X \rightarrow Y\)

Since these statements all mean the same thing, we can gain insight by comparing the verbiage and symbols used in each one.

Starting with the most verbose (1) and looking at each statement in order, we can see that each successive statement is a distillation of the previous.  This is the power of symbolic notation and, in a nutshell, the overarching point of this post.  In distilling statements into symbols there is brevity, precision of meaning, and sometimes even the ability to manipulate the symbols to better understand how things work.

Note that in calling a function into existence via the notation \(f \colon X \rightarrow Y\), we are simply giving a name to all of the function’s parts. We are not even saying what the function does at this point, and this is OK.  In math, we can reason about functions in general where there is no need to pinpoint a single function.

Thus, the notation \(f \colon X \rightarrow Y\) is expressive enough to have meaning all on its own regardless of what the sets \(X\) and \(Y\) actually are or how \(f\) has its key/value relationships defined.

 

Indicating The Key/Value Pairs Established By A Function

Suppose that \(f \colon X \rightarrow Y\) and let \(x \in X\).  How might we indicate the value that \(f\) assigns to \(x\)?  That’s what we’ll consider here.

Giving Our Input And Output Elements A Name

In the interest of establishing a shorthand notation and set of vocabulary for discussing a function’s key/value pairs, suppose that \(y \in Y\) is the value that \(f\) assigns to \(x \in X\).  We can then write \(f(x)=y\); and this can be read aloud in any of the following ways:

(a) \(f\) maps \(x\) to \(y\)
(b) The value (or image) of \(x\) under \(f\) is \(y\)
(c) When \(f\) acts on \(x\), the resulting value is \(y\)
(d) \(f\) of \(x\) equals \(y\)

Several combinations of these phrases are common, but the convention is that the word value always refers to the output or result associated with a given input.

In most cases, it is easiest to read the notation \(f(x) = y\) as “\(f\) of \(x\) equals \(y\)”.

Sometimes, we may also use the notation \(x \mapsto y\), especially if we do not have a named function such as \(f\).

For example, the function \(x \mapsto 7x\) is a nameless function whose output is equal to the given input times 7.  Note that the input set must be a set of numbers, and if we were to dive deeper into the example we’d need to clarify exactly what subset of numbers we are considering.

 

Determining The Output Based On A Given Input

So far, for our generalized function \(f \colon X \rightarrow Y\), we have designated a symbol \(y\) to represent the output element associated with a general input \(x\); but we still have not discussed how to find or compute an output if we are given a specific input.  This is the point where we are no longer able to talk in general terms, since each function behaves differently with regard to how it maps inputs to outputs.

In short, there is not a single correct way to indicate the entire set of key/value pairs established by a function.

While some functions allow the use of a formula or equation to establish an underlying relationship between inputs and outputs, other functions can only be expressed by explicitly listing each key/value pair, or by giving a verbal description of how the output is to be calculated.

Ex:

(a)

Let \(X=\{ a, b, c, d, \ldots, z \}\), and let \(Y=\{ 1, 2, 3, 4, 5, \ldots \}\)

We can define a function \(f \colon X \rightarrow Y\) in several ways.  The most obvious way would be to let \(f\) map each letter in \(X\) to the integer in \(Y\) which indicates its order in the English alphabet:

\(f(a) = 1\)
\(f(b) = 2\)
\(f(c) = 3\)
etc

We could also map each letter to a specific multiple (like \(5\)) of the integer representing its order:

\(f(a) = 5\)
\(f(b) = 10\)
\(f(c) = 15\)
etc

If we really wanted, we could even haphazardly assign an integer to each letter by hand. There is no requirement that there be any semblance of order:

\(f(a) = 1,000,023\)
\(f(b) = 6\)
\(f(c) = 9,483\)
etc

Of course, with the last example we would have to write the values for all members of \(X\) if we wanted to have a well-defined function, since there is no pattern that allows for inference.

The above example shows that with functions, we don’t need to utilize every element of \(Y\) for \(f\) to still be considered a function that maps \(X\) into \(Y\).  We must be careful though, because we do need to have \(f\) acting on all elements of \(X\).  This is part of the definition of a function, which states that each element in \(X\) must map to one and only one element of \(Y\).

 

(b) To use a more traditional math example, consider the function defined by \(f(x)=x^2\).

For starters, let’s note that our mapping notation \(f \colon \mathbb{R} \rightarrow \mathbb{R}\) applies here but usually goes unstated in math class.  However, the notation does provide us the context that \(x\) comes from the set of real numbers and that the result of squaring any real number (i.e. the values of the function) will always be another real number.  In short, we could say that \(f\) maps \(\mathbb{R}\) into \(\mathbb{R}\).

If we like, we could express the function as \(x \mapsto x^2\), but again we typically use \(f(x)=x^2\) since this notation is more versatile and also we can then refer to the function using the name \(f\) when needed.

In either case, the simple formula lets us determine the unique value for any given input.  If we input \(3\), then the result is \(9\).  If we input \(\pi\), the result is \(\pi^2\).  In general, for any of the infinitely many inputs we could think of, we have a simple and well-defined way to determine the function’s unique output.

 

A Function As A Set Of Ordered Pairs

One final way we’ll mention regarding methods of describing a function’s key/value pairs is to express the function as a set of ordered pairs.  In case the term ordered pair is not familiar, this is essentially what we get when we plot a point in the \(xy\)-plane.  For example, \((3, 7)\) is an ordered pair whose first coordinate is \(3\) and whose second coordinate is \(7\).

When using ordered pairs in relation to functions, we use the convention that the first coordinate represents an element from the function’s input set and the second coordinate represents the value of the function for that input.

Ex.

Consider the function defined by the set of ordered pairs \(f = \{(1,5), (-1,2), (6,-4)\}\).

We can make the following observations using the different types of notation we’ve learned so far:

(a) \(f(1)=5\), \(f(-1)=2\), and \(f(6)=-4\)

(b) \(f \colon \{-1,1,6\} \rightarrow \{-4,2,5\}\) (remember, the order of the listed elements in a set is meaningless.  We’re just saying the input set is \(\{-1,1,6\}\) and the output set is \(\{-4,2,5\}\) and we are not implying anything about the function mapping by the way we order the set elements here).

(c) For \(f\), we have \(1 \mapsto 5\), \(-1 \mapsto 2\), and \(6 \mapsto -4\)

(d) If \(x \notin \{1,-1,6\}\), then \(x\) is not in the domain of \(f\)

 

Conclusion

I hope that you learned some new terminology and notation while reading this post.  I also hope that some of the math concepts resonated with what you know about programming, even if the connection was not explicitly mentioned.

While we focused mainly on math here and not as much on programming, I think that we have established some important verbal and symbolic language that can help us dig further into programming concepts in the future in order to better understand the nature of code via the lens of mathematics.