Mathematics Archives - Page 31 of 60 - Shawn Zhong

2.1 Sets

$Sets • A set is an unordered collection of objects. ○ the students in this class ○ the chairs in this room • The objects in a set are called the elements, or members of the set. • A set is said to contain its elements. • The notation a∈A denotes that a is an element of the set A. • If a is not a member of A, write a∉A Describing a Set: Roster Method • S={a,b,c,d} • Order not important ○ S={a,b,c,d}={b,c,a,d} • Each distinct object is either a member or not; listing more than once does not change the set. ○ S={a,b,c,d}={a,b,c,b,c,d} • Dots (…) may be used to describe a set without listing all of the members when the pattern is clear. ○ S={a,b,c,d, …,z} Example of Roster Method • Set of all vowels in the English alphabet: ○ V={a,e,i,o,u} • Set of all odd positive integers less than 10: ○ O={1,3,5,7,9} • Set of all positive integers less than 100: ○ S={1,2,3,…,99} • Set of all integers less than 0: ○ S={…, −3,−2,−1} Some Important Sets • N = natural numbers = {0,1,2,3…} • Z = integers = {…,−3,−2,−1,0,1,2,3,…} • Z+= positive integers = {1,2,3,…} • R = set of real numbers • R+= set of positive real numbers • ℂ = set of complex numbers. • Q = set of rational numbers Set-Builder Notation • Specify the property or properties that all members must satisfy: ○ S = {x|x is a positive integer less than 100} ○ O = {x┤|x is an odd positive integer less than 10} ○ O = {x∈Z+ | x is odd and x10} • A predicate may be used: ○ S={x|P(x)} • All prime numbers ○ S={x│Prime(x) } • Positive rational numbers: ○ Q+={x∈R │x=p/q, for some positive integers p,q} Universal Set and Empty Set • The universal set U is the set containing everything currently under consideration. ○ Sometimes implicit ○ Sometimes explicitly stated. ○ Contents depend on the context. • The empty set is the set with no elements. • Symbolized ∅, but {} also used. • Venn Diagram Russell’s Paradox • Let S be the set of all sets which are not members of themselves. • A paradox results from trying to answer the question • “Is S a member of itself?” • Related Paradox: ○ Henry is a barber who shaves all people who do not shave themselves. ○ A paradox results from trying to answer the question ○ “Does Henry shave himself?” Some things to remember • Sets can be elements of sets. ○ {{1,2,3},a, {b,c}} ○ {NZQR • The empty set is different from a set containing the empty set. ○ ∅≠{∅} Set Equality • Two sets are equal if and only if they have the same elements. • Therefore if A and B are sets, then • A and B are equal if and only if ∀x(x∈A⟷x∈B) . • We write A = B if A and B are equal sets. ○ {1,3,5}={3,5,1} ○ {1,5,5,5,3,3,1}={1,3,5} Subsets • The set A is a subset of B, if and only if • every element of A is also an element of B. • The notation A⊆B is used to indicate that A is a subset of the set B. • A⊆B holds if and only if ∀x(x∈A→x∈B) is true. • Special Subsets ○ Because a∈∅ is always false, ∅⊆S, for every set S. ○ Because a∈S→a∈S,S⊆S, for every set S. Showing a Set is or is not a Subset of Another Set • Showing that A is a Subset of B ○ show that if x belongs to A, then x also belongs to B. • Showing that A is not a Subset of B ○ find an element x∈A with x∉B. ○ (Such an x is a counterexample to the claim that x∈A implies x ∈ B.) • Examples: ○ The set of all computer science majors at your school is a subset of all students at your school. ○ The set of integers with squares less than 100 is not a subset of the set of nonnegative integers. Another look at Equality of Sets • Recall that two sets A and B are equal, denoted by A=B, iff ○ ∀x(x∈A⟷x∈B) • Using logical equivalences we have that A=B iff ○ ∀x((x∈A→x∈B)∧(x∈B→x∈A)) • This is equivalent to ○ A⊆B and B⊆A Proper Subsets • If A⊆B, but A≠B, then we say A is a proper subset of B, denoted by A⊂B. • If A⊂B, then ∀x(x∈A→x∈B)∧∃(x∈B∧x∉A) is true. • Venn Diagram Set Cardinality • Finite and infinite ○ If there are exactly n distinct elements in S ○ where n is a nonnegative integer, we say that S is finite. ○ Otherwise it is infinite. • Definition ○ The cardinality of a finite set A, denoted by |A|, ○ is the number of (distinct) elements of A. • Examples: ○ |ø| = 0 ○ Let S be the letters of the English alphabet. Then |S|=26 ○ |{1,2,3}| = 3 ○ |{ø}| = 1 ○ The set of integers is infinite. Power Sets • The set of all subsets of a set A, denoted P(A), is called the power set of A. • Example ○ If A={a,b} then P(A)= {ø, {a},{b},{a,b}} • If a set has n elements, then the cardinality of the power set is 2^n. • (In Chapters 5 and 6, we will discuss different ways to show this.) Tuples • The ordered n-tuple (a_1,a_2,…,a_n) is the ordered collection that ○ has a_1 as its first element ○ and a_2 as its second element ○ and so on until an as its last element. • Two n-tuples are equal if and only if their corresponding elements are equal. • 2-tuples are called ordered pairs. • The ordered pairs (a,b) and (c,d) are equal if and only if a=c and b=d. • Note: (a,b)={a,{a,b}} Cartesian Product • Cartesian Product of two sets ○ The Cartesian Product of two sets A and B, denoted by A×B is ○ the set of ordered pairs (a,b) where a∈A and b∈B . ○ A×B={(a,b)│a∈A∧b∈B} • Example: ○ A={a,b} ○ B={1,2,3} ○ A×B={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)} • Cartesian Product of more sets ○ The cartesian products of the sets A_1,A_2,…,A_n ○ denoted by A_1×A_2×…×A_n ○ is the set of ordered n-tuples (a_1,a_2,…,a_n ) ○ where a_i belongs to A_i for i=1,2, …,n ○ A_1×A_2×…×A_n={(a_1,a_2,…,a_n )│a_i∈A_i for i=1,2,…,n} • Example ○ What is A × B × C where A = {0,1}, B = {1,2} and C = {0,1,2} ○ A×B×C= {(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)}$

Math 521 – 2/7

$Complex Numbers ℂ • Definition ○ If z∈ℂ, then z=a+bi where a,b∈R and i^2=−1 • Real part and imaginary part ○ For z=a+bi ○ Re(z)=a is the real part of z ○ Im(z)=b is the imaginary part of z • Complex conjugate ○ z ̅=a−bi is the complex conjugate of z ○ zz ̅=(a+bi)(a−bi)=a^2+b^2 • Absolute value ○ |z|=√(zz ̅ )=√(a^2+b^2 ) is the absolute value of z ○ Note § For a real number x § |x|=√(x^2+0^2 )=√(x^2 )≥0 § |x|={■8(x&if x≥0@−x&if x0)┤ • Complex division ○ If z=a+bi, w=c+di∈ℂ, then ○ z/w=(zw ̅)/(ww ̅ )=(a+bi)(c−di)/(c+di)(c−di) =(ac+bd)/(c^2+d^2 )+(bc−ad)/(c^2+d^2 ) i Theorem 1.31 • If z and w are complex numbers, then ○ (z+w) ̅=z ̅+w ̅ ○ (zw) ̅=z ̅⋅w ̅ ○ z+z ̅=2Re(z), z−z ̅=2i Im(z) ○ zz ̅ is real and positive (except when z=0) Theorem 1.33 • If z and w are complex numbers, then (1) |z|0 unless z=0 in which case |z|=0 (2) |z ̅ |=|z| (3) |zw|=|z||w| § Let z=a+bi, w=c+di § Then zw=(ac−bd)+(ad+bc)i § |zw|=√((ac−bd)^2+(ad+bc)^2 ) § =√(a^2 c^2+b^2 d^2+a^2 d^2+b^2 c^2 ) § =√((a^2+b^2 )(c^2+d^2 ) ) § =√(a^2+b^2 ) √(c^2+d^2 ) § =|z||w| (4) |Re(z)|≤|z| (5) |z+w|≤|z|+|w| (Triangle Inequality) § |z+w|^2=(z+w)((z+w) ̅ ) § =(z+w)(z ̅+w ̅ ) § =zz ̅+zw ̅+z ̅w+ww ̅ § =|z|^2+|w|^2+zw ̅+z ̅w § =|z|^2+|w|^2+2Re(zw ̅ ) § ≤|z|^2+|w|^2+2|zw ̅ | by (4) § =|z|^2+|w|^2+2|z||w ̅ | by (3) § =|z|^2+|w|^2+2|z||w| by (2) § =(|z|+|w|)^2 § So |z+w|^2≤(|z|+|w|)^2 § Thus, |z+w|≤|z|+|w|∎ Euclidean Spaces • Inner product ○ If x ⃗,y ⃗∈Rn with § x ⃗=(x_1,x_2,…,x_n ) § y ⃗=(y_1,y_2,…,y_n ) ○ Then the inner product of x ⃗ and y ⃗ is § x ⃗⋅y ⃗=∑_(i=1)^n▒〖x_i y_i 〗 • Norm ○ If x ⃗∈Rn, we define the norm of x ⃗ to be ○ |x ⃗ |=√(x ⃗⋅x ⃗ ) • Euclidean spaces ○ The vector space Rn with inner product and norm ○ is called Euclidean n-space Theorem 1.37 • Suppose x ⃗,y ⃗,z ⃗∈Rn,α∈R, then (1) |x ⃗ |≥0 (2) |x ⃗ |=0 if and only if x ⃗=0 ⃗ (3) |αx ⃗ |=|α|⋅|x ⃗ | (4) |x ⃗⋅y ⃗ |≤|x ⃗ |⋅|y ⃗ | (Schwarz$

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.$

1.7 Introduction to Proofs

Proofs of Mathematical Statements • A proof is a valid argument that establishes the truth of a statement. • In math, CS, and other disciplines, informal proofs which are generally shorter, are generally used. ○ More than one rule of inference are often used in a step. ○ Steps may be skipped. ○ The rules of inference used are not explicitly stated. ○ Easier for to understand and to explain to people. ○ But it is also easier to introduce errors. Definitions • A theorem is a statement that can be shown to be true using: ○ definitions ○ other theorems ○ axioms (statements which are given as true) ○ rules of inference • A lemma is a ‘helping theorem’ or a result which is needed to prove a theorem. • A corollary is a result which follows directly from a theorem. • Less important theorems are sometimes called propositions. • A conjecture is a statement that is being proposed to be true. • Once a proof of a conjecture is found, it becomes a theorem, it may turn out to be false. Forms of Theorems • Many theorems assert that a property holds for all elements in a domain, such as the integers, the real numbers, or some of the discrete structures that we will study in this class. • Often the universal quantifier (needed for a precise statement of a theorem) is omitted by standard mathematical convention. • For example, the statement: ○ “If xy, where x and y are positive real numbers, then x^2y^2” ○ really means ○ “For all positive real numbers x and y, if xy, then x^2y^2.” Proving Theorems • Many theorems have the form: ∀x(P(x)→Q(x)) • To prove them, we show that P(c)→Q(c) where c is an arbitrary element of the domain, • By universal generalization the truth of the original formula follows. • So, we must prove something of the form: p→q Proving Conditional Statements: p→q • Trivial Proof ○ If we know q is true, then p→q is true as well. ○ “If it is raining then 1=1. • Vacuous Proof ○ If we know p is false then p→q is true as well. ○ “If I am both rich and poor then 2 + 2 = 5.” • Even though these examples seem silly, both trivial and vacuous proofs are often used in mathematical induction, as we will see in Chapter 5 • Direct Proof Assume that p is true. Use rules of inference, axioms, and logical equivalences to show that q must also be true. • Example 1 of Direct Proof ○ Give a direct proof of the theorem “If n is an odd integer, then n^2 is odd.” ○ Assume that n is odd. Then n=2k+1 for an integer k. ○ Squaring both sides of the equation, we get: § n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1=2r+1, § where r=2k^2+2k , an integer. ○ We have proved that if n is an odd integer, then n^2 is an odd integer. • Example 2 of Direct Proof ○ Prove that the sum of two rational numbers is rational. ○ Assume x and y are two rational numbers. ○ Then there must be integers p,q,r,s such that x=p/q, y=r/s and s≠0, p≠0 ○ x+y=p/q+r/s=(ps+qr)/qs, where q,s≠0, and (ps+qr),qs are integers ○ Hence, x+y is rational • Proof by Contraposition ○ Assume ¬q and show ¬p is true also. ○ This is sometimes called an indirect proof method. ○ If we give a direct proof of ¬q→¬p then we have a proof of p→q. • Example of Proof by Contraposition ○ Prove that for an integer n, if n^2 is odd, then n is odd. ○ Use proof by contraposition. ○ Assume n is even (i.e., not odd). ○ Therefore, there exists an integer k such that n=2k. ○ Hence, n^2=4k^2=2(2k^2), and n^2 is even(i.e., not odd). ○ We have shown that if n is an even integer, then n^2 is even. ○ Therefore by contraposition, for an integer n, if n^2 is odd, then n is odd. • Proof by Contradiction: (AKA reductio ad absurdum). ○ To prove p, assume ¬p and derive a contradiction such as p∧¬p. (an indirect form of proof). ○ Since we have shown that ¬p→F is true, ○ it follows that the contrapositive T→p also holds. • Example of Proof by Contradiction ○ Use a proof by contradiction to give a proof that √2 is irrational. ○ Towards a contradiction assume that √2 is rational ○ Let a,b be such that √2=a/b, b≠0, and a,b have no common factors ○ 2=a^2/b^2 ⇒2b^2=a^2, so a^2 is even and a is even ○ Let a≔2k for some k∈Z, then a^2=4k^2 ○ Then 2b^2=4k^2⇒b^2=2k, so b^2 is even, and b is also even ○ So 2 divides a and b, which makes a contradiction ∎ Theorems that are Biconditional Statements • To prove a theorem that is a biconditional statement, that is, a statement of the form p↔q, we show that p→q and q→p are both true. • Example ○ Prove the theorem: “If n is an integer, then n is odd if and only if n^2 is odd.” ○ We have already shown (previous slides) that both p→q and q→p. ○ Therefore we can conclude p ↔ q. • Note ○ Sometimes iff is used as an abbreviation for “if an only if,” as in “If n is an integer, then n is odd iif n^2 is odd.” Looking Ahead • If direct methods of proof do not work: • We may need a clever use of a proof by contraposition. • Or a proof by contradiction. • In the next section, we will see strategies that can be used when straightforward approaches do not work. • In Chapter 5, we will see mathematical induction and related techniques. • In Chapter 6, we will see combinatorial proofs

Shawn Zhong

Shawn Zhong

Mathematics

2.1 Sets

Math 521 – 2/7

Math 541 – 2/7

1.8 Proof Methods and Strategy

1.7 Introduction to Proofs

Search

WeChat Account