Mathematics and Algorithms for Computer AlgebraPart 1c 1992 Dr Francis J. Wright – CBPF, Rio de JaneiroJuly 9, 20032a: Introduction to Abstract Algebra(continued)1 Ideals and quotient rings1.1 Quotient algebrasHomomorphic images provide simpler models of algebras, and quotient al-gebras provide a technique for constructing homomorphic images. The quo-tienting is by a congruence relation.Definition 1 A congruence relation E on an Ω-algebra A is an equivalencerelation on A such that for any operation ω ∈ Ω of arity naiE bifor i = 1, . . . , n ⇒ ω(a1, . . . , an) E ω(b1, . . . , bn).That is, if the operands of any operator are equivalent then so are thecorresponding values.Example: Equivalence mod m on Z generalizes immediately to congru-ence mod m on an arbitrary commutative ring R, thus:a ≡mb ⇐⇒ a − b = km ⇐⇒ m |(a − b), a, b, k, m ∈ R.Theorem 1 (Quotient algebras) Let A be an Ω-algebra and E a congru-ence relation on A. Then:1. the quotient set A/E is an Ω-algebra if ω ∈ Ω is defined on A/E byω([a1], . . . , [an]) = [ω(a1, . . . , an)](i.e. ω : A/E → A/E maps equivalence classes to equivalence classes);12. A/E is a homomorphic image of A under the natural mapν : a 7→ [a].Hence we have a source of homomorphic images. But do all homomorphicimages of algebras have this form? Essentially, yes, as follows.Lemma 2 Let φ : A → A0be a morphism of Ω-algebras. Then the kernelrelation Eφ, defined bya Eφb ⇐⇒ φ(a) = φ(b),is a congruence relation on A.Theorem 3 (Universal Isomorphism Theorem) Let A and A0be Ω-algebras, with A0a homomorphic image of A under φ : A → A0. ThenA0∼=A/Eφ, where ψ : [a] 7→ φ(a) is an isomorphism A/Eφ→ A0, thusAA0A/Eφ?*-φν :a 7→ [a]ψ : [a] 7→ φ(a)[This is essentially the Decomposition Theorem for Functions applied toalgebras instead of sets.]1.2 IdealsLet R be a ring. Then all homomorphic images of R are given up to isom or-phism by quotient rings R/E for some congruence relation E on R. Idealsprovide congruence relations.Definition 2 An ideal I in a ring R is a nonempty subset of R such that:1. a, b ∈ I ⇒ a −b ∈ I;2. a ∈ I, r ∈ R ⇒ ar, ra ∈ I.Requirement (1) makes I an additive subgroup of R. However:Remark A proper ideal I ⊂ R is not a subring because it does not contain1R. If 1R∈ I then I = R.2The equivalence relation EIinduced by I is defined bya EIb ⇐⇒ a − b ∈ I.This is also written as a ≡ b (mod I) (“a is congruent to b mod I”).1.2.1 Principal idealsIf R is a commutative ring and m ∈ R then(m) = {km | k ∈ R}is the smallest ideal of R containing m, called the principal ideal generatedby m (principal because it is generated by a single element).Examples: (2) ⊂ Z is the principal ideal of even integers, 63 1; (x) ⊂ R[x]is the principal ideal of all polynomials containing x as a factor, i.e. withzero constant term, 63 1.The equivalence relation a E(m)b ⇐⇒ a − b ∈ (m) induced by (m) isthe same as congruence mod m, ≡m, defined above, and is normally written“mod m” rather than “mod (m)”.1.2.2 Ideal generatorsMore generally, let a1, a2, . . . , an∈ R, a commutative ring. Then(a1, a2, . . . , an) = {Pni=1riai| ri∈ R}is the smallest ideal of R containing {ai}ni=1, called the ideal generated by{ai}ni=1. (It is principal iff ∃b ∈ R such that (a1, a2, . . . , an) = (b).)Theorem 4 Let R be a ring and I an ideal in R. Then the equivalencerelation EIinduced by I (a EIb ⇐⇒ a −b ∈ I) is a congruence relation onR.Hence ideals generate homomorphic images via their equivalence relations.1.3 Quotient ringsFirst we need a notion from group theory.Definition 3 For any element a of a ring R regarded as an additive groupand any additive subgroup I, the (left) coset of I by a is defined to bea + I = {a + i | i ∈ I}.3Since an additive group is commutative, the right coset I + a = a + I.Denote by R/I (“R mod I”) the set of all cosets of I by elements of R:R/I = {a + I | a ∈ R}.Because the coset a + I is the same as the equivalence class [a]EI, R/I andR/EIare just different notations for the same set.Theorem 5 (Quotient rings) Let I be an ideal in a ring R. Then1. R/I = R/EI= {a + I | a ∈ R}, the set of all additive cosets of I inR, is a quotient ring under the following “mod I” operations:(a + I) + (b + I) = (a + b) + I,−(a + I) = −a + I,0R/I= 0R+ I = I,(a + I)(b + I) = ab + I,1R/I= 1R+ I;2. R/I is a homomorphic image of R under the natural map ν : a 7→ a+I;3. R/I is a ring (commutative if R is).Let us consider some examples.1.3.1 The quotient ring Z/(m)This is identical to Z/≡m, and each element a + (m) has a unique represen-tative rm(a) in Zm.1.3.2 The quotient ring R[x]/(m(x))Let m(x) be a polynomial in R[x], R commutative (and assume deg m(x) >0). Then (m(x)) is an ideal in R[x], and by the quotient ring theoremR[x]/(m(x)) = {a(x) + (m(x)) | a(x) ∈ R[x]}is a ring – the “quotient ring of polynomials mod m(x)” – and a homomor-phic image of R[x] under the (natural) mapa(x) 7→ a(x) + (m(x)).4Moreover, R[x]/(m(x)) and R[x]/≡m(x)are the same sets and the coseta(x) + (m(x)) ∈ R[x]/(m(x)) is the equivalence class [a(x)] ∈ R[x]/≡m(x).Each coset or equivalence class has a unique representative having degree< deg m(x), namely rm(x)(a(x)), because:-Theorem 61. For any a(x) + (m(x)) ∈ R[x]/(m(x)),a(x) + (m(x)) = rm(x)(a(x) + (m(x))).2. If deg a(x), deg b(x) < deg m(x) thena(x) 6= b(x) ⇒ a(x) + (m(x)) 6= b(x) + (m(x)).Corollary 7 If the number of elements in the set R, denoted |R|, is k anddeg m(x) = n, then|R[x]/(m(x))| = kn(whereas |R[x]| is infinite because there is no limit on the degrees of thepolynomials in R[x]).1.3.3 The quotient ring R[[x]]/(xm)For fixed positive m,a(x) ≡xmb(x) ⇐⇒ a(x) − b(x) ∈ (xm)⇐⇒ ai= bi(i = 0, . . . , m − 1)and each element has a unique polynomial representative having degree < m.1.4 Principal ideal domainsA principal ideal domain (PID) is an integral domain D in which every idealI is principal, i.e. I = (a) = {ra | r ∈ D} for some a ∈ D.Examples: Z, F [x] and F [[x]] are PIDs, but F [x, y] is not, because (x, y)is not principal. More generally:Theorem 8 A Euclidean domain is a PID.5Proof Let D be a Euclidean domain with degree function d, and let I bean ideal in D. If I = {0} then I is the principal ideal (0), so assume I 6= {0}.Let m 6= 0 be an element of I having minimum degree; then we claim thatI = (m). (m) ⊆ I