复旦大学：《离散数学 Discrete Mathematics（上）》英文课件（赵一鸣）04/30

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 aA, a[a]; (2)If a R b, then [a]=[b]; (3)For a,bA, If (a,b)R, then [a]∩[b]=; Proof：(1)For any aA，aRa? (2)For a,bA, 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,bA, 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,bAi . i.e. R=(A1A1 )∪(A2A2 )∪…∪(AnAn ) R is an equivalence relation on A Theorem 2.12：Given a partition {Ai |iZ} of the set A, there is an equivalence relation R that has the set Ai , iZ, 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=?