Math 135 Winter 2013 Course Notes

MATH 135 - Algebra for Honours Math Kevin Carruthers Winter 2013 Implications De▯nition: An impication is a statement S such that a hypothesis (or assumption) H ensures the validity of the conclusion C, and may either be true or false. An implication is only false if a hypothesis is true and the conclusion is false (ie a counter-example exists). In other words, for S: P =) Q (P implies Q), S is true unless P is true and Q is false. Note that this can give confusing results such as ▯ If 1 = 2, then 2 = 2 ▯ If 1 = 2, then 2 = 3 Because 1 = 2 is a false hypothesis, both of these implications are true, regardless of the vailidty of their conclusion. Direct Proof For a direct proof, we start by assuming the hypothesis, and derive the conclusion. 1. Always assume the hypothesis is true. 2. Never assume the conclusion is true. 3. Starting from the hypothesis, think of what can be derived using de▯nitions, theorems, and logical deductions. 4. Look toward the conclusion, think of what needs to be achieved to prove the conclusion. Proposition: For S = 0 =) B, S = B =) C1 and S = A =) C, prove 2 2 given S 0nd S . 1 Proof: Assume A. Since both A and A =) B are true, B is true. Since B and B =) C are true, C is true. Thus A =) C is true. QED. 1 Proposition: Given S , S ,0and1S , assum2 S and S are 0rue. Mus2 S be true? 1 Proof: B =) C is false if and only if B is true and C is false. If C is false, we have A is false, so we have both A =) B and A =) C are true, but B =) C is false. Thus S and 0 S 2o not imply S . Q1D. Divisibility De▯nition: An integer m divides an integer n if there exists an integer k such that n = km. This is denoted as mjn. Proposition: Transitivity of Divisibility Let a, b, and c be integers. If a j b and b j c, then a j c. Proof: Since ajb, there exists an integer k such that b = ka. Since bjc, there exists an integer j such that c = jb. Then c = jka. Since jk 2 Z, we have ajc. QED. Sets A set is a collection of objects. We use the notation e 2 S for element e in set S. Sets can not have duplicate elements and may be de▯ned in any order. ▯hey may be described in set builder notation S = fx ;x ;:0:;1 g, T n f2k + 1 ▯k 2 Rg If S and T are sets, the cartesian product of S and T is ▯ S ▯ T = f(a;b) a 2 S;b 2 Tg The order of elements within each pair does matter. ▯ ▯ For a ▯nite set S, the cordinality of S is the number of elements in S, denoted S . Note▯ ▯ ▯ ▯ ▯ ▯▯ ▯ that S ▯ T = S T . The empty set is the only one with a cordinality of 0. Operations Note that we use ^, _, and : to denote "and", "or", and "not". ▯ 1. Union: S [ T = fx ▯ x 2 S _ x 2 Tg ▯ 2. Intersection: S \ T = fx ▯ x 2 S ^ x 2 Tg ▯ 3. Complement: S = fx ▯x 2= Sg. Note that S cc = S. ▯ Complements are transitive, ie (A \ B) = A \ B . c c ▯ 4. Di▯erence (relative complement of B in A): S n T = fx ▯x 2 S ^ x 2 = Tg. In other c words, S n T = S \ B . 2 ▯ Relative complements are inversely transitive, ie X n(A\B) = (X nA)[(X nB). Subsets De▯nition: S is a subset of T (S ▯ T) if and only if for every x 2 R, x 2 S =) x 2 T. Note that S ▯ S and the zero set is a subset of every other set. S For a set S, the power set is the set of all possible subsets of S, denoted by P(S) or 2 ▯ Example: for S = f1;2g, P(S) = fg;f1g;f2g▯ ▯;2g thus f2g 2 P(S) but 2 2 = P(S) so ▯ ▯ ▯ ▯ ▯ ▯n▯ f2g ▯ P(S). P(S) = 4, or P(n) = 2 ▯ Equality A = B if and only if for every x 2 R, (x 2 A () x 2 B). From the de▯nitions of a subset, we also have A = B () A ▯ B and B ▯ A. Proposition: S \ (T [ U) = (S \ T) [ (S \ U) Proof: Let x 2 S \ (T [ U). So x 2 S and x 2 T [ U. We have two cases: If x 2 T, x 2 S \ T. If x 2 U, x 2 S \ U. Therefore, x 2 (S \ T) [ (S \ U). QED. Quanti▯ers The universal quanti▯er 8 means "for all" and the existential quanti▯er 9 means "there exists". Examples: 8x, x = 3 is false if x 2 Z but true if x 2 f3g 9y, y < 1 is true if y 2 Z but not if y 2 N We can thus compare these quali▯ers to logical statements. For example 8x;P(x) = P(x )0^ P(x )1^ P(x ):2: and 9x;P(x) = P(x )0_ P(x )1_ P(x ):2: 3 Proving Statements Containing Quanti▯ers Note that some quanti▯ers can be h▯dden in words. For example, the mathematical de▯nition of divisibility is ajc =) 9k 2 Z ▯c = ka 1. To prove that something exists, construct this thing. 2. To prove a universal property, select an arbitrary member of the universe and prove the property for this instance. Nested Quali▯ers ▯ Proposition: 8x 2 R;9y 2 R y < x Proof: Let x 2 R, Then y = x ▯ 1 satis▯es y 2 R and y < x. QED. but Proposition: 9y 2 R;8x 2 R ▯ y < x Proof: If such a y exists, then x = y does not satisfy y < x. This is a contradiction, thus the proposition is false. QED. ▯ Proposition: 8x 2 P(N);x 2 = fg =) 9y 2 x;8z 2 x ▯y < z Proof: Can be accepted logically. QED. Binary Relations Let X be a set. A binary relation on X is a two-variable predicate Rde▯ned on X (ie for f(x;y) 2 X x Xg;R(x;y) may be either true or false). When R(x;y) holds, we say x is R-related to y and write xRy. Equality, ordering, and divisibility are all examples of relations. We also have A ▯ B () 8x 2 S;(x 2 A =) x 2 B) and for any A;B 2 P(S) the disjointedness relation A ? B () A \ B = fg For a binary relation on set X, the relation is ▯ Re exive if 8x 2 X;xRx ▯ Symmetric if 8x;y 2 X;xRy =) yRx ▯ Transitive if 8x;y;x 2 X;xRy ^ yRz =) xRz 4 Equivalence Relations Let X be a non-empty set. An equivalence relation on X is a binary relation on X that is re exive, symmetric, and transitive. The most common example of this is for S = f(x;y) 2 ▯ R x R x = yg;xRy is an equivalent relation. Implication Modi▯ers Converses The converse of A =) B is B =) A. Note that the converse does not necessarily have the same truth value as the original implication. If both statements are true, then the elements within them are equivalent. Negations Let A, B, and C be statements. Then 1. :(A ^ B) () (:A) _ (:B) 2. :(A _ B) () (:A) ^ (:b) 3. :(A =) B) () A ^ :B 4. :(:A)) () A Let S be a set, P(x) is a statement dependant on x 2 S. Then 1. :(8x 2 S;P(x)) () 9x 2 S;:P(x)) 2. :(9x 2 S;P(x)) () 8x 2 S;:P(x)) To ▯nd the negation of P(x), we can do the following ▯ P(x) = 9y 2 R;8x 2 R ▯ y < x ▯ :P(x) = :(9y 2 R;8x 2 R ▯y < x) = 8y 2 R;(:(8x 2 R ▯ y < x)) ▯ = 8y 2 R;9x 2 R ▯ y ▯ x Contrapositive De▯nition: The contrapositive of P =) Q is :Q =) :P. A statement and its contrapositive are equivalent, and it can sometimes be easier to prove the contrapositive. 2 Proposition: For n 2 Z, if n is even then n is even 5 Proof: Suppose n is odd. Then n = 2k + 1 for some k 2 Z. 2 2 2 So n = (2k + 1) = 4k + 4k + 1. Then n is odd. Thus we have n is odd =) n is odd, so n is even =) n is even. QED. Use a contrapositive when the hypothesis does not give much to work with or when the negation of the implication is nicer. Contradiction Assume the conclusion is false (or the contrapositive is false). If you derive something impossible, the assumption must be wrong. Uniqueness To prove the existence of x, suppose there are two of them x and y. Try to prove either it must be the case that x = y, or assume x 6= y and reach a contradiction. Deduction Overview Methods of deduction: ▯ Direct: assume the hypothesis and ▯nd the conclusion. ▯ Example: especially with quanti▯ers, ▯nd an example which breaks the implication. ▯ Contrapositive: prove the contrapositive. ▯ Absurdity: Assume the implication (or contrapositive) is false, try to ▯nd something blatantly contradictory. Induction Induction is useful when proving general statements 8x. Principle of Mathematical Induction Suppose P(n) is a statement for n ▯ n 0 If 1. P(n0) is true, and 6 2. 8k ▯ n ;P(k) =) P(k + 1). 0 Then, by induction, P(n) is true 8n ▯ n .0 Weak Induction Weak induction is a general technique based directly on the Principle of Mathematical Induction (henceforth refered to as POMI), and is suited to proving statements of the form "8n ▯ n 0P(n)". It consists of two steps: 1. the base case (prove P(n )0, and 2. the induction step (chose an arbitrary k ▯ n fo0 which we assume P(k), then prove P(k + 1)). Then we simply invoke the POMI to conclude 8n;P(n). n Proposition: 8n ▯ 2;(1 + x) > 1 + nx Proof: For n = 2 we have P(2) = (1 + x) 2 2 = 1 + 2x + x > 1 + 2x + 0 > 1 + 2x This proves P(2) Assume that (1 + x) > 1 + kx. Then P(k + 1) = (1 + x) k+1 k = (1 + x) (1 + x) > (1 + kx)(1 + x) > 1 + kx + x + kx 2 > 1 + (k + 1)x + 0 > 1 + (k + 1)x n So 8k ▯ 2;P(k) =) P(k + 1). Thus, by POMI, 8n ▯ 2;(1 + x) > 1 + nx. QED. Strong Induction Strong induction is an alternative to weak induction which may be used when P(k +1) is dependant on either multiple past cases or a single past case P(j) where the relative location of j < k cannot be determined. 7 Principle of Strong Induction, v1 De▯nition: Let P(n) be a property concerning integers n ▯ n . Suppose that the following 0 are true: 1. P(n 0, and 2. 8k ▯ n 08n ▯oj ▯ k;P(j) =) P(k + 1) Then 8n;P(n). Proposition: Every natural number n > 1 can be expressed as a product of primes. Proof: For any n ▯ 2, if n is prime then n is the product of a single prime (itself). Thus n is prime =) P(n). ▯ Assume n is composite. By de▯nition 9m ▯1 < m < n ^ mjn. For n = md;d 2 N, we have 1 < d < n. By induction hypothesis, P(m)^P(d), which means we can express m and d as products of primes. The we can write m = p 0 1::p s and d = q0 1:::t so n = md = (p p 0 1p )sq q0 1:q t is a product of primes. By POSI, 8n ▯ 2;n is a product of primes. QED. Principle of Strong Induction, v2 The ▯rst version of POSI can fail given certain low values of k (for certain P(n) we may have P(n) () n ▯ b ^ b ▯ n ). We 0hus modify POSI to seperately verify the multiple base cases of P(j) for n ▯ j ▯ b. o De▯nition: Let P(n) be a property concerning integers n ▯ n . Supp0se, for some integer b ▯ n 0 the following are true: 1. P(n 0;P(n +01);:::;P(b), and 2. 8k ▯ b;8n ▯ j ▯ k;P(j) o Proposition: 8n ▯ 60;n = 7x + 11y;n;x;y 2 Z;x;y ▯ 0. Use the following equalities: 1 = 7(▯3) + 11(2) (1) 1 = 7(8) + 11(▯5) (2) 60 = 7(7) + 11(1) (3) 8 Proof: Equation (3) clearly veri▯es P(60). Since we have x is multiplied by 7 and 7 < 11, we take P(j) with 60 ▯ j ▯ 66 as the base cases, all of which can be veri▯ed with a list of equations (omitted). Assume that k ▯ 67 is such that P(j) holds for all 60 ▯ j < k. Since k ▯ 67;k ▯ 7 ▯ 60 and so P(k ▯ 7) is true, thus k ▯ 7 = 7x + 11y for some x and y. We can manipulate this equation to have k = 7(x + 1) + 11y and since x + 1 2 Z ^ x + 1 ▯ 0;P(k). Thus we have shown that whenever k ▯ 67;P(60);:::P(k ▯ 1) all true imply P(k). By POSI, this proposition is true. QED. Properites of Various Things Divisibility Proposition: Divisibility of Integer Combinations Let a;b;c 2 Z. a j b ^ a j c =) a j bx + cy;8x;y 2 Z Proof: Since ajb ^ ajc, there exists k;l 2 Z such that b = ka and c = la Then bx + cy = kax + lay = a(kx + ly). Since kx + ly 2 Z;ajbx + cy. QED. Proposition: Bounds by Divisibili▯ ▯ ▯ ▯ Let a;b 2 Z:a j b ^ b 6= 0 =) a ▯ b▯ ▯ ▯ Proof: Since ▯ ▯, t▯er▯ ex▯ ▯▯ ▯2 Z▯ ▯ch that b = ka. Then b = ka = k a ▯ a . QED.▯ ▯ Division Algorithm Proposition: Let a 2 Z ^ b 2 N. Then there exist unique integers q;r such that a = qb + r where 0 ▯ r < b Greatest Common Divisors De▯nition: For any a;b 2 Z not both 0, the greatest common divisor of a and b, denoted gcd(a;b), is the integer d such that dja ^ djb and cja ^ cjb =) c ▯ d. 9 Proposition: GCD with Remainders If a;b;q;r 2 Z such that a = qb + r, then gcd(a;b) = gcd(b;r) Proof: Let d = gcd(a;b). Since d is a common divisor of a;b;djb. We see that r = a ▯ qb. Since a ▯ qb is an integer combination of a and b, dja ▯ qb, so djr. Let c be a common divisor of b and r. So cjb ^ cjr. Since qb + r is an integer combination of b and r, c j qb + r. So c j a. Therefore, c is a common divisor of a;b. Since d = gcd(a;b);c ▯ d. Thus d = gcd(b;r) so gcd(a;b) = gcd(b;r). QED. Proposition: GCD Characterization For a;b 2 Z, if d j a;d j b;d ▯ 0, and 9x;y 2 Z such that ax + by = d, then d = gcd(a;b). Proof: If a = b then gcd(a;b) = 1 so then x = 1;y = 0 is an integer solution to ax + by = a. Without loss of generality, assume a > b. De▯ne function E(a;b) to be the number of steps required when feeding (a;b) into the Euclidean algorithm. We will prove by induction on E(a;b). E(a;b) = 1 so bja. Then gcd(a;b) = b. Assume for some k ▯ 1 the result holds when E(a;b) = k. Suppose E(a;b) = k + 1. In the ▯rst step of the alogirthm, we calculate a = qb + r and gcd(a;b) = gcd(b;r). Let d = gcd(a;b). Then E(b;r) = k, so there exists x ;y0 0 2 Z such that bx + 0y = 0 gcd(b;r) = d. Substitute r = a ▯ qb to get d = bx 0 (a ▯ qb)y =0ay + 0(x ▯ q0 ). 0 Then x = y ;0 = x ▯ 0y is 0n integer soution to ax + by = d. QED. Coprimes De▯nition: For a;b 2 Z, a and b are coprime if gcd(a;b) = 1. Proposition: Coprimesness and Divisibility If a;b;c 2 Z where c j ab and a and c are coprime, then c j b. Proof: Since gcd(a;c) = 1, there exist x;y such that ax + cy = 1. Then bax + bcy = b. Since cjab ^ cjc, cjbax + bcy (by integer combination) so cjb. QED. Proposition: Primes and Divisibility If a;b 2 Z, p is prime and p j ab, then p j a or p j b. Proof: Assume p - a. Since the only positive factors of p are 1 and p and p - a, gcd(p;a) = 1. Given Coprimeness and Divisibility, pjb. So pja _ pjb. QED. Proposition: Division by GCD a b If a;b 2 Z where d = gcd(a;b > 0 then gcd( d; d = 1 10 Linear Diophantine Equations De▯nition: An LDE has the form a x + a x0+ 0:: +1a 1 = c wherenan;:::a ;c 2 Z an0 n x ;:::x are integer variables. 0 n Given the one variable case ax = c, there exists a solution if and only if a j c. If there is a solution, that solution ▯s unique. For the two variable case ax+by = c the set of all solutions ▯ is f(x0;y 0 2 Z x Z ax 0 by = 0g. Generally, ax + by = c has an integer solution whenever gcd(a;b)jc. Proposition: LDE 1 Let a;b;c 2 Z;d = gcd(a;b). Then ax+by = c has an integer solution if and only if d j c. Proposition: LDE 2 Let a;b;c 2 Z;d = gcd(a;b) > 0. If (x ;y▯▯ is a0 in0eger solu▯i▯n to ax + by = c, b a ▯ the complete set of integers is x0+ d n;y 0 n d n 2 Z . Primes Euclid’s Theorem hols that there are in▯ntiely many primes. Note that every integer greater than