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.

Functions

Definition: Function
If and are sets, then a function from to (written ) is an unambiguous rule giving, for every input , an output . is called the domain of ; is called the codomain.

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 be given by . The domain and codomain of are both ; the image is .

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:

Definition: Partial function
A partial function is a subset (called the support of ), along with a function We say that if and is undefined if .
Definition: Total
A partial function is total if the support is equal to the domain, i.e. if is a function.

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 is a predicate that depends on , then "for all , " is a proposition. It is true if every possible value of makes evaluate to true.

The fact that is 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 .

• If you know holds for all , then you can conclude holds for any specific . For example, if you know for all , , then you can conclude (since ).

There exists

If is a 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 sometimes called the existential quantifier.

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

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.