集合定义

序偶(ordered pair)：两个元素按照一定的次序组成的二元组；

重有序组：个元素按照一定的次序组成的元组

笛卡尔积(Cartesian product):对于集合，笛卡尔积为如下集合

  • 不满足交换律：，但是
  • ;
  • ;

关系(relation):对于非空集合, 称是从到的二元关系，如果是的一个子集；

  • 空关系：;
  • 恒等关系：
  • 全关系：
  • 对有关系：
  • 所有可能的关系有个

元关系：的任意子集；

对于间的二元关系;

若且

定义如下概念：

  • 前域
  • 后域
  • 定义域
  • 值域
  • 域

关系图和关系矩阵

关系可以用关系图表示

  • 若关系定义在不同的集合：用带箭头的二部图表示，由前域指向后域；
  • 若关系定义在某一个集合：用可能有向图表示，可能有自环和重边；；

称为关系的关系矩阵(邻接矩阵)，如果

显然这是一个Bool矩阵，对于是的Bool矩阵：

  • 并

  • 交

  • 布尔积

关系表

在关系代数理论中，关系可以用二维表表示；

对于关系,第个属性代表,每一个行/表项为中的元素；

复合运算

对于非空集合，：,称一个从到的关系是复合关系，如果

逆运算

对于非空集合，,的逆关系是指

逆关系的关系矩阵等于原关系的关系矩阵转置；

幂运算

对非空集合,定义关系的次幂如下：

  • ；
  • ;

注意到，幂集随着增加呈现递减趋势，得出如下定理：

proof:只需证明,注意到定义缩减没必要的复合运算即可；

性质

对于定义在一个集合上的关系，我们考察其自反性，反自反性，对称性，反对称性和传递性；

如果对，都有,那么称在 上是自反的，关系图上表现为每个结点有自环，关系矩阵上表现为主对角线上全部为1；

  • 是自反的

如果对，都有，那么称称在 上是反自反的；关系图上表现为每个结点都没有自环，关系矩阵上表现为主对角线上全部为0；

  • 是反自反的

如果对，都有,那么称在 上是对称的;关系图上表现为任意两个结点要么没有边，要么有两条反向边，关系矩阵上表现为对称矩阵；

  • 是对称的

如果对，都有,那么称在 上是反对称的;关系图上表现为任意两个结点至多一条边，关系矩阵上表现为矩阵自交为0；

  • 是反对称的

设是非空集合上的关系．对，如果＜＞＜＞，那么＜＞，则称关系是传递的;关系图上表现为每个结点有自环，关系矩阵上表现为必有；

  • 是传递的

对于定义在集合上的二元关系,考察其保守性：逆运算和交运算保守性好，并，差和复合运算的保守性差；

  • 若具有自反性，则具有自反性；
  • 若具有反自反性，则具有自反性；
  • 若具有对称性，则具有自反性；
  • 若具有反对称性，则具有自反性；
  • 若具有传递性，则具有传递性；

关系闭包

在给定关系添加尽可能少的元素，使关系满足特殊性质，这个过程称为关系闭包；

形式化说，对于定义在非空集合上的关系，若存在定义在上的另一个关系,使得,且满足

  • 是自反的/对称的/传递的
  • 对于任何自反的/对称的/传递的关系,若,必有;

称为的自反闭包(reflexive closure)/对称闭包(symmetric closure)/传递闭包(transitive closure),记作;

闭包运算算法：

等价关系

称定义在非空集合上的关系为等价关系，若具有自反性，对称性和传递性；

给定非空集合,称集合构成集合的一个划分(partition),称作划分的类(class),若

利用等价关系可以将集合划分成互不相交的子集,也即等价类；

对于定义在集合上的等价关系,对,称集合

是生成的关于的等价类(equivalence)，为该类的代表元(generator);

简单来说，在等价关系中，所有与有关系的元素处于同一个等价类中，不难观察以下结论成立

  • 对
  • 对, 若，则;若,则;
  • ;

进一步定义集合关于等价关系的商集

商集算法如下：

  1. 若非空，选取,计算并加入到中；
  2. 若，更新,回到1；

显然商集是对的等价划分，由划分也可以生成一种等价关系，如下：

定集合的一个划分，，则由该划分确定的关系

是上的等价关系,称该关系为由划分所导出的等价关系;

序关系

称定义在集合上的关系为拟序关系，如果是反自反的，反对称的和传递的，记作小于;

序偶称为拟序集，改记为,其逆关系大于为也是拟序关系；

称定义在集合上的关系为偏序关系，如果是自反的，反对称的和传递的，记作小于等于;

序偶称为偏序集，改记为,其逆关系大于等于为也是偏序关系；

规定偏序关系对应的哈斯图(Hasse diagram)如下：

  • 用小圆圈或点表示中的元素，省掉关系图中所有的自环;
  • 对于，，若且，则将画在的下方，可省掉关系图中所有边的箭头;
  • 对于，，若且，且与之间不存在，使得，，则与之 间用一条线相连，否则无线相连;

image-20241210220139067

是偏序集，是的任何一个子集，若存在元素，使得

  • 对，都有，则称为的最大元;
  • 对，都有，则称为的最小元;
  • 对，满足 ，则称为的极大元;
  • 对，满足，则称为的极小元.

若存在元素，使得

  • 对，都有，则称为的上界（upper bound）;
  • 对，都有，则称为的下界（lower bound）;
  • 设元素是的一个上界，对的任何一个上界，若均有，则称为的上确界.记为 ;
  • 设元素是的一个下界，对的任何一个下界，若均有，则称为的下确界.记为 ;

进一步有以下结论：

是偏序集，是的任何一个子集

  • 若最大元存在，则同时是极大元，上界，上确界；若中的一个上界，则是的最大元；
  • 若最小元存在，则同时是极小元，下界，下确界；若中的一个下界，则是的最小元；

对于有限子集,最大元/最小元若存在，则一定唯一，且是唯一极大元/极小元；若上确界/下确界存在，则上确界/下确界唯一；

对偏序关系来说，若，总有或其一成立，则为全序关系/线序(linear order)；

为全序集，其哈斯图表现为一条线；

对偏序关系来说，若中任意非空子集均有最小元，则为良序关系(well order)；

为良序集，良序关系一定是偏序关系，反之则不然，良序关系一定是全序关系，反之则不然；

函数

称关系为集合到集合的函数/映射(function/mapping)，记作,若对于每个,存在唯一的, 使得;

  • 定义域;
  • 值域;
  • 改记为,自变量为，函数值为;

即任意可能的输入集合对应输出集合；

称是从到的单射(injection),若对于,均有;

称是从到的满射(surjection)，若,即对,；

称是从到的双射(bijection)，若既是单射又是满射；

当双射定义在上时，称是集合上的变换(transform)；

若函数,称是上的恒等函数;

若函数,称是上的常值函数；

若定义为全集的一个子集，则子集的特征函数定义为

若变换定义在有限集合上，则称为上的置换/排列(permutation),称作置换的阶(order),通常如下表示：

不同置换个数为个；