等价类与划分

等价关系

等价关系定义: 集合X上的二元关系R称为等价关系, 如果R同时具有一下三个性质:

  1. R是自反的, 即\forall x \in X, xRx
  2. R是对称的, 即如果xRy, 则yRx
  3. R是传递的, 即如果xRy, yRz 则xRz

等价类定义: 设R为X上的一个等价关系, x \in X, X的子集E_x=\lbrace y|y \in X \wedge xRy \rbrace 称为x关于R的等价类,或记为x的等价类
x的等价类常记为[x], 即[x] = \lbrace y|y \in X \wedge xRy \rbrace

等价类的性质
设R是非空集合X上的等价关系, 则

  1. \forall x\in X,[x] \neq \emptyset
  2. \forall x,y \in X,如果xRy, 则[x]=[y]
  3. \forall x,y \in X,如果(x,y) \notin R, 则[x]\bigcap [y] = \emptyset
  4. 所有等价类的并集就是X

集合的划分
设X为非空集合, X的若干个子集形成的集族π称为X的一个划分, 如果π具有性质:
(1). \emptyset \notin π
(2). \forall x,y \in π, 若x \neq y, 则 x \bigcap y = \emptyset
(3). \bigcup \limits_{x \in x}x = X

称\pi中的元素为X的划分
如果\pi是X的一个划分, 则当|\pi| = k时, \pi被称为X的一个k-划分

等价关系与集合的划分

  1. 设R是X上的一个等价关系, 则R的所有等价类的集合是X的一个划分
  2. 设\pi是集合X的一个划分,令R=\lbrace (x,y)|x,y \in X \wedge x与y在\pi的同一划分块中 \rbrace, 则R是X上的一个等价关系,并且\pi就是R的等价类之集

由定理1, 2可得: X上的等价关系与X的划分是一一对应的, 并且互相确定

商集
等价关系R确定的划分是R的所有等价类之集 \lbrace [x]|x \in X \rbrace
设R是X上的等价关系, 由R所确定的X的划分也就是R的所有等价类之集称为X对R的商集, 并记为X/R.
即: X/R = \lbrace [x]|x \in X, [x] 是x的等价类 \rbrace

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容