(guest@joequery.me)~ $ |

Isomorphisms and a proof of Cayley's Theorem

(This post is part of the algebra notes series.)

These notes are based on the book Contemporary Abstract Algebra 7th ed.

The main idea of isomorphisms is that different groups and their operation may share a notion of equality, though they may be composed of different types of elements.

Group Isomorphism

define group isomorphism:

An isomorphism Φ from a group G to a group G is a one-to-one and onto function from G to G that preserves the group operation. That is: Φ(ab) = Φ(a)Φ(b) for all a,b∈G.

See the "Functions" section of the Abstract algebra preliminaries article for a refresher on one-to-one and onto functions.

Note that the Φ(ab) applies the operation of G, while Φ(a)Φ(b) applies the operation of G. For example, suppose we're trying to show G≈G, with G a group under the operation "+" and G a group under "*". Then when verifying operation preservation, we would need to verify that Φ(a+b) = Φ(a)*Φ(b)

The four steps to showing G≈G

  1. Define a function Φ from G to G
  2. Prove that Φ is 1-1 (one-to-one)
  3. Prove that Φ is onto
  4. Prove that Φ is operation preserving: Φ(ab) = Φ(a)Φ(b)

Examples of isomorphisms

Example 1

Let G be ℜ under addition, and G be ℜ+ under multiplication. Show G≈G under Φ(x) = 2x.

Step 1: Verify $\phi \colon G \to \overline{G}$. (Does the function makes sense? Does it have the correct domain and range?). It's clear that $\phi(x)=2^{x}$ has a domain of all real numbers. Does $2^{x}$ stay within the range of $\overline{G}$, the positive real numbers? Yes! This is because exponents cannot "change" a positive number to a negative number. \[\] Step 2: Verify $\phi$ is 1-1. Let $x,y \in G$ and suppose $\phi(x)=\phi(y)$. Then \begin{align*} 2^{x} &= 2^{y} \\ \log_{2}2^{x} &= \log_{2}2^{y} \\ x &= y \end{align*} Since $\phi(x) = \phi(y)$ implies $x = y$, $\phi$ is 1-1. \[\] Step 3: Verify $\phi$ is onto. Let $y \in G$. We must show $\exists x \in G$ such that $\phi(x) = y$. Since $y \in \overline{G}$, $y$ is a positive, real number. We can find this $x$ by \begin{align*} \phi(x) =y \Rightarrow 2^{x} &= y \\ log_{2}(2^{x}) &= log_{2}(y) \\ x &= log_{2}(y) \end{align*} \[\] Step 4: Verify $\phi$ preserves the operation. Let $x,y \in G$. Then \begin{align*} \phi(xy) &= 2^{x+y} \\ &= 2^{x}2^{y} \\ &= \phi(x)\phi(y) \end{align*} As discussed earlier, when we are attempting to show that $\phi$ is operation-preserving, $\phi(xy)$ applies the operation of $G$ while $\phi(x)\phi(y)$ applies the operation of $\overline{G}$. So, in this example, the $xy$ in $\phi(xy)$ evaluated to $\phi(x+y)$, which became $2^{x+y}$.

Example 2

Sometimes you can learn more about something by learning what it isn't. So let's describe something that is NOT an isomorphism. Verify the function Φ(x)=x3 is not an isomorphism from ℜ to itself under addition.

We can verify that $\phi$ is 1-1 and onto, but it turns out that $\phi$ is not operation preserving. To demonstrate, let $x,y \in G$. Then \begin{align*} \phi(xy) &= (x+y)^{3} \\ &= (x^{2} + 2xy + y^{2})(x+y) \\ &\ne x^{3} + y^{3} = \phi(x)\phi(y) \end{align*}

Take note: Just because you have shown a function does not form an isomorphism between G and G doesn't mean that the two groups are not isomorphic. You may simply be looking at a specific mapping that does not work! However, the existence of a single isomorphism is enough to call the two groups isomorphic, similar to how a group can be called cyclic if just one element generates the group.

Properties of special functions

As you may be able to tell from the examples, it's pretty important to know the properties of some special functions in order to create a mapping from one group to another. In the above examples, we were given Φ, but that won't always be the case! You must learn the domain/ranges of various functions in order to know when they could potentially work as a mapping. A good list of domains/ranges of important functions can be found here:

http://www.analyzemath.com/DomainRange/domain_range_functions.html

Cayley's Theorem

Every group is isomorphic to a group of permutations

define permutation:

A permutation of a finite set S is a 1-1 and onto function from S to S.

Proof of Cayley's Theorem

Let $G$ be any group. All we know about $\overline{G}$ is that its elements should be permutations. Since we know nothing else about $\overline{G}$, we must use $G$ to construct $\overline{G}$. Elements of $\overline{G}$ should be clearly related to elements of $G$ so that we can easily verify $\phi\colon G \to \overline{G}$ is into when we define $\overline{G}$. So we must create a permutation that somehow uses an arbitrary element of $G$ and, by definition of being a permutation, maps to some element of $G$. One such function is: for any $g$ in $G$, define $T_g(x)=gx$ for all $x$ in $G$. This is essentially multiplication on the left by g. We well take a moment to verify $T_g$ is a permutation on $G$.

Intermediate proof: $T_g$ is a permutation

First, we need to verify that $T_g \colon G \to G$ is well defined. We know the domain of $T_g$ is all of $G$ by how we defined $T_g$. The range is at least a subset of $G$ since $gx \in G \mbox{ for each }x \in G$. So $T_g$ is well defined. We now verify $T_g$ is 1-1. Let $x,y \in G$. Suppose $T_g(x)=T_g(y)$. Then \begin{align*} gx &= gy \\ x &= y \end{align*} Since $T_g(x)=T_g(y)$ implies $x=y$, $T_g$ is 1-1. We now verify $T_g$ is onto. Let $y \in G$. Note $g^{-1} \in G$ since G is a group, and $g^{-1}y \in G$ since $G$ is closed. Observe: \begin{align*} T_g(g^{-1}y)&=g(g^{-1}y) \\ &= (gg^{-1})y \\ &= ey \\ &= y \end{align*} So for an arbitrary $y \in G$, $\exists x \in G$ such that $T_g(x)=y$, so $T_g$ is onto. Since we have shown $T_g$ is a well defined mapping from $G$ to $G$ that is 1-1 and onto, we have shown that $T_g$ is a permutation on $G$.

So now we have for our use a permutation on $G$ constructed using an arbitrary element $g$ of $G$. We take advantage of this by constructing $$ \overline{G}=\{T_g \mid g \in G \} $$ $\overline{G}$ is clearly a set of permutations, but is it a *group* of permutations? We have to verify.

Intermediate proof: $\overline{G}$ is a group

We will attempt to show $\overline{G}$ is a group under function composition. For closure, suppose $T_g, T_h \in \overline{G}$, implying $g,h \in G$. We aim to show that $T_{gh} \in \overline{G}$. Observe: \begin{align*} T_gT_h(x)&=T_g(T_h(x)) \\ &= T_g(hx) \\ &= g(hx) \\ &= (gh)x) \\ &= T_{gh}(x) \end{align*} Since $T_g,T_h \in \overline{G}$ implies $T_{gh} \in \overline{G}$, we can conclude $\overline{G}$ is closed under composition. Now to verify $\overline{G}$ has an identity. Let $T_g \in \overline{G}$. Observe: \begin{align*} T_gT_e(x) &= T_g(T_e(x)) \\ &= T_g(ex) \\ &= T_g(x) \end{align*} and \begin{align*} T_eT_g(x) &= T_e(T_g(x)) \\ &= T_e(gx) \\ &= egx \\ &= gx \\ &= T_g(x) \end{align*} so $\overline{G}$ contains an identity, namely $T_e$. Now we will verify that $\overline{G}$ is closed under inverses. Let $T_g \in \overline{G}$. Since $g \in G, g^{-1} \in G$ and $T_{g^{-1}} \in \overline{G}$. Observe: \begin{align*} T_gT_{g^{-1}}(x) &= T_g(T_{g^{-1}}(x)) \\ &= T_g(g^{-1}x) \\ &= g(g^{-1}x) \\ &= (gg^{-1})x \\ &= x \\ &= T_e(x) \end{align*} and \begin{align*} T_{g^{-1}}T_g(x) &= T_{g^{-1}}(T_g(x)) \\ &= T_{g^{-1}}(gx) \\ &= g^{-1}(gx) \\ &= (g^{-1}g)x \\ &= x \\ &= T_e(x) \end{align*}

So not only have we verified that $T_g$ is a permutation, we have verified that $\overline{G}$ is a group of permutations under the operation of function composition. All that's left for us to do is to find an isomorphism from $G \to \overline{G}$. Hopefully, it will be clear why we went through such an effort to construct a group of permutations based upon arbitrary elements of the group $G$.

$\forall g \in G$, define $\phi(g)=T_g$. It's clear that $\phi \colon G \to \overline{G}$. To show $\phi$ is an isomorphism, we must show that $\phi$ is 1-1, onto, and operation preserving. To verify $\phi$ is 1-1, suppose $\phi(g) = \phi(h)$, meaning $T_g = T_h$. Then \begin{align*} T_g(e) &= T_h(e) \\ ge &= he \\ g &= h \end{align*} Since $\phi(g) = \phi(h)$ implies $g=h$, $\phi$ is 1-1. The onto property of $\phi$ is apparent by how $\phi$ was constructed to map every element $g$ to $T_g$. \[\] All that's left to show is that $\phi$ is operation-preserving. Let $a,b \in G$. Then \begin{align} \phi(ab) &= T_{ab} \\ &= T_aT_b \\ &= \phi(a)\phi(b) \end{align} QED.

If you're wondering why part 2 above follows from part 1, refer back to the intermediate proof of $\overline{G}$ being a group. The closure section will look familiar.

(This post is part of the algebra notes series.)

Date published - March 12, 2013