Onetone Blog

9.1 Relations and Their Properties

$Binary Relations • Definition ○ A binary relation R from a set A to a set B is a subset R⊆A×B. • Example ○ Let A={0,1,2} and B={a,b} ○ {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. ○ We can represent this relation graphically or using a table: • Note ○ Relations are more general than functions ○ A function is a relation where exactly one element of B is related to each element of A Binary Relation on a Set • Definition ○ A binary relation R on a set A is a subset of A×A or a relation from A to A. • Example 1 ○ Suppose that A={a,b,c} ○ Then R={(a,a),(a,b), (a,c)} is a relation on A • Example 2 ○ Let A={1, 2, 3, 4} ○ The ordered pairs in the relation R={(a,b)│a divides b} are ○ {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3),(4,4)} • Question: How many relations are there on a set A? ○ Because a relation on A is the same thing as a subset of A×A ○ We count the subsets of A×A. ○ Since A×A has n^2 elements when A has n elements ○ And a set with m elements has 2^m subsets ○ There are 2^(|A|^2 ) subsets of A×A. ○ Therefore, there are 2^(|A|^2 ) relations on a set A. • Example 3 ○ Consider these relations on the set of integers: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} § R_6={(a,b)│a+b≤3} ○ Note § These relations are on an infinite set and each of these relations is an infinite set § R_5 can be viewed as a function § Our definition of a function f:A→B is a subset of A×B § Therefore every function is a relation ○ Which of these relations contain each of the pairs § (1,1), (1, 2), (2, 1), (1, −1), and (2, 2)? ○ Solution § (1,1) is in R_1, R_3, R_4, and R_6 § (1,2) is in R_1 and R_6 § (2,1) is in R_2, R_5, and R_6 § (1, −1) is in R_2, R_3, and R_6 § (2,2) is in R_1, R_3, and R_4 Reflexive Relations • Definition ○ R is reflexive if and only if (a,a)∈R for every element a∈A ○ Written symbolically, R is reflexive if and only if ○ ∀x[x∈U→(x,x)∈R] • Note ○ If A = ∅ then the empty relation is reflexive vacuously. ○ That is the empty relation on an empty set is reflexive! • Example ○ The following relations on the integers are reflexive: § R_1={(a,b)│a≤b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following relations are not reflexive: § R_2={(a,b)│a b} (note that 3 ≯ 3) § R_5={(a,b)│a=b+1} (note that 3 ≠ 3 + 1) § R_6={(a,b)│a+b≤3} (note that 4+4≰3) Antireflexive Relations • Definition ○ R is antireflexive if and only if (a,a)∉R for every element a∈A ○ Written symbolically, R is antireflexive if and only if ○ ∀x[x∈U→(x,x)∉R] • Note ○ Antireflexive is different from not reflexive • Example ○ The following relations on the integers are antireflexive § R_2={(a,b)│a b} § R_5={(a,b)│a=b+1} ○ R_6={(a,b)│a+b≤3} is neither reflexive nor antireflexive Symmetric Relations • Definition ○ R is symmetric if and only if (b,a)∈R whenever (a,b)∈R,∀a,b∈A ○ Written symbolically, R is symmetric if and only if ○ ∀x∀y[(x,y)∈R→(y,x)∈R] • Example ○ The following relations on the integers are symmetric: § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_6={(a,b)│a+b≤3} ○ The following are not symmetric: § R_1={(a,b)│a≤b} (note that 3 ≤ 4, but 4 ≰ 3) § R_2={(a,b)│a b} (note that 4 3, but 3 ≯ 4) § R_5={(a,b)│a=b+1} (note that 4 = 3 + 1, but 3 ≠ 4 + 1) Antisymmetric Relations • Definition ○ R is antisymmetric if and only if a=b whenever (a,b),(b,a)∈R,∀a,b∈A ○ Written symbolically, R is antisymmetric if and only if ○ ∀x∀y[(x,y)∈R∧(y,x)∈R→x=y] • Note ○ For any integer, if a≥b and a≤b, then a=b • Example ○ The following relations on the integers are antisymmetric: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} ○ The following relations are not antisymmetric: § R_3={(a,b)│a=b or a=−b} (note that (1,−1),(−1,1)∈R_3) § R_6={(a,b)│a+b≤3} (note that (1,2),(2,1)∈R_6) Transitive Relations • Definition ○ R is transitive if and only if (a,c)∈R whenever (a,b),(b,c)∈R, ∀a,b,c∈A ○ Written symbolically, R is transitive if and only if ○ ∀x∀y∀z[(x,y)∈R∧(y,z)∈R→(x,z)∈R] • Note ○ For every integer, a≤b and b≤c, then b≤c • Example ○ The following relations on the integers are transitive: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following are not transitive: § R_5={(a,b)│a=b+1} (note that (3,2),(4,3)∈R_5, but (3,3)∉R_5), § R_6={(a,b)│a+b≤3} (note that (2,1),(1,2)∈R_6, but (2,2)∉R_6). Combining Relations • Given two relations R_1 and R_2 • We can combine them using basic set operations to form new relations • Example ○ Let A={1,2,3} and B={1,2,3,4} ○ The relations R_1 = {(1,1),(2,2),(3,3)} and R_2 = {(1,1),(1,2),(1,3),(1,4)} can be combined using basic set operations to form new relations: ○ R_1 ∪ R_2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} ○ R_1 ∩ R_2 ={(1,1)} ○ R_1 − R_2 ={(2,2),(3,3)} ○ R_2 − R_1 ={(1,2),(1,3),(1,4)} Inverse • Definition ○ Let R be a relation from A to B ○ The inverse of R is the relation § R^(−1)={(a,b)│(b,a)∈R} • Proposition ○ R is symmetric if and only if R=R^(−1) Composition • Definition ○ Suppose § R_1 is a relation from a set A to a set B. § R_2 is a relation from B to a set C ○ Then the composition of R_2 with R_1 is a relation from A to C where § if (x,y) is a member of R_1 § and (y,z) is a member of R_2 § then (x,z) is a member of R_2∘R_1 • Example ○ R_2∘R_1={(b,x),(b,z)} Powers of a Relation • Definition ○ Let R be a binary relation on A ○ Then the powers R_n of the relation R can be defined inductively by: ○ Basis Step: R_1=R ○ Inductive Step: R_(n+1)=R_n∘R • The powers of a transitive relation are subsets of the relation • This is established by the following theorem: • Theorem 1 ○ The relation R on a set A is transitive iff R_n⊆R for n = 1,2,3… ○ (see the text for a proof via mathematical induction)$

7.1 An Introduction to Discrete Probability

Probability of an Event • Introduction ○ We first study Pierre-Simon Laplace’s classical theory of probability ○ which he introduced in the 18th century, when he analyzed games of chance. • Experiment ○ A procedure that yields one of a given set of possible outcomes. • Sample space ○ The sample space of the experiment is the set of possible outcomes. • Event ○ An event is a subset of the sample space. • Probability ○ If S is a finite sample space of equally likely outcomes and E is an event ○ Then the probability of E is p(E)=|E|/|S| ○ For every event E, we have 0≤p(E)≤1 ○ This follows directly from the definition because ○ 0≤p(E)=|E|/|S| ≤|S|/|S| ≤1, since 0≤|E|≤|S| Applying Laplace’s Definition • Example 1 ○ An urn contains four blue balls and five red balls. ○ What is the probability that a ball chosen from the urn is blue? ○ The probability that the ball is chosen is 4/9 ○ since there are nine possible outcomes, and four of these produce a blue ball. • Example 2 ○ What is the probability that when two dice are rolled, the sum of the numbers on the two dice is 7? ○ By the product rule there are 62 = 36 possible outcomes. ○ Six of these sum to 7. ○ Hence, the probability of obtaining a 7 is 6/36 = 1/6. • Example 3 ○ In a lottery, a player wins a large prize when they pick four digits that match, in correct order, four digits selected by a random mechanical process. ○ What is the probability that a player wins the prize? ○ By the product rule there are 104 = 10,000 ways to pick four digits. ○ Since there is only 1 way to pick the correct digits, ○ the probability of winning the large prize is 1/10,000 = 0.0001. • Example 4 ○ A smaller prize is won if only three digits are matched. ○ What is the probability that a player wins the small prize? ○ If exactly three digits are matched, one of the four digits must be incorrect and the other three digits must be correct. ○ For the digit that is incorrect, there are 9 possible choices. ○ Hence, by the sum rule, there a total of 36 possible ways to choose four digits that match exactly three of the winning four digits. ○ The probability of winning the small price is § 36/10,000 = 9/2500 = 0.0036 • Example 5 ○ There are many lotteries that award prizes to people who correctly choose a set of six numbers out of the first n positive integers, where n is usually between 30 and 60. ○ What is the probability that a person picks the correct six numbers out of 40? ○ The number of ways to choose six numbers out of 40 is § C(40,6) = 40!/(34!6!) = 3,838,380. ○ Hence, the probability of picking a winning combination is § 1/ 3,838,380 ≈ 0.00000026. • Example 6 ○ What is the probability that the numbers 11, 4, 17, 39, and 23 are drawn in that order from a bin with 50 balls labeled with the numbers 1,2, …, 50 if ○ The ball selected is not returned to the bin. § Sampling without replacement: § The probability is 1/254,251,200 since there are § 50 ∙49 ∙47 ∙46 ∙45 = 254,251,200 ways to choose the five balls. ○ The ball selected is returned to the bin before the next ball is selected. § Sampling with replacement: § The probability is 1/〖50〗^5 = 1/312,500,000 since 〖50〗^5 = 312,500,000. The Probability of Complements and Unions of Events • Theorem 1 ○ Let E be an event in sample space S. ○ The probability of the complementary event of E:E ̅ = S − E is given by ○ p(E ̅ )=1−p(E) • Proof ○ Using the fact that |E ̅ |=|S|−|E| ○ p(E ̅ )=(|S|−|E|)/|S| =1−|E|/|S| =1−p(E) • Example ○ A sequence of 10 bits is chosen randomly. ○ What is the probability that at least one of these bits is 0? ○ Let E be the event that at least one of the 10 bits is 0. ○ Then E ̅ is the event that all of the bits are 1s. ○ The size of the sample space S is 210. Hence, ○ p(E)=1−p(E ̅ )=1−|E ̅ |/|S| =1−1/2^10 =1−1/1024=1023/1024 • Theorem 2 ○ Let E_1 and E_2 be events in the sample space S. Then ○ p(E_1∪E_2 )=p(E_1 )+p(E_2 )−p(E_1∩E_2 ) • Proof ○ Given the inclusion-exclusion formula from Section 2.2 ○ |A ∪ B| = |A| + |B| − |A ∩ B|, it follows that § p(E_1∪E_2 )=|E_1∪E_2 |/|S| § =(|E_1 |+|E_2 |−|E_1∩E_2 |)/|S| § =|E_1 |/|S| +|E_2 |/|S| −|E_1∩E_2 |/|S| § =p(E_1 )+p(E_2 )−p(E_1∩E_2 ) • Example ○ What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5? ○ Let E_1 be the event that the integer is divisible by 2 ○ Let E_2 be the event that it is divisible 5. ○ Then the event that the integer is divisible by 2 or 5 is E_1∪E_2 ○ And E_1∩E_2 is the event that it is divisible by 2 and 5. ○ It follows that: ○ p(E_1∪E_2 )=p(E_1 )+p(E_2 )−p(E_1∩E_2 )=50/100+20/100−10/100=3/5 Monty Hall Puzzle • You are asked to select one of the three doors to open. • There is a large prize behind one of the doors and if you select that door, you win the prize. • After you select a door, the game show host opens one of the other doors (which he knows is not the winning door). • The prize is not behind the door and he gives you the opportunity to switch your selection. • Should you switch? • You should switch. • The probability that your initial pick is correct is 1/3. • This is the same whether or not you switch doors. • But since the game show host always opens a door that does not have the prize, • If you switch the probability of winning will be 2/3 • Because you win if your initial pick was not the correct door • And the probability your initial pick was wrong is 2/3.

Math 541 – 4/9

$Lemma 58 • Statement ○ If G is an abelian group of order p^n, where p is a prime ○ Let a∈G has maximal order among all the elements of G ○ Then G≅A×Q, where A=⟨a⟩, Q≤G • Proof ○ We argue by induction on n ○ If n=1, then G=A, so we may take Q={1} ○ Now suppose n 1 ○ Case 1: ∃b∈G s.t. b∉A and b^p=1 § Let B≔⟨b⟩⊴G § A∩B={1} □ |b| is prime, since b^p=1 □ Recall: If (x,n)=1, then Z\/nZ=⟨x ̅ ⟩ □ So every non-identity element of B is a generator □ Thus, if x∈A∩B, and x≠1, then B=⟨x⟩⊂A∩B⊂A □ Then b∈A, which contradicts the assumption □ Therefore A∩B={1} § Let G ̅≔G\/B, then |G ̅ | |G| since B≠{1} § aB is an element of maximal order in G ̅ □ ├ |aB|┤ ||a|┤ ® a^|a| =1 ® ⇒a^|a| ∈B ® ⇒(aB)^|a| =1_G ̅ ® ⇒├ |aB|┤ ||a|┤ □ ├ |a|┤ ||aB|┤ ® (aB)^|aB| =1_G ̅ ® ⇒a^|aB| B=B ® ⇒a^|aB| ∈B ® ⇒a^|aB| ∈A∩B={1} ® ⇒a^|aB| =1 ® ⇒├ |a|┤ ||aB|┤ □ So |aB|=|a| □ Therefore aB is an element of maximal order in G ̅ § By induction, ∃Q ̅≤G ̅ s.t. G ̅≅⟨aB⟩×Q ̅ § Apply the Correspondence Theorem, choose Q≤G s.t. Q ̅=Q\/B § Claim: G≅A×Q □ By Lemma 55, we need only show A∩Q={1} and AQ=G □ A∩Q={1} ® Let g∈A∩Q, then g=a^i for some i ® Thus, a^i B∈⟨aB⟩∩Q ̅≤G ̅ ® Since G ̅≅⟨aB⟩×Q ̅, ⟨aB⟩∩Q ̅={1} ® Therefore a^i B=1_G ̅ ® ⇒├ |a|=|aB|┤ |i┤ ® ⇒a^i=1 ® ⇒A∩Q={1} □ AQ=G ® Let g∈G ® Since G ̅=⟨aB⟩×Q ̅, ® gB=a^i ByB for some a^i B∈⟨aB⟩ and yB∈Q ̅, ® Thus gB=a^i yB⟺g(a^i y)^(−1)∈B ® Choose b∈B s.t. ga^(−i) y^(−1)=b ® Then g=⏟(a^i )┬(∈A) ⏟yb┬(∈Q) ® Therefore AQ=G ○ Case 2: ∄b∈G s.t. b∉A and |b|=p § In this case, we need to prove G=A § By way of contradiction, suppose otherwise § Choose x∈G∖A with the smallest order § Recall: If H=⟨z⟩,then |⟨z^m ⟩|=|z|/((|z|,m) ) § |x^p | |x|, so x^p∈A § Choose i s.t. x^p=a^i § Say |a|=p^s § Since a has maximal order, x^(p^s )=1 § ⇒1=x^(p^s )=(x^p )^(p^(s−1) )=(a^i )^(p^(s−1) )=a^(ip^(s−1) ) § It follows that ├ p┤ |i┤ § So x^p=a^i, where ├ p┤ |i┤ § Set y≔a^(−i\/p) x, then y^p=a^(−i) x^p=1 § But y∉A, since ya^(i\/p)=x∉A § This contradicts the assumption that ∄b∈G s.t. b∉A and |b|=p § So G∖A=∅ § Therefore G=A=⟨a⟩, and Q={1} Theorem 59: Fundamental Theorem of Finite Abelian Groups • Statement ○ Every finite abelian group G is a product of cyclic groups • Proof ○ Say |G|=p_1^(m_1 )⋯p_n^(m_n ), where p_i are distinct primes ○ By Corollary 57, and induction G≅P_1×…×P_n where ○ P_i={x∈G│x^(p_i^(m_i ) )=1} and |P_i |=p_i^(m_i ) ○ So, it suffices to show each P_i is a product of cyclic groups ○ By Lemma 58, P_i≅A_i×Q_i, where A_i is cyclic ○ The result immediately follows by induction on m_i • Example ○ How may abelian groups of order 8 are there up to isomorphism ○ There are 3 abelian groups of order 8: Z8ℤ, Z2ℤ×Z4ℤ, Z2ℤ×Z2ℤ×Z2ℤ Corollary 60 • Partition ○ A partition of n∈Z( 0) is a way of writing n as a sum of positive integers ○ Example: 3 has 3 partitions: 3, 2+1, 1+1+1 • Statement ○ If n=p_1^(e_1 )⋯p_n^(e_m ), where p_i are distinct primes ○ Then the number of finite abelian groups of order n is ○ ∏_(i=1)^m▒〖number of partitions of e_i 〗 • Note ○ If (λ^1,…,λ^m ) are partitions of e_1,…,e_m, where λ_i={λ_i^1,…,λ_i^(s_i ) } ○ Then this list of partitions corresponds to the abelian group ○ (Z(p_1^(λ_1^1 ) Z×…×Z(p_1^(λ_1^(s_1 ) ) Z)×…×(Z(p_1^(λ_m^1 ) Z×…×Z(p_1^(λ_m^(s_m ) ) Z) • Example ○ When n=72=2^3⋅3^2 ○ Z2ℤ×Z2ℤ×Z2ℤ×Z3ℤ×Z3ℤ≅Z2ℤ×Z6ℤ×Z6ℤ ○ Z2ℤ×Z2ℤ×Z2ℤ×Z9ℤ ○ Z4ℤ×Z2ℤ×Z3ℤ×Z3ℤ ○ Z4ℤ×Z2ℤ×Z9ℤ ○ Z8ℤ×Z3ℤ×Z3ℤ ○ Z8ℤ×Z9ℤ$

Math 521 – 4/9

$Power Series • Given a sequence {c_n } of complex numbers • The series ∑_(n=1)^∞▒〖c_n z^n 〗 is a power series Theorem 3.39 (Convergence of Power Series) • Statement ○ Given the power sires ∑_(n=1)^∞▒〖c_n z^n 〗 ○ Put α≔(lim⁡sup)_(n→∞)⁡√(n&|c_n | ) ○ Let R≔1/α (If α=+∞,R=0; If α=0,R=+∞) ○ Then ∑_(n=1)^∞▒〖c_n z^n 〗 converges if |z| R and diverges if |z| R • Proof ○ Let a_n=c_n z^n and apply the root test ○ (lim⁡sup)_(n→∞)⁡√(n&|a_n | )=|z| (lim⁡sup)_(n→∞)⁡√(n&|c_n | )=|z|/R • Note: R is called the radius of convergence of the power series • Examples ○ ∑_(n=1)^∞▒〖n^n z^n 〗 has R=0 ○ ∑_(n=0)^∞▒z^n/n! has R=+∞ ○ ∑_(n=0)^∞▒z^n has R=1. If |z|=1, then the series diverges ○ ∑_(n=1)^∞▒z^n/n has R=1,diverges if z=1, converges for all other z with |z|=1 ○ ∑_(n=1)^∞▒z^n/n^z has R=1, but converges for all z with |z|=1 by comparison Theorem 3.43 (Alternating Series Test) • Statement ○ Suppose we have a real sequence {c_n } s.t. ○ |c_1 |≥|c_2 |≥|c_3 |≥… ○ c_(2m−1)≥0, c_2m≤0, ∀m∈N ○ lim_(n→∞)⁡〖c_n 〗=0 ○ Then ∑_(n=1)^∞▒c_n converges • Proof: HW • Example: alternating harmonic series ○ ∑_(n=1)^∞▒(−1)^(n+1)/n=1−1/2+1/3−1/4+1/5⋯converges to ln⁡2 Absolute Convergence • The series Σa_n is said to converge absolutely if the series Σ|a_n | converges • If Σa_n converges but Σ|a_n | diverges • We way that Σa_n converges nonabsolutely or conditionally Theorem 3.45 (Property of Absolute Convergence) • Statement ○ If Σa_n converges absolutely, then Σa_n converges • Proof ○ |∑_(k=1)^∞▒a_k |≤∑_(n=k)^∞▒|a_k | ○ The result follows by Cauchy Criterion Rearrangement • Let {k_n } be a sequence in which every natural number appears exactly once • Let a_n^′=a_(k_n ), then Σa_n^′ is called a rearrangement of Σa_n Theorem 3.54 (Riemann Series Theorem) • Let Σa_n be a series of real number which converges nonabsolutely • Let −∞≤α≤β≤+∞ • Then there exists a rearrangement Σa_n^′ s.t. • (lim⁡inf)_(n→∞)⁡〖s_n^′ 〗=α, (lim⁡sup)_(n→∞)⁡〖s_n^′ 〗=β Theorem 3.55 • If Σa_n is a series of complex numbers which converges absolutely • Then every rearrangement of Σa_n converges to the same sum$