Discrete Algebraic Methods

Solutions to exercises

Chapter 1

1.1. Suppose that e and f are neutral. Then, e = ef = f .

1.2. Suppose that y and z are inverses of x, in particular, yx = 1 = xz. Then, y = y ⋅1 = yxz = 1 ⋅ z = z.

1.3. We consider the mapping δ : M → M with δ(x) = ax. It is injective since δ(x) = δ(y) implies x = 1 ⋅ x = bax = b ⋅ δ(x) = b ⋅ δ(y) = bay = 1 ⋅ y = y. Then, δ is also surjective because M is finite. Let c be the element in M that is mapped to 1 ∈ M, that is, 1 = δ(c) = ac. Then, b = b ⋅ 1 = bac = 1 ⋅ c = c and therefore ab = 1.

1.4. The set of all mappings f : ℕ → ℕ forms an infinite monoid with composition as operation. The neutral element is the identity mapping id with id(n) = n. Let a: ℕ→ℕ with a(0) = 0 and a(n) = n − 1 for n ≥ 1. For the mapping ...