数学上,二元关系(英语:Binary relation,或简称关系)用于讨论两种物件的连系。诸如算术中的“大于”及“等于”、几何学中的“相似”或集合论中的“为……之元素”、“为……之子集”。
定义
设
为集合,
的任何子集称作
到
的二元关系,特别是当
时,称作
上的二元关系,一般记作
。若
,
是从
到
的二元关系;若
,那么
是
上的二元关系
或是以正式的逻辑符号表述为
![{\displaystyle (\forall r\in R)(\exists x)(\exists y)[\,r=(x,\,y)\,]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87a36b7918d77c3b54e40faead98f77498a55d56)
例一:有四件物件 {球,糖,车,枪} 及四个人 {甲,乙,丙,丁} 。若甲拥有球、乙拥有糖、丙一无所有但丁拥有车,则“拥有”的二元关系可以写为
= {(球,甲), (糖,乙), (车,丁)}
其中二元有序对的第一项是被拥有的物件,第二项是拥有者。
例二:实数系
上的“大于关系”可定义为
![{\displaystyle >\,:=\{\,(a,\,b)\in {\mathbb {R} }^{2}\,|\,(\exists r\in \mathbb {R} )[\,(a=b+r)\wedge (r\neq 0)\,]\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c1d3570445d0d86b2ccac5c2699f1c8f9b081ff)
由于习惯上
通常都是写为
,更一般来说,不引起混淆的话会把
简写成
。
集合的关系
集合
与集合
上的二元关系则定义为
,当中
( 请参见笛卡儿积 ) ,称为
的图。若
则称
与
有关系
,并记作
或
。
但经常地我们把关系与其图等价起来,即若
则
是一个关系。
话虽如此,我们很多时候索性把集合间的关系
定义为
而 “有序对
” 即是 “
”。
关系矩阵
设
及
,
是
和
上的关系,令
![{\displaystyle r_{ij}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\notin R\end{cases))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb191df42108a2d8d6256f7202bff8ec73906a4)
则0,1矩阵
![{\displaystyle (r_{ij})={\begin{bmatrix}r_{11}&r_{12}&\cdots &r_{1m}\\r_{21}&r_{22}&\cdots &r_{2m}\\\vdots &\vdots &\vdots &\vdots \\r_{n1}&r_{n2}&\cdots &r_{nm}\end{bmatrix))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26741435e5b54c62598f9d78bbb15992e5325c0b)
称为
的关系矩阵,记作
。
关系图
设
,
是
上的关系,令图
,其中顶点集合
,边集合为
,且对于任意的
,满足
当且仅当
。则称图
是关系
的关系图,记作
。
运算
关系的基本运算有以下几种:
- 设
为二元关系,
中所有有序对的第一元素构成的集合称为
的定义域,记作
。形式化表示为
![{\displaystyle {\mbox{dom))(R)=\{\,x\,|\,(\exists y)[\,(x,y)\in R\,]\,\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce1f9fa4029a638a643b8ac43748c763c0936634)
- 设
为二元关系,
中所有有序对的第二元素构成的集合称为
的值域,记作
。形式化表示为
![{\displaystyle {\mbox{ran))(R)=\{\,y\,|\,(\exists x)[\,(x,y)\in R\,]\,\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/3eb9a97218e58ee4031f801c1e2298ec5c7eb881)
- 设
为二元关系,
的定义域和值域的并集称作
的域,记作
,形式化表示为
![{\displaystyle {\mbox{fld))(R)={\mbox{dom))(R)\cup {\mbox{ran))(R)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0d841b1d8fbe292228b8bf02267e3417873ad7e)
- 设
为二元关系,
的逆关系,简称
的逆,记作
,其中
![{\displaystyle R^{-1}=\{\,p\,|\,(\exists x)(\exists y)[\,(x,y)\in R\wedge p=(y,x)\,]\,\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/eaa2328c374a84878b5ffa46a0610843699133f0)
- 设
为二元关系,
与
的合成关系记作
,其中
![{\displaystyle F\circ G=\{(x,y)|\exists t,~(x,t)\in F\wedge (t,y)\in G\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/e57cdb6290d0d28d39c513cb6f80da2a6206f4cd)
- 设
为二元关系,
是一个集合。
在
上的限制记作
,其中
![{\displaystyle R\upharpoonright A=\{(x,y)|(x,y)\in R\wedge x\in A\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/1939dbe04bca6fea065045a1b4f317f5be868054)
- 设
为二元关系,
是一个集合。
在
下的像记作
,其中
![{\displaystyle R[A]={\mbox{ran))(R\upharpoonright A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a04fd65b154a6a2ccee07823a508a17ca43b92b)
- 设
为
上的二元关系,在右复合的基础上可以定义关系的幂运算:
![{\displaystyle R^{n+1}=R^{n}\circ R\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/36493e731f8979550b11c61109579ec5347281cb)
性质
关系的性质主要有以下五种:
- 自反性:
![{\displaystyle \forall x\in A,~(x,x)\in R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/817ae5d28881c38b1adf04d092e0eb43603b2952)
- 在集合X上的关系R,如对任意
,有
,则称R是自反的。
- 非自反性(自反性的否定的强型式):
![{\displaystyle \forall x\in A,~~(x,x)\notin R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66fdc855bfc7ba1037be4c37b61570640b13713b)
- 在集合X上的关系R,如对任意
,有
,则称R是非自反的。
- 对称性:
![{\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\in R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd821a78266c5750b8e6d26e8c64a735f014a7d0)
- 在集合X上的关系R,如果有
且
必有
,则称R是对称的。
- 反对称性(不是对称性的否定):
![{\displaystyle \forall x,y\in A,~((x,y)\in R\wedge (y,x)\in R)\implies x=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3e5f8ec604d7df4ad774471727630b2688d7553)
- 非对称性(对称性的否定的强型式):
![{\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\notin R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a271a6b07a7c878d8d9fdfdc5cae17176a64ab2)
- 非对称性是 满足非自反性的反对称性。
- 传递性:
![{\displaystyle \forall x,y,z\in A,~((x,y)\in R\wedge (y,z)\in R)\implies (x,z)\in R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/318b62a9321c08599d49b2a59af0df0b8fbe6d17)
设
为集合
上的关系,下面给出
的五种性质成立的充要条件:
在
上自反,当且仅当![{\displaystyle I_{A}\subseteq R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf200e668412a2fa26bd3f8dc990596ae978558d)
在
上非自反,当且仅当![{\displaystyle R\cap I_{A}=\emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/180de104c371c112ea4a859f4a98d64bc4445b6a)
在
上对称,当且仅当![{\displaystyle R=R^{-1}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/da20b830b661807a777d01f973cf7e4550b5b539)
在
上反对称,当且仅当![{\displaystyle R\cap R^{-1}\subseteq I_{A))](https://wikimedia.org/api/rest_v1/media/math/render/svg/a902bcadbc69dd52d4901bc60e7b0f02d9284fac)
在
上非对称,当且仅当![{\displaystyle R\cap R^{-1}=\emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/31a65010b2b3839988f7cf9a452899e3250e1641)
在
上传递,当且仅当![{\displaystyle R\circ R\subseteq R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bec874926f84c336b6bd0c2ae7fc8de35a4abe17)