概念
有序对
<x,y>
笛卡尔积
其中A和B是两个非空集合。笛卡尔积是由所有可能的有序对组成的集合，其中第一个元素来自A，第二个元素来自B。
性质
笛卡尔积性质
- 不满足交换律，结合律
- 满足并交分配律
证明：根据定义分别对有序对不同位置进行讨论
二级结论
二元关系
二元关系是定义在两个集合和上的一种关系，它是的子集。形式上，如果R是A到B的二元关系，那么。二元关系可以用有序对的集合来表示，其中每个有序对表示与之间存在关系。这种关系可以是数学上的，如"大于"或"等于"，也可以是现实生活中的，如"是...的父亲"或"喜欢..."。
空关系
全域关系
称为全域关系，定义如下：
同一个集合中元素的所有组合
恒等关系
称为恒等关系，定义如下：
小于等于关系
整除关系
包含关系
关系矩阵
关系矩阵是表示二元关系的一种方法，它使用0和1来表示元素之间是否存在关系（布尔矩阵）。对于给定的关系和集合，关系矩阵M是一个的矩阵，其中如果否则这种表示方法不仅直观，而且便于计算机处理和分析关系的性质。
把关系的两个参数作为矩阵坐标看待
关系图
关系的运算
域()
定义域()
值域()
逆
合成
方向向左
元素和为逻辑和
限制
像
运算性质
分配率
对满足分配律，对分配后为包含关系
<x,z>和<z,y>生成<x,y>，因为z这个中间过程去掉了，就会造成当z不同时，<x,y>是一样的。
结合律
拆逆
幂运算
- 集合表示：计算就是n个R左复合。
- 矩阵表示：n个矩阵相乘，采用逻辑加
- 关系图
- 即求多少次幂就跨几步取值（以一次为参照）
例
关系的性质
自反性与反自反性
自反性是指关系在集合上对每个元素都成立，即对于所有，都有。例如，"等于"关系就是自反的。反自反性则是指关系R在集合A上对任何元素都不与自身有关系，即对于所有，都有。例如，"小于"关系就是反自反的。
对应到矩阵中，自反性则为对角线均为真，反自反性均为假。
对称性与反对称性
- 对称的，不反对称（顶点之间都是对称边）
- 不对称，反对称（顶点之间都是单向边）
- 既对称，又反对称（不同顶点之间没有边）
- 既不对称，又不反对称（有些顶点间是对称边，有些顶点间是单向边）
- 反对称：上三角和下三角的对称位置不能同时为1
传递性
则称R是A上的传递关系。
关系的矩阵表示
设R为A上的关系, 则
- R在A上自反当且仅当
- R在A上反自反当且仅当
- R在A上对称当且仅当
- R在A上反对称当且仅当
- R在A上传递当且仅当
ㅤ | 自反 | 反自反 | 对称 | 反对称 | 传递 |
表达式 | |||||
关系
矩阵 | 主对角线元素
全是1 | 主对角线元素全是0 | 矩阵是对称矩阵 | 若, 且
, 则 | 对M2中1所在位置,
M中相应位置都是1 |
关系图 | 每个顶点都有
环 | 每个顶点都没有环 | 如果两个顶点之间有边, 是一对方向相反的边(无单边) | 如果两点之间有边, 是一条有向边(无双向边) | 如果顶点 到有边，到有边 , 则从 到 有边 |
闭包
在原来的基础上，将变成具有特定性质的最小集合
加最少的边使得符合要求。
- 自反闭包：
- 对称闭包：
- 传递闭包：
等价关系
同时满足自反性，对称性，传递性
记作
等价类
例
性质
- 等价类非空
- 如果, 则 。
- 如果, 则 。
- 所有等价类的并集就是A
商集
以等价类为元素的集合
划分()
划分是集合A的一个子集族π，满足以下条件：
- π中的每个子集都是非空的
- π中的子集两两不相交
- π中所有子集的并集等于A
换句话说，划分将集合A分成若干个互不相交的非空子集，这些子集的并集恰好等于A。每个子集被称为划分的一个"块"或"部分"。
商集就是的由诱导的划分
偏序关系()
偏序关系是一种特殊的二元关系，它具有自反性、反对称性和传递性。在集合A上，如果关系R满足以下三个条件，则称R为A上的偏序关系：
- 自反：每个顶点都有环
- 反对称：两个顶点间若有边，则一定是单向边
- 传递：若两个顶点之间可到达，则一定有一条直接的边
可比
xy满足偏序关系即可比。
全序关系
所有元素之间都是可比的。
盖住
如果x和y是偏序集中的两个元素，且x y，并且不存在z使得，则称y盖住x。这个概念在构建哈斯图时非常有用，因为它帮助我们识别出关系中的直接连接。
位置紧密相连的x和y之间的偏序关系
哈斯图
- 不出现值域的点放在一层
- 将以放置的点为起点的关系划掉
- 重复1
- 连线
极值
极大极小元
上确界：最小上界，但如果不唯一就不存在（因为不可比）
下确界：最大下界，但如果不唯一就不存在（因为不可比）
- 如果哈斯图上存在孤立点，即其无法与其他点进行比较，所以该图没有最大元与最小元。
- 孤立点既是极小元，也是极大元。
- 最小元一定是极小元；最大元一定是极大元。
- B的极小(大)元：B中与其有链相连的点均在其上(下)方
- B的最小(大)元：B中所有点均有链与其相连且在其上(下)方（可能不存在，存在就唯一，不唯一就不存在）
例子
函数
相等
性质
单射
不存在多对一
满射
都有对应的定义
双射
一对一
可以用直线方程模拟
像
特殊函数
常函数
恒等函数
单调函数
略
特征函数
特征函数是一种用于表示集合的函数，它将集合中的元素映射为1，非集合中的元素映射为0。形式化定义如下：
其中A是一个集合，x是定义域中的元素。特征函数在集合论和概率论中有广泛应用。
自然映射
将元素映射到商集
复合
结合律
传递性
满射满射
单射单射
双射双射
反函数
存在条件
性质
- 只有双射函数才有反函数
