3.7: Properties of functions

Last updated
Save as PDF

Page ID: 95642

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

As with relations, there are certain simple properties that some (not all) functions have, and it’s useful to reason about them. A function can be:

Injective. An injective function is not only a function, but also kind of a “function in reverse": i.e., not only does no \(x\) map to two different \(y\)’s (which is the case for all functions), but no two \(x\)’s map to the same \(y\). In graphical terms, it does pass a “horizontal line test" in addition to the vertical. Note that this can’t happen if the domain is larger than the codomain (as with wizards & soft drinks), since there aren’t enough \(y\) values to accommodate all the \(x\) values uniquely. So there is no injective function between wizards and soft drinks to be found, no matter how hard we try.

The function phoneExtension — with employees as the domain and four-digit numbers as the codomain — is an example of an injective function. One mapping of this function would be “phoneExtension(Sally) = 1317", indicating that Sally can be reached at x1317. Some of the available extensions may be currently unused, but every employee does have one (and only one) which makes it a function. But since no two employees have the same extension, it is also an injective function.

Injective functions are sometimes called one-to-one functions. (One-to-one and injective are exact synonyms.)
Surjective. A surjective function is one that reaches all the elements of its codomain: some \(x\) does in fact reach every \(y\). Another way of saying this is: for a surjective function, the range equals the entire codomain. You can see that this is impossible if the domain is smaller than the codomain, since there wouldn’t be enough \(x\) values to reach all the \(y\) values. If we added Pepsi and Barq’s Root Beer to our \(Y\) set, we would thereby eliminate the possibility of any surjective functions from \(X\) to \(Y\) (unless we also added wizards, of course).

The function worksIn — with employees as the domain and departments as the codomain — is an example of an surjective function. One mapping of this function would be “worksIn(Sid) = Marketing", indicating that Sid works in the Marketing department. Each employee works for one department, which makes it a function. But at least one employee works in every department (i.e., there are no empty departments with no people in them) which makes it surjective.

Surjective functions are sometimes called “onto" functions. (Onto and surjective are exact synonyms.)
Bijective. Finally, a bijective function is simply one that is both injective and surjective. With an injective function, every \(y\) is mapped to by at most one \(x\); with a surjective function, every \(y\) is mapped to by at least one \(x\); so with a bijective function, every \(y\) is mapped to by exactly one \(x\). Needless to say, the domain and the codomain must have the same cardinality for this to be possible.

The function employeeNumber — with employees as the domain and employee numbers as the codomain — is a bijective function. Every employee has an employee number, and every employee number goes with exactly one employee. As a corollary of this, there are the same number of employees as employee numbers.

Finally, a few extensionally-defined examples. With \(X\) = { Harry, Ron, Hermione } and \(Y\) = { Dr. Pepper, Mt. Dew }, consider the function \(f_1\):

\(f_1\)(Harry) = Mt. Dew
\(f_1\)(Ron) = Mt. Dew
\(f_1\)(Hermione) = Mt. Dew

Is \(f_1\) injective? No, since more than one wizard (all of them, in fact) map to Mt. Dew. Is it surjective? No, since no wizard maps to Dr. Pepper. Is it bijective? No, duh, since to be bijective it must be both injective and surjective.

Now for \(f_2\), change Ron to map to Dr. Pepper instead:

\(f_2\)(Harry) = Mt. Dew
\(f_2\)(Ron) = Dr. Pepper
\(f_2\)(Hermione) = Mt. Dew

Is \(f_2\) injective? Still no, since more than one wizard maps to Mt. Dew. (And of course no function between these two sets can be injective, since there aren’t enough soft drinks for each wizard to have his/her own.) But is it surjective? Yes, it is now surjective, since every soft drink has at least one wizard mapping to it. (Still not bijective for obvious reasons.)

Now let’s add Pepsi and Barqs Root Beer to our set of soft drinks \(Y\), so that it now has four elements: { Dr. Pepper, Mt. Dew, Pepsi, Barqs Root Beer }. Consider the function \(f_3\):

\(f_3\)(Harry) = Pepsi
\(f_3\)(Ron) = Pepsi
\(f_3\)(Hermione) = Mt. Dew

Is \(f_3\) injective? No, since more than one wizard maps to Pepsi. Is it surjective? No, since no wizard maps to Dr. Pepper or Barqs. (And of course no function between these two sets can be surjective, since there aren’t enough wizards for each drink to have one.) And of course not bijective.

Now for \(f_4\), change Ron to map to Dr. Pepper instead:

\(f_4\)(Harry) = Pepsi
\(f_4\)(Ron) = Dr. Pepper
\(f_4\)(Hermione) = Mt. Dew

Still not surjective, of course, but now it is injective, since no drink has more than one wizard. (Still of course not bijective.)

Finally, let’s add one more wizard (Neville) to the mix for two more examples. Let \(f_5\) be:

\(f_5\)(Harry) = Barqs Root Beer
\(f_5\)(Ron) = Dr. Pepper
\(f_5\)(Hermione) = Mt. Dew
\(f_5\)(Neville) = Dr. Pepper

Is \(f_5\) injective? No, since Dr. Pepper has two wizards. Is it surjective? No, since Pepsi has none. Struck out on all counts. However, one small change and everything falls into place:

\(f_6\)(Harry) = Barqs Root Beer
\(f_6\)(Ron) = Pepsi
\(f_6\)(Hermione) = Mt. Dew
\(f_6\)(Neville) = Dr. Pepper

Is this last function injective, surjective, bijective? Yes to all three! Every wizard gets his/her own soft drink, every soft drink gets its own wizard, and no soft drinks (or wizards) are left out. How exciting. This is a perfectly bijective function, also called a bijection. Again, the only way to get a bijection is for the domain and codomain to be the same size (although that alone does not guarantee a bijection; witness \(f_5\), above). Also observe that if they are the same size, then injectivity and surjectivity go hand-in-hand. Violate one, and you’re bound to violate the other. Uphold the one, and you’re bound to uphold the other. There’s a nice, pleasing, symmetrical elegance to the whole idea.