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

§ 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
    F₁ = { (1,u), (2,v), (3,w) } and F₂ = { (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₃ = { (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₃ 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<sub>4</sub> = { (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<sub>4</sub> 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.

 
Definition 2.1.4. Let f : S -> T be a function. Then f is said to map S onto T if for each element y in T there exists an element x in S with f(x) = y.

    If f(x₁) = f(x₂) implies x₁ = x₂ for all elements x₁, x₂ 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 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.

§ 2.1 Functions: Solved problems

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

      (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ⁿ -> R^m by L(x) = Ax, for all x in Rⁿ. Show that L is a one-to-one function if
det(A^TA) 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ⁿ -> Rⁿ by L(x) = Ax, for all x in Rⁿ. 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 : Z₆ -> Z₁₅ by f([x]₆) = [5x]₁₅, for all [x]₆ in Z₆. Show that f gives a well-defined function, and compute its values.     Solution

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

28. Let [a]₁₇ be a fixed element of Z₁₇^×. Define the function f : Z₁₇^× -> Z₁₇^× by f([x]₁₇) = [ax]₁₇, for all [x]₁₇ in Z₁₇^×. 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