Home

Algebra problem solved

Problem: "Let A be an infinite set. Let us consider the set of functions \left{f \in A^A : f \ is\hspace{4}surjective\right} and the operation of function composition. Do they form a semigroup? A monoid? A group? Does the right cancellation law hold? What about the left cancellation law? And what happens if we consider the set of all function from A to A instead of the set of surjective functions?"

a) To prove that the set is a semigroup, we must show that associativity takes place, so:

(f \circ g) \circ h (x)= f \circ (g \circ h) (x)

Let's transform both sides to prove it.

(f(g)) \circ h(x) = f (g \circ h(x))

f(g(h(x))) = f (g(h(x)))

b) Monoid is a semigroup with an indentity element.

The identity element is a function e(x) = x because for all functions f \circ e (x)= f (x)

c) Group

This set is not a group because there exist functions with no inverse element. For example, let us consider quadratic function:
f(x) = x^2

Function g can be the inverse element only if f is bijective.

d) Left cancellation property

Definition: An element a in a magma (M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a * b = a * c always implies b = c.

Let us consider f \circ g (x) = f \circ h(x) \Rightarrow h(x) = g(x)

The counterexample here is again the quadratic function
f(x) = x^2
h(x) = x
g(x) = -x

For all arguments f(g(x)) = f(h(x)) but it does not imply g(x) = h(x)

d) Right cancellation property
Definition: An element a in a magma (M,*) has the right cancellation property (or is right-cancellative) if for all b and c in M, b *a = c * a always implies b = c.

This is true.

e)
If we consider a set of all function from A to A, the right cancellation property does not hold:
f(x) = 0
g(x) = x * 3
h(x) = x * 2