§2.3　等价关系（equivalent relation）

在日常生活和数学中，常常要对一些对象进行分类研究.例如，对若干几何图形，可以按“面积相等”关系对这些几何图形分类.这种分类使得每个几何图形恰好属于某一类，即不同类之间没有公共元素，从而当我们讨论几何图形的面积时，可以把“面积相等”的那些几何图形看作同样的，具有这种功能的分类法所涉及的关系在数学上称为“等价关系”，其严格定义如下：

定义2.3.1　设R是集合A上的二元关系，若R具有自反性、对称性和传递性，则称R是一个等价关系.

【例2.3】　设定义在整数集Z上的二元关系Rk（k∈Ζ）为

于是，Rk是一个等价关系.事实上，对任意x，y，z∈Z，

（1）因为x-x=0*k，所以<x，x>∈Rk；

（2）若<x，y>∈Rk，则存在m∈Z，使得

x-y=m*k

于是，y-x=（-m）*k，显然-m∈Z，故<y，x>∈Rk；

（3）若<x，y>，<y，z>∈Rk，则存在m，n∈Z，使得

x-y=m*k，y-z=n*k

于是，x-z=（x-y）+（y-z）=m*k+n*k=（m+n）*k，显然，m+n∈Z，故<x，z>∈Rk.

由定义即知Rk是等价关系.

设x和y分别被k除所得的余数为x′和y′，即存在r，s∈Z，使得x=r*k+x′，y=s*k+y′，0≤x′，y′<k.于是，xRky当且仅当存在m∈Z，使得m*k=x-y=（r*k+x′）-s（*k+y′）=（r-s）*k+（x′-y′）当且仅当x′-y′=0，当且仅当x′=y′.今后，我们可记xRky为x=y（modk），读作“x与y模k同余”.

在对一个集合A进行分类时，常常希望所分的各类没有公共元素，这在数学上称为对A进行划分，其严格定义如下：

定义2.3.2　设A为非空集合，S={S1，S2，…，Sm}，Si⊆A，i=1，2，…，m.

如果：

（1），i=1，2，…，m；

（2），i≠j，i，j=1，2，…，m；

（3），

则称S为A的一个划分（partitions）.

例如，设A={1，2，3}，于是

S1={{1}，{2}，{3}}

S2={{1，2，3}}

S3={{1，2}，{3}}

S4={{1}，{2，3}}

S5={{2}，{1，3}}

都是A的划分.特别地，称形如S1和S2的划分为A的平凡划分.显然，任何非空集合至少存在一个划分.

下面讨论集合A的划分与定义在A上的等价关系之间的联系.

定义2.3.3　设R为集合A上的等价关系，对每个x∈A，作集合

称[x]R为x（关于R）的等价类（equivalence class）.

例如，设

则　　[0]R={…，-6，-3，0，3，6，…}

[1]R={…，-5，-2，1，4，7，…}

[2]R={…，-4，-1，2，5，8，…}

等价类[x]R有如下性质：

性质1　对任意x∈A，；

性质2　若y∈[x]R，则[x]R=[y]R；

性质3　若y∉[x]R，则.

由性质2，对等价关系x≡y（mod3），有

[0]R=[3]R=[-3]R=…

[1]R=[4]R=[-2]R=…

[2]R=[5]R=[-1]R=…

定义2.3.4　设R是集合A上的等价关系，称集合

为A关于R的商集（quotient sets），记为A/R.

定理2.3.1　设R是集合A上的等价关系，于是

是A上的一个划分.

证明：显然，对任意[x]R∈A/R，[x]R⊆A，且由性质1知，；其次，设[x]R≠[y]R，则，若不然，设z∈[x]R∩[y]R，则有xRz且zRy，因R是等价关系，所以有xRy，于是y∈[x]R.由性质2，[x]R=[y]R，此与[x]R≠[y]R矛盾.故

最后，我们来证明

任取x∈A，因为x∈[x]R，所以，于是

另一方面，由于[x]R⊆A，x∈A，因此

总之，式（2.3）成立，故A/R是A的一个划分.

例如，已知x≡y（mod3）是整数集Z上的等价关系R，于是集合{[0]R，[1]R，[2]R}是Z关于R的商集，由划分的定义知这个商集是Z上的一个划分.

定理2.3.2　设S是集合A的一个划分，S={S1，S2，…Sm}.令

于是，R是A上的一个等价关系，并且A/R=S.

证明：先证R是A上的等价关系.

（1）对任意x∈A，因S是A的划分，所以存在Si∈S，使得x∈Si，于是xRx；

（2）若xRy，则存在Si∈S，使得x，y∈Si，即y，x∈Si，故yRx；

（3）若xRy，yRz，则存在Si，Sj∈S，使得x，y∈Si，y，z∈Sj，于是y∈Si∩Sj，因为S是划分，所以必有Si=Sj，因此，x，y，z∈Si，从而xRz.

以上说明R是一个等价关系，下证A/R=S.

任取Si∈S，因为，所以存在x∈Si，可以证明Si=[x]R.事实上，任取y∈Si，则x，y∈Si，于是xRy，从而y∈[x]R，故Si⊆[x]R，反之，任取y∈[x]R，则Sj∈S，使得x，y∈Sj，但x∈Si，所以Sj=Si，于是y∈Si，从而[x]R⊆Si，总之Si=[x]R，其中x∈Si，由Si的任意性知S⊆A/R.

另一方面，任取[x]R∈A/R，x∈A.因S是A的划分，所以必有Si∈S，使得x∈Si，与上类似也可证明[x]R=Si，于是A/R⊆S.

综上所述，A/R=S.

定理2.3.1和定理2.3.2表明，集合A上的等价关系和A上的划分是一一对应的.