276 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8
(b) Prove that iff is one to one, then Sf is one to one [recall Exercise 8(b)(ii)].
(c) Prove that iff is onto, then Sf is onto [recall Exercise 8(c)].
(d) Prove that iff is onto, then Sf - is one to one.
(e) Prove that iff is one to one, then Sf - is onto [recall (c) of Theorem 51.
(f) Conclude from (b) through (e) that iff is a bijection, then Sf and Sf - are both
bijections and (Sf)- ' = Sf - l.
(g) Suppose f: A -, B and g: A B satisfy Sf = S,. Prove that f = g.
- Let A and B be sets and let R be a relation from A to B; that is, R s A x B.
Define mappings p,: R -, A and p,: R -+ B by p,(a, b) = a and p,(a, b) = b for all
a E A, b E B. The mappings p, and p, are called the projections of R onto A and
B, respectively.
(a) Give examples to show that:
(i) Neither p, nor p, need be one to one
(ii) Neither p, nor p, need be onto
(b) Find a condition on R that guarantees that p, is one to one. Prove your
assertion.
(c) Find a condition on R that guarantees that p, and p, are both one to one.
Prove your assertion.
(d) Find a condition on R that guarantees that p, is onto. Prove your assertion.
(e) Find a condition on R that guarantees that p, is onto. Prove your assertion.
- (This exercise anticipates the proof of the Schroeder-Bernstein theorem in the
next article.) Consider the sets A = N and B = (5, 10, 15, 19,22, 25,28, 31, 34,.. .).
Define mappings f: A -+ B and g: B -, A by f(1) = 5, f (2) = 10, f (3) = 15, d5) = 3,
6a+10, aeven, a#2
g(10) = 2, g(15) = 1, and f(a) = 3a+ 4, aodd, with
(b + 2)/3, b even, b # 10
g(b)= {(b - 4V3, bodd, b f 5, b # 15
(a) Prove f is a one-to-one mapping of A into, but not onto B, and that g is a
one-to-one mapping of B into, but not onto, A.
(b) The following process is called tracing the ancestry of an element of B. Con-
sider the element 70 of B. We illustrate the process by tracing the ancestry of 70.
We begin by looking for an element a of A such that 70 = f(a). We note that 10
does the job; that is, f(10) = 70. We continue by focusing now on the element
10 of A and seeking an element b E B such that 10 = g(b). This time, b = 28 is
chosen since 10 = g(28). We attempt to continue the process by looking at the
element 28 of B, but at this point, our attempt fails since 28 4 im f. Thus the
process of tracing the ancestry of the element 70 of B terminates, and we say that
70 has an even number of ancestors (two, to be exact, 10 and 28). We may trace
the ancestry of an element of A in a similar manner. You should trace the
ancestry of the element 14 of A.
(c) (i) Find three elements of A having an odd number of ancestors and three
having an even number of ancestors.
(ii) Find three elements of B having an odd number of ancestors and three
having an even number of ancestors.
(iii) Find an element of A for which the process of tracing the ancestry never
terminates. We say that such an element has inJinite ancestry. Find such
an element in B.