Discrete function is also a math function?

Question

Here is a table of the Staten Island subway:

| STOP | STATION         |
|------+-----------------|
|    1 | St. George      |
|    2 | Tomkinsville    |
|    3 | Stapleton       |
|    4 | Clifton         |
|    5 | Grasmere        |
|    6 | Old Town        |
|    7 | Dongan Hills    |
|    8 | Jefferson       |
|    9 | Grant           |
|   10 | New Dorp        |
|   11 | Oakwood Heights |
|   12 | Bay Terrace     |
|   13 | Great Kills     |
|   14 | Eltingville     |
|   15 | Annadale        |
|   16 | Hugenot         |
|   17 | Prince’s Bay    |
|   18 | Pleasant Plains |
|   19 | Richmond Valley |
|   20 | Arthur Kill     |
|   21 | Tottenville     |

and here is an Elisp function that maps a number to a name:

(defun sisubstops (s)
  (pcase s
    ((guard (or (< s 1) (> s 21))) (message "Hey, just stops 1 through 21, please!"))
    ('1 (message "St. George"))
    ('2 (message "" Tomkinsville))    
    ('3 (message "Stapleton"))
    ('4 (message " Clifton"))
    ('5 (message " Grasmere"))       
    ('6 (message " Old Town"))       
    ('7 (message " Dongan Hills"))
    ('8 (message " Jefferson"))
    ('9 (message " Grant"))     
    ('10 (message " New Dorp"))
    ('11 (message " Oakwood Heights"))
    ('12 (message " Bay Terrace"))   
    ('13 (message " Great Kills"))   
    ('14 (message " Eltingville"))
    ('15 (message " Annadale"))       
    ('16 (message " Hugenot"))  
    ('17 (message " Prince’s Bay"))
    ('18 (message " Pleasant Plains"))
    ('19 (message " Richmond Valley"))
    ('20 (message " Arthur Kill"))   
    ('21 (message " Tottenville"))))

So, when I'm trying to tell students that this is a function of a basically non-continuous phenomenon, i.e., we're not dealing with a function like f(x) = x^2, rather a function that matches stops to names -- but it is still a function -- how can I get this across? One idea would be to got deep into Lambda Calculus and talk about how LC does conditionals. My first goal is to distinguish between continuous versus discrete; and yet I've written a Lisp function that can't really be represented as any sort of normal math function e.g., S(n) = M*nwhere M is some sort of machine or constant that takes a stop number and turns it into a stop name. Any ideas how, yes, this is a function? Or is this just a misnomer, i.e., comp-sci using/abusing the term function. So yes, how is sisubstops really a function?

Answer 1

Focus on the idea that the sets can be finite. They don't need to be defined by a formula. Any set of ordered pairs is a relation. If there is a unique second element for any given first element then it is a function.

For example, the set of pairs {(5,2), (5,4)} is not a function, since the value associated with 5 is not unique. This is a relation: a set of ordered pairs.

But {(5,2), (6,2)} IS a function since the value associated with 5 is unique and the same is true of 6. It is a constant function, by the way, since all values map to 2.

Additionally {(5, 2), (6, 3)} is a function and its inverse is {(2, 5), (3, 6)} which is also a function. Thus the original here is called invertible.

You don't need Lambda Calculus or any mathematics to show what a function is. Finite functions can be computed by table lookup or by hash maps. An array is a function from a certain set of integers to some other set (the values).

Actually functions defined by formulas in computing are often problematic since computations of many values (say Real Values) are only approximate.

Answer 2

Actually they are not the same thing at all. In mathematics a function consists of a univalent map between a domain and a range this is a subset of a cartesian product or just as you have described, a table. The continuous case is an extension to infinate domains and ranges, usually over the real numbers.

Functions in computing do not always behave this way. For example the read() "function" can return any number of values depending on the input, functions can make use of clocks and random number generators - results might even depend on instrumentation e.g. thermometers.

Your question was about discrete vs continuous functions for which I have always found this diagram useful :-

An explanation can proceed by considering numbers instead of shapes - abstracting to sets and then considering fractions/reals etc. But beware - the concepts are not the same in maths and computing although "function" composition works in both cases. Just be clear that this has nothing to do with the discreteness or continuousness of the setup. I suppose the real difference is that functions in computing can have side effects and like read() can be multivalued. Usually in computing the inverse function is harder to define too.

Answer 3

Talk about step functions. This might get the point across that functions do not need to be continuous. (I think going into lambda calculus would just confuse your students here - there's no need.)

As for whether this is really a function - sure it is! To make it clearer, here's something you can do. The written numbers we have - '7', for instance - just stand in for the concept of seven. We could really use the symbol 'a' to stand in for the concept of seven. (Just as we can use any variable name to hold the value inside - though we do tend to choose variable names that 'make sense' to us.)

With that in mind, what keeps us from saying that 'St. George' is just another symbol? Nothing. The symbols don't matter, the relation between them does - that's what makes a function a function.

Answer 4

In math, a function is just an association between each element in a set X and a specific element in set Y. X and Y can be any well defined set: real numbers, rational numbers, integers, even integers, odd integers, all the real numbers except 0, words, names of states, names of cities, etc. Calling a table mapping between between bus stop numbers and bus stop names a function is perfectly sound mathematically as long as no single stop maps to two different names.

Answer 5

I guess I'm slightly confused about what your students are confused about. Did they somehow get tripped up by the definition of function? If so, I can't help but wonder what you did to cause that, because I've never encountered any sort of reaction to the term whatsoever.

As others have addressed, your example is still a perfect set-to-set function. That said, we can certainly code things that at least represent non-functions (such as Random), but calling them "computer functions" seems sufficient to avoid most confusions.

If this comes up in your classroom, I would just say that a mathematical function is a set to set mapping, and that computer functions behave that way often enough to have earned the name "function", even if they're not strictly mathematical functions in the same way. Side-effects (such as mutability) and randomness are two instances where computer functions behave more broadly than mathematical functions.

(Of course, if you want to get down to the level of bits and wires, our non-functions become true functions once again, but that may actually be more confusing depending on the level of the students involved.)