Daily Calendar - Math 3306 (20505)
What I hear, I forget; what I see, I remember; what I do, I understand.
|
Session |
Date |
Read & Study Section |
Discussion Topics |
Practice HW Problems |
Other Info |
| 29 | 5 - 10 |
Final Exam Wednesday, May 10, 2:30 pm - 4:55 pm |
Some students are organizing a study group for the final exam. It will be Tuesday, May 9, starting at 9 a.m. in room S735. | ||
| 28 | 5 - 1 |
Section 18 Given two groups of the same order, a natural question to ask is if
they are isomorphic. The investigation begins by comparing the group properties
of each given group. For example, consider the groups U5
, U10 and U12
, each of which has order 4: Which pairs of these, if any, are isomorphic groups
and which are not? Section 24 By extending the algebraic structure of a group to two operations, we are better able to study the important properties of the integers with addition and multiplication. A ring is a set with two operations, denoted addition and multiplication, such that (1) the set with addition is an Abelian group; (2) multiplication is associative; (3) multiplication left distributes and right distributes over addition. See the details on page 120. You should be familiar with the definition of a ring and the specific examples given in section 24. |
See below |
Reminder: Writing Projects are due by 5 p.m. Wednesday, May 3 |
|
| 27 | 4 - 26 | 18 |
If the modulo bases are pairwise relatively prime, then a system containing 3 or
more linear congruences has a solution. A strategy to find the solution is to
reduce them one pair at a time by using rule (4) described in the previous
session. Section 18 A mapping between two groups is a homomorphism if it preserves the operation: study the definition on page 96. A mapping between two groups that is one-to-one, onto and a homomorphism is called an isomorphism: study the definition on page 94. "Isomorphic groups are essentially the same but for labeling." This means isomorphic groups have the same group properties: if one is Abelian, so is the other (theorem 18.1); the identity element of one is mapped to the identity element of the other; ..., see theorem 18.2. |
Section 20 # 18.2, 18.3, 18.6 |
|
| 26 | 4 - 24 |
class notes 60 |
Some related properties. Let a and b be integers, and n be a positive integer. (1) There exist integers x and y so ax+by=gcd(a,b). (2) If gcd(a,n)=1, then ax = b mod n has a solution, that is, a has a multiplicative inverse modulo n. (3) ax = b mod n has a solution iff gcd(a,n) | b. (4) The system x = a mod n and x = b mod m has a solution iff a = b mod [gcd(m,n)]. Moreover, if the system has a solution, then it has a solution of the form x = c mod[lcm(m,n)]. (5) If m and n are relatively prime, that is, gcd(m,n)=1, then the system x = a mod n and x = b mod m has a solution. Applications include the Chinese Remainder Theorem and the RSA public key encryption system. | (1) Find all x: 12x = 7 mod 25 [hint: (12)((23)=276]; (2) Solve the system x = 7 (mod 8) and x = 11 (mod 12) | |
| 25 | 4 - 19 | Test 2 (Sections 9, 10, 11, 14, 15, 16, 17) | |||
| 24 | 4 - 17 | Problems related to test 2 were discussed. | See below. | Please e-mail me your writing project topic for approval. | |
| 23 | 4 - 12 | 17 | Section 17 The number of distinct right cosets of a subgroup H of G is denoted [G:H], page 89, and is called the index of H in G. By Lagrange's theorem, [G:H] = |G| / |H|. Note that Theorem 17.1 is very useful in determining the orders of subgroups of a cyclic group G of order n: (a) every subgroup of a cyclic group is again cyclic; (b) if the subgroup is generated by ak, then the order of the subgroup is n ÷ gcd(k,n); (c) ak is a generator of G iff gcd(k,n) = 1; (d) for each positive divisor of n, G has exactly one subgroup of that order. Study the examples in this section and those done in class. In the group of integers modulo n, Zn, the set of elements that are relatively prime to n is denoted Un. It can be proved that Un with multiplication is a group. The order of Un is the order of the set of elements that are relatively prime to n , and this value is defined as φ(n). | See below. | Click here for the details on your writing project. |
| 22 | 4 - 10 |
16 17 |
Section 16 Each member of the class received a handout on practicing with
cosets. Note lemma 16.2: every coset of a finite subgroup has the same
cardinality as the subgroup. This leads to the important theorem: Section 17 Lagrange's theorem says that the order of a subgroup is a divisor of the order of the group, in the finite case. This theorem has many consequences/corollaries: (1) the order of any element of a finite group is a divisor of the order of the group; (2) when an element of a finite group is raised to the power of the group, you get the identity; (3) a group of prime order has no subgroups except for {e} and G; (4) every group of prime order is cyclic, generated by any one of its nonidentity elements. Study section 17. |
Section 17 # 17.1, 17.3, 17.7, 17.9, 17.11, 17.13 |
|
| 21 | 4 - 5 | 16 | Let n be a positive integer: (1) a = b mod n iff n | (a-b) so (a-b) is a multiple of n; (2) the subgroup generated by n is <n> = { kn | kÎZ } the set of all multiples of n; (3) Consequently, a = b mod n iff (a-b) Î <n>. Congruence modulo n can be generalized to any group as follows: Let G be a group and H a subgroup. Define a ~ b iff ab-1ÎH . Then ~ is an equivalence relation - see theorem 16.1, page 86. If aÎG, the equivalence class of a is the set Ha called the right coset of H containing a. Study section 16, especially the examples. |
Section 16 # 16.1, 16.2, 16.5, 16.6, 16.13, 16.14 |
|
| 20 | 4 - 3 |
14 15 |
Class will begin with Quiz 2 (section 11) Section 14 By theorem 14.3, at = e if and only if n | t where n is the order of a. Study the examples in section 14. Section 15 If A and B are groups, then AxB is a group with the operation defined componentwise; the group AxB is called the direct product of A and B. Note the identity is (eA, eB) and the inverse of (a,b) is (a-1,b-1). Also, if A and B are finite then so is AxB with |AxB| = |A| |B|. Study example 15.4. |
Section 15 # 15.7, 15.9, 15.11, 15.17, 15.19, 15.21 |
Turn-in HW 6 # 14.3, 14.5, 14.7(a,b), 14.11, 14.21, 15.9, 15.21 Justify your answers Due Monday, April 10 |
| 19 | 3 - 29 | 14 | In a multiplicative group, all integral powers of group elements are defined - see page 76. In an additive group, all integral multiples of group elements are defined - see page 77. If G is a group and a is an element of G, then the set of all integral powers of a is a subgroup of G, see Theorem 14.2, page 77; it is denoted <a>. This group is called the cyclic subgroup generated by a. Study Theorem 14.3, page 78. As a corollary to this theorem, in a finite group, <a> has finite order; the order of this subgroup is the smallest positive integer n such that an=e; the distinct elements in the subgroup are <a>={e,a,a2, ...,an-1}. The integer n is also called the order of a. A handout was given to each student in class to confirm the results of theorem 14.3 in S3 and in Z6. If G = <a> then G is called a cyclic group. Note that the group of integers Z is cyclic with Z = <1> and Z = <-1>. Study the terminology and examples in section 14. | See below. | |
| 18 | 3 - 27 |
11 14 |
Tips on proofs: (1) For a universally quantified statement such as
"for all a in S, the following is true", begin the proof with
"let
a be an element in S ....."(2) For an implication "if
p, then q", begin the proof with "assume the hypothesis p is true ....." Section 10 The set of nonzero elements in Zn , denoted Zn#, together with the operation 5 may form a group. See example 11.4, dealing with Z5#, and example 11.5, dealing with Z6# , on page 64. Section 14 The properties studied in this section are true for every group. This means we must generalize: the group operation is referred to as multiplication; the identity element is denoted by e; and the inverse element of an element a is denoted by a-1. Note the generalized associative law on page 75. By theorem 14.1, in every group, there is a left and right cancellation law; the inverse of a-1 is a; the inverse of a product ab is the product of the inverses in reverse order, b-1a-1. Note as a consequences of theorem 14.1 that for a finite group, each element appears exactly once in each row and column of the Cayley table. |
Section 14 # 14.1 - 14.17 odd, 14.21, 14.27 |
|
| 17 | 3 - 22 |
10 11 |
Section 10 Remember how to check division: when you divide b into
a, you get a quotient q and a remainder r so that a
= bq + r, 0<r<b "the remainder is
less than the divisor". Intuitively, this is the
essence of the Division Algorithm on page 59. An important
consequence of the division algorithm is
(Theorem 10.2) that each integer a is congruent modulo n
to precisely one of the integers 0, 1, ..., n-1. Hence {
0, 1, ..., n-1 } is a complete set of equivalence class
representatives for the relation "congruence modulo n". Section 11 The set of equivalence classes { [0], [1], ... [n-1] }, denoted Zn , together with the operation Å form an Abelian group, for each positive integer n. This group is called the group of integers modulo n: what properties are satisfied by a group? which element is the identity of Zn ? which element is the inverse of [a] in Zn ? Note that the order of the group Zn is n, and consequently there is a group of order n for each positive integer n. Note however that Zn together with the operation 5 does not form a group; explain why. The set of nonzero elements in Zn is denoted Zn#. Study the examples in section 11. |
Section 11 # 11.1 - 11.15 odd |
Turn-in HW 5 # 10.5, 10.8, 10.12, 10.17, 10.18 Justify your answers Due Wednesday, March 29
|
| 16 | 3 - 20 | 10 | Your first goal for this section is to study and become familiar with the special terminology and notation. We say integer n divides integer m, written n | m, if m = nq for some integer q. Some useful properties of divisibility are: (1) If n | m then n | (-m); (2) If n | a and n | b, then n | (a+b). We say integers a and b are congruent modulo n, written a = b mod n, if n | (a-b) where n is a positive integer. Note: (1) congruence modulo n defines a relation on the set of integers; (2) congruence modulo n is reflexive, symmetric and transitive, that is, congruence modulo n is an equivalence relation on the set of integers - see theorem 10.1, page 58. For a given positive integer n, there are n distinct equivalence classes: [0], [1], [2], ..., [n-1], see theorem 10.2 on page 60. It is possible to define an operation on the set of equivalence classes so that the result is a group - this is studied in section 11. |
Section 10 # 10.1 - 10.19 odd, 10.23, 10.25 |
|
| 15 | 3 - 8 | 9 |
Note: In a group table, each element of the group appears once in each row
and each column of the table. See problems 7 and 10 on test 1. Let S be a nonempty set and ~ be an equivalence relation on S. Prove: If b is in [a], then [b]=[a]. The first part of the proof was outlined in class; you just need to complete the second part. A complete set of equivalence representatives is a subset of S that contains precisely one element from each distinct equivalence class. See example 9.6, page 55. Study theorem 9.1: there is a one-to-one correspondence between the equivalence relations on a set and the partitions of the set. This theorem is useful to determine the number of equivalence relations on a finite set S. |
See below. |
Turn-in HW 4 # 9.2, 9.4, 9.6, 9.8, 9.13 Due Wednesday, March 22 |
| 14 | 3 - 6 | 9 | Let S be a set. A relation on S is a subset of the cartesian product SxS, that is, a relation on a set S consists of order pairs from SxS. Notation: we will write a ~ b to mean (a,b) is an element of a relation on S. A relation on S is said to be an equivalence relation if: (1) the relation satisfies the reflexive property; (2) the relation satisfies the symmetric property; (3) the relation satisfies the transitive property. See page 52 for the details of each of these properties. For any nonempty set, the equality relation "=" is an equivalence relation. The equivalence class of an element a in S, denoted [a], contains all elements of S that are related to a. Note that (1) a an element of [a]; (2) if b is in [a], then [b]=[a]; (3) every element is contained in the union of all the distinct equivalence classes; (4) every pair of distinct equivalences has no element in common. Therefore, the set of equivalence classes forms a partition of S - see page 53. Study the examples in section 9. |
Section 9 # 9.1 - 9.9 all, 9.15, 9.19(b,c), 9.21, 9.22 |
|
| 13 | 3 - 1 | Test 1 (Sections 1, 2, 3, 4, 5, 6, 7) | |||
| 12 | 2 - 27 |
6 7 |
Section 6 Note that problem 6.14 can be rewritten to be a question about the
number of mappings from a set S to a set T, both of which are finite
sets. Section 7 In the permutation group Sn , the elements are permutations (one-to-one and onto mappings) from {1, 2, ..., n} to {1, 2, ..., n}, and the operation is composition. Let n>2 and let H be the subset of Sn that contains the even permutations. Note: 1st, the identity mapping is an even permutation since ( 1 ) = (1 2)(1 2) and so the identity (1) is in H; 2nd, a product of two even permutations is again even; 3rd, the inverse of an even permutation is again even. Therefore, H is a subgroup of the group Sn by the 3-Step-Test-For-Subgroups. This subgroup is denoted by An and is called the Alternating Group of Degree n - study theorem 7.2, page 43. Note that the order of An is (1/2)(n!). Which permutations are the elements of A3 "the even permutations in S3"? See example 7.3, page 42. |
Ms. Nakamura will be holding study sessions for test 1 on Monday and Tuesday from 6 - 8 p.m. in room S735. You do not need to stay for the entire session. | |
| 11 | 2 - 22 |
6 7 |
Section 6 Calculating products of cycles may be done in different ways -
using the two-row form or using cycles. It is your choice as to which method
to use. Given a set S of order n and an operation * on S, how many equations must be checked to show that * is associative? Section 7 Let G be a group with the operation *. Intuitively, a subset H of G is a subgroup if H is also a group. Study the definition of subgroup on page 41. By lemma 7.1: the identity element of a subgroup and the identity element of the group must be the same; the inverse of an element in the subgroup must be the same as the inverse element in the group. To determine if a given subset of a group is a subgroup, we will use Theorem 7.1 "3-Step Test for a Subgroup." Study these three steps and the example on the handout given in class. Study the 1st part of the proof of theorem 7.2 in which the 3-step test for a subgroup is used. |
See below. | Ms. Nakamura will be holding study sessions for test 1 on Thursday, Monday and Tuesday from 6 - 8 p.m. in room S735. You do not need to stay for the entire session. |
| 10 | 2 - 20 | 6 |
Class will begin with Quiz 1 (section 6) Section 4 Problem 4.4 was discussed. Section 6 More properties of the permutation groups Sn : (4) the identity mapping is (1)=(2)=(3)=...=(n-1)=(n); (5) disjoint cycles commute; (6) every cycle can be written as a product of transpositions, where a transposition is a 2-cycle; (7) cycle notation is not unique but it is customary to write the smallest number in a cycle first. So it is true that the following 4-cycles are equal: (1 2 3 4)=(2 3 4 1)=(3 4 1 2)=(4 1 2 3). Try to read ahead through section 7 (subgroups). |
Section 6 # 6.6, 6.14 (a,b) Section 7 # 7.1, 7.2, 7.7, 7.11, 7.13, 7.21, 7.23 and see below. |
|
| 9 | 2 - 15 |
5 6 |
Section 5 In problem 5.2, you can verify that all nonzero rational numbers
with multiplication is a group. Is it true that all rational numbers,
including 0, with multiplication is a group? Note in problem 5.20 that there
is only one possible Cayley table for a group containing two elements. And
the table shows that the operation must be commutative. Therefore, any group
with only two elements is an Abelian group. It is also true that any group
with only one element is an Abelian group. Section 6 Properties of the permutation groups Sn : (1) by theorem 6.2, the order of Sn is n!; (2) by theorem 6.3, Sn is non-Abelian for n>3; (3) for a permutation written in cycle notation, to find the inverse, just reverse the order of the elements, see page 39. |
Section 5 # 5.2, 5.20 and See below. |
|
| 8 | 2 - 13 |
5 6 |
Section 5 Keep reviewing the definition of a group - you should
understand every special term that is used in the definition. If the group
operation is commutative, the group is said to be Abelian. Give an
example of an Abelian group; give an example of a non-Abelian group.
Section 6 The permutation group denoted Sn consists of the set of permutations (invertible mappings) on the set S={1,2,...,n} together with the operation of composition. Remember that a composition is performed from right to left. For which values of n is Sn an Abelian group? a non-Abelian group? Study Theorem 6.3, page 36. A permutation may be written in two-row form, page 35, or in cycle notation, page 37. How do you find the inverse of a permutation that is written in two-row form? In cycle notation? Study page 35. Note that every permutation may be written as a cycle or as a product of cycles. Study example 6.2, page 37. Read ahead: what does it mean to say that two cycles are disjoint? What properties do disjoint cycles have? |
See below. | |
| 7 | 2 - 8 |
5 6 |
HW 2 was returned and some of the problems were discussed. More hints were
given for problem 3.29 - try to complete a proof. Section 5 In practice, you should get in the habit of checking four requirements for a group: For a given set S and given operation *defined on S, (0) Is S closed under the operation? (1) Does the operation * satisfy the associative property? (2) Does S contain an identity element for the operation *? (3) Does each element in S have an inverse element in S? By theorem 5.1, a group has a unique identity element (only one), and each element of a group has a unique inverse (only one). How is the inverse of a denoted? Section 6 Invertible mappings on a set S are also called permutations of S. By theorem 4.1b, the set of all permutations of S together with composition is a group. How many permutations are there on a set with order n? See Theorem 6.2, page 36. When S = {1,2,...,n}, the permutations may be written in a two-row form. Study the examples in section 1.6. |
Section 1.6 6.1 - 6.15 odd |
|
| 6 | 2 - 6 |
4 5 |
Section 4 The proof to theorem 4.1a, page 26, was discussed. Note the
comment in the proof: "As in all proofs, it is important to understand the
justification for each step. Remember the test: Could you explain it
to someone else?" As a result of theorem 4.1b, for any nonempty set S,
the set A of all invertible mappings from S to S
together with the operation of composition satisfies the properties:
(0) set A is closed under composition; (1) composition is
associative; (2) A contains the identity mapping
ι and
ι◦α=α◦ι=α
for each α in A; (3) for each
mapping α in A, α-1
the inverse of
α is also in A, and
α-1 ◦ α = α ◦ α-1
= ι. Because of these four properties, we say set A together
the operation composition is a group. Section 5 Note in the definition of a group that a group consists of a pair of objects: a set and an operation on that set. Carefully study the examples in this section. From memory, you should be able to give a specific example of a set and an operation on that set that form a group; be able to give a specific example of a set and an operation on that set that do not form a group (and explain why). |
Section 1.5 # 5.1 - 5.13 odd, 5.16 |
Turn-in HW 3 Section 1.4 # 4.2, 4.4, 4.10, 4.11 Due Monday, February 13 |
| 5 | 2 - 1 |
3 4 |
HW 1 corrections were discussed. Section 3 If S is a finite set, how many operations can be defined on S? Remember that the domain of an operation on S is the set SxS, and the codomain is the set S. Section 4 If S is a nonempty set, then M(S) is defined as the set of all mappings from S to S. Note that composition is an operation on M(S) since if α and β are in M(S), then β◦α and α◦β are also in M(S). Which special properties of operations does composition have: (a) is composition commutative? (b) is there an identity element for composition? (c) which mappings have inverses? (d) is composition associative? Study section 1.4. |
Section 1.4 # 4.1, 4.3, 4.10 |
Turn-in HW 1 was returned today. Corrections are due by Wednesday, February 8. Help for the course is also available in the CCLC tutoring center from Ms. Nakamura. |
| 4 | 1 - 30 | 3 | Section 3 An operation * on a set S is a mapping from the cross product SxS to S, that is, each ordered pair (a,b) in SxS is mapped to exactly one element of S, denoted a*b. What does it mean to say that: (1) the operation * is associative?(2) the operation * is commutative? (3) e is an identity element for the operation *? (4) b is the inverse of a with respect to the operation *? Study the examples in section 1.3: You should be able to give a specific example that satisfies a given property as well as give a specific example that does not satisfy a given property. An operation on a finite set may be defined by a Cayley Table - study example 3.4 on pages 20-21. Describe a Cayley table that satisfies the commutative property. A handout was given to each student with questions related to section 1.3. |
Section 1.3 # 3.1 - 3.23 odd, 3.24, 3.27, 3.29
|
Turn-in HW 2 Section 1.3 # 3.18, 3.21, 3.23, 3.24, 3.29 Due Monday, February 6 Note: The number of absences that you have in the course will be counted starting today since the official day of record is January 30. |
|
3 |
2 |
Section 1 In Appendix A, you will find the definition of subset and
the definition of set equality. Study the proof of #1.28a on page 15. Section 2 Definition of composition of two mappings; which compositions are one-to-one and which are onto, study theorem 2.1 and its proof on page 17. Definition of an invertible mapping; inverse of a mapping; which mappings are invertible, study theorem 2.2 and its proof on page 18. How do you find a formula for an inverse mapping, see problems 2.9 and 2.10, page 18. |
See below | ||
|
2 |
1 2 |
Section 1 Definition of equal mappings; definition of image of a
set; definition of an onto mapping; definition of a mapping that
is not onto; the number of possible onto mappings between
finite sets. Each member of the class was given a handout to explore the
relationship between the total possible number of mappings and the number of
onto mappings. For next time, read through section 1.2. |
Page 18 # 2.1 - 2.21 odd
And see below |
Turn-in HW #1 Section 1.1 # 1.4, 1.6, 1.20, 1.22, 1.28b Section 1.2 # 2.17, 2.21, 2.27 Due Jan. 30 |
|
|
1 |
1 |
Definition of mapping, domain, codomain, image of an element or of a set; examples of mappings; examples of rules that are not mappings; number of possible mappings from a finite set S to a finite set T; definition of a one-to-one mapping; definition of a mapping that is not one-to-one; examples of mapping that are one-to-one and that are not one-to-one; number of possible one-to-one mappings between finite sets. Study the examples in section 1.1. |
Page 14
# 1.1 - 1.23 odd
|