Exercise 2.2.14. Show that if R ⊂ A × A, then IA ◦ R = R ◦ IA = R.
Exercise 2.2.15. Show that, for any relations R and S, Rng(R ◦ S) ⊆ Rng(R).
Exercise 2.2.16. For any relations R, S, and T, R ◦ (S ∩ T) ⊆ (R ◦ S) ∩ (R ◦ T).
Exercise 2.2.17. For any relation R ⊆ A × A, with Dmn(R) = Rng(R) = A IA ⊆ R ◦ R−1 and IA ⊆ R−1 ◦ R.
Exercise 2.2.18. For any relations R, S and T, show that
(a) (R ∪ S) ◦ T = (R ◦ T) ∪ (S ◦ T) and
(b) R ◦ (S ∪ T) = (R ◦ S) ∪ (R ◦ T).
Exercise 2.2.19. Prove that, for any relations, R, S, and T, (R ◦ S) ∩ T is empty if and only if (R−1 ◦ T) ∩ S is empty.
Exercise 2.2.20. Let R be a relation and let A, B be arbitrary subsets Dmn(R).
(a) Show that R[A ∪ B] = R[A] ∪ R[B].
(b) Show that R[A ∩ B] ⊆ R[A] ∩ R[B].
(c) Show that equality does not always hold in part (b).
Exercise 2.2.21. Show that for any relations R and S and any A ⊆ Dmn(S), (R ◦ S)[A] = 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].