请输入您要查询的字词:

 

单词 PartitionIsEquivalentToAnEquivalenceRelation
释义

partition is equivalent to an equivalence relation


Proposition 1.

There is a one-to-one correspondence between the set Part(S) of partitions of S and the set Equiv(S) of equivalence relationsMathworldPlanetmath on S.

Proof.

Let S be a set.

Suppose P={PiiI} is a partition of S. Form E={Pi×PiiI}. Given any aS, aPi for some iI. Then (a,a)Pi×PiE. If (a,b)E, then (a,b)Pi×Pi for some iI, so a,bPi, whence (b,a)Pi×PiE. Finally, suppose (a,b),(b,c)E. Then (a,b)Pi×Pi and (b,c)Pj×Pj, or a,bPi and b,cPj. Since bPiPj, Pi=Pj since P is a partition. So a,cPi=Pj, or (a,c)Pi×PiE.

Conversely, suppose E is an equivalence relation on S. For each aS, define

[a]={bS(a,b)E}.

Then each a[a] since E is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. If b[a], then (a,b)E or (b,a)E as E is symmetricPlanetmathPlanetmathPlanetmath. So a[b] as well. Next, pick any c[b]. Then (b,c)E. But (a,b)E. So (a,c)E since E is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath. Therefore c[a], which implies [b][a]. Collect all the information we have so far, this implies [a]=[b]. Therefore P={[a]aS} forms a partitition of S (P is being interpreted as a set, not a multiset). In fact, E={[a]×[a]aS}.∎

From the above proof, we also have

Corollary 1.

For every partition P={PiiI} of S, E={Pi2iI} is an equivalence relation. Conversely, every equivalence relation on S can be formed this way.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 13:02:28