R[S[A]].
Exercise 2.2.22. Let R and S be relations.
(a) Show that Dmn(R ◦ S) = S−1[Dmn(R)].
(b) Show that Rng(R ◦ S) = R[Rng(S)].
Exercise 2.2.23. Suppose R is a relation on U. Prove the following conditions:
(a) R is reflexive if and only if IU ⊆ R.
(b) R is irreflexive if and only if IU ∩ R =
(c) R is transitive if and only if R ◦ R ⊆ R.
(d) R is symmetric if and only if R = R−1.
(e) R is antisymmetric if and only if R ∩ R−1 ⊆ IU.
(f) If R is transitive and reflexive, then R ◦ R = R.
2.3. Functions
Functions are of fundamental importance in mathematics. The integers come equipped with binary addition and multiplication functions. In algebra and trigonometry, we learn about the exponential function and the sine, cosine, and tangent functions on real numbers. Just as relations may be viewed as sets, functions may be viewed as relations and hence also as sets.
Definition 2.3.1. A relation F on A × B is a function if, for every x ∈ Dmn(F), there is a unique y ∈ Rng(F) such that xFy. We write y = F(x) for xFy. If Dmn(F) = A and Rng(F) ⊆ B, we say that F maps A into B, written F : A → B. F is one-toone, or injective, if F−1 is also function. F maps A onto B, or is surjective, if Rng(F) = B. F is bijective, or is a set isomorphism from A to B, if F is injective and surjective.
Definition 2.3.2. For any sets A and B, BA is the set of functions mapping A into B.
A function F is said to be binary, or in general n-ary, if Dmn(F) ⊆ A×A (in general An) for some set A. Most commonly studied functions are either 1-ary (unary) or binary.
In the calculus, we studied how to determine whether functions were one-to-one and how to find their domain and range. For example, the function f(x) = x3 is both injective and surjective. The exponential function f(x) = ex is injective but not surjective. The function f(x) = x3 − x is surjective, but it is not injective, since f(0) = f(1) = 0.
In any group G, the function mapping x to its inverse x−1 is a set isomorphism.
Equality of functions may be characterized as follows.
Proposition 2.3.3. Let F and G be two functions mapping set A to set B. Then F = G if and only if F(x) = G(x) for all x ∈ A.
Proof. Suppose first that F = G and let x ∈ A. Since F and G are functions, there are unique elements b and c of B such that F(x) = a and G(x) = c. Then (x, a) ∈ F and (x, c) ∈ G. Since F = G, it follows that both (x, a) and (x, c) are in F. Since F is a function, it follows that b = c, so that F(x) = G(x).
Suppose next that F(x) = G(x) for all x ∈ A. Then, for any a ∈ A and b ∈ B, we have (a, b) ∈ F if and only if F(a) = b, if and only if G(a) = b, if and only if (a, b) ∈ G. Thus F = G.
All the results about relations also apply to functions, but there are some additional nice properties of functions. Note that, for a function F : A → B and C ⊆ B, the inverse image of C under F, F−1[C], is defined by taking the inverse of F as a relation, that is,
Proposition 2.3.4. For any function F : C → D and any subsets A, B of D,
(1) F−1[A ∩ B] = F−1[A] ∩ F−1[B];
(2) F−1[A \ B] = F−1[A] \ F−1[B].
Proof. Let x ∈ C. Then x ∈ F−1[A ∩ B] if and only if F(x) ∈ A ∩ B, if and only if F(x) ∈ A ∧ F(x) ∈ B, if and only if x∈F−1[A] ∧ x ∈ F−1[B], if and only if x ∈ F−1[A] ∩ F−1[B].
Part (2) is left to the reader.
It is not hard to see that F ◦ G is a function if F and G are functions (see the exercises). Here are some interesting results about the composition of functions.
Proposition 2.3.5. Let F : A → B be a function.
(1) F : A → B is one-to-one if and only if, for all C and all G : C → A and H : C → A, F ◦ G = F ◦ H implies G = H.
(2) F : A → B is onto if and only if, for all C and all G : B → C and H : B → C, G ◦ F = H ◦ F implies G = H.
Proof. (1) Let F : A → B. Suppose that F is one-to-one and let G : C → A and H : C → A. Suppose also that F ◦G = F ◦H. Then, for any x ∈ C, F(G(x)) = F(H(x)). Since F is one-to-one, this implies that G(x) = H(x). Thus G = H.
Next suppose that F : A → B is not one-to-one and choose a1 ≠ a2 ∈ A and b ∈ B such that F(a1)
