{ "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 10
\n", "The Structure Within Rings\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", "Subrings
\r\n", "Quotient Rings and Ideals
\r\n", "Ring Isomorphisms
\r\n", "Homomorphisms and Kernels
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

Subrings

\r\n", "\r\n", "
\r\n", "In the last chapter we introduced rings, and used Sage to define several examples of rings. It is natural to ask whether we can have smaller rings \r\n", "within a larger ring, just as we saw smaller groups inside of a larger group. So the natural definition would be as follows:

\r\n", " \r\n", "DEFINITION 10.1
\r\n", "Let R be a ring. A non-empty subset S is a subring if S is a ring with respect to the addition (+) and multiplication \r\n", "(·) of R.

\r\n", "\r\n", "We have already seen some examples of subrings. For example, the set of even integers is a ring contained in the ring of integers, which is contained in the ring of rational numbers, which in turn is contained in the ring of real numbers.

\r\n", "\r\n", "It is clear that in testing to see if a subset of R is a ring, we do not need to check all 9 of the ring properties, since many of these properties will \r\n", "be "inherited" from the ring R. The next propostion shows us a quick way to check if a subset is indeed a subring.\r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 10.1
A non-empty subset S is a subring of a ring R if, and only if, whenever x and y are \r\n", "in S, x − y and x·y are in S.

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

\r\n", "Notice that from the definition every nontrivial ring R will contain at least two subrings: the trivial ring {0} will be a subring, as well as the entire ring \r\n", "R. These two subrings are called the trivial subrings.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the subset of real numbers of the form\r\n", "

S = {x + y √2 | x, y ∈ ℤ},

\r\n", "Determine whether or not this is a subring of ℝ.

\r\n", "\r\n", "Two typical elements are a = x₁ + y₁ √2 and b = \r\n", "x₂ + y₂ √2. Then\r\n", "

a − b = (x₁ − x₂) + \r\n", "(y₁ − y₂) √2, and

\r\n", "

a·b = (x₁ x₂ + 2 y₁ y₂) + \r\n", "(x₁ y₂ + x₂ y₁) √2.

\r\n", "Since all expressions in parenthesis are integers, these are in S. Thus, by Proposition 10.1, S is a subring of ℝ.

\r\n", "\r\n", "Let us look at an example where we find other subrings. Here is the very first ring that we defined in §9.3 of order 8:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\",\"b\")\r\n", "DefineRing([4, 2],[[a, 0],[0, b]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Recall that this ring has an identity element, namely
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FindUnity(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can we find a subring of R? Suppose we considered only the elements which did not involve b:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S = [0*a, a, 2*a, 3*a]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Does this form a subring? We can look at the multiplication tables for S
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(S)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and see that S is closed with respect to multiplication and addition. Furthermore, additive inverses exist for all elements, so S is also closed with respect to subtraction. Thus, by Proposition 10.1, this is a subring.

\r\n", "\r\n", "Notice that this subring does not include the multiplicative identity of R. Does that mean that this subring is without an identity?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FindUnity(S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In fact, the subring S does have a unity, but it is different than the unity of R! In general the existence of a unity of a subring is totally independent \r\n", "of the unity of R. A ring without unity may have a subring with unity, or vice-versa. This is the main reason why the existance of a multiplicative identity is \r\n", "not required in the definition of a ring.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Try to find all of the subrings of R, using the AddTable and MultTable commands. For example, the set
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S = [0*a, a, b, a+b]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "is not a subring by looking at the tables
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and seeing the black squares in one of the tables. How many ways can you pick a set S so that the black squares aren't there?

\r\n", "\r\n", "Hint: The additive group for this ring is Z₁₅^*. How many subgroups of Z₁₅^* are there?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In the case of groups, the intersection of a number of subgroups was again a subgroup. This last experiment suggested a close tie between subgroups and subrings, so it \r\n", "is natural to ask whether an intersection of a number of subrings is another subring. This quickly leads to the next proposition.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.2
\r\n", "Given any non-empty collection of subrings of the group R, denoted by L, then the intersection of all of the subrings in the collection\r\n", "

\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^* = ∩ H
H ∈ L
\r\n", "\r\n", "is a subring of R.

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

\r\n", "As with subgroups, we now have a general method of producing subrings of a ring R. Let S be any subset of R. We can consider the \r\n", "collection L of all subrings of R that contain the set S. This collection is non-empty since it contains the subring R itself. \r\n", "So by Proposition 10.2,\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
[S] = ∩ H
H ∈ L
\r\n", "\r\n", "
\r\n", "is a subring of R. By the way that the collection was defined, [S] contains S.

\r\n", "\r\n", "Actually, [S] is the smallest subring of R containing the subset S. For if H is a subring of R which contains \r\n", "S, then H ∈ L, so that [S] ⊆ H.

\r\n", "\r\n", "DEFINITION 10.2
\r\n", "We call [S] the subring of R generated by the set S.

\r\n", "\r\n", "Just as in the case for the Group command, the Sage command Ring finds [S] for any set S. Thus, we can find \r\n", "the subring generated by S with the command

\r\n", "\r\n", "Ring(S)

\r\n", "\r\n", "provided that the ring R has already been entered.

\r\n", "\r\n", "For example, let us use this command to find all of the subrings of the non-commutative ring of order 8.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\",\"b\");\r\n", "DefineRing([4,2],[[a,b],[2*a,0]]);\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us first try to find rings generated by only one element. Of course we would have the trivial ring
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ring(0*a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "but let us look at the other 7 elements. The ring generated by the next element
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ring(a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "contains 4 elements, while the ring generated by 2a
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ring(2*a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "contains only two.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "By going though the remaining 5 elements, determine how many subrings can be generated by just one element.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can there be any subrings which require two generators? Since the additive structure of a subring is a subgroup of the additive structure of the original ring, \r\n", "Lagrange's theorem holds for rings as well as groups. Thus, any subring of a group of order 8 must be of order 1,2,4, or 8. The experiment has obviously found \r\n", "all subrings of order 2. The only other nontrivial subrings would be of order 4. Such a subring could not contain any element which generated a ring of order 4. \r\n", "Thus, the only elements such a subring could contain would be 0, 2a, b, and 2a+b. Let us check if these four elements form a subring.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S = [0*a, 2*a, b, 2*a+b]" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(S)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(S)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So this gives us one more nontrivial subring, which gives a total of six nontrivial subrings.

\r\n", "\r\n", "Let us turn our attention to finding the subrings of an infinite ring. Obviously, we will not be able to have Sage produce multiplication tables, but we ought to \r\n", "be able to derive some subrings for some common infinite rings. The simpliest such ring is the ring of integers, ℤ. The subring generated by a positive number \r\n", "n would be the set of all multiples of n. This is indeed a subring, since the difference and the product of two multiplies of n yields a \r\n", "multiple of n. What is interesting is that all subrings of ℤ are produced this way.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSTION 10.3
\r\n", "A subring of the ring of integers ℤ consists of all multiples of some non-negative number n. This subring is denoted n ℤ.

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

\r\n", "Although the subrings of ℤ are easily classified, this is not the case with the ring of real numbers. The first example, the set S of all numbers of the \r\n", "form x + y √2, gives just one of countless subrings of ℝ. We could have Sage do the computations for us. Note that
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "var('x1 x2 y1 y2')" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(x1 + y1*sqrt(2))*(x2 + y2*sqrt(2))" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "expand(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "produces a number of the correct form. Since S is obviously closed with respect to subtraction, S is a subring \r\n", "of ℝ.

\r\n", "\r\n", "We can actually define this ring in Sage. If we let e represent 1, and a \r\n", "represent √2. These two elements are both of infinite additive order. \r\n", "We can convey this to Sage by entering \"0\" for the\r\n", "order of each of the elements. Then a² = 2e, so the ring can be entered by the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"e\",\"a\")\r\n", "DefineRing([0,0],[[e,a],[a,2*e]])\r\n", "ListRing()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Of course we cannot list the elements because there are an infinite number of them. Nonetheless, we can perform some of the operations on this ring.\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(e + 2*a)*(4*e - 3*a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This last statement demonstrates that\r\n", "

(1 + 2√2)·(4 − \r\n", "3√2) = −8 + 5√2.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Does the set of all numbers of the form x + y ∛2, where x and y are integers, form a subring of ℝ? If not, what is the subring \r\n", "generated by these numbers? Use 2^(1/3) for the cube root of 2.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Clearly, the subrings of the real numbers can be much more complicated than the subrings of integers.

\r\n", "\r\n", "A natural question to ask is whether we can produce quotient \r\n", "rings from these subrings the way we constructed quotient groups out of the normal subgroups. We will look into this in the next section.

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

Quotient Rings and Ideals

\r\n", "\r\n", "
\r\n", "When we studied group theory, one of the most important concepts we discovered was being able to form a quotient group out of the cosets of certain subgroups. \r\n", "After some investigation we learned exactly which subgroups yielded such a quotient group: the normal subgroups. A natural question is whether it is possible to \r\n", "form quotient rings out of the cosets of a subring.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Here is the non-commutative ring of order 8 from the last section.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\",\"b\");\r\n", "DefineRing([4,2],[[a,b],[2*a,0]]);\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can we form a quotient ring out of this ring, the way that we constructed a quotient group?

\r\n", "\r\n", "We found this ring has six nontrivial subrings.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S1 = Ring(a); S1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S2 = Ring(2*a); S2" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S3 = Ring(b); S3" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S4 = Ring(a+b); S4" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S5 = Ring(2*a+b); S5" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S6 = Ring(2*a, b); S6" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If there is a quotient ring, what would the elements of this quotient be? We would expect the additive structure of the quotient ring to be the additive quotient \r\n", "group R/S. Since addition is commutative, we know that this quotient group always exists. We can use Sage to find the cosets \r\n", "of S under the operation of addition. Since left and right cosets are the same when working with rings, we will simply use the \r\n", "command Coset(R, S) for the list of cosets of the subgroup S of R. For the subgroup S₁, here are the cosets:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = Coset(R, S1); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can add two cosets together using the following definition:\r\n", "

X + Y = { x + y | x ∈ X and y ∈ Y}.

\r\n", "This gives the quotient Q the natural addition. We can see the addition table for Q as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can we now multiply elements of Q to form a ring? The natural way to define the product of two sets is the way we defined such a product for groups:\r\n", "

X·Y = { x·y | x ∈ X and y ∈ Y}.

\r\n", "Will such a product of two cosets in Q yield another coset? Let's try it!
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Hang on! Why are there black squares in the table! Sage is trying to tell us that the product of two cosets is not always a coset. If we first set up the two \r\n", "cosets of Q,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q1 = S1; Q1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q2 = b + S1; Q2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we find, for example,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q2 * Q1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "in indeed a coset, but the product
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q1 * Q2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "produced way too many elements! What is going on? Since {0, a, 2a, 3a} is the zero element for Q, we would expect the \r\n", "product to be {0, a, 2a, 3a}. But we somehow got some extra elements. Where did they come from?

\r\n", "\r\n", "EXPERIMENT:
\r\n", "The above product demonstrates that there are two elements of S₁, x₁ and x₂, such that\r\n", "

x₁·(b + x₂)

\r\n", "is not in S. Use Sage, along with a little trial and error, to find two such elements. For example, to see whether \r\n", "x₁ = x₂ = 0 works, enter
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "x1 = 0*a\r\n", "x2 = 0*a\r\n", "x1*(b + x2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Change x1 and x2 so that the result is not in S₁.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Although it seems as though our attempt to define a quotient ring has failed miserably, we might want to study this example to understand why we failed to have \r\n", "a quotient group. Since the additive identity of the quotient group is the subring S, S times any other coset should give S again. But that \r\n", "means that subring S times any element of R would have to produce only elements in S. But we have seen an example where this wasn't the \r\n", "case, namely
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S1*(b + x2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since the elements produced were not all in S, S did not act like the zero element in the product.

\r\n", "\r\n", "But wait! What if we found a subring for which S·x always was a subset of S for every x in R? By a similar logic, \r\n", "we would also have to require that x·S be a subset of S. A quick way to test this is to see if the \r\n", "products S·R and R·S are both subsets of S. Let us check the second subring of R that we found.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S2 * R" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R * S2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So far, so good. This at least ensures that the additive identity {0, 2a} will behave properly for multiplication. Let us use the multiplication table to see \r\n", "if the product of any two cosets will again be a coset.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = Coset(R, S2); Q" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This looks pretty good—no black squares, so we have at least defined a multiplication for these cosets. It is interesting that this multiplication table is \r\n", "not commutative, even though all of the subrings of R were commutative. So this quotient cannot be like any of the subrings of R.

\r\n", "\r\n", "But look closely at this table. Not every product yields a coset, sometimes it yields only a subset of a coset. For appearances, Sage has colored such \r\n", "a subset according to the color of the coset.

\r\n", "\r\n", "One way to rectify this slight blemish in our multiplication table is to add the identity coset to each entry in the table. That is, instead of defining the product of \r\n", "the cosets X and Y to be X·Y, we define the product of two cosets to be\r\n", "

X ∗ Y = X·Y + S.

\r\n", "We can repair the multiplication table with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "QuotientRing = true" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "A new multiplication table will now be constructed using this new definition of the product of two cosets.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This looks much better! We still have not shown that this multiplication table obeys the laws of a ring, but we will get to that shortly. First, let us see if any of \r\n", "the other subrings of R could form a multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = Coset(R, S3); Q" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This subring seemed to fail, but notice that the products
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S3 * R" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R * S3" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "are not both contained in S₃.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Try forming the multiplication tables for the cosets of S₄, S₅, and S₆. For which subrings do the cosets \r\n", "form multiplication tables? For which subrings are R·S and S·R both contained in S?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The pattern is apparent. Subrings of R for which R·S and S·R are both contained in S have a special \r\n", "property, and hence we give such subrings a special name. Rather then calling them "normal subrings" we will use the more traditional name.

\r\n", "\r\n", "DEFINITION 10.3
\r\n", "A subring I of a ring R is called an ideal of R if both I·R and R·I are contained in \r\n", "the subring I.

\r\n", "\r\n", "We now are ready to prove that the cosets of an ideal ready do form a quotient ring.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.4
\r\n", "Let R be a ring, and let I be an ideal of R. The the addition quotient group R/I forms a ring, with the product of two \r\n", "cosets X and Y being X∗Y = X·Y + I. This ring is called the quotient ring \r\n", "R/I.

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

\r\n", "From the experiment, you should have discovered that three of the six nontrivial subrings were ideals. The two trivial subrings, {0} and R itself, will be ideals \r\n", "for any ring. These two ideals are called the trivial ideals.

\r\n", "\r\n", "Let us see if we can find ideals for other rings.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the ideals of the ring ℤ, and determine the quotient rings.

\r\n", "\r\n", "By Proposition 10.3 that every subring of ℤ is of the form n ℤ for \r\n", "some non-negative n. If S = n ℤ, then since any multiple of n times any integer gives a multiple of n, we have \r\n", "S·ℤ = S, and ℤ·S = S. Thus, any subring of ℤ is an ideal of ℤ.

\r\n", "\r\n", "What is the quotient ring ℤ/(n ℤ)? The cosets can all be expressed in the form a + n ℤ, where a = 0, 1, \r\n", "2, … n − 1. Addition and multiplication is easily discribed:\r\n", "

(a + n ℤ) + (b + n ℤ) = (a + b + n ℤ) = \r\n", "(a + b) mod n + n ℤ,

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

(a + n ℤ)·(b + n ℤ) = (a·b + n ℤ) = \r\n", "a·b mod n + n ℤ.

\r\n", "Clearly the quotient ring behaves exactly like the ring Z_n. To put this another way, the quotient ℤ/(n ℤ) is isomorphic \r\n", "to Z_n. We will study ring isomorphisms in the next section.

\r\n", "\r\n", "In contrast, let us consider a ring such as the rational numbers ℚ. We can quickly see that the only ideals of ℚ are the trival ideals, even though there are \r\n", "a host of subrings of ℚ. The proof holds for any field, so let us prove the following proposition.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.5
\r\n", "Any field or skew field can only have trivial ideals.

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

\r\n", "We want to develop a way to find the ideals of a general ring R. We have already observed that the intersection of two subrings is again a subring. Using this \r\n", "fact, we were able to use Sage to find all of the subrings. So the natural question is whether the intersection of two ideals gives an ideal. If so, we will be \r\n", "able to use Sage to find all of the ideals of a finite ring.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.6
If L is a non-empty collection of ideals of a ring R, then the intersection of all of these ideals \r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
I^* = ∩ I
I ∈ L
\r\n", "is an ideal of R.

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

\r\n", "We can now define the smallest ideal of R that contains a subset S. We proceed as we did for subrings, and consider the collection of all ideals \r\n", "of R containing S. This collection will be non-empty, since R itself is such an ideal. If we denote this collection by L, then \r\n", "the smallest ideal of R containing S would have to be\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
⟨S⟩ = ∩ I
I ∈ L
\r\n", "
\r\n", "We call ⟨S⟩ the ideal generated by S. Notice the distintion between this notation and the notation of the subring generated \r\n", "by S, [S].

\r\n", "\r\n", "We can have Sage find the ideal of R generated by any set S with the command Ideal(R, S).

\r\n", "\r\n", "For example, in the non-commutative ring of order 8 which we were working with earlier,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\",\"b\");\r\n", "DefineRing([4,2],[[a,b],[2*a,0]]);\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we can find all of the ideals rather quickly. For example, the ideal generated by the element a is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ideal(R, a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "so a cannot be contained in any nontrivial ideal. Likewise, 3a would generate the whole ring R, since 3·3a = a. If we \r\n", "try the element a + b, we get
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ideal(R, a + b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This tells us that a + b is not in a nontrivial ideal. The same thing is true for 3a + b = 3(a + b). So the remaining\r\n", "three non-zero elements which could be in a nontrivial ideal form the ideals
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ideal(R, 2*a)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ideal(R, b)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Ideal(R, 2*a + b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we require two of the three of these elements to be in the ideal, it is clear that we will have the same ideal as ⟨b⟩. Thus, there are five ideals in this \r\n", "ring, which we can express as\r\n", "

⟨0⟩, ⟨a⟩, ⟨2a⟩, ⟨b⟩, and ⟨2a + b⟩.

\r\n", "Notice that all five ideals could be generated with a single element. We will give a special name for these ideals.
\r\n", "\r\n", "
\r\n", "DEFINITION 10.4
\r\n", "An ideal of R that is generated by only one element of R is called a principal ideal. If all of the ideals of R are principal \r\n", "ideals, then the ring is called a principal ideal ring.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "In Chapter 9 we found a non-commutative unity ring of order 8:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"e\",\"a\",\"b\");\r\n", "DefineRing([2,2,2],[[e,a,b],[a,a,a],[b,b,b]]);\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Find all of the ideals of this ring. Is this a principal ideal ring?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "It should be noted that the ring of integers ℤ is a principal ideal ring, since all ideals (in fact all subrings) are of the form n ℤ, which is \r\n", "generated by the single element n. Since ℤ is also an integral domain, we will combine the two terms and call ℤ \r\n", "a principal ideal domain, or PID. Principal ideal domains play an important role in ring theory, as we will see in §12.3.

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

Ring Isomorphisms

\r\n", "\r\n", "
\r\n", "As we work with different rings, it is natural to ask whether we can classify the finite rings the way that we did for small groups. Of course, we will consider two \r\n", "rings to be "equivalent" if the elements of one ring can be renamed to form the other ring. We have already seen an example of equivalent rings: the quotient \r\n", "ring ℤ/(n ℤ) was essentually the same ring as Z_n. We would like to formalize this equivalence using the same technique that we \r\n", "used for groups.

\r\n", "\r\n", "DEFINITION 10.5
\r\n", "Let A and B be two rings. A ring isomorphism from A to B is a one-to-one mapping\r\n", "

ƒ: A → B

\r\n", "such that \r\n", "

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

\r\n", "\r\n", "
\r\n", "If there exists a ring isomorphism from A to B that is surjective, then we say that the rings A and B are isomorphic, denoted \r\n", "by A ≈ B.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find an isomorphism from the quotient ring ℤ/(n ℤ) to Z_n.

\r\n", "\r\n", "The natural mapping would be as follows:\r\n", "

ƒ(a + n ℤ) = a mod n,

\r\n", "which we can verify is well defined by noting that if a + n ℤ = b + n ℤ, then a − b is a multiple \r\n", "of n, so a mod n = b mod n.\r\n", "Also, ƒ is an injective and surjective function from ℤ/(n ℤ) to Z_n. Furthermore, \r\n", "ƒ(a + b) = ƒ(a) + ƒ(b), and ƒ(a·b) = \r\n", "ƒ(a)·ƒ(b). So we have that\r\n", "

ℤ/(n ℤ) ≈ Z_n.

\r\n", "\r\n", "
\r\n", "EXAMPLE:
\r\n", "Two similar looking rings of order 10 can be defined in Sage as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\")\r\n", "DefineRing([10],[[2*a]])\r\n", "CheckRing()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = ListRing(); A" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"b\");\r\n", "DefineRing([10],[[6*b]]);\r\n", "CheckRing()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "B = ListRing(); B" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Show that these rings are isomorphic.

\r\n", "\r\n", "Here are the addition and multiplication tables for the ring A.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(A)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that the additive structure of this ring is like Z₁₀, but the multiplicative structure is totally different, since there is no identity \r\n", "element.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FindUnity(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "With a little thought one realizes that any ring of order 10 must have the same additive structure, since there is only one abelian group of order 10. \r\n", "Here are the addition and multiplication tables for the ring B:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(B)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(B)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we compare the multiplication table to that of the ring A
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([0*b, b, 2*b, 3*b, 4*b, 5*b, 6*b, 7*b, 8*b, 9*b])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We find many simularities, but they are not exactly the same.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Can you find an isomorphism from A to B by rearranging the elements of B above so that the multiplication tables for A and \r\n", "B have the same color pattern? Careful! The addition tables for A and B must also have the same color pattern! Rather than \r\n", "using trial and error, see if you use inductive reasoning using the properties of the ring. There is, in fact, only one solution.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Another way to demonstrate the isomorphism is to construct a mapping between the two rings. Since a is an \r\n", "additive generator of A, we know that it should map to one of the additive generators of B, \r\n", "{b, 3b, 7b, 9b}. So we can use trial and error.\r\n", "In Sage, the command RingHomo defines a ring homomorphism, similar to the way \r\n", "that Homomorph defined a group homomorphism.\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = RingHomo(A, B)\r\n", "HomoDef(F, a, b)\r\n", "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = RingHomo(A, B)\r\n", "HomoDef(F, a, 3*b)\r\n", "FinishHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Try sending a to one of the other two additive generators of B. Can we get a homomorphism? If you find a homomorphism, what is the kernel?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "From either of the experiments, we found an isomorphism from A to B, but it was far from obvious. We would like a way to generalize this example so we \r\n", "can determine if two similar \r\n", "rings are isomorphic.\r\n", "\r\n", "

\r\n", "One way to help find an isomorphism between A and B is to show that both of these are isomorphic to a subring of the familiar \r\n", "rings Z_n for some n. For example, consider 2 Z₂₀, the even elements of Z₂₀.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z20 = ZRing(20); Z20" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R = Ring(Z20[2]); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we compare the multiplication tables for A and R,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that they have the same color pattern. Furthermore, the addition tables
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(A)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddTable(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "are the same, showing that \r\n", "

A ≈ 2 Z₂₀.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Using the same technique as 2 Z₂₀, define Z₆₀, and form the subring 6 Z₆₀. Does this have the same color \r\n", "pattern in the multiplication table as the ring B?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "These last two isomorphisms suggest a pattern that can be extended to many finite rings.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.7
\r\n", "Let R be a finite ring whose additive structure is a cyclic group of order n. Let x be a generator of the additive group. Then \r\n", "x² = k x for some positive integer k ≤ n, and \r\n", "

A ≈ k Z_{k n}.

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

\r\n", "This proposition suggests that rings of the form k Z_{k n} are important. Hence, we will refer to such rings by the following \r\n", "terminology.

\r\n", "\r\n", "DEFINITION 10.6
\r\n", "A cyclic ring is a ring whose additive group is cyclic.

\r\n", "\r\n", "Note that this definition of cyclic rings also includes the infinite rings ℤ and its subrings n ℤ.

\r\n", "\r\n", "Proposition 10.7 shows that for the two cyclic rings A and B that we worked with in the beginning of this section, \r\n", "

A ≈ 2 Z₂₀ and B ≈ 6 Z₆₀.

\r\n", "\r\n", "Our experiment showed that in fact 2 Z₂₀ must be isomorphic to 6 Z₆₀. But this isomorphism was not nearly as obvious. How would \r\n", "anyone guess that ƒ(a) had to be 7 b?

\r\n", "\r\n", "In order to prove that such isomorphisms exist in general, we will need a few lemmas about number theory. Once these are proven, we will be able to \r\n", "determine all non-isomorphic rings of order 10.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 10.1
\r\n", "Let d be a positive divisor of n, and let f be the largest divisor of d that is coprime \r\n", "to ⁿ⁄_d. Then if q is coprime to both f and ⁿ⁄_d , then \r\n", "q is coprime to n.

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

\r\n", "With this lemma, we can strengthen the greatest common divisor theorem (0.4).\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 10.2
\r\n", "Given two positive numbers x and y, there exist u and v in ℤ such that\r\n", "

u x + v y = gcd(x, y),

\r\n", "where u is coprime to y.

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

\r\n", "With Lemma 10.2, we can now prove determine which cyclic rings of the form x Z_{x n} are isomorphic.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 10.1: The Cyclic Ring Theorem
\r\n", "If x and n are positive integers, then\r\n", "

x Z_{x n} ≈ k Z_{k n}

\r\n", "where k = gcd(x, n).

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

\r\n", "We can now understand why 2 Z₂₀ was isomorphic to 6 Z₆₀. We merely have to notice that 2 = gcd(10, 6). Since the only rings of \r\n", "order 10 are cyclic rings, there are in fact four possibilities for a ring of order 10:\r\n", "

Z₁₀, 2 Z₂₀, 5 Z₅₀, 10 Z₁₀₀.

\r\n", "To see if these four rings are distinct, we can look at the multiplication tables.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z10 = ZRing(10);\r\n", "MultTable(Z10)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z20 = ZRing(20);\r\n", "R = Ring(Z20[2])\r\n", "MultTable(R)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z50 = ZRing(50);\r\n", "R = Ring(Z50[5])\r\n", "MultTable(R)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z100 = ZRing(100);\r\n", "R = Ring(Z100[10])\r\n", "MultTable(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The last ring has the property that any product of elements gives 0. Notice that there are exactly as many rings of order 10 as there are divisors of 10. We can \r\n", "generalize this result to give the following corollary.\r\n", "\r\n", "

\r\n", "\r\n", "COROLLARY 10.1
\r\n", "The number of non-isomorphic cyclic rings of order n is precisly the number of divisors of n (including 1 and n).

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

\r\n", "Although this corollary seems to be a big help in finding all finite rings, there are, in fact, many non-cyclic rings. For example, there are 8 non-cyclic rings \r\n", "of order 4, which when combined with the 3 cyclic rings from Corollary 10.1 gives a total of 11 rings of order 4. There are 52 rings of order 8 (4 cyclic, 20 with \r\n", "additive group Z₁₅^*, and 28 with an additive group Z₂₄^*).

\r\n", "\r\n", "As one can see, finding all rings of a given order is a much more difficult task than finding all the groups of the same order. In fact, it is still unknown how \r\n", "many non-isomorphic rings there are of order 32. Here is a table of the number of rings of a given order:\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
\r\n", " Rings of order n\r\n", "
n rings n rings
1 1 17 2
2 2 18 22
3 2 19 2
4 11 20 22
5 2 21 4
6 4 22 4
7 2 23 2
8 52 24 104
9 11 25 11
10 4 26 4
11 2 27 59
12 22 28 22
13 2 29 2
14 4 30 8
15 4 31 2
16 390 32 ???
\r\n", "\r\n", "
\r\n", "There are at least 18590 known rings of order 32, but it has not been proven these are all of them. There are some patterns in this table. Can you find any?

\r\n", "\r\n", "In Sage, we can load any of the rings of order 15 or less. The command NumberSmallRings will produce the number of rings of a given order, \r\n", "up to order 15.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "NumberSmallRings(8)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now we can load any of these 52 rings.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R = SmallRing(8, 51); R" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(R)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In this way, we can explore a multitude of different rings.\r\n", "\r\n", "\r\n", "

\r\n", " Rings of order n\r\n", "
n	rings	n	rings
1	1	17	2
2	2	18	22
3	2	19	2
4	11	20	22
5	2	21	4
6	4	22	4
7	2	23	2
8	52	24	104
9	11	25	11
10	4	26	4
11	2	27	59
12	22	28	22
13	2	29	2
14	4	30	8
15	4	31	2
16	390	32	???

Homomorphisms and Kernels

\r\n", "\r\n", "
\r\n", "In the last section we determined two rings were isomorphic by finding a one-to-one and onto function mapping one ring to the other. If we considered a similar \r\n", "function which was not nessesarily one-to-one or onto, we would have a ring homomorphism.

\r\n", "\r\n", "DEFINITION 10.7
\r\n", "If A and B are two rings, then a mapping ƒ : A → B such that \r\n", "

ƒ(x + y) = ƒ(x) + \r\n", "ƒ(y), and ƒ(x·y) = ƒ(x)·ƒ(y) for \r\n", "all x and y in A

\r\n", "is called a ring homomorphism.

\r\n", "\r\n", "Notice that a ring homomorphism preserves both of the ring operations. In particular, a ring homomorphism will also be a group homomorphism from the additive group \r\n", "of A to the additive group of B. Thus, we can immediately apply the results of group homomorphisms to see two properties of ring homomorphisms:

\r\n", "If ƒ is a homomorphism from A to B, then \r\n", "

ƒ(0) = 0 and ƒ(−x) = −ƒ(x) for \r\n", "all x ∈ A.

\r\n", "We have seen some examples of ring homomorphisms in the last section, since any isomorphism is certainly a homomorphism. But let us see if we can define a \r\n", "homomorphism between two non-isomorphic rings. Consider for example a homomorphism between Z₃ and Z₆.

\r\n", "\r\n", "First we must define Z₃ and Z₆ simultaneously.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z3 = ZRing(3); Z3" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z6 = ZRing(6); Z6" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now suppose we wish to define a \r\n", "homomorphism ƒ from Z₃ to Z₆. We already see that ƒ(0) must be 0, \r\n", "and ƒ(2) = ƒ(−1) = −ƒ(1). Thus, the homomorphism is determined completely by the \r\n", "value of ƒ(1). A natural choice would be to let ƒ(1) = 2 mod 6. We can define a ring homomorphism the same way as we \r\n", "did for group homomorphisms, except we use the command RingHomo instead of Homomorph to let Sage know that F is a \r\n", "ring homomorphism. We can try to define a homomorphism \r\n", "from Z₃ to Z₆ with the commands:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = RingHomo(Z3, Z6)\r\n", "HomoDef(F, 1, 2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Even though 1 and 2 are technically elements of ℤ, not Z₃ or Z₆, Sage\r\n", "makes the natural translations, knowing the arguments are expected to be in the rings \r\n", "Z₃ and Z₆.\r\n", "We can now use the command FinishHomo(F) to check to see if the function F can be completed to form a homomorphism. If we check \r\n", "the function we just defined,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that this is not a homomorphism!

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Replace the 2 in the command defining F with other elements of Z₆, and check to see which are homomorphisms. How many \r\n", "possible homomorphisms are there from Z₃ to Z₆?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Design another homomorphism G which maps elements from Z₆ to Z₃. Notice that all that must be defined in Sage \r\n", "is the element G(1). Then use Sage to check if this can be completed for form a homomorphism.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In both of these experiments one may have noticed that one possible mapping would be to send all elements to 0. This in fact will always yield a homomorphism, and we \r\n", "will give this a special name.

\r\n", "\r\n", "DEFINITION 10.8
\r\n", "If A and B are any two rings, then the mapping \r\n", "

ƒ : A → B, ƒ(x) = 0 for all x ∈ A

\r\n", "is called the zero homomorphism from A to B.

\r\n", "\r\n", "Although the zero homomorphism works for both of the above experiments, there are also nonzero homomorphisms which map from Z₃ to \r\n", "Z₆ and Z₆ to Z₃. If you haven't found these already, go back and try to find them.

\r\n", "\r\n", "Once we have the homomorphism ƒ defined, we can define ƒ(S), where S is a set of elements in the domain \r\n", "of ƒ, to be the set of all values ƒ(x), where x is in S. We can also define the inverse image of an \r\n", "element y to be ƒ⁻¹(y), the set of elements x such that ƒ(x) = y. In fact, we can \r\n", "define the inverse image of a set of elements in the same way: ƒ⁻¹(T) is the set of elements x such \r\n", "that ƒ(x) is in T. We can use Sage to find the image of a set by merely entering Image(F,S). We can find the inverse image of an element or a set S with \r\n", "the Sage command HomoInv(F, S).

\r\n", "\r\n", "For example, here are the nonzero homomorphisms from the previous two experiments.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = RingHomo(Z3, Z6)\r\n", "HomoDef(F, 1, 4)\r\n", "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = RingHomo(Z6, Z3)\r\n", "HomoDef(G, 1, 1)\r\n", "FinishHomo(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can evaluate the homomorphism in the standard way:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F(2)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G(4)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "To compute ƒ({0,1}), we enter the Sage command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F,[0, 1])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can also find the inverse image of the element a under G by the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(G, 1)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Likewise, we can take the inverse image of the set {0,1} with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoInv(G, [0, 1])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "What is the difference between F(x), and G^-1(x)? Does F(G(x)) always produce x? What \r\n", "about G(F(x))?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can ask whether the image or inverse image of a subring will again be a subring. This is actually very easy to prove, as seen in the next proposition.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.8
\r\n", "Suppose ƒ is a homomorphism from the ring A to the ring B. Then if S is a subring of A, then ƒ(S) \r\n", "is a subring of B. Likewise, if T is a subring of B, then ƒ⁻¹(T) will be a subring of A.

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

\r\n", "We can define the kernel and the image of a homomorphism in the same way that we did for group homomorphisms.

\r\n", "\r\n", "DEFINITION 10.9:
\r\n", "Given a homomorphism ƒ from the ring A to the ring B, the kernel of ƒ is ƒ⁻¹(0), \r\n", "denoted Ker(ƒ). The image of ƒ is ƒ(A), denoted Im(ƒ).

\r\n", "\r\n", "We can use the HomoInv command to find the kernel of a homomorphism, or we can simply use the command Kernel(ƒ) to find the kernel of \r\n", "the homomorphism. For example, the kernels of the homomorphisms F and G that we have defined are
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The images found using the Image command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F, Z3)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(G, Z6)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "When we have a homomorphism from A to B, since A is a trivial subring of A, we have by Proposition 10.8 that the image will be a \r\n", "subring of B. Likewise, the kernel of a homomorphism will be a subring of A, since {0} is a subring of B. However, we can say even more about \r\n", "the kernel.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 10.9
\r\n", "If ƒ is a homomorphism from the ring A to the ring B, then the kernel of ƒ is an ideal of B. Furthermore, \r\n", "ƒ is injective if, and only if, Ker(ƒ) = {0}.

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

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the non-commutative ring of order 8 that we looked at earlier in this chapter.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\",\"b\");\r\n", "DefineRing([4,2],[[a,b],[2*a,0]]);\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Find a non-zero homomorphism from this ring to some other ring.

\r\n", "\r\n", "The kernel would have to be an ideal of R. But we have already found that \r\n", "R has only three nontrivial ideals:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "I1 = Ideal(R, 2*a); I1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "I2 = Ideal(R, 2*a + b); I2" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "I3 = Ideal(R, b); I3" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Thus, the kernel would have to be R, {0}, or one of these three ideals. If the kernel is all of R, then the homomorphism is the zero homomorphism. \r\n", "On the other extreme, if the kernel is {0}, then the homomorphism is injective by Proposition 10.9. To produce a more interesting homomorphism, we would have to use \r\n", "one of the three above ideals. The question is, to which ring should we map R?

\r\n", "\r\n", "It seems that a natural answer would be a quotient ring! Since there is a natural group homomorphism from R to R/I, we can ask \r\n", "whether this group homomorphism extends to become a ring homomorphism.

\r\n", "\r\n", "Let us try this out with the ideal I₁. The quotient ring is given by:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = Coset(R, I1); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We wish to define a homomorphism i(x) which maps an element in R to the coset of Q containing that element. We only need to define \r\n", "i(a) and i(b) to complete the definition.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "i = RingHomo(R, Q)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(i, a, a + I1)\r\n", "HomoDef(i, b, b + I1)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(i)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So i defines a homomorphism from R to Q. The kernel of this homomorphism is given by:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(i)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Try forming similar homomorphisms using the ideals I₂ and I₃ instead. Use the FinishHomo command to see if they\r\n", "really are homomorphisms.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In general, we can form a homomorphism from a ring R to a quotient ring R/I using the same technique. We will state this as a lemma:\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 10.3
\r\n", "\r\n", "If I is an ideal of the ring R, then the natural mapping\r\n", "

i: R → R/I

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

i(x) = x + I

\r\n", "is a surjective ring homomorphism from R to R/I with the kernel being I.

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

\r\n", "In the homomorphisms produced by Lemma 10.3, the image of the homomorphism is isomorphic to R/Ker(ƒ). It wouldn't be too surprising if this were \r\n", "true for all ring homomorphisms, since the first isomorphism theorem studied in Chapter 4 shows that the additive group on Im(ƒ) would be group \r\n", "isomorphic to the additive structure of R/Ker(ƒ). It is easy to show that the ring Im(ƒ) is isomorphic to the \r\n", "ring R/Ker(ƒ) as well, giving us an isomorphism theorem for rings.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 10.2:The First Ring Isomorphism Theorem
\r\n", "\r\n", "Let ƒ be a ring homomorphism from a ring R to a ring S, whose image is H. If the kernel of ƒ is I, then \r\n", "there is a natural surjective isomorphism\r\n", "

ϕ : R/I → H

\r\n", "which causes the following diagram to commute:\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "


R	i ―――►			R/I
ƒ	↘		⤢	ϕ
		H

\r\n", "
\r\n", "(Here, i(x) is the homomorphism defined in Lemma 10.3.) Thus, H ≈ R/I.

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

\r\n", "It should be noted that there are second and third ring isomorphism theorems, which correspond to the second and third isomorphism theorems studied in our work with \r\n", "groups. These are covered in Problems 15 and 16. However, we are mainly interested in the first ring isomorphism theorem, because this allows us to guarantee \r\n", "the existance of isomorphisms without having to actually write them down. This becomes particularly important when we start working with infinite rings, since \r\n", "the isomorphisms could become unwieldy.

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

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

Proofs:

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

\r\n", "\r\n", "Certainly if S is a subring, then x − y and x·y would be in S whenever x and y \r\n", "are in S. So let us suppose that S is non-empty, and is closed with respect to subtraction and multiplication. If x is any element in \r\n", "S, then x − x = 0 is in S, so S contains an additive identity. Also, 0 − x = −x \r\n", "would also be in S, so S contains additive inverses of all of its elements. Then whenever x and y are in S, \r\n", "x − (−y) = x + y is in S, so S is closed with respect to addition. The commutative and \r\n", "associative properties of addition, as well as the associative and two distributive laws for multiplication, come from the original ring R. Finally, \r\n", "S is closed with respect to multiplication, so S is a subring.

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

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

\r\n", "\r\n", "First of all, note that H^* is not the empty set, since 0 is in each H in the collection. We now can apply Proposition 10.1. \r\n", "Let x and y be two elements in H^*. Then, for every H ∈ L, we have x, y ∈ H.\r\n", "

\r\n", "\r\n", "Since each H is a subring of R, we have\r\n", "

x − y ∈ H and x·y ∈ H

\r\n", "for all H ∈ L. Therefore, x − y and x·y are in H^*, and so \r\n", "H^* is a subring of R.

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

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

\r\n", "\r\n", "First of all, the trivial subring {0} can be considered the set of all multiples of 0. Also, the entire ring ℤ could be considered all of the multiples of 1. \r\n", "Let S be a nontrivial subring, and let x be in S. Then −x is also in S, so S must contain some positive \r\n", "integers. Let n be the smallest positive integer contained in S. Certainly all multiples of n would be in S, but suppose that some \r\n", "element m in S is not a multiple of n. Then by the greatest common divisor theorem (0.4), there exist two integers u and v \r\n", "such that\r\n", "

u n + v m = gcd(n, m).

\r\n", "Since S is closed under addition, this implies that gcd(n, m) is in S. But m is not a multiple of n, so \r\n", "gcd(n, m) < n. But this contradicts the fact that n is the smallest positive integer in S. Thus, S \r\n", "consists exactly of all of the multiples of n, and so S = n ℤ.

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

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

\r\n", "\r\n", "The quotient group R/I is an abelian group, so we need only to check that the multiplication is closed, and that the associativity and two distributive \r\n", "laws hold.

\r\n", "\r\n", "Let X and Y be two cosets of R/I. Let x be an element in X, and y an element in Y. Then the product \r\n", "of the cosets X and Y is\r\n", "

X∗Y = \r\n", "X·Y + I = (x + I)·(y + I) + I = \r\n", "x·y + I·y + x·I + I·I + I.

\r\n", "Because I is an ideal, I·y, x·I, and I·I are all subsets of I. Hence, the \r\n", "sum I·y + x·I + I·I + I will be a subset of I. But since the last term of \r\n", "this expression is I, I·y + x·I + I·I + I contains the ideal I, so \r\n", "this sum equals I. Thus,\r\n", "

(x + I)·(y + I) + I = X∗Y = \r\n", "X·Y + I = x·y + I,

\r\n", "which is a coset of R/I.

\r\n", "\r\n", "Now suppose that X, Y, and Z are three cosets of R/I, with x, y, and z being representative \r\n", "elements, respectively. Then\r\n", "

(X∗Y)∗Z = \r\n", "((x + I)∗(y + I))∗(z + I) = \r\n", "(x·y + I)∗(z + I) =((x·y)·z + I) = \r\n", "(x·(y·z) + I) = (x + I)∗(y·z + I) = \r\n", "(x + I)∗((y + I)∗(z + I)) = X∗(Y∗Z).

\r\n", "So multiplication is associative. Also,\r\n", "

X∗(Y + Z) = (x + I)∗(y + z + I) = \r\n", "(x·(y + z) + I) = x·y + x·z + I =\r\n", "(x·y + I) + (x·z + I) = X∗Y + X∗Z,

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

(X + Y)∗Z = (x + y + I)∗(z+ I) = \r\n", "((x + y)·z + I) = \r\n", "x·z + y·z + I =(x·z + I) + (y·z + I) = \r\n", "X∗Z + Y∗Z.

\r\n", "Thus, the two distributive laws hold, so R/I is a ring.

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

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

\r\n", "\r\n", "Let K be a field or skew field, and suppose that there is a nontrivial ideal I of K. Then there is a nonzero element x in I, \r\n", "and hence x^-1 exists in K. Thus\r\n", "

1 = x·x^-1 ∈ I·K ⊆ I.

\r\n", "So the multiplicative identity 1 is contained in I. But then,\r\n", "

K = 1·K ⊆ I·K ⊆ I.

\r\n", "Hence, I = K, so the only ideals of K are the trivial ideals.

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

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

\r\n", "\r\n", "Since I^* is an intersection of subrings of R, by Proposition 10.2 I^* is a subring of R. Thus, we only need to \r\n", "check that I^*·R and R·I^* are contained in I^*.

\r\n", "\r\n", "Suppose that x is an element of I^*. Then x is in each I ∈ L, and so x·R \r\n", "and R·x are subsets of each I in the collection. Thus, x·R and R·x will both be \r\n", "subsets of I^*. Since this result is true for every x in I^*, we have that I^*·R \r\n", "and R·I^* are both subsets of I^*. Therefore, I^* is an ideal.

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

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

\r\n", "\r\n", "If x² = 0, we can let k = n, so that k will be positive \r\n", "and k x = 0 = x². If x² is not zero, then since x generates the additive group, there is a k such \r\n", "that x² = k x with 0 < k < n.

\r\n", "\r\n", "Now the natural mapping is one that sends ƒ(a·x) = k·a mod (k n). This is obviously one-to-one \r\n", "and onto, since the value of a ranges from 0 to n − 1. To check that this is an isomorphism, note that\r\n", "

ƒ(a·x + b·x) = ƒ((a + b)·x) = \r\n", "k·(a + b) mod (k n) = (k·a mod (k n) + \r\n", "k·b mod (k n)) mod (k n) = \r\n", "ƒ(a·x) + ƒ(b·x).

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

ƒ((a·x)·(b·x)) = \r\n", "ƒ(a·b·x²) = ƒ(a·b·k·x) =\r\n", "k·a·b·k mod (k n) = \r\n", "((k·a mod (k n))·(k·b mod (k n))) = \r\n", "ƒ(a·x)·ƒ(b·x).

\r\n", "Therefore, ƒ is an isomorphism, and R ≈ k Z_{k n}.

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

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

\r\n", "\r\n", "Suppose that gcd(q, n) is not 1. Then there is a prime number p that divides neither f nor \r\n", "ⁿ⁄_d , yet divides n. Thus, p must divide d.

\r\n", "\r\n", "Now f·p will be coprine to ⁿ⁄_d since both f and p are. Also, since f is \r\n", "not a multiple of p while d is, f·p will be a divisor of d. But we defined f to be the largest factor \r\n", "of d coprime to ⁿ⁄_d . This contradiction shows that gcd(q, n) = 1.

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

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

\r\n", "\r\n", "The greatest common divisor theorem (0.4) would give us values for u and v, but there would be no way to guarantee that u would be coprime \r\n", "to y.

\r\n", "\r\n", "Let k = gcd(x, y). Then ^x⁄_k and ^y⁄_k are coprime, so \r\n", "^x⁄_k has an multiplicative inverse in Z_(y/k), say n. That is,\r\n", "

^x⁄_k ·n ≡ 1 (mod ^y⁄_k ).

\r\n", "Let f be the largest divisor of k that is coprime to ^y⁄_k . By the Chinese remainder theorem (0.7), there is \r\n", "a number u such that\r\n", "

u ≡ n (mod ^y⁄_k )

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

u ≡ 1 (mod f).

\r\n", "Since n is coprime to ^y⁄_k , u is coprime to ^y⁄_k . Also, \r\n", "u is coprime to f, so by Lemma 10.1 u is coprime to y. Also,\r\n", "

u·^x⁄_k ≡ 1 (mod ^y⁄_k )

\r\n", "so there is a v such that\r\n", "

u·^x⁄_k + v·^y⁄_k = \r\n", "1.

\r\n", "Multiplying both sides by k gives us\r\n", "

u·x + v·y = k = gcd(x, y).

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

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

\r\n", "\r\n", "Since k = gcd(x, n), by Lemma 10.2 we can find integers u and v such that \r\n", "u·x + v·n = k, where u is coprime to n. We now define a mapping ƒ from \r\n", "k Z_{k n} to x Z_{x n} as follows:\r\n", "

ƒ(k·w mod (k n)) = \r\n", "u x w mod (x n).

\r\n", "Note that this is well defined, since if k·w is equivalent to k·p (mod k n), then \r\n", "

w ≡ p (mod n) ⟹ x w ≡ x p \r\n", "(mod x n) ⟹ u x w ≡ u x p \r\n", "(mod x n).

\r\n", "Next we need to show that ƒ is a homomorphism from k Z_{k n} to x Z_{x n}. If a = k·w \r\n", "(mod k n) and b = k·z (mod k n), then \r\n", "

ƒ(a + b) = ƒ((k·w + k·z) mod (k n)) = \r\n", "u·(x·w + x·z) mod (x n) = \r\n", "(u·x·w + u·x·z) mod (x n) = ƒ(a) + \r\n", "ƒ(b),

\r\n", "

ƒ(a·b) = ƒ((k·w·k·z) \r\n", "mod (k n)) = \r\n", "(u·x·w·k·z) mod (x n) = \r\n", "(u·x·w·(u·x + v·n)·z) mod (x n)
=\r\n", "(u·x·w·u·x·z + \r\n", "u·x·w·v·n·z) mod (x n) = \r\n", "(u·x·w)·(u·x·z) mod (x n) = \r\n", "ƒ(a)·ƒ(b).

\r\n", "So ƒ is indeed a homomorphism from k Z_{k n} to x Z_{x n}.

\r\n", "\r\n", "Since u is coprime to n, u has an inverse, u^-1 (mod n). Then we see that ƒ is onto, since any \r\n", "element x·a (mod x n) in x Z_{x n} can be obtained by taking\r\n", "

ƒ(k·a·u^-1 mod (k n) ) = \r\n", "(u·x·a·u^-1) mod (x n) = x·a mod (x n).

\r\n", "Finally, both x Z_{x n} and k Z_{k n} contain n elements, so by the pigeonhole principle ƒ must be a \r\n", "one-to-one function. Thus, ƒ is an isomorphism, and\r\n", "

x Z_{x n} ≈ k Z_{k n}.

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

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

\r\n", "\r\n", "By Proposition 10.7 every cyclic ring of order n is isomorphic to k Z_{k n} for some value of k. By the cyclic ring theorem, we see \r\n", "that this is isomorphic to d Z_{d n}, where d = gcd(k, n). Hence d is a divisor \r\n", "of n. We need \r\n", "to show that \r\n", "two different rings of this form are non-isomorphic. Consider the rings A = d Z_{d n} and \r\n", "B = f Z_{f n}, where \r\n", "d and f are different divisors of n. Perhaps the easiest way to show that these are different is to count the number of elements in A \r\n", "and B that can appear in the multiplication tables. The elements that can appear in the table for A are\r\n", "

d², 2 d², 3 d², … n·d = 0.

\r\n", "while the elements appearing in the multiplication table of B are\r\n", "

f², 2 f², 3 f², … n·f = 0.

\r\n", "Thus, there are ⁿ⁄_d such elements of A, and ⁿ⁄_f elements of \r\n", "B. \r\n", "Since d and f are different, we see that the rings A and B are not isomorphic. Therefore, there is a one-to-one correspondance between \r\n", "the factors of n and the cyclic rings of order n.

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

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

\r\n", "\r\n", "Suppose S is a subring of A. We will use Proposition 10.1 to show that ƒ(S) is a subring of B. The element \r\n", "ƒ(0) = 0 is in ƒ(S), so ƒ(S) is non-empty. If u and v are two elements of \r\n", "ƒ(S), then there exist elements x and y in S such that\r\n", "

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

\r\n", "But x·y and x − y are also in S, and so\r\n", "

ƒ(x·y) = ƒ(x)·ƒ(y) = \r\n", "u·v and ƒ(x − y) = ƒ(x) − ƒ(y) = \r\n", "u − v

\r\n", "must be in ƒ(S). Thus, by Proposition 10.1, ƒ(S) is a subring of B.

\r\n", "\r\n", "Now suppose that T is a subring of B. Since 0 is contained in ƒ⁻¹(T), we have that \r\n", "ƒ⁻¹(T) is non-empty. If x and y are two elements of ƒ⁻¹(T), then \r\n", "ƒ(x) and ƒ(y) will be two elements of T. Thus,\r\n", "

ƒ(x·y) = \r\n", "ƒ(x)·ƒ(y) and ƒ(x − y) = \r\n", "ƒ(x) − ƒ(y)

\r\n", "would be elements of T. Hence, x·y and x − y are in ƒ⁻¹(T). Thus, \r\n", "by Proposition 10.1, ƒ⁻¹(T) is a subring of A.

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

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

\r\n", "\r\n", "Suppose that x is in the kernel of ƒ, and y is any other element of A. Then \r\n", "

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

\r\n", "Hence, x·y and y·x are in the kernel of ƒ, so the kernel is an ideal of A.

\r\n", "\r\n", "If ƒ is injective, then ƒ⁻¹(0) can only contain one element, which must be 0. On the other hand, \r\n", "if ƒ⁻¹(0) = {0}, then\r\n", "

ƒ(x) = ƒ(y) ⟹ ƒ(x) − ƒ(y) = \r\n", "0 ⟹ ƒ(x − y) = 0 ⟹ x − y = 0 ⟹ x = y.

\r\n", "Therefore, ƒ is injective if, and only if, Ker(ƒ) = {0}.

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

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

\r\n", "\r\n", "It is clear that the rule i(x) = x + I defines a surjective mapping i from R to R/I, and that \r\n", "Ker(i) = I. We need only to check that i(x) is a homomorphism.

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

i(x + y) = (x + y) + I = (x + I) + (y + I) = \r\n", "i(x) + i(y)

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

i(x·y) = x·y + I = \r\n", "(x + I)·(y + I) = i(x)·i(y),

\r\n", "we see that i(x) is indeed a surjective ring homomorphism.

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

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

\r\n", "\r\n", "The diagram actually helps us determine how ϕ needs to be defined. For each coset (x + I) in R/I, we need to have\r\n", "

ϕ(x + I) = ƒ(x)

\r\n", "in order for the diagram to commute. To prove that this rule defines a mapping, we need to show that this is well defined. That is, if \r\n", "x + I = y + I, it needs to be true that ƒ(x) = ƒ(y), or else there would be a contradiction in the \r\n", "definition of ϕ. But\r\n", "

x + I = y + I ⟺ x − y ∈ \r\n", "I ⟺ ƒ(x − y) = 0 ⟺ ƒ(x) = \r\n", "ƒ(y) ⟺ ϕ(x + I) = ϕ(y + I).

\r\n", "So we see that the definition of ϕ will not produce any such contradictions.

\r\n", "\r\n", "To show that ϕ is a homomorphism, we have that\r\n", "

ϕ((x + I) + (y + I)) = ϕ(x + y + I) = \r\n", "ƒ(x + y) = ƒ(x) + ƒ(y) = \r\n", "ϕ(x + I) + ϕ(y + I),

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

ϕ((x + I)·(y + I)) = ϕ(x·y + I) = \r\n", "ƒ(x·y) = ƒ(x)·ƒ(y) = \r\n", "ϕ(x + I)·ϕ(y + I),

\r\n", "So ϕ is a homomorphism from R/I to H. It is apparent that this homomorphism is onto, and\r\n", "

ϕ(x + I) = 0 ⟹ ƒ(x) = 0 ⟹ x ∈ \r\n", "I ⟹ x + I = I.

\r\n", "So the kernel of ϕ is {I}, the zero element of R/I. \r\n", "Thus, ϕ is an isomorphism from R/I onto H, so R/I ≈ H. Since the mapping ϕ \r\n", "was defined so that the diagram commutes, the theorem is proved.

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

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

Sage Interactive Problems

\r\n", "\r\n", "
\r\n", "§10.1 #19)
\r\n", "Find all of the subrings of the ring of order 8:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[a, b],[0, 0]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.1 #20)
\r\n", "Find all of the subrings of the ring of order 8:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[2*a, 0],[2*a, 2*a]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.2 #21)
\r\n", "Which of the subrings of the ring of order 8, found in Problem 19 of §10.1 are ideals?\r\n", "The ring is given as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[a, b],[0, 0]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.2 #22)
\r\n", "Which of the subrings of the ring of order 8, found in Problem 20 of §10.1 are ideals?\r\n", "The ring is given as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[2*a, 0],[2*a, 2*a]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.3 #19)
\r\n", "Load the rings Z₁₂ and Z₆ into Sage simultaneously with the commands:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z12 = ZRing(12)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z6 = ZRing(6)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Show that I = {0, 6} is an ideal of Z₁₂, and display addition and multiplication tables of the \r\n", "quotient Z₁₂/I, showing that Z₁₂/I is isomorphic to Z₆.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.3 #20)
\r\n", "Use Sage to find the eight non-isomorphic non-cyclic rings of order 4. (Hint: The additive group must be isomorphic to Z₈^*,\r\n", "so the ring is defined by:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([2,2],[[???,???],[???,???]])\r\n", "CheckRing()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Fill in each ??? with a member of {0, a, b, a + b} to see whether a ring is formed. Is there a faster way than \r\n", "trying all 4⁴ = 256 combinations?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.3 #21)
\r\n", "Use Sage to display the multiplication tables of all rings of order 6.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.4 #18)
\r\n", "The ring of Example 10.11,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[a, b],[2*a, 0]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "also has an ideal I₂ = {0, 2 a + b}. Define a homomorphism from the ring R to R/I₂.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.4 #19)
\r\n", "The ring of Example 10.11,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[a, b],[2*a, 0]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "also has an ideal I₃ = {0, b, 2 a, 2 a + b}. Define a \r\n", "homomorphism from the ring R to R/I₃.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§10.4 #20)
\r\n", "Use Sage to find a non-trivial homomorphism from the ring of Example 10.11,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitRing(\"a\", \"b\")\r\n", "DefineRing([4, 2],[[a, b],[2*a, 0]])\r\n", "R = ListRing(); R" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "to itself, which is not an automorphism.
" ] }, { "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	rings	n	rings
1	1	17	2
2	2	18	22
3	2	19	2
4	11	20	22
5	2	21	4
6	4	22	4
7	2	23	2
8	52	24	104
9	11	25	11
10	4	26	4
11	2	27	59
12	22	28	22
13	2	29	2
14	4	30	8
15	4	31	2
16	390	32	???

n	rings	n	rings
1	1	17	2
2	2	18	22
3	2	19	2
4	11	20	22
5	2	21	4
6	4	22	4
7	2	23	2
8	52	24	104
9	11	25	11
10	4	26	4
11	2	27	59
12	22	28	22
13	2	29	2
14	4	30	8
15	4	31	2
16	390	32	???

n	rings	n	rings
1	1	17	2
2	2	18	22
3	2	19	2
4	11	20	22
5	2	21	4
6	4	22	4
7	2	23	2
8	52	24	104
9	11	25	11
10	4	26	4
11	2	27	59
12	22	28	22
13	2	29	2
14	4	30	8
15	4	31	2
16	390	32	???