February 2018 - Page 6 of 7 - Shawn Zhong

Math 541 – 2/7

$Multiplicative Group of Z\/nZ • Let n∈Z( 0) fixed, Proposition 9 implies that there is a well-defined function ○ Z\/nZ×Z\/nZ→Z\/nZ ○ (a ̅,b ̅ )→(ab) ̅ • Check group property ○ Identity: 1 ̅⋅a ̅=(1⋅a) ̅=1 ̅ ○ This operation is associative ○ And 1 ̅ is a reasonable candidate for an identity, but there is no inverse ○ Example: Z\/4Z § 2 ̅⋅0 ̅=0 ̅ § 2 ̅⋅1 ̅=2 ̅ § 2 ̅⋅2 ̅=0 ̅ § 2 ̅⋅3 ̅=2 ̅ • Definition ○ Define (ZnZ^×≔{a ̅∈ZnZ(a,n)=1} ○ By HW 2 #2, a ̅∈(ZnZ^× iff ○ ∃c ̅∈Z\/nZ s.t. (ac) ̅=1 ̅ Proposition 11: (ZnZ^× • Statement ○ (ZnZ^× is a group with opeation given by multiplication • Proof ○ Closure: If a ̅,b ̅∈(ZnZ^×, then (ab) ̅∈(ZnZ^× as well ○ Associativity: Clear, from associativity of multiplication of integers ○ Identity: 1 ̅ ○ Inverses: Built in HW 2 #2 List of Groups Set Operation Z,Q,R,ℂ + Q∗,R∗,ℂ^∗ ⋅ GL_n (R, n 0 Matrix multiplication Z\/nZ, n 0 + 〖Z/nZ^∗, n 0 ⋅ Proposition 12: Properties of Group • Let G be a group, then G has the following properties • The identity of G is unique ○ i.e. If ∃〖1,1〗^′∈G s.t. ∀g∈G,1g=g1=g and 1^′ g=g1^′=g, then 1 =1^′ ○ Proof: 1=1⋅1^′=1^′∎ • Each g∈G has a unique inverse ○ i.e. If g∈G and ∃h,h′∈G s.t. hg=gh=1 and h′ g=gh′=1 ○ Let g∈G, and suppose h,h′∈G are inverses of g ○ h=h⋅1=h(gh′ )=(h�) h′=1⋅h′=h′ • (g^(−1) )^(−1)=g, ∀g∈G ○ Let g∈G, then gg^(−1)=1=g^(−1) g ○ Since the inverse is unique, g=(g^(−1) )^(−1) • The Generalized Associative Law ○ i.e. If g_1,…,g_n∈G, then g_1…g_n is independent of how it is bracketed ○ First show the result is true for n=1,2,3 ○ Assume for any k n any bracketing of a product of k elements ○ b_1 b_2⋯b_k can be reduced to an expression of the form b_1 (b_2 (b_3⋯b_k )) ○ Then any bracketing of the product a_1 a_2⋯a_n must break into ○ 2 sub-products, say (a_1 a_2⋯a_k )(a_(k+1) a_(k+2)⋯a_n ) ○ where each sub-product is bracketed in some fashion ○ Apply the induction assumption to each of these two sub-products ○ Reduce the result to the form a_1 (a_2 (a_3…a_n )) to complete the induction. • (gh^(−1)=h(−1) g^(−1), ∀g,h∈G ○ By the generalized associative law ○ (gh(h(−1) g^(−1) )=g(h^(−1) ) g^(−1)=gg^(−1)=1 ○ (h(−1) g^(−1) )(gh=h(gg^(−1) ) h(−1)=hh(−1)=1 • Notation ○ We will apply the Generalized Associative Law without mentioning it ○ In particular, if G is a group and n∈Z( 0), we will write § g^n=⏟(g…g)┬(n copies) § g^(−n)=⏟(g^(−1)…g^(−1) )┬(n copies) § g^0=1 Proposition 13: Cancellation Law • Statement ○ Let G be a group, and let a,b,u,v∈G ○ If au=av, then u=v ○ If ua=va, then u=v • Proof ○ au=av⇒a^(−1) au=a^(−1) av⇒u=v ○ ua=va⇒uaa^(−1)=vaa^(−1)⇒u=v • Warning ○ ua=av⇏u=v ○ This holds in abelian groups, but not in general Corollary 14 • Let G be a group, and let g,h∈G • If gh=g,then h=1 ○ gh=g ○ ⇒gh=g1 ○ ⇒h=1 • If gh=1,then h=g^(−1) ○ gh=1 ○ ⇒gh=gg^(−1) ○ ⇒h=g^(−1)$

1.8 Proof Methods and Strategy

$Proof by Cases • To prove a conditional statement of the form: ○ \(p_1∨p_2∨…∨p_n)→q • Use the tautology ○ \(p_1∨p_2∨…∨p_n)→q ↕ ○ (p_2→q)∧(p_2→q)∧…∧(p_n→q) • Each of the implications p_i→q is a case. • Example ○ Let a@b=max{a, b}=a if a≥b, ○ otherwise a@b=max{a, b}=b. ○ Show that for all real numbers a, b, c § (a@b)@c=a@(b@c) ○ (This means the operation @ is associative.) ○ Let a, b, and c be arbitrary real numbers. ○ Then one of the following 6 cases must hold. § a≥b≥c § a≥c≥b § b≥a≥c § b≥c≥a § c≥a≥b § c≥b≥a Without Loss of Generality • Show that if x and y are integers and both x∙y and x+y are even, • then both x and y are even. • Use a proof by contraposition. • Suppose x and y are not both even. • Then, one or both are odd. • Without loss of generality, assume that x is odd. • Then x=2m+1 for some integer m. • Case 1: y is even. ○ Then y=2n for some integer n, so ○ x+y=(2m+1)+2n=2(m+n)+1 is odd. • Case 2: y is odd. ○ Then y=2n+1 for some integer n, so ○ x∙y=(2m+1)(2n+1)=2(2m∙n+m+n)+1 is odd. • We only cover the case where x is odd • because the case where y is odd is similar. • The use phrase without loss of generality (WLOG) indicates this. Existence Proofs • Proof of theorems of the for ∃x P(x). • Constructive existence proof: ○ Find an explicit value of c, for which P(c) is true. ○ Then ∃x P(x) is true by Existential Generalization (EG). • Example: ○ Show that there is a positive integer that can be written as ○ the sum of cubes of positive integers in two different ways: ○ 1729=〖10〗^3+9^3=〖12〗^3+1^3 • Nonconstructive existence proof ○ In a nonconstructive existence proof, ○ we assume no c exists which makes P(c) true ○ and derive a contradiction. • Example ○ Show that there exist irrational numbers x,y such that x^y is rational. ○ We know that √2 is irrational. ○ Consider the number 〖√2〗^√2. ○ If 〖√2〗^√2 is rational § we have two irrational numbers x and y with x^y rational § namely x=√2 and y=√2. ○ If 〖√2〗^√2 is irrational § then we can let x=〖√2〗^√2 and y=√2 so that § x^y= (〖√2〗^√2 )^√2=〖√2〗^(√2×√2)=〖√2〗^2=2. Uniqueness Proofs • Some theorems asset the existence of • a unique element with a particular property, ∃!x P(x). • The two parts of a uniqueness proof are ○ Existence § We show that an element x with the property exists. ○ Uniqueness § We show that if y≠x, then y does not have the property. • Example ○ Show that if a and b are real numbers and a≠0, then ○ there is a unique real number r such that ar+b=0. ○ Existence § The real number r =−b/a is a solution of ar+b=0 § because a(−b/a)+b=−b+b=0. ○ Uniqueness § Suppose that s is a real number such that as+b=0. § Then ar+b=as+b, where r=−b/a. § Subtracting b from both sides § and dividing by a shows that r = s. Additional Proof Methods • Later we will see many other proof methods: • Mathematical induction ○ which is a useful method for proving statements of the form ∀n P(n), ○ where the domain consists of all positive integers. • Structural induction ○ which can be used to prove such results about recursively defined sets. • Cantor diagonalization ○ used to prove results about the size of infinite sets. • Combinatorial proofs use counting arguments.$