2.6 Equivalence relation 1. Equivalence relation Definition 2.18: A relation r on a set a is called an equivalence relation if it is reflexive symmetric, and transitive. Example: Let m be a positive integer with m>l Show that congruence modulo m is an equivalence relation. R=(a, b )la=b mod m) Proof: (Reflexive (for any aEZ, aRa?) 2)symmetric (for any arb, bRa?) transitive(for arb, bRc, arc?)
2.6 Equivalence Relation 1.Equivalence relation Definition 2.18: A relation R on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. Example: Let m be a positive integer with m>1. Show that congruence modulo m is an equivalence relation. R={(a,b)|ab mod m} Proof: (1)reflexive (for any aZ，aRa?) (2)symmetric (for any aRb， bRa?) (3)transitive (for aRb，bRc，aRc?)
2. Equivalence classes partition Definition 2. 19: A partition or quotient set of a nonempty set A is a collection II of nonempty subsets ofa such that (1) DEach element of a belongs to one of the sets in II. (2)IfAi and Ai are distinct elements of Il, then A∩A: The sets in l are called the bocks or cells of the partition. Example: Let A=a, b,c), P={a,b},c},S={a},{b},{c},T={a,b,c}, U={a,(},V={a,b},{b,},W={a,b},{a,c},(C}, nfinite
2.Equivalence classes partition Definition 2.19: A partition or quotient set of a nonempty set A is a collection of nonempty subsets of A such that (1)Each element of A belongs to one of the sets in . (2)If Ai and Aj are distinct elements of , then Ai∩Aj=. The sets in are called the bocks or cells of the partition. Example: Let A={a,b,c}, P={{a,b},{c}},S={{a},{b},{c}},T={{a,b,c}}, U={{a},{c}},V={{a,b},{b,c}},W={{a,b},{a,c},{c}}, infinite
Example: congruence modulo 2 is an equivalence relation For any xEZ, or x=0 mod 2,or x=I mod 2, le or x∈E,orx∈O. AndE∩O= E and o RE, O is a partition of Z
Example：congruence modulo 2 is an equivalence relation. For any xZ, or x=0 mod 2,or x=1 mod 2, i.e or xE ,or xO. And E∩O= E and O， {E, O} is a partition of Z
Definition 2. 20: Let r be an equivalence relation on a set a. The set of all element 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 lairs When only one relation is under consideration, we will delete the subscript r and write a for this equivalence class. Example: equivalence classes of congruence modulo 2 are 0 and 1 0}={…-4,-2,0,2,4,}=[2=4]=-2=|-4}= ={,-3,-1,1,3,}=|3=-1l-3}= the partition of ZIL/R=o1
Definition 2.20: Let R be an equivalence relation on a set A. The set of all element 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 will delete the subscript R and write [a] for this equivalence class. Example：equivalence classes of congruence modulo 2 are [0] and [1]。 [0]={…,-4,-2,0,2,4,…}=[2]=[4]=[-2]=[-4]=… [1]={…,-3,-1,1,3,…}=[3]=[-1]=[-3]=… the partition of Z =Z/R={[0],[1]}
Example: equivalence classes of congruence modulo n are 0}={…,-2n,-n,0,n,2n,} I={…,-2n+1,n+1,1,n+1,2n+1,} n-1]l={…,-n-1,1,n-1,2n-1,3n-1,} A partition or quotient set of Z, Z/R={01,1l…,n-1
Example: equivalence classes of congruence modulo n are： [0]={…,-2n,-n,0,n,2n,…} [1]={…,-2n+1,-n+1,1,n+1,2n+1,…} … [n-1]={…,-n-1,-1,n-1,2n-1,3n-1,…} A partition or quotient set of Z, Z/R={[0],[1],…,[n-1]}
Theorem 2.11: LetR be an equivalence relation on A. Then (1) For any a∈A,a∈al; (2)IfaR b, then a=bl; 3)Fora,b∈A,If(a2b)R,then[a∩b=; (4)∪a=A Proof: (1)For any aEA, ara (2)For a, bEA, arb, as?b], bc?al For any x∈|a],x∈?[b] when arb,ie,xRb for any x∈b],x∈?| a] when arb,i,e.xRa 3Fora,b∈A,If(a2b)gR,then[a∩b= Reduction to absurdity Suppose a]∩bl≠, Then there exists x∈a]∩b] (4)
Theorem 2.11：Let R be an equivalence relation on A. Then (1)For any aA, a[a]; (2)If a R b, then [a]=[b]; (3)For a,bA, If (a,b)R, then [a]∩[b]=; Proof：(1)For any aA，aRa? (2)For a,bA, aRb, [a]?[b]，[b]?[a] For any x[a] ,x?[b] when aRb，i.e. x R b for any x[b], x?[a] when aRb，i,.e.xRa (3)For a,bA, If (a,b)R, then [a]∩[b]= Reduction to absurdity Suppose [a]∩[b]≠, Then there exists x[a]∩[b]. (4) a A a A = (4)[ ]
The equivalence classes of an equivalence relation on a set form a partition of the set Equivalence relation =partition R={(1,1)(2,2)3)(4 and let Example: LetA=(1, 2, 3, 4) (1,3),(2,4),(3,1),(4,2)} is an equivalence relation Then the equivalence classes are
The equivalence classes of an equivalence relation on a set form a partition of the set. Equivalence relation partition Example：Let A={1,2,3,4}, and let R={(1,1),(2,2),(3,3),(4,4), (1,3),(2,4),(3,1),(4,2)} is an equivalence relation. Then the equivalence classes are:
Conversely, every partition on a set can be used to form an equivalence relation. Let I=A,A2.A be a partition of a nonempty set A. Let r be a relation on A, and arb if only if there exists A; Ell s.t. a,b∈A ie.R=(A1×A1)∪U(A2×A2)U….∪(An×An) R is an equivalence relation on A Theorem 2.12: Given a partition AiEZ of the set A, there is an equivalence relation R that has the set A s iEZ, as its equivalence classes
Conversely, every partition on a set can be used to form an equivalence relation. Let ={A1 ,A2 ,…,An } be a partition of a nonempty set A. Let R be a relation on A, and aRb if only if there exists Ai s.t. a,bAi . i.e. R=(A1A1 )∪(A2A2 )∪…∪(AnAn ) R is an equivalence relation on A Theorem 2.12：Given a partition {Ai |iZ} of the set A, there is an equivalence relation R that has the set Ai , iZ, as its equivalence classes
Example: Let Ii-a, b,,c be a partition ofA=a, b, c) Equivalence relation R-
Example: Let ={{a,b},{c}} be a partition of A={a,b,c}. Equivalence relation R=?
2.7 Partial order relations 1. Partially ordered sets Definition 2.21: A relation on a set A is called a partial order if R is reflexive, antisymmetric, and transitive. The set A together with the partial order R is called a partially ordered set, or simply a poset and we will denote this poset by(A, R). And the notation asb denoted that (a, bER. Note that the symbol s is used to denote the relation in any poset, not just the " lessthan or equals relation The notation a< b denotes that a≤ b but a≠b
2.7 Partial order relations 1.Partially ordered sets Definition 2.21: A relation R on a set A is called a partial order if R is reflexive, antisymmetric, and transitive. The set A together with the partial order R is called a partially ordered set, or simply a poset, and we will denote this poset by (A,R). And the notation a≼b denoteds that (a,b)R. Note that the symbol ≼ is used to denote the relation in any poset, not just the “lessthan or equals” relation. The notation a≺b denotes that a≼b but ab