Surjective functions

Question

As an extension question my lecturer for my maths in computer science module asked us to find examples of when a surjective function is vital to the operation of a system, he said he can't think of any!

I've been doing some googling and have only found a single outdated paper about non surjective rounding functions creating some flaws in some cryptographic systems.

Answer 1

A very simple scheduler implemented by the function random(0, number of processes - 1) expects this function to be surjective, otherwise some processes will never run.

In practice the scheduler has some sort of internal state that it modifies. If you want to see it as a function in the mathematical sense, it takes a state and returns a new state and a process number to run, and in this context it's no longer important that it is surjective because not all possible states have to be reachable. Not a very good example, I'm afraid, but the only one I can think of.

Answer 2

A hashing function should ideally be surjective.

But in general I think the question is too vague to be answered. What is a system? What is a function used inside a system?

Edit: I think the question is not very meaningful. After all there are many cases where you need to be able to produce every desired result. Just think about the identity function and imagine where you could argue that it is used:

• using a reference to a variable in programming
• using a text (or even hex-editor) to produce a file

It would be very bad, if you could not create any bit combination by xor or not when doing bit manipulations.

Answer 3

Master edit:
[btw, thank you for the accepted response.]

In reviewing my response, and these of others in this post, I realized two things.
The first one is the fact that in looking things at a higher level of abstraction, most (all?) of the [counter-]examples provided are a form of "discretization" function. In other words, they correspond to the ubiquitous requirement in computer systems of mapping [possibly infinitely] numerous entities/values to a set (possibly "infinite" too, though most often a finite one) of discrete entities/values. While not all such mappings imply or require a non bijective surjection, many do, hence the several examples found.
The other observation is that the most compelling examples seem to be tied to stochastic (random) processes, or to the underlying primitives which support them.

Both of these things are quite telling, I think, for it mirrors, if only loosely, the way the real world's complexity (read "randomness", at many levels) is exploited in various systems in human (and animals) to produce simplified/stable/discrete maps that represent elements of this complex reality: Another case where mathematics and its practical-oriented friend, Computer Science, team up to describe or to mimic fundamental realities (or... are these realities? hum... we're getting too philosophical...)

It could be a matter of understanding exactly the frame of the question:

• do bijective functions count (they are indeed a special case of a surjection)
  Edit: No, bijective functions are not considered.
• has it got to be a "function" in the sense of a procedural calculation as opposed to say a "relation" as in databases
  Edit: yes, a procedural function of sorts... "take in a value and return another value" (IMHO this distinction is very tenuous as any "map" is a function, regardless of the inner working, but let's entertain this "numeric calculation like" restriction in the spirit of this question)
• define "vital"...

With all these caveats in mind, the following may apply:

• Elementary mathematical functions such as ABS() or even ROUND(), FLOOR() (absolute value, rouding of a decimal/float value to the nearest int respectively) etc.
  In the case of ABS(), for example, used in the context of a program which draws shapes on the screen, using various properties of say symmetry, would be able to count on getting two, and exactly two values to map to a a given value, and to have all values in a given integral range (say from 0 to 10), to be an ABS() value, lest the drawings will start to look funny ;-)
• the Soundex function (and its many derivations)
• Modulo operations, even in such trivial uses as to show the status of a process, every x items processed.
• Classification processes: it is both important that there'd be a important reduction factors (thousands instances mapped to a handful of categories), and it is vital [in some cases] that all instances yield one and only one category (ex: in real-time decision systems).
• Various "simple" mathematical functions used in pseudo-random number generators.
  It is vital that they'd be surjective, so that a) all values within the namespace would be reacheable, indeed, expectations of a specific, often uniform, distribution is implied. (Note, could be bit of a repeat of the "modulo" example above, although it doesn't have to use modulo arithmetic proper, other math function can do)

Following is a bad example, now that Martin clarified that [math operations like functions that] "take in a value and return another value" is what defines "function" hence disqualifying database/table-driven "maps" and such. And also that bijections were not considered either.

• One-to-One relations (or one-to-many relations for that matter) : it can be so important to maintain these that we require triggers etc. to keep up with referential integrity