Some definitions regarding functions

A function is a mapping from one set to another set. For a function f, we write "f:D->R" (where "->" is an arrow) to mean that f is a mapping from set D, called the domain, to set R, called the range. That is, f(x) is defined for all x in the set D, and this f(x) value is always in the set R, so long as x is in the set D.

So for example, the domain of the sqrt function is the set of non-negative real numbers, and sqrt's range is also the set of non-negative real numbers. This statement about the domain means that sqrt(-1) is invalid. And the statement about the range means that we know that sqrt(123) will be a non-negative real number, given that 123 is in the domain set.

A function is injective, or "one-to-one", if there does not exist a distinct x and y such that f(x)=f(y). This is the same as being "invertible". If f is an injective function and you have a value for f(x), this determines what x is (it might be hard to compute (perhaps even beyond human capability), but it's unique).

A function is surjective, or "onto", if it covers the range set; that is, every member of the range set is actually equal to f(x) for some x in the domain. Sometimes this is considered to be implied by the "f:D->R" notation, but usually not, and not by my definition in the first paragraph above.

A function is bijective if it is both injective and surjective. This constitutes a "one-to-one correspondence", and is the basis for isomorphisms. If the domain and range are finite sets, then if the function is bijective then the size of the sets (number of members) must be equal.

We only call a bijective function an isomorphism if the mapping preserves some structure of interest, such as, in the case of a graph isomorphism, the list of which vertices are adjacent.


[back to notes about graph isomorphism]
[course notes available (evening section)]
[main course page]