Mathematics and Algorithms for Computer AlgebraPart 1c 1992 Dr Francis J. Wright – CBPF, Rio de JaneiroJuly 9, 20032: Introduction to Abstract AlgebraThe notes this week are based on several chapters of the very nice bookby Lipson, which now unfortunately appears to be out of print. The first twosections of these notes provide a rapid summary of some of the basic notionsof pure mathematics, as a reminder and in order to fix the notation andnomenclature that I will use. Subsequent sections summarize the propertiesof the computational domains of main interest for computer algebra. Wewill return in subsequent weeks to consider in more concrete detail severalof the topics introduced this week.1 Sets, relations and functions1.1 Some fundamental setsZ = {0, ±1, ±2, . . .} is the set of integers.Q = {m/n | m, n ∈ Z; n 6= 0} is the set of rational numbers.R is the se t of real numbers.C = {a + ib | a, b ∈ R} is the se t of complex numbers (i =√−1).Some important subsets of these are the following:Z+= {a ∈ Z | a > 0} is the set of positive integers – the positive rationalsand reals are denoted similarly.N = {a ∈ Z | a ≥ 0} is the set of natural numbers.1Note that Z+⊂ N ⊂ Z ⊂ Q ⊂ R ⊂ C (with strict inclusions).1It could be argued that 0 is not a natural numbe r, and some authors call Z+thenatural numbers, but in computing it is conventional and convenient to count from 0, andit turns out that in our present context N is more natural than Z+.1The Cartesian product A × B of sets A and B is the set of all orderedpairs thusA × B = {(a, b) | a ∈ A, b ∈ B}.Examples: R ×R = R2is the Cartesian plane;{0, 1} × {a, b, c} = {(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}.1.2 Equivalence relationsA relation “≡” between a set A and a set B is the subset of A × B definedby {(a, b) ∈ A ×B | a ≡ b}. A relation ≡ on a set A (i.e. between A and A)is an equivalence relation if ∀a, b, c ∈ A it is1. Reflexive: a ≡ a2. Symmetric: a ≡ b ⇒ b ≡ a3. Transitive: a ≡ b and b ≡ c ⇒ a ≡ cExamples: Equality (=) is an equivalence (but inequality (6=) is not, because(1) and (3) are not satisfied).The subset [a]≡= {b ∈ A | a ≡ b} is called the ≡-equivalence class ofa. The set of all ≡-equivalence classes in A is denoted A/≡ = {[a] | a ∈ A}and is called either the quotient set of A by ≡ or A modulo ≡ (abbreviatedto A mod ≡).Lemma 1[a] = [b] ⇒ a ≡ bProof is an exercise! 21.2.1 Equivalence mod m on ZFor m a positive integer, definea = b (mod m) or a ≡mb ⇐⇒ a − b = km for some k ∈ Z.Thus [a]m= {a + km | k ∈ Z. For example, with m = 3,[0]3= {. . . , −6, −3, 0, 3, 6, . . .},[1]3= {. . . , −5, −2, 1, 4, 7, . . .},[2]3= {. . . , −4, −1, 2, 5, 8, . . .},and hence [0]3∪[1]3∪[2]3= Z. Generally, Z/≡m= {[0]m, [1]m, . . . , [m−1]m}.21.2.2 Rational numbersLet X = Z × (Z − {0}) = {(a, b) | a, b ∈ Z; b 6= 0}, and define the relation∼ ⊆ X by (a, b) ∼ (c, d) ⇐⇒ ad = bc. Then [(a, b)]∼represents allequivalent rational numbe rs of the form a/b = (ka)/(kb)∀k.Philosophy: The set A/≡ is simpler than A because it represents subsetsof elements of A as single elements of A/≡. Frequently A is infinite butA/≡ is finite.1.2.3 Partial and total orderingsA relation ≤ on a set P is a partial order if ∀x, y ∈ P it is1. Reflexive: x ≤ x2. Antisymmetric: x ≤ y and y ≤ x ⇒ x = y3. Transitive: x ≤ y and y ≤ z ⇒ x ≤ zA set P with a partial order ≤ is called a partially ordered set. It is totallyordered if all elements x, y ∈ P satisfy either x ≤ y or y ≤ x, i.e. x 6≤ y ⇒y ≤ x.Examples: Z is totally ordered by the usual meaning of ≤; the positiveintegers Z+are partially ordered by divisibility ( |), but not totally orderedbecause 2 - 3 ; 3 |2.1.3 Functions or maps&%'$&%'$-fa ∈ Ab ∈ BA = domain of f B = co domain of fr rIf f : A → B is a function or map then it must map a 7→ b = f(a) for alla ∈ A, i.e. f must assign a unique image or value b ∈ B to every a ∈ A.A function f : A → B defines a relation on A × B, which is its graph. IfA0⊂ A then f0: A0→ B is a partial function on A (e.g.√: R+→ R, whereR+= {x ∈ R | x ≥ 0} is the set of non-negative real numbers).If f, g : A → B then f = g ⇐⇒ f (a) = g(a)∀a ∈ A.The function f : A → B is:31. injective or one-to-one if a 6= b ⇒ f(a) 6= f(b) (or if f(a) = f(b) ⇒a = b);2. surjective or onto if ∀b ∈ B, b = f (a) for some a ∈ A;3. bijective if it is both injective and surjective.The image of S ⊆ A under f : A → B isf(S) = {b ∈ B | b = f (s) for som e s ∈ S}.f(A) ⊆ B is called the image of f, Im f , or the range of f. The inverseimage of T ⊆ B under f : A → B isf−1(T ) = {a ∈ A | f (a) ∈ T }.The composition of f : A → B and g : B → C is denoted g ◦ f : A → Cand defined by g ◦ f (a) = g(f(a)), which means apply the functions fromright to left. Generally function composition does not commute! Functioncomposition is sometimes displayed in a mapping diagram of the formA CB?*-hfgwhich means that h : A → C is the composition of f : A → B withg : B → C, i.e. h = g ◦ f . (Note the order!)1.3.1 Inverse functionsf : A → B is1. left invertible if ∃g : B → A such that g ◦ f = 1A(where 1Ais theidentity function on A);2. right invertible if ∃h : B → A such that f ◦ h = 1B;3. (two-sided) invertible is it is both left and right invertible.Theorem 2 If f : A → B has a left inverse g : B → A and a right inverseh : B → A then g = h.4This unique two-sided inverse of f is denoted f−1.Theorem 31. f is left invertible ⇐⇒ f is injective.2. f is right invertible ⇐⇒ f is surjective.Corollary 4 f is (two-sided) invertible ⇐⇒ f is bijective.1.3.2 Functions and …