Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

## § 2.1 Functions

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
F1 = { (1,u), (2,v), (3,w) } and F2 = { (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
F3 = { (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 F3 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
F4 = { (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 F4 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(x1) = f(x2) implies x1 = x2 for all elements x1, x2 in S, then f is said to be a one-to-one function.

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 1S : S -> S is defined by the formula

1S(x) = x for all x in S.

If f : S -> T is a function, then a function g : T -> S is called an inverse for f if

g ° f = 1S     and     f ° g = 1T.

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.

## § 2.1 Functions: Solved problems

Besides reading this section of the text, it might help to get out your calculus textbook and review composite functions, one-to-one and onto functions, and inverse functions. The functions f : R -> R+ and g : R+ -> R defined by f(x) = ex, for all x in R, and g(y) = ln y, for all y in R+, provide one of the most important examples of a pair of inverse functions.

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 : Rn -> Rn by L(x) = Ax, for all x in Rn.

(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 : Rn -> Rm by L(x) = Ax, for all x in Rn. Show that L is a one-to-one function if
det(ATA) 0, where AT is the transpose of A.     Solution

25. Let A be an n × n matrix with entries in R. Define a linear transformation L : Rn -> Rn by L(x) = Ax, for all x in Rn. 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 Ax = x.

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

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

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

```

```