【离散数学-集合论】等价关系及等价类

目录

前言 ▹

正文 ▹

参考 ▹

正文

等价关系

1.2.2等价关系（equiναΙence relαtion)

定义1.2.10 设A是一个非空集合，R是A上一个关系。如果R具有自反性，对称性，传递性，则称R是一个等价关系。通常，用“≅”表示等价关系。

例：整数的同余关系，几何图形的面积相等关系，人群中的同姓关系、同龄关系等。

考虑A是非空集合，若A上的关系R满足自反、对称、传递性，则称R是A上的一个等价关系。

等价类

定义1.2.11等价类(equivalence class)

❖设A是一个非空集合，R是A上的等价关系。A的一个非空子集M叫做A关于R的一个等价类，如果

1)若a∈M，b∈M，则a R b。

2)若a∈M，b∉M，则a ℟ b；或者，若a∈M，a R b，则b∈M。

❖通常，用[a]ʀ 表示包含元素a的等价类，则[a]ʀ＝{x|(x，a)∈R}，a称为该等价类代表元。

用我自己的话来阐述一下：

设A是一个非空集合，R是A上的等价关系，我们称同时满足下列条件的A的非空子集M为等价类：

1. 若α ∈ M，b ∈ M，必有αRb。

2. 若α ∈ M，b ∉ M，必有α ℟b。或者说若α ∈ M，且αRb，则必有b ∈ M。

通常，用[α]ʀ表示包含元素α的等价类， 则[α]ʀ＝{x|(x，α) ∈ R}，其中 a 称为该等价类代表元。

这个举同余关系就很好理解，考虑整数集Z，对模3同余，则可以将整数集划分为三个等价类

{x|x ∈ Z x ≡ 0 (mod 3)}，{x|x ∈ Z x ≡ 1 (mod 3)}，{x|x ∈ Z x ≡ 2 (mod 3)}。

定理1.2.6

❖设≅是集合A上的等价关系，于是等价类是存在的。

证明：(1)任取a∈A，令M＝{x|x∈A并且x≅a}，显然，M非空。

(2)任取x₁ ∈ M，x₂ ∈ M，根据M的定义，则有x₁≅a，x₂≅a，而≅具有对称性，传递性，所以 x₁≅x₂。

X1=X2。

(3)任取x₁∈M，若x₁≅y，则x₁≅a，而≅具有对称性，传递性，所以y≅a，故y∈M。

因此，M是一个等价类。

这个定理说了2个东西

1. 由等价关系必然可以推导出等价类。

2. 根据等价关系构建等价类的方式：∀α ∈ A，M＝{x|x ∈ A，x ≅ α}其中a是等价类M的代表元。

定理1.2.7

❖设≅是集合A上的等价关系，M₁，M₂，. . .，是A中关于≅的所有等价类。于是

A＝M₁∪M₂∪ . . .

并且Mᵢ∩Mᵢ＝ф(i≠j)，亦即，集合A上的等价关系把A分成了互不相交的等价类。

个人感觉这个定理并没有说清楚，因为它默认i ≠ j时，Mᵢ ≠ Mⱼ，然而这一点并没有在PPT上体现。

我用自己的话阐述一下：

1、设≅是集合A上的等价关系，由[公式]可以得到的A的所有等价类，任取其中两个等价类，它们要么相等，要么相交为空。

证明：

假设Ⅹ₁，Ⅹ₂是A上关于≅的两个等价类，则必然出现下面两种情况之一：

(1)、X₁，X₂；(2)、X₁ ≠ X₂ 。

我们将证明对于情况(2)而言，必有X₁∩Ⅹ₂＝∅。

由于X₁ ≠ X₂ ，不失一般性，必然存在x ∈ X₁，x ∉ X₂（x ∈ X₂，x ∉ X₁是类似的）。

假若X₁∩X₂不为空，则必然存在y∈X₁∩Ⅹ₂，由等价类定义可得x≅y，但由于y∈X₂，则可知必然有x∈X₂，这就与x∉X₂形成矛盾，故而X₁∩X₂＝∅。

2、取A上关于≅的所有两两相交为空的等价类，依次命名为M₁，M₂，. . .（也就是说Mᵢ∩Mⱼ＝∅，i ≠ j)，则必然有A＝M₁∪M₂ . . .。

证明：

一方面，M₁∪M₂ · · · ⊆ A是显然的。

另一方面，任取x∈A，若x∉M₁∪M₂ . . . ，则可构建A上的一个等价类P＝{y|y∈A，y ≅ x}，显然x∈P，但是由题目条件知M₁，M₂，. . .是A上关于≅的所有两两相交为空的等价类，故而必然有x∈M₁∪M₂ . . .，这与x∉M₁∪M₂ . . .形成了矛盾，因此必然有x∈M₁∪M₂ . . .。因此A ⊆ M₁ ∪ M₂ . . .。

综上，A＝M₁∪M₂ . . .。

书上证明

证明：

❖任取Mᵢ，Mᵢ，i≠j。假设Mᵢ∩Mᵢ≠ф，则必存在x∈Mᵢ∩Mᵢ，则任取a∈Mᵢ，b∈Mᵢ，都有a≅x，b≅x，所以a≅b，故Mᵢ＝Mᵢ，矛盾。

❖任取a∈A，令M＝{x|x∈A并且x≅a}，由定理1.2.6知，M是等价类，故有k，使得M＝Mₖ，因为a∈M，所以，

a∈M₁∪M₂∪. . .∪Mₖ∪. . . 。显然有M₁∪M₂∪ . . .⊆A 。故A＝M₁∪M₂∪. . . 。

参考

离散数学集合论参考 吉林大学的网课 离散数学课程主页

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。