FA18:Lecture 6 functions

From CS2800 wiki

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

Functions


Definition: Function
If [math]A [/math] and [math]B [/math] are sets, then a function from [math]A [/math] to [math]B [/math] (written [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]) is an unambiguous rule giving, for every input [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], an output [math]f(x) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math]. [math]A [/math] is called the domain of [math]f [/math]; [math]B [/math] 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, [math]f : \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] given by [math]f(1) := 2 [/math], [math]f(2) := 2 [/math], and [math]f(1+1):=4 [/math] is not unambiguous, because [math]2 = 1 + 1 [/math] so it is not clear if [math]f(2) = 2 [/math] or [math]f(2) = 4 [/math].


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 [math]f(x) : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]; the image is [math]\{y ∈ \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} y ≥ 0\} [/math].

drawings

We can draw a function:

Fun-a2b1c3.svg

The domain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math], and the codomain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math].

We might also write this as [math]f : \{a,b,c\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \{1,2,3\} [/math] 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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], or [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]? 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 [math]dji : Days \href{/cs2800/wiki/index.php/%E2%86%92}{→} ℝ [/math] give, on input [math]d [/math], the closing Dow-Jones Industrial average on day [math]d [/math].

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 [math]f(x) : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] be given by [math]f(x) := x^2 [/math]. The domain and codomain of [math]f [/math] are both [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]; the image is [math]\{y ∈ \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} y ≥ 0\} [/math].

drawings

We can draw a function:

Fun-a2b1c3.svg

The domain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math], and the codomain of [math]f [/math] is [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math].

We might also write this as [math]f : \{a,b,c\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \{1,2,3\} [/math] 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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]? Or [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], or [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math]? 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 [math]dji : Days \href{/cs2800/wiki/index.php/%E2%86%92}{→} ℝ [/math] 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 [math]ℓ : \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1,\dots,n\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]; the kth element of the list would be [math]ℓ(k) [/math].

For example, the list [5,7,1] would be represented as the function [math]f : \{0,1,2\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php?title=Natural_numbers&action=edit&redlink=1}{\mathbb{N}} [/math] 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]s : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math]; [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 [math]f : \{1,2\} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] 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 [math]f : \{1,2\} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] given by [math]f(1):=5 [/math] and [math]f(2):=5 [/math] is a perfectly good function.

undefined (partial) functions

The function [math]f : \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b\}} [/math] given by the following diagram:

Parfun-1a23b.svg


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 [math]f : A \href{/cs2800/wiki/index.php/%E2%86%9B}{↛} B [/math] is a subset [math]S⊆A [/math] (called the support of [math]f [/math]), along with a function [math]\tilde{f}:S \href{/cs2800/wiki/index.php/%E2%86%92}{→}B [/math] We say that [math]f(x)=y [/math] if [math]\tilde{f}(x) = y [/math] and [math]f(x) [/math] is undefined if [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S [/math].
Definition: Total
A partial function [math]f [/math] is total if the support is equal to the domain, i.e. if [math]f [/math] 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,

Parfun-nosupp.svg

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

Fun-a2b1c3.svg

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

empty codomain

If [math]A [/math] is a non-empty set, then there is no function [math]f:A \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math].

Operations on functions

Function equality

Two functions [math]f [/math] and [math]g : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] are equal (written [math]f = g [/math]) if they agree on every input. In other words, [math]f = g [/math] if, for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]f(x) = g(x) [/math].

Image of a function

Definition: Image
If [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], then the image of [math]f [/math] (written [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) [/math]) is the set of values that are output by [math]f [/math]. Formally, [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{y ∈ B \mid} \href{/cs2800/wiki/index.php/%E2%88%83}{∃x} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\text{ such that }y=f(x)\} [/math] or more succinctly, [math]\href{/cs2800/wiki/index.php?title=Im&action=edit&redlink=1}{im}(f) := \href{/cs2800/wiki/index.php/Set_comprehension}{\{f(x) \mid x ∈ A\}} [/math].

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 [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] and a function [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math], the composition of [math]g [/math] with [math]f [/math] (written [math]g \href{/cs2800/wiki/index.php/%E2%88%98}{∘} f [/math]) is the function [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math] given by [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(a) := g(f(a)) [/math].


Note that (with the domains and codomains described above), [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g [/math] is not defined; it is impossible to take outputs of [math]g [/math] (which live in the set [math]C [/math]) and pass them into [math]f [/math] (whose domain is [math]A [/math]).


For example, Composition.svg

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 [math]A [/math] is a set, then the identity function on [math]A [/math] (written [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id}_A [/math] or simply [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math] if [math]A [/math] is clear) is the function [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] given by [math]id(x)\href{/cs2800/wiki/index.php/Definition}{:=x} [/math].

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 [math]X [/math] and [math]Y [/math] are sets, then [math]⟦X→Y⟧ [/math] denotes the set of all functions with domain [math]X [/math] and codomain [math]Y [/math].

Note: I usually use the notation [X → Y], but it interferes with the wiki formatting, so I will use [math]\href{/cs2800/wiki/index.php/%E2%9F%A6X%E2%86%92Y%E2%9F%A7}{⟦X→Y⟧} [/math] in the wiki. You may use either notation.

For example, if [math]X \href{/cs2800/wiki/index.php/Definition}{:=} \{1,2\} [/math] and [math]Y \href{/cs2800/wiki/index.php/Definition}{:=} \{a,b\} [/math], then [math]\href{/cs2800/wiki/index.php/%E2%9F%A6X%E2%86%92Y%E2%9F%A7}{⟦X→Y⟧} [/math] would contain four functions:

  • One taking both [math]1 [/math] and [math]2 [/math] to [math]a [/math]
  • One taking both [math]1 [/math] and [math]2 [/math] to [math]b [/math]
  • One taking both [math]1 [/math] to [math]a [/math] and [math]2 [/math] to [math]b [/math]
  • One taking both [math]1 [/math] to [math]b [/math] and [math]2 [/math] to [math]a [/math]


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

⟦X→Y⟧.svg