Forward to §2.2 | Back to §1.4 | Up | Table of Contents | About this document

**Definition 2.1.1.**
Let S and T be sets. A
**function**
from S into T is a subset F of
S × T such that for each element x in S
there is exactly one element y in T such that
(x,y) belongs to F. The set S is called the
**domain**
of the function, and the set T is called the
**codomain**
of the function.

The subset { y in T |
(x,y) is in F for some x in S }
of the codomain is called the
** image **
of the function.

**Example** 2.1.1.
Let S = { 1,2,3 } and T = { u,v,w }.
The subsets

F_{1} = { (1,u), (2,v), (3,w) } and
F_{2} = { (1,u),(2,u),(3,u) }

of S × T
both define functions since in both cases each element of S
occurs exactly once among the ordered pairs. The subset

F_{3} = { (1,u),(3,w) }

does not define a function with domain S because the element
2 in S does not appear as the first component of any ordered pair.

Note that F_{3}
is a function if the domain is changed to the set { 1,3 }.

Unlike the conventions used in calculus, the domain and codomain
must be specified as well as the ``rule of correspondence''
(list of pairs) when you are presenting a function. The subset

F_{4} = { (1,u),(2,u),(2,v),(3,w) }

does not define a function since 2 appears as the
first component of two ordered pairs.
When a candidate such as F_{4}
fails to be a function in this way, we say that it is not ``well-defined.''

**Definition 2.1.2.**
Let f : S -> T and g : T -> U be functions. The
**composition**
g ° f of f and g
is the function from S to U defined by the formula
(g ° f)(x) = g(f(x)) for all x in S.

**Proposition 2.1.3.**
Composition of functions is associative.

If f is both one-to-one and onto, then it is called a
**one-to-one correspondence**
from S to T.

**Proposition 2.1.5.**
Let f : S -> T be a function.
Suppose that S and T are finite sets with the same number of elements.
Then f is one-to-one if and only if it is onto.

**Proposition 2.1.6.**
Let f : S -> T and g : T -> U be functions.

**(a)**If f and g are one-to-one, then g ° f is one-to-one.**(b)**If f and g are onto, then g ° f is onto.

**Definition 2.1.7.**
Let S be a set. The
**identity**
function 1_{S} : S -> S is defined by the formula

1_{S}(x) = x
for all x in S.

g ° f = 1_{S}
and
f ° g = 1_{T}.

**Proposition 2.1.8.**
Let f : S -> T be a function.
If f has an inverse, then it must be one-to-one and onto.
Conversely, if f is one-to-one and onto, then it has a unique inverse.

Our definition of function is stated rather formally in terms of ordered pairs. (Think of this as a definition given in terms of the ``graph'' of the function.) When actually using this definition, the text almost immediately goes back to what might be a more familiar definition: a function f : S -> T is a ``rule'' that assigns to each element of S a unique element of T.

One of the most fundamental ideas of abstract algebra is that algebraic structures should be thought of as essentially the same if the only difference between them is the way elements have been named. To make this precise we will say that structures are the same if we can set up an invertible function from one to the other that preserves the essential algebraic structure. That makes it especially important to understand the concept of an inverse function, as introduced in this section.

**20.**
The ``Vertical Line Test'' from calculus says that
a curve in the xy-plane is the graph of a function of x
if and only if no vertical line intersects the curve more than once.
Explain why this agrees with Definition 2.1.1.
*Solution*

**21.**
The ``Horizontal Line Test''
from calculus says that a function is one-to-one if and only if
no horizontal line intersects its graph more than once.
Explain why this agrees with Definition 2.1.4.
*Solution*

**22.**
In calculus the graph of an inverse function
f^{ -1} is obtained by reflecting the graph of f about the line y = x.
Explain why this agrees with Definition 2.1.7.
*Solution*

**23.**
Let A be an n × n matrix with entries in **R**.
Define a linear transformation
L : **R**^{n} -> **R**^{n}
by L(**x**) = A**x**, for all **x** in **R**^{n}.

(a) Show that L is an invertible function if and only if det(A) 0.

(b) Show that if L is either one-to-one or onto, then it is invertible.
*Solution*

**24.**
Let A be an m × n matrix
with entries in **R**, and assume that m > n.
Define a linear transformation

L : **R**^{n} -> **R**^{m}
by L(**x**) = A**x**, for all **x** in **R**^{n}.
Show that L is a one-to-one function if

det(A^{T}A) 0,
where A^{T} is the transpose of A.
*Solution*

**25.**
Let A be an n × n matrix with entries in **R**.
Define a linear transformation
L : **R**^{n} -> **R**^{n}
by L(**x**) = A**x**, for all **x** in **R**^{n}.
Prove that L is one-to-one if and only if no eigenvalue of A is zero.
*Solution*

*Note:*
A vector **x** is called an eigenvector of A
if it is nonzero and there exists a scalar
such that
A**x** = **x**.

**26.**
Define the formula
f : **Z**_{6} ->
**Z**_{15} by
f([x]_{6}) = [5x]_{15},
for all [x]_{6} in **Z**_{6}.
Show that f gives a well-defined function, and compute its values.
*Solution*

**27.**
Define the formula
f : **Z**_{24}^{×} ->
**Z**_{12}^{×} by
f([x]_{24}) = [5x]_{12},
for all [x]_{24} in **Z**_{24}^{×}.
Show that f gives a well-defined function, and compute its values.
*Solution*

**28.**
Let [a]_{17} be a fixed element of **Z**_{17}^{×}.
Define the function
f : **Z**_{17}^{×} ->
**Z**_{17}^{×} by
f([x]_{17}) = [ax]_{17},
for all [x]_{17} in **Z**_{17}^{×}.
Is f one to one? Is f onto?
If possible, find the inverse function f^{ -1}.
*Solution*

Solutions to the problems | Forward to §2.2 | Back to §1.4 | Up | Table of Contents