1 等价关系与集合的分类

对应视频的 p1-p6

  1. 定义二元关系RR

    二元关系是集合中元素之间的某种联系。对于集合AA，如果a,b∈Aa, b \in A，我们说aa与bb有关系RR，记作aRbaRb。
    对于集合中的任意两个元素，aa 与 bb,总是能判断他们是否满足条件RR

  2. 等价关系

  3. 反身性：∀a→aRa\forall a \to aRa

  4. 对称性：aRb⇒bRaaRb \Rightarrow bRa

  5. 传递性：aRb∧bRc⇒aRcaRb \land bRc \Rightarrow aRc

  6. 等价类

  7. 定义：[a][a]表示所有与aa等价的元素的集合

  8. 等价类是满足以下条件的集合：任意两个元素aa和bb都属于同一个等价类当且仅当aRbaRb

  9. 公式定义：[a]={x∈S∣xRa}[a]= \{ x \in S | xRa \}

  10. 类在这里的意思为：“物以群分”, 分类的意思，等价类就是把满足等价关系的元素归为一类。

  11. 商集：SS的全体等价类构成的集合，集合SS在等价关系下的商集记作S/∼S / \sim

  12. 集合的分类

  13. 分类的定义: 集合 s 是他的某些两两不相交的非空子集的并,这些非空集，何就是 s 的分类

  14. 其中每一个子集称为一个类

  15. 定义：SS是一个集合，如果存在一个等价关系RR使得SS的所有元素都可以划分为等价类，则称SS为RR的分类

  16. 如果非空集合SS是它的某些两两不相交的非空子集的并，则称这些子集为集合SS的一种分类 ( partition ) , 其中每个子集称为集合SS的一个类 ( class )

  17. 集合的分类必须满足不重不漏的原则

若集合SS的子集族{Si∣i∈I}\{S_i | i \in I\}构成了 S 的一种分类当且仅当

  1. S=⋃i∈ISiS = \bigcup_{i \in I} S_i
  2. Si∩Sj=∅S_i \cap S_j = \varnothing( i.e., SiS_i and SjS_j are pairwise disjoint )

集合SS的任何一种等价关系都确定了SS的一种分类。

例题

例 5

aRb⇔m∣a−b,∀a,b∈Z(1) aRb \Leftrightarrow m \mid a - b , \forall a,b \in \mathbb{Z} \tag 1

证明 1 式是等价关系。也就是证明$m | a -b $是等价关系。

公式的含义解释：m 是 a 与 b 差的因子，则说明 a,b 对于 m 同余。这两者是等价的。

下面证明这两者是等价关系。

设 A:a≡b(mod  m)a \equiv b ( \mod m ), B: m∣a−bm \mid a-b.

A→BA \to B, 把 a,b 写成带余数除法的形式。

a=k1×m+rb=k2×m+ra−b=m(k1−k2)→m∣a−b a = k_1 \times m + r \\ b = k_2 \times m + r \\ a - b = m ( k_1 - k_2 ) \to m \mid a - b

必要性证明完毕，证明充分性。

m∣a−b→a−b=k×m→a=b+k×m→amod  m=(b+k×m)mod  m→amod  m=bmod  m m \mid a - b \\ \to a -b = k \times m \\ \to a = b + k \times m \\ \to a \mod m = ( b+k \times m ) \mod m \\ \to a \mod m = b \mod m

qed;

证明自反性：

aRa⇔m∣a−a aRa \Leftrightarrow m \mid a - a

显然成立。

证明对称性：

根据

m∣x→m∣−x m \mid x \to m \mid -x

那么

m∣a−b→m∣−(a−b)→m∣b−a m \mid a - b \to m \mid - ( a - b ) \to m \mid b - a

证明传递性：

m∣a−b∧m∣b−c→m∣a−cm | a - b \land m| b - c \to m | a - c

a=k1×m+rb=k2×m+rc=k3×m+r→a−c=k1×m+r−k3×m−r→m∣a−c a = k_1 \times m + r \\ b = k_2 \times m + r \\ c = k_3 \times m + r \\ \to a - c = k_1 \times m + r - k_3 \times m - r\\ \to m \mid a - c

证明完毕

说明同余是一种等价关系.

书上又定义了什么叫做同余剩余类。

例 9

这个见书。

课后题目

习题 1. 试分别举出满足下列条件的关系：

  • ( 1 ) 有对称性，传递性，但无反身性；
  • ( 2 ) 有反身性，传递性，但无对称性；
  • ( 3 ) 有反身性，对称性，但无传递性。

解：设集合S={a,b,c}S = \{a,b,c\}

  • ( 1 ) ,R={(a,b),(b,a),(a,a),b,b}R = \{( a,b ) , ( b,a ) , ( a,a ) ,{b,b}\}, 因为没有(c,c)( c,c )所以不满足反身性。
  • ( 2 ) ,R={(a,a),(b,b),(c,c),(a,b)}R = \{( a,a ) , ( b,b ) , ( c,c ) , ( a,b ) \}, 因为没有(b,a)( b,a )所以不满足对称性。
  • ( 3 ) ,R={(a,a),(b,b),(c,c),(a,b),(b,a),(c,a),(c,b)}R = \{( a,a ) , ( b,b ) , ( c,c ) , ( a,b ) , ( b,a ) , ( c,a ) , ( c,b ) \}, 因为没有(a,c)( a,c )所以不满足传递性。

习题 2. 找出下面证明中的错误：

有人断言，若 S 的关系 R 有对称性和传递性，则必有反身性。这晨因 因为，对任意的 a∈S, 由对称性，如果 aRb, 则 bRa. 再由传递性，得 aRa, 所以 R 有反身性。

关键在于a∈Sa \in S，但如果aa就没有自己的关系呢？例如习题 1 的 ( 1 ) , 就没有 c 的关系，所以不能说 R 有反身性。因为不一定有cRbcRb这个关系。

习题 4

  1. 设 ϕ\phi 是集合 AA 到 BB 的映射，a,b∈Aa,b\in A, 规定关系 “∼\sim”:
a∼b  ⟺  ϕ(a)=ϕ(b)a\sim b\iff\phi ( a ) =\phi ( b )

证明 :∼: \sim 是 AA 的一个等价关系，并求其等价类

如何求等价类呢？其实这里是问我们等价类的数学描述,我们只要按照等价类的定义来写就可以了:

A/∼={[a]∣a∈A}A/\sim=\{[a] \mid a\in A\}

它的含义是：

对于一个集合 A 和在其上定义的等价关系 ~，A 的商集 A/~ 是一个由 A 中所有元素的等价类 [a] 组成的新集合。

简单来说，就是将集合 A 按照等价关系 ~ 进行划分，每个划分出的子集（即一个等价类）都作为商集 A/~ 中的一个元素。

[a]={x∈A∣ϕ(x)=ϕ(a)} [a] = \{ x \in A \mid \phi(x) = \phi(a) \}