Notes Archives - Page 18 of 84 - Shawn Zhong

$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

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

Shawn Zhong

Shawn Zhong

Notes

Math 541 – 4/16

Math 541 – 4/11

9.1 Relations and Their Properties

7.1 An Introduction to Discrete Probability

Math 541 – 4/9

Search

WeChat Account