SP18:Lecture 6 Function Properties
We gave more examples and non-examples of functions, and defined important properties that functions may have.
- 1 Function examples and non-examples
- 2 Function Properties
Function examples and non-examples
When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input. There are many, many ways to do this, as long as the output is clear. We gave a few examples last lecture, here are some more.
We can define the output of the function directly:
We can draw a function:
We might also write this asis given by , , and .
Another way to draw a function is with a table:
This almost describes a function; the domain is clearly (because if there were any other domain elements, would not be a function); and the rule is clear. However, the codomain is not clear: is it ? Or ? Or , or ? When describing a function with a table, the codomain should be specified somewhere.
A function need not have an algorithm for constructing the output; a description of the output is also fine. For example, letgive, on input , the closing Dow-Jones Industrial average on day .
lists / sequences
Many data structures can be represented by functions with a specialized domain or codomain. For example, one could represent a list of natural numbers as a function ; the kth element of the list would be .
For example, the list
[5,7,1] would be represented as the function given by , , and .
Examples that are not functions
However, the functiongiven by and is a perfectly good function.
undefined (partial) functions
The functiongiven by the following diagram:
A partial function is like a function, except that it does not need to give an output for every input. However, the outputs it does give must be unambiguous. One way to formalize this is by defining a partial function as a function from a restricted domain:
Note that, somewhat confusingly, not all partial functions are functions. However, we do consider a (total) function to be a partial function. We use this terminology because it is standard in mathematics and because it simplifies proofs (so that we don't have to say "a partial or total function" in places where the same argument works for both).
There are certain nice properties that a function can have. We define them here, and prove things about them in the next lecture.
Injectivityone-to-one is a synonym for injective.
because but ).and are both 2 (
In short, every element of the codomain gets "hit". (Mnemonic device: the prefix sur- means "over" or "above", as in "surcharge" or "surname", etc. So each element of the codomain has at least one preimage (and maybe more)).
because there is no with .