Modeling Arithmetic, Computation, and LanguagesAlgebraic StructuresSlide 3Slide 4Slide 5Slide 6Slide 7Basic Results About GroupsSlide 9SubgroupsSlide 11Slide 12Isomorphic GroupsSlide 14Slide 15Modeling Arithmetic, Computation, and LanguagesMathematical Structures for Computer ScienceChapter 8Copyright © 2006 W.H. Freeman & Co. MSCS Slides Algebraic StructuresSection 8.1 Algebraic Structures 2Algebraic StructuresDEFINITIONS: PROPERTIES OF BINARY OPERATIONS Let S be a set and let - denote a binary operation on S. (Here - does not necessarily denote multiplication but simply any binary operation.)The operation is associative if(x)(y)(z)[x - (y - z) = (x - y) - z]Associativity allows us to write x - y - z without using parentheses because grouping does not matter.1. The operation is commutative if(x)(y)(x - y = y - x)2. [S, -] has an identity element if(i)( x)(x - i = i - x = x)3. If [S, -] has an identity element i, then each element in S has an inverse with respect to if(x)(x1)(x - x1 = x1 - x = i )Section 8.1 Algebraic Structures 3Algebraic StructuresDEFINITIONS: GROUP, COMMUTATIVEGROUP [S, -] is a group if S is a nonempty set and - is a binary operation on S such that- is associativean identity element exists (in S)each element in S has an inverse (in S) with respect to -A group in which the operation is commutative is called a commutative group.Section 8.1 Algebraic Structures 4Algebraic StructuresFor example, Let R+ denote the positive real numbers and let - denote real-number multiplication, which is a binary operation on R+. Then [R+, -] is a commutative group.Multiplication is associative and commutative.The positive real number 1 serves as an identity becausex - 1 = 1 - x = xEvery positive real number x has an inverse with respect to multiplication, namely the positive real number 1/x, becausex - 1/x = 1/x - x = 1Section 8.1 Algebraic Structures 5Algebraic StructuresA structure called a monoid results from dropping the inverse property in the definition of a group.A semigroup results from dropping the identity property and the inverse property in the definition of a group.Many familiar forms of arithmetic are instances of semigroups, monoids, and groups.Section 8.1 Algebraic Structures 6Algebraic StructuresAn expression of the formanxn + an1xn1 + ... + a0where ai R, i = 0, 1, ... , n, and n N is a polynomial in x with real-number coefficients (or a polynomial in x over R).For each i, ai is the coefficient of xi.If i is the largest integer greater than 0 for which ai 0, the polynomial is of degree i.If no such i exists, the polynomial is of zero degree. Terms with zero coefficients are generally not written.The set of all polynomials in x over is denoted by R[x].Section 8.1 Algebraic Structures 7Algebraic StructuresWe define binary operations of + and - in R[x] to be polynomial addition and multiplication.For polynomials f (x) and g(x) members of R[x], the products f (x) - g(x) and g(x) - f (x) are equal because the coefficients are real numbers, and we can use all the properties of real numbers under multiplication and addition.Similarly, for f (x), g(x), and h(x) members of R[x], ( f (x) * g(x)) - h(x) = f (x) - (g(x) - h(x)).The constant polynomial 1 is an identity because 1 - f (x) = f (x) - 1 = f (x).Thus, [R[x]], - ] is a commutative monoid.It fails to be a group because only the nonzero constant polynomials have inverses.Section 8.1 Algebraic Structures 8Basic Results About GroupsTHEOREM ON THE UNIQUENESS OF THE IDENTITY IN A GROUP In any group (or monoid) [G, -], the identity element i is unique.To prove that the identity element is unique, suppose that i1 and i2 are both identity elements. Then i1 = i1 - i2 = i2.THEOREM ON THE UNIQUENESS OF INVERSES IN A GROUP For each x in a group [G, -], x1 is unique.THEOREM ON THE INVERSE OF A PRODUCTFor x and y members of a group [G, -], (x - y) 1 = y1 - x1.DEFINITION: CANCELLATION LAWS A set S with a binary operation satisfies the right cancellation law if for x, y, z S, x - z = y - z implies x = y. It satisfies the left cancellation law if z - x = z - y implies x = y.Section 8.1 Algebraic Structures 9Basic Results About GroupsTHEOREM ON CANCELLATION IN A GROUPAny group [G, -] satisfies the left and right cancellation laws.THEOREM ON SOLVING LINEAR EQUATIONS IN A GROUP Let a and b be any members of a group [G, -]. Then the linear equations a - x = b and x - a = b have unique solutions in G.If [G, -] is a group where G is finite with n elements, then n is said to be the order of the group, denoted by G. If G is an infinite set, the group is of infinite order.Section 8.1 Algebraic Structures 10SubgroupsDEFINITION: SUBGROUP Let [G, -] be a group and A G. Then [A, -] is a subgroup of [G, -] if [A, -] is itself a group.To test whether [A, -] is a subgroup of [G, -], we can assume the inherited properties of a well-defined operation and associativity and check for the three remaining properties required.THEOREM ON SUBGROUPS For [G, -] a group with identity i and A G, [A, -] is a subgroup of [G, -] if it meets the following three tests: A is closed under -. i A.Every x A has an inverse element in A.Section 8.1 Algebraic Structures 11SubgroupsIf [G, -] is a group with identity i, then it is true that [{i}, -] and [G, -] are subgroups of [G, -].These somewhat trivial subgroups of [G, -] are called improper subgroups. Any other subgroups of [G, -] are proper subgroups.An interesting subgroup can always be found in the symmetric group Sn for n > 1. We know that every member of Sn can be written as a composition of cycles, but it is also true that each cycle can be written as the composition of cycles of length 2, called transpositions. In S7, (5, 1, 7, 2, 3, 6) = (5, 6) ° (5, 3) ° (5, 2) ° (5, 7) ° (5, 1).We classify any permutation as even or odd according to the number of transpositions in any representation of that permutation.Section 8.1 Algebraic Structures 12SubgroupsTHEOREM ON ALTERNATING GROUPS For n N, n > 1, the set An of even permutations determines a subgroup, called the alternating group, of [Sn, °] of order n!/2.There is a relationship between the size of a group and the size of a subgroup. This relationship is stated in Lagrange’s theorem.LAGRANGE’S THEOREM The order of a
View Full Document