Mathematics 243, section 1 – Algebraic Structures Selected Solutions, Problem Set 3 October 1, 2003

1.4/9 Let a ∈ A, and assume b, c are both inverses of a for ∗. Consider the “product” (b ∗ a) ∗ c. First, since b is an inverse for a, (b ∗ a) ∗ c = e ∗ c = c (where the last equality comes since e is the identity element for ∗). But we also know ∗ is associative, so (b ∗ a) ∗ c = b ∗ (a ∗ c) = b ∗ e = b. Hence b = c, so the inverse of a is unique (if it exists).

1.4/13 The problem says show that f : A → A has a left inverse (for composition) if and only if f^{−1}(f(S)) = S for all subsets S ⊆ A. From Discussion 2, or Lemma 1.23 in the text, we know that f has a left inverse if and only if f is injective. Hence it suffices to prove that f is injective if and only if f^{−1}(f(S)) = S for all S ⊆ A.

⇒: We show that f injective implies f^{−1}(f(S)) = S for all S. The inclusion S ⊆ f^{−1}(f(S)) is automatic from the definitions of the direct and inverse images (if you don’t see why, work this out from the definitions(!)). So the key point is the other inclusion. Let x ∈ f^{−1}(f(S)). By definition, this means f(x) ∈ f(S), so f(x) = f(a) for some a ∈ S. But we are assuming f is injective, so x = a ∈ S. Hence x ∈ S and f^{−1}(f(S)) ⊆ S, which finishes this part of the proof.

⇐: Now we assume that f^{−1}(f(S)) = S for all S, and use that to show f is injective. Let x ∈ A, and consider the subset S = {x}. By hypothesis in this part, f^{−1}(f({x})) = {x}. If f(a) = f(x) for some a ∈ A, then by the definition of the direct image, f(a) ∈ f(S). Then by the definition of the inverse image, a ∈ f^{−1}(f(S)). But then a ∈ S = {x}, so the only possibility is a = x. Hence f is injective. This concludes the proof.

1.4/13 The problem says show that f : A → A has a right inverse (for composition) if and only if f(f^{−1}(T)) = T for all subsets T ⊆ A. From Discussion 2, or Lemma 1.24 in the text, we know that f has a right inverse if and only if f is surjective. Hence it suffices to prove that f is surjective if and only if f(f^{−1}(T)) = T for all T ⊆ A.

⇒: We show that f surjective implies f(f^{−1}(T)) = T for all T. The inclusion f(f^{−1}(T)) ⊆ T is automatic from the definitions of the direct and inverse images (if you don’t see why, work this out from the definitions(!)). So the key point is the other inclusion. Let x ∈ T. Since f is surjective, there is some a ∈ A such that f(a) = x. By definition a ∈ f^{−1}(T), so x = f(a) ∈ f(f^{−1}(T)). Hence T ⊂ f(f^{−1}(T)).

⇐: Now we assume that f(f^{−1}(T)) = T for all subsets, and use that to show f is surjective. As in problem 13 above, the “action” all goes on with one-element subsets(!) Let x ∈ A be arbitrary, and consider T = {x}. Since T = f(f^{−1}(T)), x = f(a) for some a ∈ f^{−1}(T). But x was arbitrary in A, so this shows that all x in A are in the range of f. Hence f is surjective. This concludes the proof.

1.6/19. Let {A_{λ}}, λ ∈ L be a collection of subsets of A defining a partition of A. That is we are given:

\{ \begin{matrix}A = ⋃_{λ∈L} A_{λ} & and \\ A_{λ} ∩ A_{μ} = ∅ & if λ ≠ μ \end{matrix}

The problem is to show that if we define a relation R on A by

xRy ⇔ x, y ∈ the same A_{λ}

then R is an equivalence relation. (Note: by the second property of a partition, x and y cannot be in more than one of the A_{λ}.) To show that R is an equivalence relation, we check that R is reflexive, symmetric, and transitive.

reflexive: xRx is true for all x since there is just one subset A_{λ} such that x ∈ A_{λ} (the different subsets in the partition do not overlap).

symmetric: If xRy is true, then x, y ∈ A_{λ}. But that says y, x ∈ A_{λ} also, so yRx follows.

transitive: If xRy and yRz, then x, y are in the same A_{λ}, and y, z are in the same A_{λ}. Hence x, z are in the same A_{λ}, so xRz follows.