SP20:Lecture 5 Functions
The output of a function is unambiguous if there is only one output for any input. It is especially important to check this when the input of the function can be written in different ways. For example, given by , , and is not unambiguous, because so it is not clear if or .
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 during lecture:
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 .
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).
QuantifiersFor all and there exists are quantifiers: they describe how to interpret a variable in a predicate.
- If your goal is to prove "for all , P", you can proceed by choosing an arbitrary value and then proving that P holds for that .
The fact that arbitrary does not mean you get to pick ; on the contrary, your proof should work no matter what you choose. This means you can't use any property of other than that .is
- If you know for all , then you can conclude holds for any specific . For example, if you know for all , , then you can conclude (since ). holds
- To disprove that a predicate holds for all , you only need to choose a specific (called a counterexample) and show that is false. Put another way, the logical negation of "for all , " is "there exists an such that is false".For all and there exists are quantifiers: they describe how to interpret a variable in a predicate.
- To prove that there exists an such that holds, it suffices to give a specific and then prove that is true for that . Such a proof usually starts "let ", and then goes on to prove that holds for the given . is sometimes referred to as a witness for .
- If you know there exists some satisfying , you can use it in a proof by treating as an arbitrary value. is arbitrary because the only thing you know about is that it exists, not what its value is.
- To disprove that there exists an logical negation of "there exists an such that " is "for all x, not P". satisfying , you must disprove for an arbitrary . Put another way, the
Often, in a proof, it is not immediately obvious what the witness should be. Finding one often involves solving some equations or combining some known values.
One nice technique for finding a witness is to simply leave a blank space for the value of and continue on with your proof of . As you go, you may need to satisfy certain properties (for example, maybe you need at one point, and later you need ). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want to satisfy. Once you've completed your proof, you can go back and find a specific value of (say, ) that satisfies all of your wishes.