# SP20:Lecture 5 Functions

We spent a lot of time going through examples of things that are or are not functions or partial functions. We also briefly touched on quantifiers: for all and there exists.

## Contents

# Functions

**Function**

When giving a function, you must indicate the domain, the codomain, and an unambiguous rule giving an output for every input.

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 .

## Specifying functions

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:

### direct specification

We can define the output of the function directly:

let domain and codomain of are both ; the image is .

be given by . The### drawings

We can draw a function:

The domain of is , and the codomain of is .

We might also write this as

is given by , , and .### tables

Another way to draw a function is with a table:

x | |
---|---|

a | 1 |

b | 1 |

c | 1 |

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.

### function description

A function need not have an algorithm for constructing the output; a description of the output is also fine. For example, let

give, on input , the closing Dow-Jones Industrial average on day .# Partial functions

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:

**Partial function**

**undefined**if .

**Total**

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).

To summarize,

is a partial function, but not a function (because it is not total), while

is a partial function, a function and a total function (also an injection, a surjection, a bijection, and a relation).

# Quantifiers

For all and there exists are quantifiers: they describe how to interpret a variable in a predicate.## For all

If predicate that depends on , then "for all , " is a proposition. It is true if every possible value of makes evaluate to true.

is a- 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.

## There exists

If predicate depending only on , then "there exists such that P" (written or ) is a proposition. It is true if there is some value that makes evaluate to true.

is a is sometimes called the- 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

When trying to prove an existential statement , you need to give a specific value of (a witness).

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.