STUDENT NOTES SERIES

SMA6014 - Modern Algebra and Geometry
Norashiqin Mohd Idrus Shahrizal Shamsuddin Department of Mathematics, Faculty of Science and Mathematics, Universiti Pendidikan Sultan Idris (Semester 1 Session 2014/2015)

Contents

1 Fundamentals 1.1 History of Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 1.1.2 1.2 1.2.1 1.2.2 1.2.3 1.3 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5 1.4 1.5 1.4.1 1.5.1 1.5.2 1.5.3 1.5.4 1.6 1.6.1 1.6.2 1.6.3 Classical Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Modern Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 1 1 1 2 3 6 7 7 8 8 9 9

Logic and Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Proof by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basic Notion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . Power Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Domain and Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Injective, Surjective and Bijective Functions . . . . . . . . . . . . . . 14 Composite Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Inverse Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 16 GCD and LCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Congruence of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . 17 19 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Properties of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Groups and Subgroups 2.1 2.1.1

Binary Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Properties of Operations . . . . . . . . . . . . . . . . . . . . . . . . . 20 ii

CONTENTS 2.2 2.3

iii

Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 2.3.1 2.3.2 Cayley Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Cancellation Property . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Exponents and Multiples . . . . . . . . . . . . . . . . . . . . . . . . 22 Center of a Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Properties of Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4 2.5 2.6

Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1 Cyclic Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6.1 Properties of Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . 25 27

3 Isomorphism 3.1 3.2

Isomorphisms and Automorphisms . . . . . . . . . . . . . . . . . . . . . . . 27 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.1 Kernel of Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . 30 31

4 Rings and Fields 4.1 4.2 4.3 4.1.1 4.2.1

Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Subrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Zero Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Integral Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 39

5 Permutation Groups 5.1 5.2 5.3 5.1.1

Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Finite Permutation Groups . . . . . . . . . . . . . . . . . . . . . . . 39 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Symmetric Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Cycles and Orbits 5.3.1 5.3.2 Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Transpositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Conjugates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 42

5.4 5.5

Alternating Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4.1 Cayley’ Theorem s

6 Cosets, Normal Subgroups and Quotient Groups 6.1 6.1.1 6.1.2 6.2

Left and Right Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Partitions and Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 The Lagrange’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . 43 s

Normal Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

CONTENTS 6.3 6.4

iv

Quotient Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Fundamental Theorem of Group Homomorphism(FTGH) . . . . . . . . . . 45

Chapter 1 Fundamentals

1.1
1.1.1

History of Algebra
Classical Algebra Algebra - al jebr in Arabic …rst used by Mohammed of Kharizm, who taught mathematics in Baghdad during the ninth century. Meaning “reunion” - method of collecting terms of an equation in order to solve it. Omar Khayyam - science of solving equations Girolamo Cardan, Tartaglia, Ferrari,...

1.1.2

Modern Algebra Algebra as a branch of Mathematics - the study of Algebraic Structures Niels Henrik Abel, Evariste Galois, Arthur Cayley, ...

1.2

Logic and Proof
Statement: A sentence that is either TRUE or FALSE Theorem: A major landmark in the mathematical theory. Proposition: A lesser result. Lemma: A result that is needed to prove a theorem or proposition but not very interesting on its own. Corollary: A result that follows almost immediately from a theorem. Example: A particular case of a theorem or proposition. 1

CHAPTER 1. FUNDAMENTALS

2

Algorithm: An explicit procedure for solving a problem in a …nite number of steps. De…nition: Give a precise meaning to a mathematical term. Proof : A mathematical argument intended to convince that a result is correct. 1.2.1 Logic

De…nition 1.1 (Conjunction, Disjunction and Negation) Let p and q be statements. 1. The statement p AND q; denoted by p ^ q; is called the conjunction of p and q: 2. The statement p OR q; denoted by p _ q; is called the disjunction of p and q: 3. The negation of p is denoted by NOT p or :p: De…nition 1.2 (Conditional Statement) Given two statements p and q; the conditional statement “If p, then q" is denoted by p =) q (read “p implies q"): The statement “If P , then Q" can also be expressed in any of the following ways: p =) q p implies q If p, q q if p p only if q p is su¢ cient for q q is necessary for p The converse of the conditional statement p =) q is q =) p De…nition 1.3 (Biconditional Statement) Given two statements p and q; the biconditional statement “p if and only if Q" is denoted by P () Q, and de…ne it by (P =) Q) ^ (Q =) P ) : The statement “If P , then Q" can also be expressed in any of the following ways: P () Q

CHAPTER 1. FUNDAMENTALS P if and only if Q P i¤ Q If P , Q P is equivalent to Q P is necessary and su¢ cient for Q

3

De…nition 1.4 (Universal Quanti…cation) Let P (x) be a sentence depending on the variable x: The universal quanti…cation of P (x) is the statement: P (x) is true for all values of x; and is denoted by 8x; P (x) : The statement 8x; P (x) can also be expressed in any of the following ways: for all x; P (x) for every x; P (x) for each x; P (x) P (x) ; for all x: De…nition 1.5 (Existential Quanti…cation) Let P (x) be a sentence depending on the variable x: The existential quanti…cation of P (x) is the statement : There exist an x for which P (x) is true, and is denoted by 9x; P (x) : The statement 9x; P (x) could also be expressed in any of the following ways: there is an x for which P (x) for some x; P (x) P (x) ; for some x 1.2.2 Methods of Proof

Mathematics is most probably the most cumulative of subjects; later work nearly always relies on previous theorems. A proof of a theorem is a series of logical deductions, using the assumption of the theorem, the de…nitions of the terms involved, and previous result that have been proven. Most theorems are conditional statements (P =) Q). The statement P is called the assumption or hypothesis of the theorem, and the statement Q is called the conclusion.

CHAPTER 1. FUNDAMENTALS

4

A theorem that is not stated in conditional form is often equivalent to a conditional statement. For instance, the statement \Every integer greater than 1 is a product of primes” is equivalent to \If n is an integer and n > 1; then n is a product of primes” The …rst step in proving a theorem that can be phrased in conditional form is to identify the hypothesis P and the conclusion Q: In order to prove theorem “P =) Q; ” , one assumes that the hypothesis P is true then uses it, together with axioms, de…nitions, and previously proved theorems, to argue that the conclusion Q is necessarily true. Some Tips to Tackle a Proof Understand the de…nitions. Know the technical terms involved in the result. Use previous results. Use previously proved theorems, corollary and lemmas. Try examples. Look for various concrete examples that satisfy the hypothesis. These examples should convince you that the result is true. Draw diagram, pictures, etc. If you can …nd an example that satis…es the hypothesis but does not satisfy the conclusion, then you have found a counterexample, and the result is false. Try standard proof methods. Direct Proof Method (P =) Q) To prove the theorem “P =) Q ” by the direct method, …nd a series of statements P1 ; P2 ; : : : ; Pn and then verify that each of the implications P =) P1 ; P1 =) P2 ; P2 =) P3 ; : : : ; Pn is true. Example 1.1 Prove: If S \ T = S; then S if x 2 S; then x 2 T: T:
1

=) Pn ; Pn =) Q

Proof. Suppose that S \ T = S: To prove that S is a subset of T; we need to show that

Hence, by de…nition of inclusion, S

Let x 2 S: Since S = S \ T; then x 2 S \ T: By de…nition of intersection of sets, x 2 T: T:

CHAPTER 1. FUNDAMENTALS If and Only If Proof Method (P () Q)

5

The result “P if and only if Q ”can be split up into two cases: the “only if ”part P =) Q; and the “if ” part Q =) P; and then each case can be proved separately. Example 1.2 Prove: S \ T = S [ T if and only if S = T Proof. To prove (S \ T = S [ T ) =) (S = T ) ; we need to show that if S T and

T T

implies that x 2 T: So, S

S; then S = T: Suppose that S \ T = S [ T: If x 2 S; then x 2 S [ T = S \ T; which

T: Similarly (by interchanging S and T ), we can show that

S \ T = S \ S = S and S [ T = S [ S = S: Hence, S \ T = S [ T: Contrapositive Proof Method ((~Q) =) (~P ) ) To prove the theorem “P =) Q ” we may prove “~Q =) ~P ” ,

S: Thus, S = T: To prove (S = T ) =) (S \ T = S [ T ) : Suppose that S = T: Then,

Example 1.3 Prove: If x is a real number such that x3 + 7x2 < 9; then x < 1:1: Proof. The contrapositive of the statement that we have to prove is “ If x x3 + 7x2 9: ” Suppose x x3 + 7x2 1:1: Then, (1:1)3 + 7 (1:1)2 = 1:331 + 8:47 = 9:801 9 1:1; then

Proof by Contradiction To prove the theorem “P =) Q ” we may assume that P is true and not Q is true. This , will lead to not Q =) S; where S is a statement known to be false. Conclude that not Q must be false, i.e., Q is true. Example 1.4 Prove that there is no real solution to x2 6x + 10 = 0 6x + 10 = 0:

Proof. Assume that the conclusion is false, i.e, there is a real solution to x2 By completing the square, we get (x But (x 3)2 3)2 + 1 = 0 3)2 + 1

0 for any real number x: So, (x x2

1 = 0; which is a contradiction.

Hence, there is no real solution to

6x + 10 = 0

CHAPTER 1. FUNDAMENTALS Construction Method

6

This method is appropriate for theorems that include a statement of the type “There exists a such-and-such with property so-and-so.” To prove such a statement, we must construct (…nd, build, guess,etc.) an object with desired property.

Counter Examples Note that, although an example is su¢ cient to prove an existence statement, examples can never prove a statement that directly or indirectly involves a universal quanti…er. However, a counterexample is su¢ cient to disprove a statement. Example 1.5 Let x be a real number. Disprove the statement: If x2 9 then x > 3 4:

Solution 1 One counterexample to the statement is obtained by taking x =

1.2.3

Proof by Induction

Assume that for each positive integer n; a statement P (n) is given. If 1. P (1) is a true statement; and, 2. Whenever P (k) is a true statement, then P (k + 1) is also true, then P (n) is a true statement for every n: n (n + 1) for all positive integer n: 2 +n= n (n + 1) ” . 2

Example 1.6 Prove that 1 + 2 +

+n=

Proof. Let P (n) be the statement “1 + 2 + 1 (1 + 1) : So, P (1) is true. 2 +k =

1. P (1) : 1 =

2. Suppose P (k) : 1 + 2 +

k (k + 1) is true. Need to show that: 2 + k + (k + 1) = (k + 1) (k + 2) 2

P (k + 1) : 1 + 2 +

CHAPTER 1. FUNDAMENTALS is also true. So, 1+2+ + k + (k + 1) = = = Hence, P (n) is a true statement for every n: k (k + 1) + (k + 1) 2 k (k + 1) + 2 (k + 1) 2 (k + 1) (k + 2) 2

7

1.3
1.3.1

Sets
Basic Notion A set is an unde…ned term. We can think of a set as a collection of objects, called the elements of the set: A set S is said to be well de…ned if for some object x; then either x is de…nitely in S, denoted by x 2 S; or x is de…nitely not in S; denoted by x 2 S. = A set S with only …nite number of elements is called a …nite set; otherwise S is the notation jSj < 1 to denote that S is a …nite set). called an in…nite set. The number of elements of S is denoted by jSj : (We’ use ll The null set or empty set is the set with no elements, and usually denoted by ;: A set S may be described either by: – listing the elements: S = fx; y; z; : : :g ; or, – giving a characterizing property P (x) of its elements x: S = fx j P (x)g ; and is read “the set of all x such that the statement P (x) about x is true.

Examples of Sets Z = f:::; 3; 1; 0; 1; 2; 3; :::gdenotes the set of all integers Z+ = f1; 2; 3; :::g denotes the set of all natural numbers. na o Q= j a; b 2 Z; and b 6= 0 denotes the set of all rational numbers. b

R denotes the set of all real numbers.

CHAPTER 1. FUNDAMENTALS R+ = fx 2 R j x > 0g denotes the set of all positive real numbers. Rn f0g = fx 2 R j x 6= 0gdenotes the set of all nonzero real numbers. C= a + bi j a; b 2 R;i2 = 1.3.2 Subsets 1 denotes the set of all complex numbers.

8

De…nition 1.6 (Subset) A set A is said to be a subset of a set S, if every element of A is an element of S: We will denote it by A If A S but A 6= S; then we will write A S and say that A is contained in S: S and say that A is properly contained

in S or that A is a proper subset of S:

Theorem 1.1 Let A and B be sets. Then A = B if and only if A 1.3.3 Operations on Sets

B and B

A

Intersection De…nition 1.7 (Intersection) The intersection of two sets A and B is de…ned to be A \ B = fx j x 2 A and x 2 Bg The intersection of the sets A1 ; A2 ; : : : ; An is denoted by \ i2I Ai =

\n

i=1

Ai = A1 \ A2 \ : : : \ An

where I = f1; 2; 3; :::; ng is called the indexing set. De…nition 1.8 (Disjoint Sets) Let A and B be sets. A and B are said to be disjoint if A \ B = ;. Let A1 ; A2 ; : : : ; An be sets. Any two sets Ai ; Aj are said to be mutually disjoint if Ai \ Aj = ; for i; j 2 I; i 6= j Union De…nition 1.9 (Union) The union of two sets A and B is de…ned to be A [ B = fx j x 2 A or x 2 Bg The union of the sets A1 ; A2 ; : : : ; An is denoted by [ i2I Ai =

[n

i=1

Ai = A1 [ A2 [ : : : [ An

CHAPTER 1. FUNDAMENTALS Theorem 1.2 Let A and B be sets. Then the following statements hold: 1. A A [ B and B A[B B

9

2. A \ B Complement

A and A \ B

De…nition 1.10 (Complement) Given two sets A and B; the complement of B with respect to A, denoted by AnB; is the set AnB = fx j x 2 A and x 2 Bg = 1.3.4 Power Sets

De…nition 1.11 (Power Sets) For any set X; the power set of X; denoted by } (X) ; is de…ned to be } (X) = fA j A 1.3.5 Cartesian Products Xg

De…nition 1.12 (Cartesian Product) For any two nonempty sets A and B; the Cartesian product of A and B, denoted by A a 2 A and b 2 B: That is A B = f(a; b) j a 2 A; b 2 Bg B; is the set of all ordered pairs (a; b) of elements

Example 1.7 Let A = fa; bg and B = fx; y; zg : Then, A and B A = f(x; a) ; (x; b) ; (y; a) ; (y; b) ; (z; a) ; (z; b)g B = f(a; x) ; (a; y) ; (a; z) ; (b; x) ; (b; y) ; (b; z)g

Note that if A is a set, then: A A A | A A n times

A = A3 = f(a1 ; a2 ; a3 ) j a1 ; a2 ; a3 2 Ag A = f(a1 ; a2 ; a3 ; : : : ; an ) j a1 ; a2 ; a3 ; : : : ; an 2 Ag }

A = A2 = f(a1 ; a2 ) j a1 ; a2 2 Ag

A {z

CHAPTER 1. FUNDAMENTALS

10

1.4

Relations

De…nition 1.13 (Relation) Let A and B be two nonempty sets. A relation R from A into B is a subset of A relation from A into B: If (a; b) 2 R; we write aRb and say that a has the relation R to b, B of ordered pairs (a; b) of elements a 2 A; b 2 B: Let R be a

or a is related to b. If A = B; then we will say R is a relation on A:

Example 1.8 Let A = f1; 2; 3; 4g and let R be the relation on A de…ned by (a; b) 2 R () a Then, R = f(1; 1) ; (1; 2) ; (1; 3) ; (1; 4) ; (2; 2) ; (2; 3) ; (2; 4) ; (3; 3) ; (3; 4) ; (4; 4)g De…nition 1.14 (Domain, Range) Let R be a relation from a set A into a set B: Then, the domain of R; denoted by Domain (R) ; is the set Domain (R) = fx 2 A j (x; y) 2 R for some y 2 Bg The range or image of R; denoted by Range (R) ; is the set Range (R) = fy 2 B j (x; y) 2 R for some x 2 Ag 1.4.1 Equivalence Relations b; 8a; b 2 A

De…nition 1.15 (Equivalence Relation) A relation R on a nonempty set A is an equivalence relation if for arbitrary a; b; c 2 A: 1. aRa; 8a 2 A (Re‡exive Property) 2. aRb =) bRa (Symmetric Property) 3. aRb and bRc =) aRc (Transitive Property) Example 1.9 The relation R de…ned on the set R2 by a2 + d2 = c2 + b2 is an equivalence relation since for (a; b) ; (c; d) ; (e; f ) 2 R2 , 1. (a; b) R (a; b) : I.e, a2 + b2 = a2 + b2 ; 8 (a; b) 2 R2 2. (a; b) R (c; d) =) a2 + d2 = c2 + b2 =) c2 + b2 = a2 + d2 =) (c; d) R (a; b)

CHAPTER 1. FUNDAMENTALS 3. (a; b) R (c; d) and (c; d) R (e; f ) =) a2 + d2 = c2 + b2 andc2 + e2 = d2 + f 2 =) a2 + f 2 = e2 + b2 =) (a; b) R (e; f ) Equivalence Class

11

De…nition 1.16 (Equivalence Class) Let R be an equivalence relation on A; and a 2 A: The set of all the elements equivalent to a is called the equivalence class of a; and is denoted by [a] = fx 2 A j xRag Example 1.10 Let A = f1; 2; : : : ; 10g and let R be a relation on A de…ne by aRb if and only if 3 divides a equivalence class of: b; for all a; b 2 A: Verify that R is an equivalence relation on A. The

[1] = fx 2 A j xR1g = fx 2 A j 3 divides x [2] = fx 2 A j xR2g = fx 2 A j 3 divides x [3] = fx 2 A j xR3g = fx 2 A j 3 divides x

1g = f1; 4; 7; 10g 2g = f2; 5; 8g 3g = f3; 6; 9g

Note that: [1] = [4] = [7] = [10] ; [2] = [5] = [8] ; [3] = [6] = [9] Theorem 1.3 Let R be an equivalence relation on the set A: Then 1. [x] 6= ;; for all x 2 A 2. if y 2 [x] ; then [x] = [y] 3. for all x; y 2 A; either [x] = [y] or [x] \ [y] = ; S 4. A = x2A [x] 1. Let x 2 A: Since R is an equivalence relation, by re‡ exive property, xRx; and hence by the de…nition of an equivalence class, x 2 [x] 6= ;: 2. Let y 2 [x] ; then yRx and by the symmetric property, xRy: To show that [x] = [y], implies u 2 [y] : Hence, [x] let u 2 [x] : Then uRx; and since xRy; by transitive property, we have uRy which [y] : Similarly, let v 2 [y] : Then vRy; and since yRx; [x] : By

Proof.

previous theorem , [x] = [y] :

by transitive property, we have vRx which implies v 2 [x] : Hence, [y]

CHAPTER 1. FUNDAMENTALS

12

3. Let x; y 2 A: Suppose [x] \ [y] 6= ;: Then there exists u 2 [x] \ [y] : Thus, u 2 [x] uRx; we have xRu; and uRy; and by transitivity, xRy which implies that x 2 [y] : By (ii), [x] = [y] : 4. Let x 2 A: Then x 2 [x] Thus, A S and hence by previous theorem, A = x2A [x] : S x2A [x] :

and u 2 [y] which implies that uRx and uRy respectively. Since R is symmetric and

S

x2A [x] :

Similarly,

S

x2A [x]

A;

Partition De…nition 1.17 (Partition) Let A be a set and P = fAi j i 2 Ig be the collection of the partition) if the following properties are satis…ed: 1. for all Ai ; Aj 2 P; either Ai = Aj or Ai \ Aj = ; for i; j 2 I; i 6= j. 2. S i2I nonempty subsets of A: Then P is called a partition of A (and Ai are called the cells of

Ai = A1 [ A2 [

[ Ai [

[ An = A

Example 1.11 Let A be a set partitioned into four cells A1 ; A2 ; A3 ; A4 as shown in the …gure below. The family fA1 ; A2 ; A3 ; A4 g is called a partition of the set A: Note that: A1 [ A2 [ A3 [ A4 = A

A A2 A1 A3 A4

Example 1.12 Let A be a set.partitioned into seven cells A1 ; A2 ; A3 ; A4 ; A5 ; A6 ; and A7 as shown in the …gure below.
A A1 A5 A2

A6 A4

A3

A7

Then, A1 = A5 ; A2 = A6 ; and A3 = A7

CHAPTER 1. FUNDAMENTALS

13

Remark 1.1 If fAi j i 2 Ig is a partition of A; we may de…ne an equivalence relation R

on A by letting xRy if and only if x and y are in the same cell of the partition. In other

words, two elements “equivalent” if there are members of the same cell. It is called the equivalence relation determined by the partition fAi j i 2 Ig : Example 1.13 Let ff1; 4; 7; 10g ; f2; 5; 8g ; f3; 6; 9gg be a partition of A = f1; 2; : : : ; 10g : the partition. Remark 1.2 If R is an equivalence relation on A; the family of all the equivalence classes, by the equivalence relation R that is, f[x] j x 2 Ag ; is a partition of A: We call this partition the partition determined

We obtain an equivalence R by letting xRy if and only if x and y are in the same cell of

alence classes, that is, f[1] ; [2] ; [3]g ; is a partition of A:

Example 1.14 From previous example with A = f1; 2; : : : ; 10g, the family of all the equiv-

1.5
1.5.1

Functions
Domain and Range

De…nition 1.18 (Function) Let A and B be two nonempty sets. A function or mapping f from a set A into a set B; f : A ! B or A ! B is a rule that assigns to each element a 2 A exactly one element b 2 B: We say that f maps a into b; denoted by f (a) = b De…nition 1.19 (Function - Alternate) Let A and B be nonempty sets. A subset f A is a unique element b 2 B such that (a; b) 2 f: B is a function (mapping) from A to B if and only if for each a 2 A; there f De…nition 1.20 (Domain, Codomain, Image, Range, Inverse Image) Let of f: The set f : A ! B: The set A is called the domain of f ; the set B is called the codomain f (A) = Range (f ) = fb = f (a) 2 B j a 2 Ag is called the image of f:, also called the range of f: B

CHAPTER 1. FUNDAMENTALS 1.5.2 Injective, Surjective and Bijective Functions

14

De…nition 1.21 (One to One/Injective Function) A function f from a set A to a set B is called one to one if each element of B has at most one element of A mapped into it, that is for a1 ; a2 2 A,if f (a1 ) = f (a2 ) then a1 = a2 : De…nition 1.22 (Onto/Surjective Function) A function f from a set A to a set B is said to be onto B if each element of B is the image of at least one element of A, that is, for each b 2 B;there exists a 2 A such that f (a) = b: That is, f is onto or surjective if and only if B = f (A). De…nition 1.23 (One-to-One Correspondence/Bijective Function) A function f from a set A into a set B is called a one to one correspondence or bijective function if it is both one to one and onto. We sometimes writes f :A !B onto 1 1

Example 1.15 Let f : R ! R be a function from real numbers to real numbers. Determine whether f is injective and/or surjective. 1. f (x) = 2x (a) Injective? Suppose f (x1 ) = f (x2 ) ; want x1 = x2 In other words, given f (x1 ) = f (x2 )

=) 2x1 = 2x2 =) x1 = x2 Hence, f is injective. (b) Surjective? Let y 2 R: Want to …nd x so that f (x) = y: In other words 2x = y y x = can be solve for any y 2 R 2 Hence, f is surjective. de…nition, f is bijective. 2. f (x) = x2 (a) Injective? Suppose f (x1 ) = f (x2 ) ; want x1 = x2 In other words, given x2 = x2 1 2

CHAPTER 1. FUNDAMENTALS but, x1 6= x2 since we can choose x1 = 1 and x2 =

15 1: Hence, f is not injective.

(b) Surjective? Let y 2 R: Want to …nd x so that f (x) = y: In other words x2 = y p x = y But, if we choose y = not surjective. 1.5.3 Composite Functions f and g be the functions with 1 2 R; we cannot solve for x since x 2 R: Hence, f is

De…nition 1.24 (Composite Functions) Let f : A called the composite function and is denoted by ! B and g : B

! C; then there is a natural function mapping A into C;

(g f ) (a) = (gf ) (a) = g (f (a)) ; 8a 2 A Note that we can write f : A ! B and g : B ! C as A ! B f g

that gf is read from right-to-left; …rst apply f and then g:Also note that: 1. If f and g are injective, then g f is injective. 2. If f and g are surjective, then g f is surjective 3. If f and g are bijective, then g f is bijective Example 1.16 f : A B!B

! C: Also note

A is de…ned by f (x; y) = (y; x) ; and g : B

de…ned by g (y; x) = y: Find g f: (g f ) (x; y) = g (f (x; y)) = g (y; x) = y 1.5.4 Inverse Functions

A!B

De…nition 1.25 (Inverse Function) Let f : A exists, is a function f
1

from B to A such that x=f
1

! B: The inverse function f; if it

(y)

i¤

y = f (x)

Note that: If f

1

exists, f must be injective and surjective, that is, bijective.

Example 1.17 Each of the following functions f is bijective. Find its inverse.

CHAPTER 1. FUNDAMENTALS 1 1 : Let y = . By de…nition, x = f x x 1 ; x 1 = y

16
1 (y)

1. f : (0; 1) ! (0; 1) ; de…ned by f (x) = i¤ y = f (x) : Solve for x

y = then, x =
1

1

(y)

So,

(x) =

1 x
1 (y)

2. f : R ! (0; 1) ; de…ned by f (x) = ex : Let y = ex . By de…nition, x = f y = f (x) : Solve for x y = ex ln y = ln ex x = ln y = f Hence, f
1 (x) 1

i¤

(y)

= ln x

1.6
1.6.1

Properties of Integers
The Division Algorithm

De…nition 1.26 (Divisor and Multiple) A nonzero integer b is a divisor (factor) of an integer a if there is an integer c such that a = bc In this case we say “b divides a ” and write bja Also, we say that a is a multiple of b: Theorem 1.4 (The Division Algorithm) Let a and b be integers with b > 0: Then there exist unique integers q and r with the property that a = bq + r where 0 r 1: For a; b 2 Z; a is con-

a if and only if n j (a b) :

b (mod n)

CHAPTER 1. FUNDAMENTALS Example 1.21 3 11 62 1 (mod 2) since 2 j (3 2 (mod 3) since 3 j (11 1) 2) 62)

18

62 (mod 85) since 85 j (62

Remark 1.3 The relation of congruence modulo n is an equivalence relation on Z: There are n distinct equivalence classes for congruence modulo n that form a partition of Z: Let Zn denote this set of classes: Zn = f[0] ; [1] ; [2] ; : : : ; [n Where [0] = f: : : ; 2n; n; 0; n; 2n; : : :g [1] = f: : : ; 2n + 1; n + 1; 1; n + 1; 2n + 1; : : :g 1]g

[2] = f: : : ; 2n + 2; n + 2; 2; n + 2; 2n + 2; : : :g . . . [n 1] = f: : : ; n 1; 1; n 1; 2n 1; 3n

1; : : :g

For convenience, we will let Zn = f0; 1; 2; : : : ; n

1g through out the course.

Chapter 2 Groups and Subgroups

2.1

Binary Operation on a nonempty set A is a rule

De…nition 2.1 A binary operation (or just operation) (relation) which assigns to each ordered pair (a; b) 2 A That is: :A A!A

A exactly one element a b 2 A: (BinOp)

Example 2.1 Some examples of operations: addition (+), multiplication ( ), substraction ( ) ; division ( ) ; composition ( ), intersection (\) ; union ([) De…nition 2.2 A mathematical system is an ordered n + 1 tuples (A; where A is a nonempty set and i 1; 2; : : : ; n)

is an operation de…ned on A:

Example 2.2 (Z; +) ; (Q; +) ; (R; ) ; (C; ) are examples of mathematical systems with one operation. (R+ ; ; +) ; (C; +; ) are examples of mathematical systems with two operations. Remark 2.1 1. a b is de…ned for every ordered pair (a; b) of elements of A: 2. a b must be uniquely de…ned. 3. If a; b 2 A; then a b must also be in A: This condition is often expressed by saying that A is closed under the operation : 19

CHAPTER 2. GROUPS AND SUBGROUPS 2.1.1 Properties of Operations

20

De…nition 2.3 (Commutative Property) An operation if (and only if ) a b = b a; 8a; b 2 A De…nition 2.4 (Associative Property) An operation (and only if ) (a b) c = a (b c) ; 8a; b; c 2 A De…nition 2.5 (Identity Element) Let element e 2 A with the property that e a = a = a e; 8a 2 A

on a set A is commutative (CommProp) on a set A is associative if (AssocProp)

be an operation on a set A: If there is an

(Id)

then e is called an identity or “neutral” element in A with respect to the operation De…nition 2.6 (Inverse Element) Let exists an element a
1

2 A with the property that a a
1

be an operation on a set A: For a 2 A; if there
1

=e=a

a

(Inv)

then a

1

is called an inverse of a in A
1

Remark 2.2 In a general set A, the inverse element of a 2 A is denoted by a identity element is denoted by e:

and the

2.2

Groups

De…nition 2.7 (Group) A mathematical system (G; ) is called a group if it satis…es the following properties: [G1] The operation is associative, i.e x (y z) = (x y) z; 8x; y; z 2 G; [G2] There exists a unique identity element e 2 G such that e x = x e = x; 8x 2 G (G2) (G1)

CHAPTER 2. GROUPS AND SUBGROUPS [G3] There exists a unique inverse element x x
1 1

21 2 G such that = e; 8x 2 G (G3) is

x=x x

1

De…nition 2.8 (Abelian Group) A group (G; ) is called abelian if its operation commutative. That is: x y = y x; 8x; y 2 G

(G4)

Example 2.3 (In…nite Groups) (Z; +) ; (Q; +) ; (R; +) ; (C; +) ; (Q ; ) ; (R ; ) ; and (C ; ) are examples of groups. In fact, they are also abelian groups. CHECK! Determine the identity and inverse of each group. Example 2.4 (Z+ ; +) ; (Z+ ; ) ; (Z; ) ; (R ; +) ; (R; ) are examples of mathematical systems which are not groups. WHY? Remark 2.3 When we use a letter, say G, to represent a group, we mean that it represents a set together with an operation that satis…es properties [G1] ; [G2] ; and [G3] : Without any confusion, if it is known that a particular set is a group, we will sometimes use the symbol for the set. When it is convenient, for a general group G, we use multiplicative notation to be the operation in G; that is, for a; b 2 G; we will write the groups and groups with operation multiplication as multiplicative groups. De…nition 2.9 (Order of a Group) A group G is called a …nite group if G has a …nite number of elements. The order of G; denoted by o (G) (sometimes we use the G: A group of in…nitely many elements is said to have in…nite order. 2.2.1 Cayley Table notations: jGj or ord (G) to denote the order of a group G ) is the number of elements of operation as ab; instead of a b: We will call groups with operation addition as additive

For a …nite set, an operation on the set can be de…ned by mean of a table in which the elements of the set are listed across the top as heads of columns and the left side as heads of rows. This table is called a Cayley table or an operation table.

2.3
2.3.1

Properties of Groups
Cancellation Property

Theorem 2.1 (Cancelation Property) Suppose G is a group and a; x; y 2 G: Then, 1. If ax = ay; then x = y

CHAPTER 2. GROUPS AND SUBGROUPS 2. If xa = ya; then x = y Remark 2.4 In general, we cannot cancel a in the equation ab = ca: (Why not?) Theorem 2.2 Suppose G is a group and a; b; x; y 2 G: Then the linear equations ax = b and ya = b have unique solutions in G: Theorem 2.3 If G is a group and a; b 2 G; then 1. (ab) 2. a 2.3.2
1 1

22

=b
1

1a 1

=a

Exponents and Multiples

De…nition 2.10 (Integral Exponents and Multiples) Let G be a group and let a 2 G: For any positive integer n; we de…ne the following: Multiplicative Notation a0 = e; a1 an a = a; a2 = aa; : : : = | {z a aaa } = a n factors 1 n

Additive Notation 0a = 0; 1a = a; : : : na = a + a + | {z n summands

n

( n) a = n ( a)

+a }

(IntMult)

Theorem 2.4 (Exponents and Multiples) Let G be a group and let a; b 2 G: Then for all m; n 2 Z Laws of Exponents am an = am+n amn (am )n = Laws of Multiples ma + na = (m + n) a n (ma) = (nm) a If G is abelian, n (a + b) = na + nb (LawsIntMult)

If G is abelian, (ab)n = an bn

2.4

Subgroups

De…nition 2.11 (Subgroup) Let G be a group and H is a nonempty subset of G: If H is closed under the operation of G and H is itself a group, then H is a subgroup of G: We write H G (ImpSubgrp)

CHAPTER 2. GROUPS AND SUBGROUPS to denote that H is a subgroup of G; and H