{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "

\n", "Abstract Algebra: An Interactive Approach, 2e\n", "

\n", "\n", "

\n", "\n", "\n", "\n", "

\n", "Chapter 4
\n", "Mappings Between Groups\n", "

\n", "\n", "\n", "

Initialization: This cell MUST be evaluated first:

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%display latex\n", "try:\n", " load('absalgtext.sage')\n", "except IOError:\n", " load('/media/sf_sage/absalgtext.sage')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Isomorphisms
\r\n", "Homomorphisms
\r\n", "The Three Isomorphism Theorems
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

Isomorphisms

\r\n", "\r\n", "
\r\n", "We have now seen two examples of groups of order 6, namely, S₃ and the quotient group G/M just studied. Are these really two \r\n", "different groups? Technically, yes, since the names for their elements are totally different. However, there is a correlation between these two groups.

\r\n", "\r\n", "EXAMPLE:
\r\n", "The group S₃ could be written simply as {e, a, b, a·b, b², \r\n", "a·b²}, whereas the group G/M was written\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

{{e, a·b²·c, c²,\r\n", "a·b²·c³},

{a, b²·c, a·c²,\r\n", "b²·c³},

{b, a·b·c, b·c², a·b·c³},

{a·b, b·c, a·b·c², b·c³},

{b², a·c, b²·c², a·c³},

{a·b², c, a·b²·c², c³}}.

\r\n", "
\r\n", "In the last experiment, you were asked to rearrange the elements of S₃ so that the multiplication tables for these two groups had the same color \r\n", "pattern. With a little fiddling, one might have come up with a correlation like the following:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

e	↔	{e, a·b²·c, c²,\r\n", "a·b²·c³}
a·b²	↔	{a, b²·c, a·c²,\r\n", "b²·c³}
b	↔	{b, a·b·c, b·c², \r\n", "a·b·c³}
a	↔	{a·b, b·c, a·b·c², b·c³}
b²	↔	{b², a·c, b²·c², a·c³}
a·b	↔	{a·b², c, a·b²·c², c³}

\r\n", "\r\n", "Thus, by using an ordering of S₃ such as
\r\n", "

{e, a·b², b, a, b², \r\n", "a·b},

\r\n", "the multiplication tables for G/M and S₃ have the exact same color pattern.

\r\n", "\r\n", "What does that mean? Suppose we define a function from S₃ to G/M. We are used to plugging real numbers into a function, \r\n", "and having a real number come out. But there is no reason why we cannot have a function which is evaluated at an element of a group! We define the function \r\n", "ƒ(x) as follows: \r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

ƒ(e)	=	{e, a·b²·c, c²,\r\n", "a·b²·c³},
ƒ(a·b²)	=	{a, b²·c, a·c²,\r\n", "b²·c³},
ƒ(b)	=	{b, a·b·c, b·c², \r\n", "a·b·c³},
ƒ(a)	=	{a·b, b·c, a·b·c², b·c³},
ƒ(b²)	=	{b², a·c, b²·c², a·c³},
ƒ(a·b)	=	{a·b², c, a·b²·c², c³}.

\r\n", "\r\n", "Then we have \r\n", "

ƒ(x·y) = ƒ(x) · ƒ(y).

\r\n", "
\r\n", " \r\n", "We can also notice two other things about the function ƒ. Note that two different elements of S₃ produce two different elements of \r\n", "G/M.That is, ƒ(x) is one-to-one, or injective. Another thing to notice is that every element of G/M \r\n", "appears as ƒ(x) for some element x. This is expressed by saying that ƒ(x) is onto, or surjective. \r\n", "If a function, such as this one, is both injective and surjective, we say that it is bijective.

\r\n", " \r\n", "This function allows us to see that the two groups S₃ and G/M are really the same group in disguise. \r\n", "The function indicates how to "relabel" the elements so that one group becomes the other group.

\r\n", " \r\n", "DEFINITION 4.1
\r\n", "Let G₁ and G₂ be two groups. An isomorphism from G₁ to G₂ is a one-to-one \r\n", "function sending elements of G₁ to elements of G₂ such that\r\n", "

ƒ(x·y) = ƒ(x) · ƒ(y) for all x, y ∈ G₁.

\r\n", "
\r\n", "If there exists an isomorphism from G₁ to G₂ that is also onto, then we say that G₁ and \r\n", "G₂ are isomorphic, denoted by \r\n", "

G₁ ≈ G₂.

\r\n", "\r\n", "
\r\n", "Because of the function we defined above, it is clear that S₃ is isomorphic to G/M. We now have a way of saying that the two \r\n", "groups have essentially the same multiplication table, as indicated by the color patterns.

\r\n", " \r\n", "It should be noted that ≈ is an equivalence relation on groups. (Reflexive property is obvious, symmetric and transitive properties are covered in Problems 1 and 2.) \r\n", "One of the most important yet extremely hard problems in group theory is to find all of the groups of order n. Of course, there are really an infinite \r\n", "number of different groups if we can relabel the elements. But the concept of isomorphism allows us to say that S₃ and G/M \r\n", "are really the same group. So we may ask how many non-isomorphic groups there are of order n. Even though this is still unsolved in general, \r\n", "we do know of an upper bound for the number of groups.\r\n", " \r\n", "

\r\n", " \r\n", "PROPOSITION 4.1
\r\n", "There are at most n^(n²) non-isomorphic groups of order n.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Of course, not very many of these tables will actually form a group. Even though this proposition gives us an upper bound, it is too big to be practical. \r\n", "The following proposition will be helpful for many values of n.
\r\n", " \r\n", "

\r\n", " \r\n", "PROPOSITION 4.2
\r\n", "For n a given positive integer, every cyclic group of order n is isomorphic to Z_n.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "How does this proposition help us determine all of the groups of order n? If p is prime, then Corollary 3.3 tells us that the groups must \r\n", "be cyclic. Then this proposition would tell us that the group must be isomorphic to Z_p. So in fact, if p is prime, there is only \r\n", "one non-isomorphic group of order p.
\r\n", "
\r\n", " \r\n", "Let us see if we can find all isomorphic groups of order up to 8. The following lemma will help us out.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 4.1
\r\n", "Suppose a group G whose order is greater than 2 has all non-identity elements being of order 2. Then G has a subgroup isomorphic \r\n", "to Z₈^*.

\r\n", " \r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "The group Z₈^* is also called the Klein 4-group. We are now ready to find all groups of \r\n", "order n up to n = 8.

\r\n", "\r\n", "\r\n", "n = 1: The one element must be the identity, so we have the trivial group, {e}.

\r\n", "\r\n", "n = 2: Since 2 is prime, the only group is Z₂.

\r\n", "\r\n", "n = 3: Since 3 is prime, the only group is Z₃.

\r\n", "\r\n", "n = 4: Every element must be of order 1, 2, or 4. If there is an element of order 4, the group is cyclic. On the other hand, if all of non-identity \r\n", "elements are of order 2, then Lemma 4.1 states that there is a subgroup isomorphic to Z₈^*. But this subgroup must be the group itself. \r\n", "Thus, there are two possible groups: Z₄ and Z₈^*.
\r\n", "
\r\n", "\r\n", "n = 5: Since 5 is prime, the only group is Z₃.

\r\n", "\r\n", "n = 6: Every element must be of order 1, 2, 3 or 6. If there is an element of order 6, the group is cyclic. If all non-identity elements are of order 2, \r\n", "then Lemma 4.1 states that there is a subgroup isomorphic to Z₈^*. But this is impossible, since four does not divide six. Thus, there is \r\n", "an element of order 3, say a. Then H = {e, a, a²} is a subgroup with index 2, and so by \r\n", "Proposition 3.5, H is normal. If b is any element not in H, then the two cosets of H are \r\n", "

{{e, a, a²}, {b, a·b, a²·b}}.

\r\n", "Thus, the group can be expressed by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^3, e)\r\n", "G = [e, a, b, a^2, a*b, a^2*b]; G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "However, this is not enough to define the whole group, as we can see in the black holes in the multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "How many ways can we complete this table? Because the quotient group is isomorphic to Z₂, b² must be in H. \r\n", "Yet if is a or a², then we find b has order 6, which we have already considered. So we may suppose \r\n", "b² = e. If we add this definition, we get
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b^2, e)\r\n", "G = [e, a, b, a^2, a*b, a^2*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that we had to re-establish the elements in G, since adding a new rule redefines the variables a and b. \r\n", "Although we have more information in the table, there are still black squares.

\r\n", "\r\n", "The rest of the multiplication table of G can be determined by finding b·a. Again, because of the quotient group, \r\n", "b·a is not in H. Obviously b·a is not b, since b cannot appear twice in the same row. \r\n", "If b·a = a·b, then b·a will have order 6, which we have covered. So the only possibility \r\n", "left is b·a = a²·b. If we add this final definition, we get the following multiplication table:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b*a, a^2*b)\r\n", "G = [e, a, b, a^2, a*b, a^2*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This multiplication table satisfies the Latin square property, and since it was defined in Sage, it will follow the associative law. Which group is this? \r\n", "We already know of a non-cyclic group of order 6, namely S₃, so this must be it. Thus, the two possible groups of order 6 are Z₆\r\n", "and S₃.

\r\n", "\r\n", "n = 7: Since 7 is prime, the only group is Z₇.

\r\n", "\r\n", "n = 8: Every element must be of order 1, 2, 4, or 8. If there is an element of order 8, the group is cyclic, so the group would be isomorphic to \r\n", "Z₈. Suppose instead that all non-identity elements are of order 2. By Lemma 4.1, there is a subgroup H isomorphic \r\n", "to Z₈^*. But the index of H would be two, so H is a normal subgroup. Thus, if c is any element not \r\n", "in H, then the cosets of G can be expressed as \r\n", "

{{e, a, b, a·b}, \r\n", "{c, a·c, b·c, a·b·c}}.

\r\n", "Since c, a·c, and b·c all are of order 2, we have\r\n", "

c·a = a·a·c·a·c·c = \r\n", "a·(a·c)²·c = a·c
\r\n", "c·b = b·b·c·b·c·c = \r\n", "b·(b·c)²·c = b·c

\r\n", "Using Sage, we see the only possible group would be
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\", \"c\")\r\n", "Define(a^2, e)\r\n", "Define(b^2, e)\r\n", "Define(c^2, e)\r\n", "Define(b*a, a*b)\r\n", "Define(c*a, a*c)\r\n", "Define(c*b, b*c)\r\n", "G = ListGroup()\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can easily check that the Latin square property holds, and since Sage was able to construct this, it is associative. Thus, this is a group, and clearly every \r\n", "non-identity element has order 2. But what group is this? Consider the group Z₂₄^*:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = ZStar(24)\r\n", "MultTable(M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This also is a group of order 8 with all non-identity elements of order 2. So from the above argument, this must be isomorphic to our group G. In fact, if we \r\n", "look closely, we will see that the color patterns match!
\r\n", "\r\n", "
\r\n", "If we have a group of order 8, and there is no element of order 8, but not all non-identity elements are of order 2, then there must be an element of order 4, \r\n", "call this a. Then\r\n", "

H = {e, a, a², a³}

\r\n", "is a subgroup of G, and since the index of H is two, Proposition 3.5 tells us that H is normal. Let b be an element not in \r\n", "H. Then the cosets of H are \r\n", "

H = {{e, a, a², a³}, \r\n", "{b, a·b, a²·b, a³·b}}.

\r\n", "The multiplication table for so looks like the following:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note from the Latin square property that b² must be in H. \r\n", "If b² = a or b² = a³, then b would \r\n", "have order 8, which would indicate a cyclic group. So we can assume that b² = e or b² = a².\r\n", "Note also from the Latin square property that b·a cannot be in H, and cannot be b. Thus, b·a is either \r\n", "a·b, a²·b, or a³·b.\r\n", "Hence, we have six possible cases. We will let Sage do the dirty work in verifying which are groups.

\r\n", "\r\n", "Case 1) If b² = e and b·a = a·b, we have
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a*b)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage verified that this is a commutative group. Compare this to the group Z₁₅^*:
\r\n", "

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = ZStar(15)\r\n", "MultTable(M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "These two tables have quite a few properties in common, but currently the color patterns are not matching. Let us see if we can find an isomorphism between the two groups.\r\n", "

\r\n", "Since a is of order 4, we must find an element of order 4 in Z₁₅^*, say 2. Suppose ƒ(a) = 2. Then \r\n", "ƒ(a²) = 4, ƒ(a³) = 8, and ƒ(e) = 1. Since b is of order 2, it must \r\n", "map to a remaining element of order 2, say ƒ(b) = 14. Then ƒ(a·b) = 2·14 = 13,\r\n", "ƒ(a²·b) = 4·14 = 11, and finally ƒ(a³·b) = 8·14 = 7.\r\n", "Let us test this isomorphism by rearranging the elements of G.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([e, a, a^2, a^3*b, a^3, a^2*b, a*b, b])\r\n", "MultTable(M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Now the color patterns are now the same, showing that G ≈ Z₁₅^*.

\r\n", "\r\n", "Case 2) Next we consider b² = e, b·a = a²·b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^2*b)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What happened? This table obviously does not satisfy the Latin square property, and in fact there seems to be only 2 elements in this group. If we ask Sage \r\n", "to list the group,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see only 2 elements. Apparently, the rules b² = e and b·a = a²·b imply \r\n", "that a = e. So we do not get a group of order 8.

\r\n", "\r\n", "Case 3) Let us try b² = e, b·a = a³·b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^3*b)\r\n", "G = ListGroup(); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is the first non-commutative group of order 8 that we have seen. This group appears when we consider the symmetries of a square, as in Problem 1 of §1.1. \r\n", "The element a corresponds to rotating the square 90° clockwise, while the element b corresponds to flipping the square over. For this reason, \r\n", "we call this group the dihedral group of order 4, or D₄.

\r\n", " \r\n", "Case 4) Let us consider b² = a², and b·a = a·b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, a^2)\r\n", "Define(b*a, a*b)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is a commutative group, but is it a different group then Z₁₅^*, which we have seen before? We can use the same logic used in \r\n", "case 1 to find an isomorphism.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = ZStar(15)\r\n", "MultTable(M)\r\n", "MultTable([e, a, a^2, b, a^3, a^3*b, a^2*b, a*b])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "With the colors arranged this way, we see that in fact we found the same group twice.

\r\n", " \r\n", "Case 5) Next, we will try b² = a², and b·a = a²·b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, a^2)\r\n", "Define(b*a, a^2*b)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage shows that this is not a group! Thus, there is one last combination to try:

\r\n", "\r\n", "Case 6) b² = a², and b·a = a³·b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^4, e)\r\n", "Define(b^2, a^2)\r\n", "Define(b*a, a^3*b)\r\n", "G = [e, a, a^2, a^3, b, a*b, a^2*b, a^3*b]\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage verifies that this is a non-commutative group. But is it isomorphic to the group D₄ found in case 3? \r\n", "Note that in this group, the identity e appears along the diagonal only twice, so a² is the only element of order 2. In the table for \r\n", "D₄, the identity appeared 6 times along the diagonal, so there were 5 elements of order 2. Thus, this is a new group.
\r\n", "
\r\n", " \r\n", "This non-commutative group is called the quaternion group, Q. Although we used a and b as the generators, the group is typically \r\n", "described by the elements {1, i, j, k, -1, -i, -j, -k}.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = InitQuaternions(); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The number 1 is used for the identity, and the following gives a multiplication table for Q:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice the strange resemblance between this groups multiplication, and the cross product of two unit vectors in three dimensions.

\r\n", " \r\n", "All groups of order 8 have now been considered. We found five possible groups: Z₈, Z₂₄^*, \r\n", "Z₁₅^*, D₄, and Q.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Using Sage, find all groups of order 9, and display the multiplication tables. (Hint: By Corollary 3.1, the order of an element must be 1, 3, or 9. Thus, if \r\n", "the group is non-cyclic, all elements besides the identity have order 3.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "As one can imagine, the analysis becomes even more complicated as we consider larger n. Here is a table of the number of non-isomorphic groups of \r\n", "order n, when n is not prime:

\r\n", "\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

\r\n", " Groups of order n\r\n", "
n	groups	n	groups	n	groups
4	2	39	2	72	50
6	2	40	14	74	2
8	5	42	6	75	3
9	2	44	4	76	4
10	2	45	2	77	1
12	5	46	2	78	6
14	2	48	52	80	52
15	1	49	2	81	15
16	14	50	5	82	2
18	5	51	1	84	15
20	5	52	5	85	1
21	2	54	15	86	2
22	2	55	2	87	1
24	15	56	13	88	12
25	2	57	2	90	10
26	2	58	2	91	1
27	5	60	13	92	4
28	4	62	2	93	2
30	4	63	4	94	2
32	51	64	267	95	1
33	1	65	1	96	230
34	2	66	4	98	5
35	1	68	5	99	2
36	14	69	1	100	16
38	2	70	4	102	4

\r\n", "\r\n", "\r\n", "

Homomorphisms

\r\n", "\r\n", "
\r\n", "In the last section we considered the possibility of functions which were defined on elements of a group, rather than on a set of numbers. With such functions, we could \r\n", "show that two groups were essentially the same. That is, when ƒ(x) is a one-to-one and onto function from G to M, and if\r\n", "

ƒ(x·y) = ƒ(x)·ƒ(y)

\r\n", "for all x and y in G, then the two groups G and M were essentially the same, or isomorphic.

\r\n", "\r\n", "In this section we want to consider functions between two groups that are not necessarily one-to-one or onto. However, we still want to have the property that \r\n", "

ƒ(x·y) = ƒ(x)·ƒ(y)

\r\n", "for all x and y in G. Such functions are fundamental to the theory of groups, so we will give such functions a name.

\r\n", "\r\n", "DEFINITION 4.2
\r\n", "Let G and M be two groups. A function \r\n", "

ƒ: G → M

\r\n", "mapping elements of G to elements of M is called a homomorphism if it satisfies\r\n", "

ƒ(x·y) = ƒ(x)·ƒ(y) \r\n", "for all x, y ∈ G.

\r\n", "\r\n", "
\r\n", "The group G is called the domain of the homomorphism, and the group M is called the target of the homomorphism. \r\n", "Note that a homomorphism need not be either one-to-one or onto.

\r\n", " \r\n", "Of course, all isomorphisms are also homomorphisms. But we can have many other homomorphisms, as the following examples show.

\r\n", " \r\n", "EXAMPLE:
\r\n", "Let G be any group, and let M be a group with identity e. If we let\r\n", "

ƒ(x) = e for all x ∈ G,

\r\n", "then ƒ will obviously be a homomorphism, since \r\n", "

ƒ(x·y) = e = e·e = ƒ(x)·ƒ(y).

\r\n", "This is called the trivial homomorphism.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Let ℝ^* = ℝ − {0} be the group of nonzero real numbers, and let ƒ(x) = x². This forms a \r\n", "homomorphism\r\n", "

ƒ: ℝ^* → ℝ^*,

\r\n", "so this gives an example of a homomorphism which maps a group onto itself. Note that this homomorphism is neither one-to-one nor onto since \r\n", "ƒ(−2) = ƒ(2) = 4, yet there is no real number such that ƒ(x) = −1.

\r\n", "\r\n", "EXAMPLE:
\r\n", "We can generalize the previous example as follows: Let G be any commutative group, and let n be any integer. We can define \r\n", "ƒ(x) = xⁿ. Then ƒ(x) is a homomorphism from G to itself, since\r\n", "

ƒ(x·y) = (x·y)ⁿ = \r\n", "xⁿ·yⁿ = ƒ(x)·ƒ(y).

\r\n", "We can prove a few properties that must be true of all homomorphisms.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 4.3
\r\n", "Let ƒ: G → M be a homomorphism. Let e denote the identity of G. Then ƒ(e) is the \r\n", "identity element of M.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 4.4
\r\n", "If ƒ: G → M is a homomorphism, then ƒ(a^-1) = [ƒ(a)]^-1.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find a homomorphism from Z₁₅^* to Z₄ such that f(2) = f(7) = 1.

\r\n", "\r\n", "We know from Proposition 4.3 that the identity must map to the identity, so f(1) = 0. Also, f(4) = f(2)² = 1² = 2. \r\n", "(Recall the operation \r\n", "of Z₄ is addition mod 4.) Likewise, f(8) = f(2)³ = 3, f(13) = f(7)³ = 3, \r\n", "f(14) = f(7)·f(2) = 2, \r\n", "and f(11) = f(13)·f(2) = 0.

\r\n", "\r\n", "Let us now look at how to define homomorphisms using Sage. To begin we need to define two groups simultaneously. This can be done in Sage by using \r\n", "different sets of letters for the generators.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Let us create a homomorphism from the octahedral group to the quaternion group.

\r\n", "\r\n", "We first load the octahedral group with the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\");\r\n", "AddGroupVar(\"a\",\"b\",\"c\");\r\n", "Define(a^2, e);\r\n", "Define(b^3, e);\r\n", "Define(c^4, e);\r\n", "Define(b*a, a*b^2);\r\n", "Define(c*a, a*b*c);\r\n", "Define(c*b, a*c^2);\r\n", "Oct = ListGroup(); Oct" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next let us define the quaternion group Q which we discovered in the last section. We will use a shortcut to define this group in terms of i, \r\n", "j, and k.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = InitQuaternions(); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We now have both groups defined simultaneously, one group using the generators a, b, and c, and the other using i and j and \r\n", "k. Note that expressions such as
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "c*i" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "produce an error message, since we cannot multiply elements from two different groups.

\r\n", "\r\n", "We now wish to define a homomorphism from Q to Oct. We need only define the homomorphism on the generators of Q, since \r\n", "Sage would then be able to use the properties of the homomorphism to determine where the other elements map to. Suppose we have the homomorphism given by \r\n", "the following mapping:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
1 → e,
i → c²,
−1 → e,
−i → c²,
j → a·b²·c,
k → a·b²·c³,
−j → a·b²·c,
−k → a·b²·c³.
\r\n", "
\r\n", "We have only to define F[i] and F[j] to define the homomorphism.
\r\n", "\r\n", "
\r\n", "The Sage command for setting up a homomorphism named F is:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(Q, Oct)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that both the domain and the target groups are included in the definition. \r\n", "Next, we define the homomorphism on a set of elemtents that generate the domain group. In this case, Q is generarated by the elements i and j, so\r\n", "we define these using the following format.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, i, c^2)\r\n", "HomoDef(F, j, a*b^2*c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The final step is to verify that this can be completed to form a homomorphism. The command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "will define the function F for the whole group Q. (Had the mapping failed to be a homomorphism, Sage would have \r\n", "returned "Homomorphism failed".)\r\n", "\r\n", "We can see where an element of Q is mapped to by treating F as a function.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F(i^3*j)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "gives a·b²·c³ as expected.

\r\n", " \r\n", "To have Sage draw a picture of this homomorphism, we can execute the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that only four of the elements of the octahedronal group are displayed: those four elements relevant to the homomorphism.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "See if you can define a homomorphism G from the octahedronal group Oct to Q, for which\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
G(a) = −1,
G(b) = 1,
G(c) = −1.
\r\n", "
\r\n", "Use Sage to enter in this mapping, and verify that this produces a homomorphism. Then use the GraphHomo command to see a picture of this homomorphism.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "It is even possible to define a homomorphism using a quotient group for either the domain or the target group. \r\n", "For example, suppose we define K to be the normal subgroup {1, -1} of Q:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = [1, -1]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The quotient group Q/K is given by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = RtCoset(Q,K); M" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us define the following homomorphism from Q/K to Oct in Sage.\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
{−1, 1} → e,
{−i, i} → c²,
{−j, j} → a·b²·c,
{−k, k} → a·b²·c³.
\r\n", "
\r\n", "The quotient group is non-cyclic, so we need two elements to describe the homomorphism. We will use the second and the third.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Homomorph(M, Oct)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(H, [-i, i], c^2)\r\n", "HomoDef(H, [-j, j], a*b^2*c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that we had to express the elements of the quotient group exactly as they appear in M. Thus, we could not use [i, -i], since this is not the \r\n", "order shown in M.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(H)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(H)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:

\r\n", "How is the homomorphism H related to the homomorphism F?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can not only apply a homomorphism ƒ to an element in a group, but also to a set of elements. We do this by applying the homomorphism to each \r\n", "element in the set and consider the set of all possible results. For example, consider the set of real numbers S = \r\n", "{−2, −1, 1, 2, 3, 4}. \r\n", "Let ƒ(x) be the homomorphism in example 2 above, ƒ(x) = x². Then\r\n", "

ƒ(S) = {1,4,9,16}.

\r\n", "The set ƒ(S) is smaller than the set S, since the homomorphism mapped two elements to both 1 and 4.
\r\n", "\r\n", "
\r\n", "To apply the homomorphism to a set of elements in Sage, we can use the Image command using a list for the second argument.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F, [i, k, -i, -k])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What happens if we take a homomorphism of a subgroup?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F, [1, i, -1, -i])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This turns out to be a subgroup of Oct. It is not hard to prove that this will be the case in general.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 4.5
\r\n", "If ƒ: G → M is a homomorphism and H is a subgroup of G, then ƒ(H) is a subgroup of \r\n", "M.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "One obvious subgroup that we could choose would be the entire domain. For example, we could find F(Q) with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F, Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives a list all possible elements that are produced by the function F.

\r\n", "\r\n", "DEFINITION 4.3
\r\n", "If ƒ: G → M is a homomorphism, then the group ƒ(G) is called the range, or image of \r\n", "the homomorphism ƒ. We denote this set by \r\n", "

Im(ƒ).

\r\n", "Since the domain will be a group, by Proposition 4.5 the image will always be a subgroup of the target group.

\r\n", " \r\n", "We can also consider taking the inverse homomorphism ƒ⁻¹ of an element or a set of elements. Because homomorphisms are not always one-to-one, \r\n", "ƒ⁻¹(x) may not represent a single element. Thus, we will define ƒ⁻¹(x) to be the \r\n", "set of numbers such that ƒ(y) = x. Likewise, we define for a subset S,\r\n", "

ƒ⁻¹(S) = { y | ƒ(y) ∈ S}.

\r\n", "We can take the inverse homomorphism in Sage with the command HomoInv(ƒ, x) where x is the element or set to take the inverse function. Thus,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, c^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "finds F⁻¹(c²). We can find the inverse of a set as well.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F,[a, b, a*b^2*c])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that the definition is valid even if not all of the elements in the set are in the image of ƒ.

\r\n", "There is one inverse image that is very important:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\r\n", "DEFINITION 4.4
\r\n", "If ƒ is a homomorphism from G to M and e is the identity element of M, then we define the \r\n", "kernel of ƒ to be the set \r\n", "

Ker(ƒ) = ƒ⁻¹(e).

\r\n", "Although this definition seems like corny terminology, it in fact is very descriptive term, for the kernel of the homomorphism in essence defines the entire function. \r\n", "The Sage command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "can be used to find the kernel of a homomorphism directly.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Find the image and the kernel of the homomorphisms G and H which were previously defined. \r\n", "Recall that the domain of G is Oct, while the domain of H is M. \r\n", "What do you observe about the kernel of these homomorphisms?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us observe one important property of the kernel.\r\n", " \r\n", "

\r\n", "\r\n", "PROPOSITION 4.6
\r\n", "\r\n", "If ƒ is a homomorphism from G to M, then the kernel of ƒ is a normal subgroup of the domain G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "EXPERIMENT:

\r\n", " \r\n", "Find the inverse image of F for different elements of the octahedral group. For example, one inverse image is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, c^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is there a pattern in the inverse images?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\r\n", "\r\n", "PROPOSITION 4.7
\r\n", "Let ƒ be a homomorphism from the group G to the group M. Suppose that y is in the image of ƒ, and that \r\n", "ƒ(x) = y. Then\r\n", "

ƒ⁻¹(y) = x·Ker(ƒ).

\r\n", "\r\n", "Click here for the proof.\r\n", "

\r\n", "\r\n", "We now have a quick way to determine if a homomorphism is an isomorphism.\r\n", "

\r\n", "\r\n", "COROLLARY 4.1
\r\n", "Let ƒ: G → M be a homomorphism. Then ƒ is an injection (one-to-one) if, and only if, the kernel of ƒ is \r\n", "the identity element of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We now can begin to see the importance of the kernel of the homomorphism. If the homomorphism is an isomorphism then the kernel is just the identity. \r\n", "The larger the kernel of the homomorphism, the further it is from being an isomorphism. For example, the homomorphism H is in fact an \r\n", "isomorphism, since
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(H)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "yields just the identity element. (Note the double curly braces. The kernel is a single element, which is the identity coset of M.) On the other hand, the \r\n", "kernel of the homomorphism G done in the experiment is large, so this is not an isomorphism.

\r\n", "\r\n", "We noticed that whenever we have a homomorphism ƒ: G → M, if we take the image of a subgroup of G, we get a subgroup \r\n", "of M. What if we take the inverse image of a subgroup of M? Will we get a subgroup of G? The next corollary says that we do, and in some \r\n", "cases we can even know more.\r\n", "\r\n", "

\r\n", "\r\n", "COROLLARY 4.2
\r\n", "Let ƒ: G → M be a homomorphism. Let H be a subgroup of M. Then ƒ⁻¹(H) is a \r\n", "subgroup of G. Furthermore, if H is a normal subgroup of M, then ƒ⁻¹(H) is a normal \r\n", "subgroup of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "

The Three Isomorphism Theorems

\r\n", "\r\n", "
\r\n", "In the last section we saw that whenever y is in the image of ƒ, ƒ⁻¹(y) is a coset of the kernel. \r\n", "This indicates that there is a mapping from Im(ƒ) to the quotient group G/Ker(ƒ). A natural question to ask is whether this \r\n", "mapping is again a homomorphism. The next proof shows that this mapping is, in fact, an isomorphism.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 4.1: The First Isomorphism Theorem
\r\n", "Let ƒ: G → M be a homomorphism with Ker(ƒ) = K, and Im(ƒ) = I. \r\n", "Then there is a natural isomorphism \r\n", "

ϕ: I → G/K

\r\n", "which is onto. Thus, I ≈ G/K.
\r\n", "
\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This theorem says that whenever we have a homomorphism ƒ from G to M with an image I, then we get a natural isomorphism \r\n", "ϕ from I to G/Ker(ƒ). We can picture this situation by drawing a partial diagram:
\r\n", "\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

G ƒ
―――――► I
↙ ϕ
G/Ker(ƒ)
\r\n", "\r\n", "\r\n", "
\r\n", "This diagram shows that we can apply the homomorphism ƒ and then the isomorphism ϕ to get a homomorphism from G to \r\n", "G/Ker(ƒ). This mapping would be \r\n", "

ϕ(ƒ(x)): G → G/Ker(ƒ).

\r\n", "What does this homomorphism do? Since ϕ(ƒ(x)) = ƒ⁻¹(ƒ(x)),\r\n", "we have that x ∈ ϕ(ƒ(x)).\r\n", "Thus, this homomorphism sends every element of G to the coset in G/Ker(ƒ) which contains that element.

\r\n", " \r\n", "It seems that we should be able to go directly from the group G to the group G/Ker(ƒ) without involving the homomorphism ƒ. \r\n", "The next proposition shows how this can be done.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 4.8
\r\n", "Let G be a group, and N be a normal subgroup of G. Then there is a natural isomorphism \r\n", "

i_N : N → G/N

\r\n", "given by i_N(a) = a·N. This homomorphism is surjective, and Ker(i_N) = N.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We call the homomorphism i_N the canonical homomorphism associated with N.

\r\n", " \r\n", "From Proposition 4.8, every normal subgroup of G appears as a kernel of a homomorphism, namely the canonical homomorphism.

\r\n", "\r\n", "We can now finish the diagram that we drew after the first isomorphism theorem. We now can go directly from the group G to the quotient group \r\n", "G/Ker(ƒ) using a canonical homomorphism:\r\n", "\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

G ƒ
―――――► I
i_N ↘ ⤢ ϕ
G/Ker(ƒ)
\r\n", "
\r\n", "Notice that we now have two ways of getting from G to G/Ker(ƒ), one route though the canonical homomorphism, and the other route \r\n", "through ƒ and ϕ. Yet we have drawn this diagram to indicate that ϕ(ƒ(x)) = i_N(x) for \r\n", "all elements in G. Thus, the two routes from G to G/Ker(ƒ) produce the same function. We express this fact by saying that \r\n", "the diagram is commutative. In other words, for a commuting diagram, the functions defined by two paths with the same beginning and ending points produce the \r\n", "same composition function. In this diagram there are arrows going in both directions for the function ϕ to indicate that this is a isomorphism. \r\n", "We will later be able to visualize many theorems about homomorphisms by means of commuting diagrams.

\r\n", " \r\n", " \r\n", "We observed in §3.3 that the product of two subgroups H and K was not necessarily a subgroup. However, it is possible that if one of the groups is normal, \r\n", "then indeed the product H·K would be a subgroup. (In fact, this was proven in Problem 15 of §3.3.) Let us try it\r\n", "on the octahedral group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\");\r\n", "AddGroupVar(\"a\",\"b\",\"c\");\r\n", "Define(a^2, e);\r\n", "Define(b^3, e);\r\n", "Define(c^4, e);\r\n", "Define(b*a, a*b^2);\r\n", "Define(c*a, a*b*c);\r\n", "Define(c*b, a*c^2);\r\n", "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXAMPLE:
\r\n", "Explore the product of two subgroups of order 4, one of which is normal, of the octahedral group.

\r\n", "\r\n", "The only normal subgroup of order 4 which we have found so far is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = Group(a*b^2*c, c^2); M" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here are some other subgroups of order 4:" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Group(c); H" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Group(b*c); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Unfortunately, this does not express all of the elements in the ListGroup format that appears in G. One way to fix this is to turn on \r\n", "SetReducedMult. But there is another command that allows us to express the elements\r\n", "of K in the format given in the group G.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Conform(K, G); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that if we multiplied H·K, we do not get a subgroup, for there would be 16 elements, and 16 is not a divisor of 24.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Conform(H * K, G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let's instead try to multiply H·M.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "L = Conform(H * M, G); L" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives a set of order 8, which is a divisor of 24. So it is possible that this set is a subgroup. How can we check? We can form the multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(L)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is closed under multiplication and inverses, so it is a subgroup of G.

\r\n", "\r\n", "This encourages us to try multiplying the groups in the other order. Let us see if M·H forms a subgroup:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Conform(M * H, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is this a subgroup of G? Yes, in fact it is the same subgroup as H·M. In this case, it apparently didn't matter which order we \r\n", "multiplied.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Is the product K·M a subgroup of G? What about the product M·K? Is K·M and \r\n", "M·K the same, as in the case for H?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "From this experiment, there seems to be a connection between whether H·N is a subgroup, and whether H·N = \r\n", "N·H. It is not hard to prove this connection.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 4.2
\r\n", "Suppose H and K are two subgroups of G. Then H·K is a group if, and only if,\r\n", "

H·K = K·H.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We are now in a position to show that H·K is a subgroup if one of the subgroups H or K is normal.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 4.3
\r\n", "If H is a subgroup of G, and N is a normal subgroup of G, then H·N is a subgroup of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "Since we have found a new subgroup of G which contains the normal subgroup M, the natural question is whether it is a normal subgroup. We can try to find the left and right \r\n", "cosets of H·M from the example.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "LftCoset(G, H * M)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RtCoset(G, H * M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that these are not the same, so in general, H·N is not a normal subgroup if only N is normal. (Note that if both H and N were normal, then Problem 17 of §3.3 shows that H·N is normal.

\r\n", "\r\n", "But would M be a normal subgroup of H·M?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "LftCoset(L, M)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RtCoset(L, M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can quickly see in this case it is normal, since M contains half of the elements of H·M. But we can prove that this will happen in general, \r\n", "using the fact that H·M is a subgroup of G.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 4.4
\r\n", "Let N be a normal subgroup of G, and suppose that H is a subgroup of G which contains N. \r\n", "Then N is a normal subgroup of H.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "Given two subgroups of a group G, there is another way of forming a new subgroup. Proposition 2.3 tells us that the intersection of \r\n", "two subgroups will again be a subgroup. Recall that the intersection ofthe groups H and M is given in Sage by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Intersection(H, M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "which is a group of order 2.

\r\n", "\r\n", "In this case since H is abelian, the intersection of H and M is a normal subgroup of H. However, whenever M is normal, \r\n", "the intersection will always be a normal subgroup.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 4.5
\r\n", "If N is a normal subgroup of G, and H is a subgroup of G, then H ∩ N is a normal subgroup of H.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Because we have a normal subgroup, we can consider the quotient group generated by this group. We can let
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R = Intersection(H, M); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "be the intersection. Then the quotient group is given by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "LftCoset(H, R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Compare this to the quotient group of (H·M)/M we found earlier.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = LftCoset(L, M); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What do we observe about these two quotient groups? They both have two elements, so they are obviously isomorphic. But there is another connection which helps to \r\n", "explain why they would be isomorphic. Notice that each coset in (H·M)/M contains one of the cosets from H/R. \r\n", "In fact, if we threw out all elements in a coset of (H·M)/M that were not an element of H, we would get a coset of \r\n", "H/R. Thus, if we could come up with a mapping which "filters out" the elements which are not in H, we would have a possible \r\n", "homomorphism between (H·M)/M and H/R. Let's see if we can construct such a mapping.

\r\n", "\r\n", "We will begin by defining a homomorphism from H into G. It will be defined simply by\r\n", "

i: H → G, i(h) = h.

\r\n", "This is called the identity homomorphism on H for the obvious reason. How will this help us create a filter? Let us define the homomorphism \r\n", "in Sage to find out.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "I = Homomorph(H, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Because H uses c as the generator we only have to define i[c]:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(I, c, c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage can quickly complete the homomorphism:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(I)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(I)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that i[h] will not be defined on the elements of G which are not in H. However, i^-1(S) will be \r\n", "defined on all subsets of G. For example, if we consider the subset
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S = [a, a*b, c, a*c, a*b*c^2, c^3, e]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Then i^-1(S) is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(I, S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The inverse apparently filters out the elements of S which are not in H. This is almost what we want, but we want a filter for a single coset, \r\n", "so the trick is to first take the inverse of the canonical isomorphism ƒ from H·M to (H·M)/M. Let \r\n", "us quickly define this, using F for the homomorphism name.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(L, Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The set H·M is generated by the elements a·b·b and c. In this case we only need 2 definitions \r\n", "to define the entire homomorphism.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, c, c * M)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, a*b^2 , a*b^2 * M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Does this define the homomorphism? We will let Sage verify that this does:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can now try out our filter to see if it works. We pick an element in (H·M)/M:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Conform(c * M, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next, we find i^-1(F⁻¹(x)) for this element.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, [_])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(I, _)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "A bit of explanation is needed here. The second argument for the HomoInv command can either be a single element, or a list of elements. But when \r\n", "the element looks like a list, we have to enclose it is an extra set of brackets to make it a list of one element. That is why there are extra brackets as we \r\n", "take F^-1. However, the output of HomoInv is a list of elements, so we didn't need these brackets in computing I^-1.
\r\n", "\r\n", "
\r\n", "We see that this combination of inverse homomorphisms can be used for our filter. This gives us the guidelines for showing that, in general, \r\n", "H/(H∩N) ≈ (H·N)/N.\r\n", "\r\n", "

\r\n", "\r\n", "
THEOREM 4.2:The Second Isomorphism Theorem
\r\n", "Suppose that N is a normal subgroup of G, and that H is a subgroup of G. Then\r\n", "

H/(H∩N) ≈ (H·N)/N.

\r\n", "\r\n", "Click here for the proof.
\r\n", "\r\n", "

\r\n", "We can describe the second isomorphism theorem (4.2) pictorially with a commuting diagram. We can let ϕ denote the canonical homomorphism \r\n", "from H to the quotient group. Then the first isomorphism theorem (4.1) states that the following diagram commutes:\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
H i
―――► H·N
ϕ↓ ↓ƒ
H/(H∩N) ◄――► (H·N)/N
\r\n", "\r\n", "
\r\n", "With this diagram, it is easy to find the number of elements in the product of two finite groups H·N. Since \r\n", "

|H/(H∩N)| = |(H·N)/N|

\r\n", "we have|H|/|H∩N| = |H·N|/|N|. Thus,\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

\|H·N\| =	\| H \| \| N \|	.
\| H ∩ N \|

\r\n", "
\r\n", "In the example above H and M had 4 elements with 2 elements in common. Thus, the size of H·M was 4·4/2 = 8 elements. \r\n", "The only problem with this argument is that we had to assume that one of the two groups was a normal subgroup of a larger group. Let us show \r\n", "that the number of elements in H·K is given by the above formula even if we do not make that assumption.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 4.9
\r\n", "Let H and K be two subgroups of a finite group G. Then the number of elements in the product H·K is given by\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
|H·K| = | H | | K | .
| H ∩ K |
\r\n", "Click here for the proof.\r\n", "

\r\n", "\r\n", "If we consider a group with two subgroups, one of which is is subgroup of the other, we begin to see more patterns. Let us reload the octahedral group, and look at two normal subgroups.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\");\r\n", "AddGroupVar(\"a\",\"b\",\"c\");\r\n", "Define(a^2, e);\r\n", "Define(b^3, e);\r\n", "Define(c^4, e);\r\n", "Define(b*a, a*b^2);\r\n", "Define(c*a, a*b*c);\r\n", "Define(c*b, a*c^2);\r\n", "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXAMPLE:
\r\n", "The octahedral group has two non-trivial normal subgroups, one being the subgroup of the other. Explore the possible quotient groups.

\r\n", "\r\n", "In searching for properties of quotient groups, we found one normal subgroup of order 4:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = Group(a*b^2*c, c^2); M" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us see if we can find another normal subgroup of the octahedral group. Consider the subgroup
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Group(b, c^2); H" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Conform(H, G); H" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is a fairly large subgroup, but not the entire group. Let us find the order of this subgroup:" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Therefore this group is half the size of the original octahedral group. By Proposition 3.5, H must be a normal subgroup of G.

\r\n", "\r\n", "Since we have two normal subgroups, we have two quotient groups. Here is the quotient group G/H:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q1 = RtCoset(G, H); Q1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is the quotient group G/M:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q2 = RtCoset(G, M); Q2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "At this point there doesn't seem to be much connection between these. But notice that M is also a subgroup of H. By Lemma 4.4, M will be a \r\n", "normal subgroup of H. This gives us a third quotient group to consider:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q3 = RtCoset(H, M); Q3" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that every coset in Q3 is also a coset in Q2. In other words, the quotient group Q3 is a subgroup \r\n", "of Q2. Is this a normal subgroup? In the case we are looking at, Q2 is of order 6 and Q3 is of order 3, so \r\n", "Proposition 3.5 states that Q3 must be a normal subgroup of Q2. So this means that we can consider a fourth quotient \r\n", "group―a quotient group of the quotient group!
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q4 = LftCoset(Q2, Q3)\r\n", "Q4 = Conform(Q4, G); Q4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Before we try to interpret this mess, let us first see why H/N will be a normal subgroup of G/N in general.\r\n", "\r\n", "

\r\n", "\r\n", "
LEMMA 4.6
\r\n", "If H and N are normal subgroups of G, and if N is a subgroup of H, then H/N is a normal \r\n", "subgroup of G/N.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Let us compare the quotient group Q4 with our first group Q1.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We notice that both of these have two main elements, so both of these must be isomorphic to Z₂. But consider the first elements of these groups:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q1[0]" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q4[0]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that if we remove all of the interior curly braces from the element in Q4, we get the element from Q1 after rearranging the \r\n", "terms. The same thing is true with the other element of Q4. Thus we see that not only are Q4 and Q1 isomorphic, \r\n", "but there is a natural mapping from Q4 to Q1 which strips away the inside brackets.

\r\n", "\r\n", "This natural mapping seems to indicate that (G/N)/(H/N) is isomorphic to G/H. In order to prove this we merely \r\n", "have to describe this mapping in terms of the canonical homomorphisms. That is, we need a mapping that will essentially remove the innermost curly braces from an element \r\n", "in (G/N)/(H/N). We will use the canonical homomorphisms as building blocks.

\r\n", "\r\n", "The first canonical homomorphism we consider is from G to G/N. Let us use our example to illustrate, calling this \r\n", "homomorphism R.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R = Homomorph(G, Q2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This homomorphism will send each element of G to the coset containing that element. This can be done by sending x to x M. For \r\n", "example, a would be sent to
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a * M" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We now can tell Sage where the three generators a, b, and c will be sent.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(R, a, a * M )" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(R, b, b * M )" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(R, c, c * M )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "It's fairly obvious that this will be a homomorphism, but we could have Sage check it using the following command.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage can now evaluate this homomorphism on the elements of G.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R(a*b)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R(b*c^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can even graph this homomorphism.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that R(x) gives the coset of G/M which contains the element x.

\r\n", " \r\n", "Next we can consider a homomorphism from G/M to (G/M)/(H/M). Let us call this homomorphism F.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(Q2, Q4)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next we tell Sage what F does to the elements of G/M.\r\n", "The coset x M is mapped to (x M)·Q₃ = x·Q₃, since \r\n", "M ∈ Q₃.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, a * M, a * Q3 )" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, b * M, b * Q3 )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The quotient group has 6 elements, so it ought to be generated by two elements.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The graph shows that each coset y in G/K is mapped to the complex coset in (G/N)/(H/N) which contains the \r\n", "coset y. \r\n", "\r\n", " \r\n", "We can now experiment with combining these two homomorphisms:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F(R(c^2))" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F(R(a*c))" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F(R(b^2*c))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Apparently F(R(x)) gives the coset of (G/M)/(H/M) for which contains the \r\n", "element x within.

\r\n", " \r\n", "How can we use this to find a mapping which removes the inside brackets? We can consider the inverse of this combination, \r\n", "R^-1(F^-1(y)). This would give a list of all elements of G which are embedded in the \r\n", "coset y. Let us check this:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Conform(b^2*c * Q3, G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, [_])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(R, _)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us try again with a different element.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Conform(a*b*c * Q3, G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(F, [_])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(R, _)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Therefore, we have a mapping, namely R^-1(F^-1(y)) that removes the inside curly braces. Let us use this \r\n", "to show that Q4 and Q1 will always be isomorphic.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 4.3: The Third IsomorphismTheorem
\r\n", "Let H and N be normal subgroups of G, and let N be a subgroup of H. Then\r\n", "

(G/N)/(H/N) ≈ G/H.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We can describe the third isomorphism theorem visually with the following diagram.

\r\n", "\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
G ϕ
―――► G/N
i_H↓ ↓ƒ
G/H ◄――► (G/N)/(G/H)
\r\n", "\r\n", "
\r\n", "Since H is the kernel of the composition homomorphism \r\n", "

ƒ(ϕ): G → (G/N)/(H/N)

\r\n", "we have by the first isomorphism theorem that this diagram commutes.

\r\n", "\r\n", "The three isomorphism theorems work not only for groups, but many other objects as well, such as the rings we will study in Chapter 9. Because the same theorems apply to many different types of objects, an abstraction of these theorems can be made which would apply to any object for which there are natural mappings defined, called morphisms. This introduces a rich field called category theory. Although category theory is another level of abstraction beyond group theory, there are applications in physics and computer languages. \r\n", " \r\n", "

\r\n", "\r\n", "

Proofs:

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 4.1:

\r\n", "\r\n", "If two groups have the same multiplication table, they are isomorphic, so a group is completely determined by its multiplication table. Notice that each element \r\n", "of this table must be one of n elements, and there are n² entries in the table. So there are n^(n²) ways \r\n", "of creating such a table.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 4.2:

\r\n", "\r\n", "Let G be a group of order n, and let g be a generator of G. For clarity, we will let · denote the group operation of G, and ∗ denote the group operation of Z_n. Since gⁿ = e, we have\r\n", "

G = {e = g⁰, g¹, g², g³, …, \r\n", "gⁿ⁻¹}.

\r\n", "Define ƒ: Z_n → G by\r\n", "

ƒ(x) = g^x (0 ≤ x ≤ n − 1).

\r\n", "That is, ƒ will map the elements of Z_n to elements of G. Clearly ƒ is one-to-one and onto, and we would like to show that it is \r\n", "an isomorphism. Suppose x and y both satisfy 0 ≤ x, y ≤ n − 1.
\r\n", "
\r\n", "\r\n", "We let z = x ∗ y = (x + y) mod n. Then we can find an m such that\r\n", "x + y = m n + z. \r\n", "Now, ƒ(x ∗ y) = ƒ(z) = g^z by the definition of ƒ. Thus,\r\n", "

ƒ(x ∗ y) = g^z = g^{(x+y−m n)} = \r\n", "g^x·g^y·(gⁿ)^−m = g^x·g^y \r\n", "= ƒ(x)·ƒ(y).

\r\n", "Since ƒ is an isomorphism of Z_n onto G, we have Z_n ≈ G.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 4.1:

\r\n", "\r\n", "Since the order of G is greater than 2, there are two distinct elements a and b besides the identity element e. Since these will have order 2, we have a² = b² = e. Consider the product a·b. It can be neither a \r\n", "nor b since this would imply the other was the identity. On the other hand, a·b = e implies that\r\n", "

a = a·e = a·(b·b) = \r\n", "(a·b)·b = e·b = b.

\r\n", "So a·b is not the identity either. So there must be a fourth element in G, which we will call c, such that \r\n", "a·b = c. This element will also be of order 2, so we have c² = e.

\r\n", "\r\n", "Finally, note that\r\n", "

b·a = e·b·a·e = \r\n", "a·a·b·a·b·b = \r\n", "a·(a·b)²·b = \r\n", "a·c²·b = a·e·b = a·b = c.

\r\n", "With this result we can quickly find the remaining products involving a, b, and c.\r\n", "

c·a = b·a·a = b, c·b = \r\n", "a·b·b = a, a·c = a·a·b = b, \r\n", "b·c = b·b·a = a.

\r\n", "Hence, the set H = {e, a, b, c} is closed under multiplication, contains the identity, and also contains the inverses of \r\n", "every element in the set. Hence, H is a subgroup of G. The multiplication table for H\r\n", "

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

·	e	a	b	c
e	e	a	b	c
a	a	e	c	b
b	b	c	e	a
c	c	b	a	e

\r\n", "\r\n", "
\r\n", "shows that this is isomorphic to Z₈^* using the mapping\r\n", "

ƒ(e) = 1,
ƒ(a) = 3,
ƒ(b) = 5,
ƒ(c) = 7.

\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 4.3:

\r\n", "\r\n", "Since e·e = e in the group G, we have\r\n", "

ƒ(e) = ƒ(e·e) = \r\n", "ƒ(e)·ƒ(e).

\r\n", "Multiplying both sides by [ƒ(e)]^-1 gives us that ƒ(e) is the identity element of M.

\r\n", " \r\n", "Return to text\r\n", " \r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 4.4:

\r\n", " \r\n", "We merely need to show that ƒ(a)·ƒ(a^-1) is the identity element of M. If e represents \r\n", "the identity element of G, then\r\n", "

ƒ(a)·ƒ(a^-1) = ƒ(a·a^-1) = \r\n", "ƒ(e)

\r\n", "By Proposition 4.3 this is the identity element of M. So ƒ(a^-1) = [ƒ(a)]^-1.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 4.5:

\r\n", "\r\n", "We want to show that ƒ(H) is a subgroup using Proposition 2.2. If u and v are elements in \r\n", "ƒ(H), there must be elements x and y in H such that\r\n", "

ƒ(x) = u, and ƒ(y) = v.

\r\n", "Then x·y^-1 is in H, and so \r\n", "

ƒ(x·y^-1) = ƒ(x)·ƒ(y^-1) = \r\n", "ƒ(x)·[ƒ(y)]^-1 = u·v^-1

\r\n", "is in ƒ(H). So by Proposition 2.2, ƒ(H) is a subgroup of M.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 4.6:

\r\n", " \r\n", "First we need to show that the kernel of ƒ is a subgroup of G. If e is the identity element of M, and if a and \r\n", "b are two elements of Ker(ƒ), then\r\n", "

ƒ(a·b^-1) = ƒ(a)·ƒ(b)^-1 = \r\n", "e·e^-1 = e.

\r\n", "so a·b^-1 is also in the kernel of ƒ. Thus, by Proposition 2.2, Ker(ƒ) is a subgroup.

\r\n", "\r\n", "Now let us show that Ker(ƒ) is a normal subgroup of G. Let a be an element in Ker(ƒ), and g be any element \r\n", "in G. Then by Proposition 3.4, since\r\n", "

ƒ(g·a·g^-1) = \r\n", "ƒ(g)·ƒ(a)·ƒ(g^-1) = \r\n", "ƒ(g)·e·ƒ(g)^-1 = e,

\r\n", "g·a·g^-1 is in Ker(ƒ), and so Ker(ƒ) is a normal subgroup.

\r\n", " \r\n", "Return to text \r\n", " \r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 4.7:

\r\n", " \r\n", "First let us consider an element z ∈ x·Ker(ƒ). Then z = x·k for some element \r\n", "k in the kernel of ƒ. Therefore,\r\n", "

ƒ(z) = ƒ(x·k) = ƒ(x)·ƒ(k) \r\n", "= ƒ(x)·e = ƒ(x)

\r\n", "since k is in Ker(ƒ). Here, e is the identity element of M. But ƒ(x) = y, and so\r\n", "z ∈ ƒ⁻¹(y). Thus we have proved that \r\n", "

ƒ⁻¹(y) ⊆ x·Ker(ƒ).

\r\n", "
\r\n", "To prove the inclusion the other way, note that if z ∈ ƒ⁻¹(y), then ƒ(z) = y, and so we \r\n", "have\r\n", "

ƒ(x^-1·z) = ƒ(x)^-1·ƒ(z) = \r\n", "y^-1·y = e.

\r\n", "Thus, x^-1·z is in the kernel of ƒ, and since \r\n", "z = x·(x^-1·z) ∈ x·Ker(ƒ), we have\r\n", "

x·Ker(ƒ) ⊆ ƒ⁻¹(y).

\r\n", " \r\n", "Return to text \r\n", " \r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Corollary 4.1:

\r\n", " \r\n", "If ƒ is an injection, it is clear that the kernel would just be the identity element. Suppose that the kernel is just the identity. Then \r\n", "Proposition 4.7 states that if h is in the image of ƒ, then ƒ⁻¹(h) consists of exactly one element. \r\n", "Therefore, ƒ is one-to-one.
\r\n", "
\r\n", " \r\n", "Return to text \r\n", " \r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Corollary 4.2:

\r\n", " \r\n", "Let x and y be in ƒ⁻¹(H). Then since ƒ(x·y^-1) = \r\n", "ƒ(x)·ƒ(y)^-1, which is in H, we have that x·y^-1 is in \r\n", "ƒ⁻¹(H). Thus, by Proposition 2.2, ƒ⁻¹(H) is a subgroup of G.
\r\n", "
\r\n", "\r\n", "Now suppose that H is a normal subgroup of M. Then if y is in ƒ⁻¹(H), and g is in G, then \r\n", "ƒ(g·y·g^-1) = \r\n", "ƒ(g)·ƒ(y)·ƒ(g)^-1. Since ƒ(y) is in H, \r\n", "which is normal in M, we have that ƒ(g)·ƒ(y)·ƒ(g)^-1 is \r\n", "in H. Thus, g·y·g^-1 is in ƒ⁻¹(H), and so by Proposition 3.4, \r\n", "ƒ⁻¹(H) is normal in G.
\r\n", "
\r\n", " \r\n", "Return to text \r\n", " \r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Theorem 4.1:

\r\n", " \r\n", "Note that this theorem states more than just I ≈ G/K, but that there is a natural isomorphism between these two groups. \r\n", "This isomorphism is given by\r\n", "

ϕ(h) = ƒ⁻¹(h).

\r\n", "
Proposition 4.7 states that whenever h is in the image of ƒ, ƒ⁻¹(h) is a member of the quotient group \r\n", "G/Ker(ƒ). Thus, ϕ: I → G/K is properly defined.

\r\n", "\r\n", "Let us show that the mapping ϕ is one-to-one. Suppose ϕ(x) = ϕ(y) for two different elements of \r\n", "I. Then ƒ(ϕ(x)) = ƒ(ϕ(y)). But ƒ(ϕ(x)) =\r\n", "ƒ(ƒ⁻¹(x)) is the set containing just the element x, and also ƒ(ϕ(y)) is the \r\n", "set containing just the element y. Thus, x = y, and we have shown that ϕ is one-to-one.

\r\n", "\r\n", "Now let us show that ϕ is onto. If x K is an element of G/K, then ƒ(x) ∈ I. Thus,\r\n", "

x ∈ ƒ⁻¹(ƒ(x)) = ϕ(ƒ(x)) \r\n", "∈ G/K.

\r\n", "So we have that x is an element of both cosets x K and ϕ(ƒ(x)). Since two different cosets have no elements in \r\n", "common, we must have ϕ(ƒ(x)) = x K. We therefore have that any coset in G/K is mapped by ϕ \r\n", "from an element in I, so ϕ is onto.
\r\n", "
\r\n", "\r\n", "Finally, we want to show that ϕ is a homomorphism. That is, we wish to show that\r\n", "

ƒ⁻¹(v)·ƒ⁻¹(w) = \r\n", "ƒ⁻¹(v·w).

\r\n", "
Let x ∈ ƒ⁻¹(v) and y ∈ ƒ⁻¹(w). Then \r\n", "ƒ(x) = v and ƒ(y) = w, so we have\r\n", "

ƒ(x·y) = ƒ(x)·ƒ(y) = \r\n", "v·w.

\r\n", "Hence, x·y ∈ ƒ⁻¹(v·w). Since \r\n", "ƒ⁻¹(v)·ƒ⁻¹(w) and ƒ⁻¹(v·w) are two cosets in \r\n", "G/K, and both contain the element x·y, they must be the same coset. So we have that\r\n", "

ϕ(v)·ϕ(w) = ϕ(v·w).

\r\n", " \r\n", "Return to text \r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 4.8:

\r\n", " \r\n", "To show that i_N is a homomorphism, we note that if a and b are elements of G, then\r\n", "

i_N(a·b) = a·b·N = \r\n", "a·N·b·N = i_N(a)·i_N(b).

\r\n", "Also, i_N is clearly surjective. To find the kernel of i_N, we note that the identity element of G/N is\r\n", "e N = N, and so x is in the kernel if, and only if,\r\n", "

i_N(x) = N ⟺ x N = N ⟺ x ∈ N.

\r\n", "Therefore, the kernel of i_N is N.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 4.2:

\r\n", "\r\n", "First suppose that H·K is a subgroup. Let h ∈ H and k ∈ K.

\r\n", "We wish to show that the element h·k in H·K is also in K·H. Since H·K \r\n", "is a subgroup, (h·k)^-1 is in H·K. Thus, (h·k)^-1 = \r\n", "x·y for some x ∈ H and y ∈ K. But then, h·k = \r\n", "(x·y)^-1 = y^-1·x^-1, and y^-1·x^-1\r\n", "is in K·H. Thus,\r\n", "

H·K ⊆ K·H.

\r\n", "By a similar argument, the inverse of any element in K·H must be in H·K, and so \r\n", "K·H ⊆ H·K. Therefore, we have H·K = K·H.

\r\n", "\r\n", "Now, let us suppose that H·K = K·H. We want to show that H·K is a subgroup. Let\r\n", "

h₁, h₂ ∈ H, and k₁, k₂ ∈ K

\r\n", "so both h₁·k₁ and h₂·k₂ are elements of H·K. \r\n", "By Proposition 2.2, it is enough to show that \r\n", "h₁·k₁·(h₂·k₂)^-1 is in H·K. \r\n", "But (k₁·k₂^-1)·h₂^-1 is in \r\n", "K·H = H·K, and so there must be two elements\r\n", "

h₃ ∈ H, and k₃ ∈ K

\r\n", "such that (k₁·k₂^-1)·h₂^-1 = \r\n", "h₃·k₃. Then we have\r\n", "

h₁·k₁·(h₂·k₂)^-1 =\r\n", "h₁·(k₁·k₂^-1)·h₂^-1 =\r\n", "(h₁·h₃)·k₃

\r\n", "which is in H·K. Thus, H·K is a subgroup if, and only if, H·K = \r\n", "K·H.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 4.3:

\r\n", "\r\n", "If h ∈ H and n ∈ N, then h·n·h^-1 is in N, since N \r\n", "is normal. Then\r\n", "

h·n = (h·n·h^-1)·h

\r\n", "is in N·H. Thus, H·N ⊆ N·H.

\r\n", "\r\n", "By a similar argument N·H ⊆ H·N, so H·N = N·H.\r\n", "Therefore, H·N is a group by Lemma 4.2.
\r\n", "
\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 4.4:

\r\n", "\r\n", "Since N is a group, and is contained in H, N is a subgroup of H. For any x in H, we have that\r\n", "

x·N·x^-1 = N

\r\n", "since x is also in G. Therefore, by Proposition 3.4, N is a normal subgroup of H.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 4.5:

\r\n", "\r\n", "Given elements h ∈ H and x ∈ H ∩ N, we note that since x is in N which is a normal subgroup \r\n", "of G, h·x·h^-1 is in N. Also, x is in H, so \r\n", "h·x·h^-1 is in H. Thus, \r\n", "

h·x·h^-1 ∈ H ∩ N

\r\n", "and so by Proposition 3.4, the intersection is a normal subgroup of H.
\r\n", "
\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 4.2:
\r\n", "
\r\n", "\r\n", "By Lemma 4.3, H·N is a subgroup, and by Lemma 4.4, N is a normal subgroup of H·N. Also, by Lemma 4.5, \r\n", "H ∩ N is a normal subgroup of H, and so both of the quotient groups are defined.

\r\n", "\r\n", "We will use the two homomorphisms\r\n", "

i: H → H·N
\r\n", "ƒ: H·N → (H·N)/N

\r\n", "where i is the identity mapping i(h) = h, and ƒ is the canonical homomorphism.

\r\n", "\r\n", "We can now consider the combination of the two,\r\n", "

ƒ(i(x)): H → (H·N)/N.

\r\n", "Let us call the composition function ψ(h) = f(i(h)). We want to find the kernel of ψ, for then we \r\n", "can use the first isomorphism theorem (4.1). If we let e denote the identity element of \r\n", "(H·N)/N, then\r\n", "

h ∈ \r\n", "Ker(ψ) ⟺ ƒ(i(h)) = e ⟺ i(h) ∈ \r\n", "Ker(ƒ) = N ⟺ h ∈ N and h ∈ H ⟺ h ∈ \r\n", "H ∩ N.

\r\n", "So by the first isomorphism theorem (4.1), we have\r\n", "

(H·N)/N ≈ \r\n", "H/(H ∩ N).

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 4.9:

\r\n", "\r\n", "Even though H·K is not a group, it still makes sense to consider the set of left cosets (H·K)/K. \r\n", "A typical left coset belonging to (H·K)/K would be h·k·K, where h is an element \r\n", "of H, and k is an element of K. Note that since k·K = K, this simplifies to h·K.\r\n", "By Lemma 3.1, all cosets contain |K| elements, and by Lemma 3.2 two cosets would intersect if, \r\n", "and only if, they are equal. Thus the elements of H·K are distributed into non-overlapping cosets, each having |K| elements.\r\n", "Thus, the number of cosets in (H·K)/K is

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

\|(H·K)/K\| =	\| H·K \|	.
\| K \|

\r\n", "
\r\n", "Likewise, we have\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

\|H/(H∩K)\| =	\| H \|	.
\| H ∩ K \|

\r\n", "
\r\n", "Thus, if we can show that |H/(H∩K)| = |(H·K)/K|, we will have proven the proposition.

\r\n", "\r\n", "Let us define a mapping (not a homomorphism) that will relate the elements of these two sets. Let\r\n", "

ϕ : (H·K)/K → H/(H∩K)

\r\n", "be defined by \r\n", "

ϕ(h·K) = h·(H∩K).

\r\n", "To see that this is well defined, note that if h₁·K = h₂·K for two elements h₁ \r\n", "and h₂ in H, then h₂^-1·h₁·K = \r\n", "K, so h₂^-1·h₁ must be in K. But \r\n", "h₂^-1·h₁ is also in H, hence in the intersection. Thus,\r\n", "

h₂·(H∩K) = \r\n", "h₂·(h₂^-1·h₁)·(H∩K) = \r\n", "h₁·(H∩K).

\r\n", "So we see that if h₁·K = h₂·K, then ϕ(h₁·K) = \r\n", "ϕ(h₂·K), and the function ϕ is well defined.

\r\n", "\r\n", "On the other hand, if h₁·(H∩K) = h₂·(H∩K), then \r\n", "h₂^-1·h₁ would have to be in the intersection of H and K. So then, \r\n", "h₁·K = h₂·K. Hence the mapping is one-to-one. It is clear that the mapping is also \r\n", "surjective, so ϕ is a bijection, and the proposition is proved.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 4.6:

\r\n", "\r\n", "From Lemma 4.4, N is a normal subgroup of H. A typical element of G/N is g N, where g is an element of G.\r\n", "A typical element of H/N is h N, where h is an element of H. Thus, H/N is contained in \r\n", "G/N, and so H/N is a subgroup of G/N.

\r\n", "\r\n", "To show that H/N is in fact a normal subgroup of G/N, we will use Proposition 3.4. That is, we will see if\r\n", "

(g N)·(h N)·(g N)^-1

\r\n", "will always be in H/N. But this simplifies to (g·h·g^-1)·N, and \r\n", "g·h·g^-1 is in H since H is a normal subgroup of G. Therefore, \r\n", "(g·h·g^-1)·N is in H/N, and hence H/N is a normal subgroup \r\n", "of G/N.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 4.3:

\r\n", "\r\n", "We will use the example to guide us in finding a mapping from (G/N)/(H/N) to a set of elements in G. We have a canonical \r\n", "mapping from G to G/N, and another canonical mapping from G/N to (G/N)/(H/N). \r\n", "Let us call these mappings ϕ and ƒ, respectively.

\r\n", "\r\n", "For an element x in G, the composition homomorphism ƒ(ϕ(x)) gives the element of \r\n", "(G/N)/(H/N) which contains x somewhere inside of it. Let us call this composition homomorphism ψ. \r\n", "Since ƒ and ϕ are both surjective, \r\n", "the composition ψ(x) = ƒ(ϕ(x)) is surjective. Thus, the inverse of this homomorphism, \r\n", "ψ^-1(y), gives a list of elements of G that are somewhere inside of the element y. \r\n", "This inverse is the mapping that removes the interior brackets. We only need to check that this is in fact a coset of G/H. \r\n", "Let us determine the kernel of the composition homomorphism ψ(x).

\r\n", "\r\n", "Note that x if is in G, and e is the identity element of (G/N)/(H/N), then \r\n", "

x ∈ Ker(ψ) ⟺ ƒ(ϕ(x)) = e
\r\n", "⟺ ϕ(x) ∈ Ker(ƒ) = H/N
\r\n", "⟺ x ∈ ϕ^-1(H/N) = H.

\r\n", "Therefore, the kernel of the composition ψ is H, and so from the first isomorphism theorem (4.1), \r\n", "

(G/N)/(H/N) ≈ G/H.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "

Sage Interactive Problems

\r\n", "\r\n", "
\r\n", "§4.1 #18)
\r\n", "Prove that there are exactly two non-isomorphic groups of order 10. Find these two groups, and have Sage produce the multiplication tables.

\r\n", " \r\n", "(Hint: Follow the logic for n = 6.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "For Problems 19 through 21: Each of the following groups is of order 8. Which of the known five groups \r\n", "

( Z₈, Z₂₄^*, Z₁₅^*, D₄, or \r\n", "Q )

\r\n", "is each of these isomorphic to? First have Sage display a table of the new group, and then rearrange the elements of one of the five known groups so that the \r\n", "color pattens in the two tables are identical.

\r\n", "\r\n", "§4.1 #19) Z₁₆^*
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.1 #20) Z₂₀^*
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.1 #21) Z₃₀^*
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.2 #19)
\r\n", "Define Terry's group in Sage with
the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry = InitTerry()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and then define the group S₃.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(b*a, a*b^2)\r\n", "S3 = ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now define an isomorphism F from S₃ to Terry's group. Use Sage's FinishHomo command to verify that \r\n", "your function is a homomorphism. Finally, find the kernal of F to prove that F is an isomorphism.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.2 #20)
\r\n", "Use Sage to find all of the homomorphisms from S₃ to itself. Label these homomorphisms F1, \r\n", "F2, F3, etc. How many of these are isomorphisms? The following loads the group S₃ into\r\n", "Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(b*a, a*b^2)\r\n", "S3 = ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.3 #19)
\r\n", "Use Sage to find a non-trivial homomorphism from the octahedral group to Q.

\r\n", "(Hint: According to the first isomorphism theorem, what could the image be?)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§4.3 #20)
\r\n", "Use Sage to find a non-trivial homomorphism from the octahedral group onto S₃.

\r\n", "(Hint: Use the first isomorphism theorem to determine what the kernel must be.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\r\n", "\r\n", "\r\n", "\r\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath (stable)", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 0 }

n	groups	n	groups	n	groups
4	2	39	2	72	50
6	2	40	14	74	2
8	5	42	6	75	3
9	2	44	4	76	4
10	2	45	2	77	1
12	5	46	2	78	6
14	2	48	52	80	52
15	1	49	2	81	15
16	14	50	5	82	2
18	5	51	1	84	15
20	5	52	5	85	1
21	2	54	15	86	2
22	2	55	2	87	1
24	15	56	13	88	12
25	2	57	2	90	10
26	2	58	2	91	1
27	5	60	13	92	4
28	4	62	2	93	2
30	4	63	4	94	2
32	51	64	267	95	1
33	1	65	1	96	230
34	2	66	4	98	5
35	1	68	5	99	2
36	14	69	1	100	16
38	2	70	4	102	4

1	→	e,
i	→	c²,
−1	→	e,
−i	→	c²,
j	→	a·b²·c,
k	→	a·b²·c³,
−j	→	a·b²·c,
−k	→	a·b²·c³.

{−1, 1}	→	e,
{−i, i}	→	c²,
{−j, j}	→	a·b²·c,
{−k, k}	→	a·b²·c³.

n	groups	n	groups	n	groups
4	2	39	2	72	50
6	2	40	14	74	2
8	5	42	6	75	3
9	2	44	4	76	4
10	2	45	2	77	1
12	5	46	2	78	6
14	2	48	52	80	52
15	1	49	2	81	15
16	14	50	5	82	2
18	5	51	1	84	15
20	5	52	5	85	1
21	2	54	15	86	2
22	2	55	2	87	1
24	15	56	13	88	12
25	2	57	2	90	10
26	2	58	2	91	1
27	5	60	13	92	4
28	4	62	2	93	2
30	4	63	4	94	2
32	51	64	267	95	1
33	1	65	1	96	230
34	2	66	4	98	5
35	1	68	5	99	2
36	14	69	1	100	16
38	2	70	4	102	4

n	groups	n	groups	n	groups
4	2	39	2	72	50
6	2	40	14	74	2
8	5	42	6	75	3
9	2	44	4	76	4
10	2	45	2	77	1
12	5	46	2	78	6
14	2	48	52	80	52
15	1	49	2	81	15
16	14	50	5	82	2
18	5	51	1	84	15
20	5	52	5	85	1
21	2	54	15	86	2
22	2	55	2	87	1
24	15	56	13	88	12
25	2	57	2	90	10
26	2	58	2	91	1
27	5	60	13	92	4
28	4	62	2	93	2
30	4	63	4	94	2
32	51	64	267	95	1
33	1	65	1	96	230
34	2	66	4	98	5
35	1	68	5	99	2
36	14	69	1	100	16
38	2	70	4	102	4