algebraic structures, Blogs

Composition of Mappings on a Set

In the past, we have looked at showing that mappings are well-defined, one-to-one, or onto. Here, we will look at the mappings of a set into itself as a set in itself. When doing so, we will find what properties are held by this set. In particular, we will want to know if the set of all mapping from a set to itself is a semigroup, monoid or group.

Semigroup, Monoid or Group?

Let \(A\) be set with \(|A| >1\). Let \(M(A)\) be the set of all mapping from \(A \to A\) and \(\circ\) the composition of mappings. Is \(\langle M(A), \circ \rangle\) a semigroup, monoid or group?

Closure

As we try to determine the answer to this questions, we will work through the different properties that the set must satisfy in order to be any of the above. Before even getting to determining whether or not this set is one of the given things, we must first show that we have an algebra by showing that the set of mappings on a set is closed under composition.

Therefore, we must show that for any two arbitrary mappings on \(A\), the composition of these two mappings is again a mapping on \(A\). Now, we let \(f,g \in M(A)\). Then \(f:A \to A\) and \(g:A \to A\) are mappings. In order to show that \(f\circ g\) is a mapping on \(A\), we must show that the image of any element of \(A\) under this is well-defined in \(A\). Now, if we let \(x \in A\), we see that
\begin{align*}
(f \circ g)(x) &=f(g(x)) \\
&=f(y) \text{ for some } y \in A, \\
&=z \text{ for some } z \in A.
\end{align*}

That is, since \(x \in A\) and \(g\) is well-defined, \(g(x)\) is a well-defined element in \(A\). Furthermore, since \(f(x)\) is well-defined and \(g(x) \in A\), we see that \(f(g(x))\) is again a well-defined in \(A\). That is, \(f \circ g\) is a well-defined mapping from \(A \to A\). If we put this together, we can now give a formal proof that the set is closed under composition.

Proof of Closure

Let \(f,g \in M(A)\) and \(x \in A\). Then note that, since \(x \in A\), we have that \(g(x) \in A\) because \(g\) is a well-defined mapping on \(A\). Furthermore, since \(g(x) \in A\) and \(f\) is a well-defined mapping on \(A\), we get that \(f(g(x)) \in A\). Hence, \(f \circ g: A \to A\) is a well-defined mapping.

Associative

Now that we’ve seen that the set of mappings from a set into itself is closed under composition, we how have to show that the composition of mappings satisfies associativity. That is, we need to show that, for all \(f,g,h \in M(A)\) we have \(f \circ (g \circ h)=(f \circ g) \circ h\). Since two mappings are equal if they map every element to the same point. We get that this is true if and only if
\begin{align*}
(f\circ (g \circ h))(x)=((f\circ g) \circ h)(x).
\end{align*}

We will simplify and compare both of these to see what happens. First, we get
\begin{align*}
(f \circ (g \circ h))(x)&=f((g \circ h)(x)) \\
&=f(g(h(x))).
\end{align*}
We then find that
\begin{align*}
((f \circ g) \circ h)(x)&=(f \circ g)(h(x)) \\
&=f(g(h(x))).
\end{align*}

In both cases, we would find the image of \(x\) by plugging into \(h\), then the answer into \(g\) and this answer into \(f\). Hence, we get the same answer both times. Because this is true for any \(x \in A\), we get that these two equations are indeed equal. We can now give a formal proof.

Note that, since \(M(A)\) is closed for \(\circ\) and \(\circ\) is associative, this gives us that \(A\) is a semigroup.

Proof of Associativity

Let \(f,g, h \in M(A)\) and \(x \in A\). Then note that
\begin{align*}
(f \circ (g \circ h))(x)&=f((g \circ h)(x)) \\
&=f(g(h(x))) \\
&=(f \circ g)(h(x)) \\
&=((f \circ g)\circ h)(x).
\end{align*}

Hence, composition is associative.

Identity

Now that we have associativity and closure, we must determine if there is an identity for composition. That is, does there exists an \(e\) such that \(e \circ f = f \circ e =f\) for all \(f \in M(A)\)? If we take a moment to look at this, we realize that we want to find a function that won’t change anything. Therefore, we will try \(e(x)=x\). Then, note that,
\begin{align*}
(e \circ f)(x)&=e(f(x)) \\
&=f(x) \text{ and } \\
(f \circ e)(x)&=f(e(x)) \\
&=f(x).
\end{align*}
Hence, this is the desired function. Note that, since our set is closed, associative and has an identity under composition, it is a monoid. We are now ready for our proof.

Proof of Identity

Let \(f \in M(A)\). Then let \(e(x)=x\). Note that \(e:A \to A\) is a mapping, since for all \(x \in A\), \(e(x)=x\) is well-defined in \(A\). Furthermore,
\begin{align*}
(e \circ f)(x)&=e(f(x))\\
&=f(x) \\
&=f(e(x)) \\
&=(f \circ e)(x).
\end{align*}
Hence, \(e\) is the identity for composition of mappings.

Inverse

The last thing we need to check for are inverses. If \(M(A)\) is a group, this would mean that every mapping on \(A\) will have an inverse. That is, for all \(f \in M(A)\), there exists a \(g \in M(A)\) such that \(f \circ g=e=g \circ f\).

As we try to answer this, we will run into problems trying to get this to work out. This is because not every mapping has an inverse. To see this, think about the mappings from \(\mathbb{R} \to \mathbb{R}\), are all functions invertible? Recall that a function would be invertible if and only if it is one-to-one and onto. Therefore, if we can find a mapping that is not one-to-one, we can show that not all mappings have inverses, so \(M(A)\) will not be a group. All that’s left is to choose such a mapping.

Now, we have to look at some properties of \(A\). In particular, we want to define a mapping, so we need to know something about the elements in \(A\). Since we are given that \(|A| > 1\), this means that something is in \(A\). Therefore, let \(y \in A\). Then if we defined \(f(x)=y\) for all \(x \in A\), we hope this will not be a one-to-one mapping.

Recall that a mapping is one-to-one if \(f(x)=f(z)\) implies that \(x=z\). Therefore, we need to show that there exists an \(x, z \in A\) such that \(f(x)=f(z)\) and \(x \neq z\). We now have to use that \(|A| > 1\) to say that not only is there some \(y \in A\), but there is also some \(w \in A\) with \(w \neq a\). Now \(f(y)=y=f(w)\), but \(y \neq w\), so \(f\) is not one-to-one and therefore not invertible.

We can now give a formal proof.

Proof of no Inverses

Note that \(|A| > 1\), hence there exists \(w,y \in A\) with \(w \neq y\). Let \(f(x)=y\) for all \(x \in A\). Then note that \(f(y)=f(w)\) but \(w \neq y\). Therefore, there exists an \(f \in M(A)\) that is not invertible. Hence, not all mapping in \(M(A)\) have inverses.

Combining These

We have now shown that under composition, \(M(A)\) is closed, associative has an identity but not all mappings have an inverse. Hence, \(M(A)\) is a semigroup and monoid but not a group.

Conclusion

Thank you for following along as we looked at the set of mapping from a set to itself together with composition and determined that, while this was a monoid, this is not a group. Being able to check these properties in different cases will give us what we should call different sets as we look at other sets. If this helped, make sure to share it with anyone else that will find it useful. Also, be sure to check out our YouTube channel for helpful videos.

1 thought on “Composition of Mappings on a Set”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.