# FA18:Lecture 6 functions

We defined functions and give several examples of things that are functions and are not functions.

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

# Function examples and non-examples

## 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 last lecture, here are some more.

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

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

Similarly, we can think of a sequence of elements of as a function ; is just shorthand for .

## Examples that are not functions

When we write down things that we claim are functions, we must check that they are well-defined, i.e. that they actually are functions.

### ambiguous functions

The function given by , , and is not well-defined, because the output on input 2 is ambiguous.

However, the function given by and is a perfectly good function.

### undefined (partial) functions

The function given by the following diagram:

is not well-defined (i.e. is not a function). A function must give an output for every input; but this function does not give an output for 2.

Although we would not call this a function, it is an example of a partial function.

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

# Operations on functions

## Function equality

Two functions and are equal (written ) if they agree on every input. In other words, if, for all , .

## Image of a function

Definition: Image
If , then the image of (written ) is the set of values that are output by . Formally, or more succinctly, .

Some authors use the term range to refer to the image; I tend to avoid this term, because others use it to refer to the codomain.

## Function composition

One way to combine functions together to create new functions is by composing them:

Definition: Composition
Given a function and a function , the composition of with (written ) is the function given by .

Note that (with the domains and codomains described above), is not defined; it is impossible to take outputs of (which live in the set ) and pass them into (whose domain is ).

For example,

Note that this picture is not backwards; we draw functions from left to right (the input is on the left, and the output is on the right) but we apply them with the input on the right. This means the symbolic composition looks backwards when you draw a picture.

## Identity function

The identity function is a simple but useful function (in fact, it is a bijection):

Definition: Identity function
If is a set, then the identity function on (written or simply if is clear) is the function given by .

## Set of all functions from X to Y

Since functions are things, we can consider sets of functions, and we can even create functions whose domain and codomain are themselves sets of functions

Definition: ⟦X→Y⟧
If and are sets, then denotes the set of all functions with domain and codomain .

Note: I usually use the notation [X → Y], but it interferes with the wiki formatting, so I will use in the wiki. You may use either notation.

For example, if and , then would contain four functions:

• One taking both and to
• One taking both and to
• One taking both to and to
• One taking both to and to

It might be drawn this way (for example, to draw it as the domain of another function):