数学上,二元关系(英語:Binary relation,或简称关系)用於讨论两种物件的连系。诸如算术中的「大於」及「等於」、几何学中的「相似」或集合论中的「为……之元素」、「为……之子集」。
设为集合,的任何子集称作到的二元关系,特别是当时,称作上的二元关系,一般记作。若, 是从到的二元关系;若,那么是上的二元关系
或是以正式的邏輯符號表述為
例一:有四件物件 {球,糖,车,枪} 及四个人 {甲,乙,丙,丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有车,则「擁有」的二元关系可以寫為
- = {(球,甲), (糖,乙), (车,丁)}
其中二元有序对的第一项是被擁有的物件,第二项是擁有者。
例二:實數系 上的「大於關係」可定義為
由於習慣上 通常都是寫為 ,更一般來說,不引起混淆的話會把 簡寫成 。
集合与集合上的二元关系則定義為 ,当中 ( 請參見笛卡儿积 ) ,称为 的图。若 则称 与 有关系 ,并记作 或 。
但经常地我们把关系与其图等价起来,即若 则 是一个关系。
话虽如此,我们很多時候索性把集合間的關係 定义为 而 “有序对 ” 即是 “ ”。
设及,是 和上的关系,令
则0,1矩阵
称为的关系矩阵,记作。
设,是上的关系,令图,其中顶点集合,边集合为,且对于任意的,满足当且仅当。则称图是关系的关系图,记作。
关系的基本运算有以下几种:
- 设为二元关系,中所有有序对的第一元素构成的集合称为的定义域,记作。形式化表示为
- 设为二元关系,中所有有序对的第二元素构成的集合称为的值域,记作。形式化表示为
- 设为二元关系,的定义域和值域的并集称作的域,记作,形式化表示为
- 设为二元关系,的逆关系,简称的逆,记作,其中
- 设为二元关系,與的合成關係记作,其中
- 设为二元关系,是一个集合。在上的限制记作,其中
- 设为二元关系,是一个集合。在下的像记作,其中
- 设为上的二元关系,在右复合的基础上可以定义关系的幂运算:
-
关系的性质主要有以下五种:
- 自反性:
- 在集合X上的关系R,如对任意,有,则称R是自反的。
- 非自反性(自反性的否定的強型式):
- 在集合X上的关系R,如对任意,有,则称R是非自反的。
- 对称性:
- 在集合X上的关系R,如果有且必有,则称R是对称的。
- 反对称性(不是對稱性的否定):
- 非對稱性(對稱性的否定的強型式):
- 非對稱性是 滿足非自反性的反對稱性。
- 传递性:
设为集合上的关系,下面给出的五种性质成立的充要条件:
- 在上自反,当且仅当
- 在上非自反,当且仅当
- 在上对称,当且仅当
- 在上反对称,当且仅当
- 在上非對稱,当且仅当
- 在上传递,当且仅当