如果集合A上的关系R满足以下三个属性, 则称为等价关系：
 
关系R是自反的, 即aRa∀a∈A。
 
关系R是对称的, 即aRb⟹bRa
 
关系R是传递的, 即aRb和bRc⟹aRc。
 
示例：设A = {1, 2, 3, 4}, R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3 , 3), (4、2), (4、4)}。
 
证明R是一个等价关系。
 
解：
 
自反的：关系R自反为(1, 1), (2, 2), (3, 3)和(4, 4)∈R.
 
对称的：关系R是对称的, 因为无论何时(a, b)∈R, (b, a)也属于R.
 
例子：(2, 4)∈R⟹(4, 2)∈R.
 
可传递的：关系R是可传递的, 因为无论何时(a, b)和(b, c)属于R, (a, c)也属于R。
 
例如：(3, 1)∈R和(1, 3)∈R⟹(3, 3)∈R.
 
因此, 由于R是自反的, 对称的和可传递的, 因此R是等价关系。
 
注1：如果R1和R2是等价关系, 则R1∩R2也是等价关系。
 
例如：A = {1, 2, 3} R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} R2 = {(1, 1), (2、2), (3、3), (2、3), (3、2)}R1∩R2 = {(1、1), (2、2), (3、3)}
 
注2：如果R1和R2是等价关系, 则R1∪R2可能是也可能不是等价关系。
 
例如：A = {1, 2, 3} R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} R2 = {(1, 1), (2、2), (3、3), (2、3), (3、2)}R1∪R2 = {(1、1), (2、2), (3、3), (1、2), (2、1), (2、3), (3、2)}
 
因此, 自反或对称是等价关系, 但可传递可能是也可能不是等价关系。
 
逆关系
 
令R为从集合A到集合B的任何关系。R-1表示的R的逆是从B到A的关系, 它由那些有序对组成, 这些对在反向时属于R, 即：
 
R-1 = {(b, a): (a, b) ∈ R}
 
范例1：A = {1, 2, 3} B = {x, y, z}
 
解：R = {((y, y), (1, z), (3, y)R-1 = {{(y, 1), (z, 1), (y, 3)}显然(R-1 )-1 = R
 
注1：R-1的域和范围等于R的范围和域。
 
示例2：R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (3, 2)} R-1 = {(1, 1 ), (2、2), (3、3), (2、1), (3、2), (2、3)}
 
注2：如果R是等价关系, 则R-1始终是等价关系。
 
示例：令A = {1, 2, 3} R = {((1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} R-1 = { (1、1), (2、2), (3、3), (2、1), (1、2)} R-1是等价关系。
 
注3：如果R是对称关系, 则R-1 = R, 反之亦然。
 
示例：设A = {1, 2, 3} R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2) } R-1 = {(1, 1), (2, 2), (2, 1), (1, 2), (3, 2), (2, 3)}
 
注4：逆序法律(SOT)-1 = T-1或S-1(ROSOT)-1 = T-1或S-1或R-1。

定义：集合S上的关系$\equiv$,称为S上为等价关系，当且仅当它在S上是对称的，自反的，传递的。 
 例如：
 
x=x
x=y意味着y=x
x=y且y=z意味着x=z 
 可以使用等价关系将集合S划分为等价类，S的两个元素x和y属于同一等价类，当且仅当$\equiv$，例如，有12个编号为0至11元素： 
 0$\equiv$4,3$\equiv$1,6$\equiv$10,8$\equiv$9,7$\equiv$4,6$\equiv$8,3$\equiv$5,2$\equiv$11,11$\equiv$0 
 那么根据关系$\equiv$的自反性，对称性和传递性的结果，可以归为以下几个等价类： 
 {0, 2, 4, 7, 11};{1, 3, 5};{6, 8, 9, 10}. 
 如果用二维数组去表示其等价关系，不仅会浪费大量空间，还需相当的时间去寻找两个等价元素之间的第三个等价元素。那么我们可以考虑用链表来去查找等价类的元素，来减少时间和空间复杂度，其用链表设计查找等价类的结构如图： 
  
 代码实现：
 
#include <iostream>
#include<stdlib.h>
#include<stdio.h>
//等价关系最大范围(0-MAX_SIZE)其中不包括MAX_SIZE
#define MAX_SIZE 24
#define IS_FULL(ptr) (!(ptr))
//标记输出过
#define FALSE 0
//标记没有输出过
#define TRUE 1
typedef struct node *node_pointer;
//存储结构
struct node
{
   int data;
   node_pointer link;
};
using namespace std;
int main()
{
   //存储元素是否输出过的标记
   int out[MAX_SIZE];
   //每个等价元素链表的头结点
   node_pointer seq[MAX_SIZE];
   node_pointer x,y,top;
   int i,j,n;
   //输入其元素范围[0,n)
   printf("Enter the size(<=%d) ",MAX_SIZE);
   scanf("%d",&n);
   //初始化操作
   for(i=0;i<n;i++)
   {
      out[i]=TRUE;
      seq[i]=NULL;
   }
   printf("Enter a pair of numbers (-1 -1 to quit):" );
   //循环输入等价关系的元素对
   scanf("%d%d",&i,&j);
   while(i>=0)
   {
      x=(node_pointer)malloc(sizeof(node));
      if(IS_FULL(x))
      {
         fprintf(stderr,"the memory is full\n");
         exit(1);
      }
      //插入到第i个链表的前端
      x->data=j;
      x->link=seq[i];
      seq[i]=x;
      x=(node_pointer)malloc(sizeof(node));
      if(IS_FULL(x))
      {
         fprintf(stderr,"the memory is full\n");
         exit(1);
      }
      //插入到第j个链表的前端
      x->data=i;
      x->link=seq[j];
      seq[j]=x;
      printf("Enter a pair of numbers (-1 -1 to quit):" );
      scanf("%d%d",&i,&j);
   }
   for(i=0;i<n;i++)
   {
      //判断是否输出
      if(out[i])
      {
         printf("\nNew class:%5d",i);
         out[i]=FALSE;
         //查找剩下的等价结点
         x=seq[i];
         top=NULL;
         for(;;)
         {
            //输出链表的等价元素
            while(x)
            {
               j=x->data;
               if(out[j])
               {
                  printf("%5d",j);
                  out[j]=FALSE;
                  //使其链表结点的指针方向反向
                  y=x->link;
                  x->link=top;
                  top=x;
                  x=y;
               }
               else
               {
                  x=x->link;
               }
            }
            if(!top) break;
            //查找第top->data个等价链表的元素
            x=seq[top->data];
            top=top->link;
         }
      }
   } 
}
 
分析：seq和out初始化的时间开销为O(n),输入等价对时，其时间开销是常量，故该阶段为的时间总开销为O(m+n),在第二阶段中，每个节点至多放入链栈一次，由于只有2m个节点，并且for循环n次，故该阶段的时间开销是O(m+n),因此总的计算时间开销是O(m+n).其算法空间的开销是O(m+n).

等价关系、等价类与划分
 


 
文章目录
 
等价关系、等价类与划分
等价关系的定义
等价类
等价类的性质
   
集合的划分
商集
等价关系与划分的一一对应
 

 
等价关系的定义
 
 
定义：设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一 个等价关系，若<x,y> ∈R ，称x等价于y，记作x~y。
 
（即R同时满足自反性、对称性、传递性，则R为A上的等价关系）
 
例1：
 
设A={1,2...,8}，如下定义A上的关系R：
R={<x,y>|x,y≡∈A∧x≡y(mod3)}, 其中x≡y(mod3)叫做x与y模3相等（即x除以3的余数与y除以3的余数相等）

R={ <1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<8,8>,   <1,4>,<1,7>,<4,1>,<4,7>,<7,1>,<7,4>,<2,5>,<2,8>,<5,2>,<5,8>,<8,2>,<8,5>,<3,6>,<6,3>}
因为∀x∈A,有x≡x(mod3)
∀x,y∈A,有x≡y(mod3),则有y≡x(mod3)
∀x,y,z∈A,有x≡y(mod3),y≡z(mod3)则有x≡z(mod3)
同时满足自反性、对称性、传递性，所以R为A上的等价关系
以下为R的关系图
 
 
例2：
 
设S={a,b,c},定义S上的关系R=Is∪{<a,b>,<b,a>}，R是否是S上的等价关系？（注：Is中的s为I的下标）

正确答案：是

 
等价类
 
定义：设R为非空集合A上的等价关系, ∀x∈A，令[x]R = { y | y∈A∧xRy }
 称 [x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为[x]。
 
例3：
 
求例1中等价关系的等价类。

等价类：
	[1]=[4]=[7]={1,4,7}
    [2]=[5]=[8]={2,5,8}
    [3]=[6]={3,6}
 
等价类的性质
 
设R是非空集合A上的等价关系, 则
 
(1) ∀x∈A, [x] 是A的非空子集
 
(2) ∀x, y∈A, 如果 x R y, 则 [x]=[y]
 
(3) ∀x, y∈A, 如果 x y, 则 [x]与[y]不交
 
(4) ∪{ [x] | x∈A}=A，即所有等价类的并集就是A
 
例4：
 
A={ 1, 2, … , 8 }上模 3 等价关系的等价类：
 [1]=[4]=[7]={1,4,7}，      
 [2]=[5]=[8]={2,5,8}，      
 [3]=[6]={3,6}
      以上3 类两两不交；   
       {1,4,7}∪{2,5,8}∪{3,6} = {1,2, … ,8}

 
例5：
 
设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则[a]=？[b]=？[c]=？

[a]={a,b}
[b]={a,b}
[c]={c}
 
集合的划分
 
定义 设A为非空集合, 若A的子集族π(π ⊆ P(A)) 满足下面条件：
 (1) Ø ∉ π
 
(2) ∀x∀y (x,y∈π∧x≠y→x∩y= Ø)
 
(3) ∪π=A
 
称π是A的一个划分, 称π中的元素为A的划分块。
 
例6：
 
设A＝{a, b, c, d}, 
给定π1,π2,π3,π4,π5,π6如下：
      π1= { {a, b, c}, {d} }，
      π2= { {a, b}, {c}, {d} }
      π3= { {a}, {a, b, c, d} },
      π4= { {a, b}, {c} }
      π5= { Ø,{a, b}, {c, d} }, 
      π6= { {a, {a}}, {b, c, d} }
  
π1,π2是A的划分，其他都不是A的划分。
 
商集
 
定义：设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A }
 
例7：
 
 A={1,2,…,8},A关于模3等价关系R的商集为：
      A/R = { {1,4,7}, {2,5,8}, {3,6} }
      A关于恒等关系和全域关系的商集为：
              A/IA = { {1},{2}, … ,{8}}
              A/EA = { {1, 2, … ,8} }

 
例8：
 
设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则S/R=？

正确答案：{{a,b},{c}}
 
等价关系与划分的一一对应
 
商集 A/R 就是 A 的一个划分；
 
例如： A={1,2,…,8},A关于模3等价关系R的商集为：
 A/R = { {1,4,7}, {2,5,8}, {3,6} }，它就是Ａ的一个划分
 
不同的商集对应于不同的划分；
 
任给 A 的一个划分π, 如下定义 A 上的关系 R：
 
R = {<x,y> | x,y∈A∧x 与 y 在π的同一划分块中}，则 R 为 A上的等价关系, 且该等价关系确定的商集是π。
 
例9：
 
求出A＝{1,2,3}上所有的等价关系
求解思路：先求出A的所有划分, 然后根据划分写出对应的等价关系。(如下图)

π1对应于全域关系 EA
π2对应等价关系 R2={<2,3>,<3,2>}∪IA
π3对应等价关系 R3 ={<1,3>,<3,1>}∪IA
π4对应等价关系 R4={<1,2>,<2,1>}∪IA
π5  对应于恒等关系 IA
(注：以上所出现的IA，A为I的下标)
 

 
 
 
 

9.5 等价关系
 
等价关系
 
定义：
 
 
 
定义在集合A上的关系如果是自反，对称和传递的，则该关系称为等价关系。
 
 
自反，对称和传递的定义见这里
 
元素等价
 
 
 
如果集合A中两个关系是被等价关系关联的，则称它们是等价的，记做 a ~ b
 
 
等价类
 
$$\begin{gathered} 在一个集合A中，所有a的等价元素组成的子集合叫做a的等价类，记做{\left[a\right]}_R，有时候也可以把 \\ 下标R去掉，写作[a] \end{gathered}$$
 
例如，对于正整数集合，R为a=-b或者a=b。7的等价类就是[7]={7,-7}
 
 
等价关系划分集合
 
$$\begin{gathered} 假设集合A中的关系R是等价的，a和b具有以下形式： \\ \begin{array}{ll}1& aRb\\ 2& [a]=[b]\\ 3& [a]\cap [b]\ne \varnothing \end{array} \\ 中的任何一个时，都可以证明另外两个。 \end{gathered}$$
 
这个证明我自己想的，没有抄书上。
 $$\begin{gathered} 假设a,b\in A，且(a,b)\in R，因为R是等价关系，所以(b,a)\in R，同理，(a,a)\in R,(b,b)\in R。 \\ 所以[a]=[b],[a]\cap [b]\ne \varnothing \end{gathered}$$
 简单来说就是如果一个集合存在等价关系，则我们可以使用该等价关系来划分集合。同时，如果集合可以划分成几部分，我们也可以找到一个等价关系来使其中的各部分符合该关系。