EF Basics

🔗

Section 10.1 Basics

🔗

Subsection 10.1.1 Terminology and basic concepts

🔗

function (working definition): 🔗
a rule which assigns to each input element from a set $A$ a single output element from a set $B$
domain: 🔗
the set of all possible input elements for a function
codomain: 🔗
a set containing all possible output elements for a function
$f : A \to B$: 🔗
$f$ is a function with domain $A$ and codomain $B$
input-output rule: 🔗
the process/algorithm/rule/formula that describes how each input element from the domain will be transformed into an output element in the codomain
$f (a) = b$: 🔗
function $f : A \to B$ associates the codomain element $b \in B$ to the domain element $a \in A$
$a \mapsto b$: 🔗
alternative notation for $f (a) = b$
image (of an domain element): 🔗
when $f (a) = b$ we say that $b$ is the image of $a$ under $f,$ or that $f$ maps $a$ to $b$

🔗
Figure 10.1.1. A Venn diagram of a function transforming a domain element into a codomain element.

🔗

Warning 10.1.2. Domain elements are necessarily inputs, but codomain elements are not necessarily outputs.

🔗

When we define a function, the domain should either be implicitly clear from the input-output rule, or explicitly stated so that the precise collection of allowable input elements is known.

🔗

However, it would be too onerous to do the same for the precise collection of output elements — often when we create a function we won’t initially know exactly what outputs it will produce. The purpose of stating a codomain is so that it is at least clear what type of output element is produced.

🔗

Subsection 10.1.2 Defining functions

🔗

Defining a function is a two-step process, in which we need to specify three pieces of information:

🔗

The first two pieces of information are specified in one step, when we write

f : A \to B .

🔗

This notation indicates that

A

will be the domain and

B

will be the codomain for the function named

f .

Of course, the name of the function is an additional piece of information being specified with this notation, but naming a function is optional (though highly recommended!).

🔗

Specifying the input-output rule may be done in many different ways, e.g. by a formula, table of values, a description of a step-by-step process or algorithm to determine or compute an output given an arbitrary input, etc.

🔗

Example 10.1.3. Defining a function by an input-output formula.

🔗

An input-output formula like

f (x) = \sqrt{x}

defines a function, but we here need to be careful about the domain. The domain and codomain for this function could be specified as

f : R_{\geq 0} \to R,

where

R_{\geq 0}

represents the set of nonnegative real numbers.

🔗

Example 10.1.4. Correctly stating a domain and codomain.

🔗

In the function definition

\begin{aligned} f : R & \to R, \\ x & \mapsto \frac{1}{x^{2}}, \end{aligned}

🔗

the first line of the definition tells us the domain (

R

), codomain (again

R

), and a name for the function (

f

). The second line tells us the input-output rule, so that

f (x) = \frac{1}{x^{2}} .

🔗

However, on closer inspection we discover that the domain has been incorrectly specified, as

x = 0

is not a permissible input for the input-output rule. Instead, we should write

f : R ∖ {0} \to R .

🔗

Even though this function will only ever produce positive real numbers as outputs, the codomain is acceptable as stated. It would be more precise to write

f : R ∖ {0} \to R_{> 0},

🔗

where

R_{> 0}

represents the set of positive real numbers, but it is not necessary to do so.

🔗

Example 10.1.5. Defining a function by an input-output algorithm.

🔗

Consider the function

P (Z) \to N

where outputs are computed according to the following algorithm.

🔗

Given an input element

X \in P (Z)

(which, by definition, is a set of integers), carry out the following.

🔗
Compute the absolute value of each element in $X .$ (If $X$ is empty, skip this step.)
🔗
Determine the minimum result of the absolute value computations in the previous step. (If $X$ is empty, there will not be any absolute value computation results to compare, so take $0$ as the “mininum” instead.)
🔗
Multiply the minimum value found in the previous step by $2$ and add $1 .$ Output this final result.

🔗

However, with the right notation, an algorithm like the above can often be converted into an input-output formula — see Example 10.4.7.

🔗

Example 10.1.6. Defining a function by listing input-ouput pairs.

🔗

For

N = {1, 2, 3}

and

A = {a, b, c, d},

one way to define a function

f : N \to A

\begin{aligned} f (1) & = d, & f (2) & = a, & f (3) & = d . \end{aligned}

🔗

Example 10.1.7. Multi-variable functions.

🔗

In a first course in calculus a student typically studies only single-variable functions, i.e. functions with a single input variable and a single output variable. In subsequent calculus courses a student may study multi-variable functions with multiple input variables, such as

f (x, y) = x^{2} + y^{2} .

🔗

Technically, we should write

f ((x, y)) = x^{2} + y^{2},

🔗

as the proper definition of

f

f : R^{2} \to R,

but the extra brackets convey no additional information and only clutter things up.

🔗

Functions with multiple real output variables are often called vector functions. For example,

g : R \to R^{2}

defined by

g (t) = (t, t^{2})

🔗

can be considered as a vector parametrization of a parabola in the plane.

🔗

And of course we could consider multi-variable vector functions as well. A function

φ : R^{2} \to R^{2}

φ (s, t) = (s - t, s + t)

🔗

could be considered as a change of variables

\begin{aligned} x & = s - t, & y & = s + t . \end{aligned}

🔗

Example 10.1.8. Logical statements as functions.

🔗

A logical statement

S

involving statement variables

p_{1}, p_{2}, \dots, p_{m}

is essentially a multi-variable function

S : Λ^{m} \to Λ,

🔗

where

Λ = {T, F} .

For example, the statement

S (p_{1}, p_{2}) = (p_{1} \to p_{2})

🔗

is a function

S : Λ \times Λ \to Λ,

where

\begin{aligned} S (T, T) & = T, & S (T, F) & = F, & S (F, T) & = T, & S (F, F) & = T . \end{aligned}

🔗

Subsection 10.1.3 Graph of a function

🔗

graph (of a function): 🔗
the set of all input-output pairs for the function
$Δ (f)$: 🔗

🔗
the graph of function $f : A \to B,$ so that

$Δ (f) = {(a, f (a)) | a \in A} \subseteq A \times B$

🔗

Example 10.1.9. Graph of a single-variable, real-valued function.

🔗

The graph of a function

f : R \to R

is a subset of

R \times R = R^{2} .

We usually represent

R^{2}

visually as the

x y

-plane and the graph

Δ (f) \subseteq R^{2}

as a curve in the plane.

The graph $\funcgraph{x \mapsto x^2}$ represented as a curve in the Cartesian plane. — Figure 10.1.10. The graph $Δ (x \mapsto x^{2})$ represented as a curve in the Cartesian plane.

🔗

In the graph of

f (x) = x^{2}

above, each point on the curve represents an element of

R^{2}

which is in the subset

Δ (f) .

For example,

(- 1, 1) \in Δ (f)

but

(- 1, π) \notin Δ (f) .

🔗

Example 10.1.11. Graph of a multi-variable, real-valued function.

🔗

The graph of a function

f : R^{2} \to R

is technically a subset of

R^{2} \times R,

but usually we just think of this as

R^{3},

3

-space. Instead of a curve, such a graph defines a surface in

R^{3} .

For example, the graph of the function

f (x, y) = x^{2} + y^{2}

from Example 10.1.7 is a parabolic cone, i.e. a (non-solid) cone-like surface with parabolic sides.

🔗

Example 10.1.12. Graph of a function defined by a list.

🔗

To describe the graph of the function

f : N \to A

defined in Example 10.1.6, we just need to collect the defined input-output pairs into Cartesian product elements:

Δ (f) = {(1, d), (2, a), (3, d)} .

🔗

This graph can most simply be represented by a table:

$x$	$1$	$2$	$3$
$f (x)$	$d$	$a$	$d$

🔗

Similarly to Example 9.5.7, we can also visualize this graph as a set of “points” relative to a set of perpendicular “axes,” where the horizontal axis represents the domain set and the vertical axis represents the codomain set.

$A$
$d$	$∙$		$∙$
$c$
$b$
$a$		$∙$
	$1$	$2$	$3$	$N$

🔗

Notice that we have not joined the points in the above visualization with lines or a curve, since the three points pictured are the only points on the graph.

🔗

Example 10.1.13. Graph of a logical statement.

🔗

We’ve already encountered the graph of a logical statement: it is usually represented as a truth table. For example, the graph

Δ (S)

of the logical statement

\begin{aligned} S : Λ \times Λ & \to Λ, & S (p_{1}, p_{2}) & = p_{1} \to p_{2}, \end{aligned}

🔗

where

Λ = {T, F}

as usual, can be represented as below.

$p_{1}$	$p_{2}$	$S (p_{1}, p_{2})$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Figure 10.1.14. The graph

Δ (S)

of the logical statement

S (p_{1}, p_{2}) = p_{1} \to p_{2} .

🔗

Unfortunately, our working definition for function is lacking: what is a “rule”? Rather than chasing some circle of definitions, we can come up with a better definition by noticing that the graph of a function contains all the necessary information about the function.

🔗

function (formal definition): 🔗
a subset $F \subseteq A \times B$ such that for every $x \in A$ there is exactly one element $(a, b) \in F$ with $a = x$

🔗

In this formal definition, we are defining a function to be what we previously would have called its graph.

🔗

Example 10.1.15. Formal definition for a single-variable, real-valued function.

🔗

We are now defining a function

f : R \to R

to be the subset of the Cartesian plane

R^{2}

consisting of the graph of the function. In this case, you can think of the “exactly one” requirement as equivalent to the vertical line test: an input value may not produce more than one output value. (Though the “one” part of “exactly one” captures our requirement that a function be defined on every domain element.)

🔗

Subsection 10.1.4 Undefined and well-defined

🔗

We have to be careful defining functions; sometimes what we think is a function turns out to not be a function.

🔗

Example 10.1.16. A function must be defined on the whole domain.

🔗

Again write

N = {1, 2, 3}

and

A = {a, b, c, d},

and consider

F = {(1, a), (3, d)} \subseteq N \times A .

🔗

Does this subset define a function with domain

N

and codomain

A ?

That is, does there exist a function

f : N \to A

such that

F = Δ (f) ?

The answer is no, because there is no input-output pair in

F

with domain element

2 .

If we attempt to consider a function

f

with graph

Δ (f) = F,

we have no way to tell what result

f (2)

should return. In other words, such an

f

will have been left undefined on element

2,

which is supposed to be part of the domain.

🔗

The set

F

does define a function, just not one with domain

N .

If we consider the smaller set

N^{'} = {1, 3},

then there is a function

f : N^{'} \to A

with

F = Δ (f) .

🔗

Example 10.1.17. A function must be well-defined.

🔗

Again write

N = {1, 2, 3}

and

A = {a, b, c, d},

and consider

F = {(1, a), (3, a), (3, d)} \subseteq N \times A .

🔗

Does this subset define a function with domain

N

and codomain

A ?

That is, does there exist a function

f : N \to A

such that

F = Δ (f) ?

The answer is no, because there are more than one input-output pairs with domain element

3 .

In other words, a function

f

with graph

Δ (f) = F

is not well-defined, because we have no way to tell whether

f (3)

should be

a

d .

🔗

Example 10.1.18. An input-output rule does not necessarily define a function.

🔗

Recall that

Q = {\frac{m}{n} | m, n \in Z, n \neq 0} .

🔗

Suppose we attempt to define

f : Q \to Z

f (\frac{m}{n}) = m + n .

This seems like a valid way to define a function, until we realize that, for example,

\begin{aligned} f (\frac{1}{2}) & = 1 + 2 = 3, & f (\frac{2}{4}) & = 2 + 4 = 6. \end{aligned}

🔗

This is nonsense, because

\frac{1}{2}

and

\frac{2}{4}

represent the same element of

Q .

Thus, rule

f

is not well-defined as a function, since to each element of the domain

Q

it associates more than one element of the codomain

Z .

🔗

Subsection 10.1.5 Equality of functions

🔗

equality of functions: 🔗
for $f : A \to B$ and $g : A \to B,$ write $f = g$ if $f (a) = g (a)$ for all $a \in A$

🔗

Example 10.1.19. Seemingly different input-output rules can define the same function.

🔗

The functions

f : R \to R,

f (x) = | x |,

and

g : R \to R,

g (x) = \sqrt{x^{2}},

are equal.

🔗

Subsection 10.1.6 Image of a function

🔗

image of a function: 🔗
the set of all possible outputs of the function
$f (A)$: 🔗

🔗
the image of function $f : A \to B,$ so that

$f (A) = {f (a) | a \in A} \subseteq B$

🔗
Figure 10.1.20. A Venn diagram of the image of a function.

🔗

Warning 10.1.21. Codomain elements are not necessarily image elements.

🔗

We have stated before that a codomain in a function definition may be “larger” than necessary because we do not always know precisely what output elements a given input-output rule will produce. Our idea of codomain is that it should at least tell us what “type” of outputs will be produced, but not necessarily exactly what outputs will be produced.

🔗

With our new concept of function image, we can now repeat this more technically: a function image is always a subset of the codomain, but it might be a proper subset.

🔗

How do we know if a codomain element is an image element?

🔗

For function

f : A \to B

and codomain element

b \in B,

we have

b \in f (A)

if and only if there exists

a \in A

such that

b = f (a) .

🔗

Worked Example 10.1.22. Verifying a function image description.

🔗

Consider

f : R \to R,

f (x) = x^{2} .

Prove

f (R) = R_{\geq 0},

where

R_{\geq 0}

is the set of nonnegative real numbers.

Solution.

Following the Test for Set Equality, we need to show both

\begin{aligned} f (R) & \subseteq R_{\geq 0}, & f (R) & \supseteq R_{\geq 0} . \end{aligned}

To be more explicit about the second set

R_{\geq 0},

we can write

R_{\geq 0} = {x \in R | x \geq 0} .

Show $f (R) \subseteq R_{\geq 0}$ .

Let

y

represent an arbitrary element of

f (R) .

As an element of the image of

f,

y

is an output corresponding to some input. That is, there exists some

x \in R

such that

y = f (x) = x^{2} .

Therefore, since square numbers are always positive, we have

y \geq 0,

and hence

y \in R_{\geq 0} .

Show $f (R) \supseteq R_{\geq 0}$ .

Let

y

represent an arbitrary element of

R_{\geq 0} .

To show

y \in f (R),

we need to find

x \in R

such that

f (x) = y .

Let

x = \sqrt{y},

which is defined since

y \in R_{\geq 0}

implies

y \geq 0 .

Then

f (x) = x^{2} = (\sqrt{y})^{2} = y,

as desired.

🔗

image of a function on a subset: 🔗
the set of all outputs of a function when only fed inputs from a given subset
$f (A^{'})$: 🔗

🔗
the image of the subset $A^{'} \subseteq A$ under a function $f : A \to B,$ so that

$f (A^{'}) = {f (a) | a \in A^{'}} \subseteq B$

🔗

Example 10.1.23.

🔗

We saw in Worked Example 10.1.22 that for

f : R \to R,

f (x) = x^{2},

we have

f (R) = R_{\geq 0} .

Now, the set of integers

Z

is a subset of the domain

R,

so we can compute

f (Z) = {0, 1, 4, 9, 16, \dots, n^{2}, \dots} \subseteq R_{\geq 0} .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 10.1 Basics

Subsection 10.1.1 Terminology and basic concepts

Warning 10.1.2. Domain elements are necessarily inputs, but codomain elements are not necessarily outputs.

Subsection 10.1.2 Defining functions

Example 10.1.3. Defining a function by an input-output formula.

Example 10.1.4. Correctly stating a domain and codomain.

Example 10.1.5. Defining a function by an input-output algorithm.

Example 10.1.6. Defining a function by listing input-ouput pairs.

Example 10.1.7. Multi-variable functions.

Example 10.1.8. Logical statements as functions.

Subsection 10.1.3 Graph of a function

Example 10.1.9. Graph of a single-variable, real-valued function.

Example 10.1.11. Graph of a multi-variable, real-valued function.

Example 10.1.12. Graph of a function defined by a list.

Example 10.1.13. Graph of a logical statement.

Example 10.1.15. Formal definition for a single-variable, real-valued function.

Subsection 10.1.4 Undefined and well-defined

Example 10.1.16. A function must be defined on the whole domain.

Example 10.1.17. A function must be well-defined.

Example 10.1.18. An input-output rule does not necessarily define a function.

Subsection 10.1.5 Equality of functions

Example 10.1.19. Seemingly different input-output rules can define the same function.

Subsection 10.1.6 Image of a function

Warning 10.1.21. Codomain elements are not necessarily image elements.

How do we know if a codomain element is an image element?

Worked Example 10.1.22. Verifying a function image description.

Show $f (R) \subseteq R_{\geq 0}$ .

Show $f (R) \supseteq R_{\geq 0}$ .

Example 10.1.23.

Section 10.1 Basics

Subsection 10.1.1 Terminology and basic concepts

Warning 10.1.2. Domain elements are necessarily inputs, but codomain elements are not necessarily outputs.

Subsection 10.1.2 Defining functions

Example 10.1.3. Defining a function by an input-output formula.

Example 10.1.4. Correctly stating a domain and codomain.

Example 10.1.5. Defining a function by an input-output algorithm.

Example 10.1.6. Defining a function by listing input-ouput pairs.

Example 10.1.7. Multi-variable functions.

Example 10.1.8. Logical statements as functions.

Subsection 10.1.3 Graph of a function

Example 10.1.9. Graph of a single-variable, real-valued function.

Example 10.1.11. Graph of a multi-variable, real-valued function.

Example 10.1.12. Graph of a function defined by a list.

Example 10.1.13. Graph of a logical statement.

Example 10.1.15. Formal definition for a single-variable, real-valued function.

Subsection 10.1.4 Undefined and well-defined

Example 10.1.16. A function must be defined on the whole domain.

Example 10.1.17. A function must be well-defined.

Example 10.1.18. An input-output rule does not necessarily define a function.

Subsection 10.1.5 Equality of functions

Example 10.1.19. Seemingly different input-output rules can define the same function.

Subsection 10.1.6 Image of a function

Warning 10.1.21. Codomain elements are not necessarily image elements.

How do we know if a codomain element is an image element?

Worked Example 10.1.22. Verifying a function image description.

Show f(R)⊆R≥0.

Show f(R)⊇R≥0.

Example 10.1.23.

Show $f (R) \subseteq R_{\geq 0}$ .

Show $f (R) \supseteq R_{\geq 0}$ .