We gave more examples and non-examples of functions, and defined important properties that functions may have.

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 [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both ; the image is .

drawings

We can draw a function:

The domain of [math]f [/math] is , and the codomain of [math]f [/math] is .

We might also write this as is given by [math]f(a):=2 [/math], [math]f(b):=1 [/math], and [math]f(c):=3 [/math].

tables

Another way to draw a function is with a table:

x	[math]f(x) [/math]
a	1
b	1
c	1

This almost describes a function; the domain is clearly [math]\{a,b,c\} [/math] (because if there were any other domain elements, [math]f [/math] 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 [math]d [/math], the closing Dow-Jones Industrial average on day [math]d [/math].

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 [math]ℓ(k) [/math].

For example, the list [5,7,1] would be represented as the function given by [math]f(0):=5 [/math], [math]f(1):=7 [/math], and [math]f(2):=1 [/math].

Similarly, we can think of a sequence [math](x_0, x_1, x_2, \dots) [/math] of elements of [math]X [/math] as a function ; [math]x_i [/math] is just shorthand for [math]s(i) [/math].

empty domain

Claim:There is a unique function with empty domain

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 [math]f(1):=5 [/math], [math]f(2):=3 [/math], and [math]f(1):=2 [/math] is not well-defined, because the output on input 2 is ambiguous.

However, the function given by [math]f(1):=5 [/math] and [math]f(2):=5 [/math] 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).

empty codomain

Claim (see proof):

If is a non-empty set, then there is no function .

Function Properties

There are certain nice properties that a function can have. We define them here, and prove things about them in the next lecture.

Injectivity

Definition: Injective

A function is injective if, for all and , whenever , we have .

one-to-one is a synonym for injective.

A good way of thinking about injectivity is that the domain is "injected" into the codomain without being "compressed". In other words, no two (different) inputs go to the same output.

The following function is not injective:

because [math]f(b) [/math] and [math]f(c) [/math] are both 2 (but [math]b \neq c [/math]).

Surjectivity

Definition: Surjective

A function is surjective if for every output , there exists an input such that .

Onto is a synonym for surjective.

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

The following function is not surjective:

because there is no with [math]f(x) = 3 [/math].

Bijectivity

A bijection (or bijective function) gives a way of matching every element of one set to every element of another set. Formally:

Definition: Bijective

A function is bijective if it is both injective and surjective.

SP18:Lecture 6 Function Properties

Contents