Math 541 – 4/25 Apr 30, 2018 Shawn Math 541 No comments yet Math 541 – 4/23 Apr 29, 2018 Shawn Math 541 No comments yet 9.5 Equivalence Relations Apr 23, 2018 Shawn Math 240 No comments yet 9.3 Representing Relations Apr 23, 2018 Shawn Math 240 No comments yet Math 541 – 4/20 Apr 22, 2018 Shawn Math 541 No comments yet 1 … 14 15 16 17 18 … 84
![Polynomial Ring • Polynomials over a ring ○ Let R be a commutative ring ○ A polynomial over R is a sum a_n x^n+a_(n−1) x^(n−1)+…+a_1 x+a_0 ○ Where x is a variable, and a_i∈R • Degree ○ If f=a_n x^n+a_(n−1) x^(n−1)+…+a_1 x+a_0 is a polynomial over R ○ The degree of f, denoted deg(g), is sup{n≥0│a_n≠0} ○ Note: deg(0)=−∞ • Leading term and leading coefficient ○ If deg(f)=n≥0 ○ The leading term of f is a_n x^n ○ The leading coefficient of f is a_n • Notation ○ Let R[x]≔{Polynomials over a commutative ring R} ○ Then R[x] is a commutative ring with ○ ordinary addition and multiplication of polynomials • R is a subring of R[x] ○ R is identified with the constant polynomials ○ There is a ring homomorphism i:R→R[x] defined as ○ mapping the ring element r∈R to the constant polynomial r ○ The constant polynomials in R[x] form a subring ○ And i gives an isomorphism between R and the subring • Polynomial ring with multiple variables ○ We define polynomial rings in several variables inductively ○ R[x_1,x_2 ]=(R[x_1 ])[x_2 ] ○ ⋮ ○ R[x_1,…,x_n ]=(R[x_1,…,x_(n−1) ])[x_n ] Proposition 67: Properties of Polynomial Rings • Statement ○ Let R be a domain. Let p,q∈R[x]∖{0}, then 1. deg(pq)=deg(p)+deg(q) 2. (R[x])^×=R^× 3. R[x] is a domain • Proof ○ Write § p=a_n x^n+…+a_1 x+a_0, where deg(p)=n § q=b_m x^m+…+b_1 x+b_0, where deg(q)=m ○ Then a_n≠0 and b_m≠0 ○ Since R is a domain, a_n m_m≠0 ○ So, the leading term of pq is a_n b_m x^(m+n), which verifies (1) ○ Also, a_n b_m x^(m+n)≠0. This proves (3) ○ For (2), suppose pq=1, then § deg(p)+deg(q)=deg(pq)=0 by (1) § Thus, deg(p)=0=deg(q) i.e. p,q∈R § Since pq=1, p,q∈R^× § Thus (R[x])^×⊆R^× § Also, R^×⊆(R[x])^× § Therefore (R[x])^×=R^× Ideal • Definition ○ Let R be a ring, let I be a subset of R, and let r∈R ○ rI≔{rx│x∈I} is a left ideal of R if § I is a additive subgroup of R § rI=I, ∀r∈R ○ Right ideal Ir≔{xr│x∈I} are defined similarly ○ I is an ideal if I is both a left and right ideal • Intuition ○ Normal subgroups are to groups as ideals are to rings • Example ○ If R is a ring, then R and {0} are both ideals Proposition 68 • Statement ○ If I⊆R is an ideal, then I=R⟺1∈I • Proof ○ (⟹) Trivial ○ (⟸) Let r∈R. ○ By definition of ideal, rI=I ○ So r=r⋅1∈I ○ Thus R=I • In particular, if R is a ring, and S is a subring of R ○ S is an ideal in R⟺S=R (subrings contain 1) ○ Similarly, if I⊆R is an ideal, and I is a subring of R⟺I=R Principal Ideal • Definition ○ Let R is a commutative ring, and let r∈R, then ○ (r)≔{ar│a∈R} is called the principal ideal generated by r • Proof: principal ideals are ideals ○ 0=0⋅r∈(r), so (r) is not empty ○ Let ar,br∈(r), then § ar−br=(a−b)r∈(r) § Therefore, (r) is an additive subgroup of R ○ Let a∈R, br∈(r), then § a(br)=abr∈(r) § (br)a=bra=abr∈(r) § So a(r)=(r)a,∀a∈R • Example ○ If n∈Z, (n) is just the cyclic subgroup generated by n](https://shawnzhong.com/wp-content/uploads/2018/05/img_5aec78da6ebc7.png)
![Equivalence Relations • Definition 1 ○ A relation on a set A is called an equivalence relation if ○ it is reflexive, symmetric, and transitive • Definition 2 ○ Two elements a,b that are related by an equivalence relation are called equivalent ○ The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation. Strings • Example ○ Suppose that R is the relation on the set of strings of English letters such that ○ aRb if and only if l(a) = l(b), where l(x) is the length of the string x. ○ Is R an equivalence relation? • Solution ○ Show that all of the properties of an equivalence relation hold ○ Reflexivity § Because l(a)=l(a), it follows that aRa for all strings a. ○ Symmetry § Suppose that aRb. Since l(a)=l(b), l(b)=l(a) also holds and bRa. ○ Transitivity § Suppose that aRb and bRc § Since l(a)=l(b),and l(b)=l(c), l(a)=l(a) also holds and aRc. Congruence Modulo m • Example ○ Let m be an integer with m 1 ○ Show that the relation ○ R={(a,b)│a≡b (mod m) } ○ is an equivalence relation on the set of integers. • Solution ○ Recall that a≡b (mod m) if and only if m divides a−b ○ Reflexivity § a≡a (mod m) since a−a=0 is divisible by m since 0 = 0 ∙ m. ○ Symmetry § Suppose that a≡b (mod m) § Then a−b is divisible by m, and so a−b=km, where k is an integer § It follows that b−a=(−k)m, so b≡a (mod m). ○ Transitivity § Suppose that a≡b (mod m) and b≡c (mod m). § Then m divides both a−b and b−c. § Hence, there are integers k and l with a−b=km and b−c=lm § We obtain by adding the equations: § a−c=(a−b)+(b−c)=km+lm=(k+l)m § Therefore, a≡c (mod m) Divides • Example ○ Show that the “divides” relation on the set of positive integers is not an equivalence relation. • Solution ○ The properties of reflexivity, and transitivity do hold, but there relation is not transitive. ○ Hence, “divides” is not an equivalence relation. ○ Reflexivity § a ∣ a for all a. ○ Not Symmetric § For example, 2 ∣ 4, but 4 ∤ 2 § Hence, the relation is not symmetric. ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b=ak and c=bl. § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. Equivalence Classes • Let R be an equivalence relation on a set A. • The set of all elements that are related to an element a of A is called the equivalence class of a • The equivalence class of a with respect to R is denoted by [a]_R. • When only one relation is under consideration, we can write [a], without the subscript R • Note that [a]_R={s|(a,s)∈R} • If b∈[a]_R, then b is called a representative of this equivalence class. • Any element of a class can be used as a representative of the class. • The equivalence classes of the relation congruence modulo m are called the congruence classes modulo m. • The congruence class of an integer a modulo m is denoted by [a]_m • So [a]_m={…,a−2m,a−m,a+2m,a+2m,…} • For example, ○ [0]_4 = {…, −8, −4 , 0, 4 , 8 , …} ○ [1]_4 = {…, −7, −3 , 1, 5 , 9 , …} ○ [2]_4 = {…, −6, −2 , 2, 6 , 10 , …} ○ [3]_4 = {…, −5, −1 , 3, 7 , 11 , …} Equivalence Classes and Partitions • Theorem 1 ○ Let R be an equivalence relation on a set A. ○ These statements for elements a and b of A are equivalent: i) aRb ii) [a]=[b] iii) [a]∩[b]=∅ • Proof ○ We show that (i) implies (ii). ○ Assume that aRb. ○ Now suppose that c ∈ [a].Then aRc. Because aRb and R is symmetric, bRa. ○ Because R is transitive and bRa and aRc, it follows that bRc. ○ Hence, c ∈ [b]. Therefore, [a]⊆ [b]. ○ A similar argument (omitted here) shows that [b]⊆ [a]. ○ Since [a]⊆ [b] and [b]⊆ [a], we have shown that [a] = [b]. Partition of a Set • A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union. • In other words, the collection of subsets A_i, where i∈I, forms a partition of S if and only if ○ A_i≠∅ for i∈I, ○ A_i∩A_j=∅ when i≠j, ○ ⋃8_(i∈I)▒A_i =S An Equivalence Relation Partitions a Set • Let R be an equivalence relation on a set A. • The union of all the equivalence classes of R is all of A • Since an element a of A is in its own equivalence class [a]_R. In other words, ○ ⋃8_(a∈A)▒[a]_R =A • From Theorem 1, it follows that these equivalence classes are either equal or disjoint • So [a]_R∩[b]_R=∅ when [a]_R≠[b]_R. • Therefore, the equivalence classes form a partition of A • Because they split A into disjoint subsets. Equivalence Relation and Partition • Theorem 2 ○ Let R be an equivalence relation on a set S. ○ Then the equivalence classes of R form a partition of S. ○ Conversely, given a partition {A_i│i∈I} of the set S ○ There is an equivalence relation R that has the sets A_i, i∈I, as its equivalence classes. • Proof ○ We have already shown the first part of the theorem. ○ For the second part, assume that {A_i│i∈I} is a partition of S. ○ Let R be the relation on S consisting of the pairs (x, y) ○ where x and y belong to the same subset A_i in the partition. ○ We must show that R satisfies the properties of an equivalence relation. ○ Reflexivity § For every a∈S, (a,a)∈R, because a is in the same subset as itself. ○ Symmetry § If (a,b)∈R, then b and a are in the same subset of the partition, so (b,a)∈R ○ Transitivity § If (a,b)∈R and (b,c)∈R, then a and b are in the same subset of the partition, as are b and c. § Since the subsets are disjoint and b belongs to both, the two subsets of the partition must be identical. § Therefore, (a,c)∈R since a and c belong to the same subset of the partition.](https://shawnzhong.com/wp-content/uploads/2018/04/img_5addedc1250d8.png)
![Representing Relations Using Matrices • A relation between finite sets can be represented using a zero-one matrix. • Suppose R is a relation from A={a_1,a_2,…,a_m } to B={b_1,b_2,…,b_n } ○ The elements of the two sets can be listed in any arbitrary order ○ When A=B, we use the same ordering. • The relation R is represented by the matrix ○ M_R = [m_ij], where ○ m_ij={■8(1&if (a_i,b_j )∈R@0&if (a_i,b_j )∉R)┤ • The matrix representing R has ○ a 1 as its (i,j) entry when a_i is related to b_j ○ a 0 if a_i is not related to b_j. Examples of Representing Relations Using Matrices • Example 1 ○ Suppose that A = {1,2,3} and B = {1,2} ○ Let R be the relation from A to B containing (a,b) if a b. ○ What is the matrix representing R (with increasing numerical order) • Solution ○ Because R={(2,1), (3,1),(3,2)}, the matrix is ○ M_R=[■8(0&0@1&0@1&1)] • Example 2 ○ Let A={a_1,a_2, a_3} and B={b_1,b_2, b_3,b_4, b_5}. ○ Which ordered pairs are in the relation R represented by the matrix ○ M_R=[■8(0&1&0&0&0@1&0&1&1&0@1&0&1&0&1)] • Solution ○ Because R consists of those ordered pairs (a_i,b_j) with m_ij = 1 ○ R={(a_1, b_2), (a_2, b_1),(a_2, b_3), (a_2, b_4),(a_3, b_1), {(a_3, b_3 ), (a_3, b_5 )} Matrices of Relations on Sets • If R is a reflexive relation, all the elements on the main diagonal of M_R are equal to 1 • R is a symmetric relation, if and only if m_ij = 1 whenever m_ji = 1 • R is an antisymmetric relation, if and only if m_ij = 0 or m_ji = 0 when i≠j Example of a Relation on a Set • Example 3: Suppose that the relation R on a set is represented by the matrix ○ M_R=[■8(1&1&0@1&1&1@0&1&1)] • Is R reflexive, symmetric, and/or antisymmetric? • Because all the diagonal elements are equal to 1, R is reflexive • Because M_R is symmetric, R is symmetric • R not antisymmetric because both m_1,2 and m_2,1 are 1 Representing Relations Using Digraphs Definition ○ A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). ○ The vertex a is called the initial vertex of the edge (a,b) ○ The vertex b is called the terminal vertex of this edge. ○ An edge of the form (a,a) is called a loop. Example 1 ○ A drawing of the directed graph with vertices a, b, c, and d ○ and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is shown here. Example 2 ○ What are the ordered pairs in the relation represented by this directed graph? § ○ The ordered pairs in the relation are ○ (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) Determining which Properties a Relation has from its Digraph • Reflexivity: A loop must be present at all vertices in the graph. • Symmetry: If (x,y) is an edge, then so is (y,x). • Antisymmetry: If (x,y) with x≠y is an edge, then (y,x) is not an edge. • Transitivity: If (x,y) and (y,z) are edges, then so is (x,z) Determining which Properties a Relation has from its Digraph • Example 1 ○ Reflexive? No, not every vertex has a loop ○ Symmetric? Yes (trivially), there is no edge from one vertex to another ○ Antisymmetric? Yes (trivially), there is no edge from one vertex to another ○ Transitive? Yes, (trivially) since there is no edge from one vertex to another • Example 2 ○ Reflexive? No, there are no loops ○ Symmetric? No, there is an edge from a to b, but not from b to a ○ Antisymmetric? No, there is an edge from d to b and b to d ○ Transitive? No, there are edges from a to c and from c to b, but there is no edge from a to d • Example 3 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from c to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? No, there is no edge from a to b • Example 4 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from d to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? Yes (trivially), there are no two edges where the first edge ends at the vertex where the second edge begins Closures • Definition ○ The closure of a relation R on A with respect to property P ○ is the least relation on A that contains R and has property P • Note ○ Least relation R^′ on A s.t. ○ R⊆R′ ○ R′ has property P ○ If S is a relation that safisfies the condition above, then R^′⊆S • Example ○ The reflexive closure of R is just R∪{(a,a)│a,∈A} ○ The symmetric closure of R is R∪R^(−1) ○ The transitive closure of R is R∪R^2∪R^3∪… Path in Directed Graphs • Definition ○ A path from a to b is a directed graph G is a sequence of edges ○ (a=x_0,x_1 ),(x_1,x_2 ),…,(x_(n−1),x_n=b) where n 0 ○ We denote the path by x_0,x_1,…,x_n say that the path has length n • Theorem ○ Let R be a relation on a set A ○ There is a path of length n from a to b if and only if (a,b) is an element of R^n The Connectivity Relation • Definition ○ Let R be a relation on A ○ The connectivity relation R^∗ cibsusts if all elements (a,b) s.t. ○ There is a path from a to b in R ○ In other words, R^∗ is the union of R,R^2,R^3,… ○ R^∗=⋃24_(i=1)^∞▒R^((i) ) • Example 1 ○ Let R be the relation between US state such that (a,b) is in R if a and b share a border. What is R^∗? ○ All pairs of states except Alaska and Hawaii • Example 2 ○ Let R be the relation between integers s.t. (a,b) is in R if b=a+1 ○ What is R^2, R^n, R^∗ ○ R^2={(a,b)│b=a+2} ○ R^n={(a,b)│b=a+n} ○ R^∗={(a,b)│a b} • Transitive closure ○ The connectivity relation R^∗ is exactly the transitive closure of R ○ We need to show that R is a subset of R^∗, R^∗ is transitive and least with that property. ○ The first two are easy ○ Let S be a transitive relation containing R ○ By induction we show that S contains R^n for every n Computing The Connectivity Relation • Theorem ○ Let R be a relation on A and let n be the number of elements in A. ○ The connectivity relation R^∗ is the union of R,R^2,…,R^n • Proof ○ Let (a,b) be the element of R^∗ ○ Let a_0=x_0,x_1,…,x_m=b be the shortest path witnessing this. ○ If m n, then two of the vertices among x_1,…,x_m must be the same, say x_i=x_j ○ But then we can find a shorter path x_0,x_1,…,x_i=x_j,x_(j+1),x_n • Corollary ○ M_(R^∗ )=M_R∨M_R^[2] ∨…∨M_R^[n] • Example ○ Compute M_(R^∗ ) for the relation R={(a,b),(b,c),(c,d),(d,b)} ○ M_R=[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)] ○ M_R^[2] =[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]⨀[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]=[■8(0&0&1&0@0&0&0&1@0&1&0&0@0&0&1&0)] ○ Similarly, compute M_R^[3] ,M_R^[4] ○ Then M_(R^∗ )=M_R∨M_R^[2] ∨M_R^[3] ∨M_R^[4]](https://shawnzhong.com/wp-content/uploads/2018/04/img_5added4674c91.png)
