查看“︁二元关系”︁的源代码

[[数学]]上，'''二元关系'''（{{lang-en|Binary relation}}，或简称'''关系'''）用於讨论两种物件的连系。诸如[[算术]]中的「大於」及「等於」、[[几何学]]中的「相似」或[[集合论]]中的「为……之元素」、「为……之子集」。

== 定义 ==

设<math>A,B</math>为集合，<math>A\times B</math>的任何子集称作<math>A</math>到<math>B</math>的二元关系，特别是当<math>A=B</math>时，称作<math>A</math>上的二元关系,一般记作<math>R</math>。若<math>R \subseteq A \times B</math>, <math>R</math>是从<math>A</math>到<math>B</math>的二元关系；若<math>R \subseteq A \times A</math>,那么<math>R</math>是<math>
A</math>上的二元关系

或是以[[一阶逻辑#量詞的簡寫|正式的邏輯符號]]表述為
:<math>(\forall r \in R)(\exists x)(\exists y)[\,r = (x,\,y)\,]</math>

例一：有四件物件 {''球''，''糖''，''车''，''枪''} 及四个人 {''甲''，''乙''，''丙，丁''} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有车，则「擁有」的二元关系可以寫為

:<math>R</math> = {(''球''，''甲''), (''糖''，''乙''), (''车''，''丁'')}

其中二元[[有序对]]的第一项是被擁有的物件，第二项是擁有者。

例二：[[实数系|實數系]] <math>\mathbb{R}</math> 上的「大於關係」可定義為
:<math>> \,:=
\{\,
(a,\, b) \in {\mathbb{R}}^2
\,|\,
    (\exists r \in \mathbb{R})[\,(a = b + r) \wedge (r \neq 0)\,]
\} </math>
由於習慣上 <math>(a,\,b) \in\, ></math>  通常都是寫為 <math>a > b</math> ，更一般來說，不引起混淆的話會把 <math>(x,\,y)\in R</math> 簡寫成 <math>xRy</math> 。

== 集合的關係 ==
[[集合 (数学)|集合]]<math>X</math>与集合<math>Y</math>上的二元关系則定義為 <math>R=(X, Y, G(R)) </math> ，当中 <math>G(R)\subseteq X \times Y</math> ( 請參見[[笛卡儿积]] ) ，称为 <math>R</math> 的'''图'''。若 <math>(x, y) \in G(R)</math> 则称 <math>x</math> 与 <math>y</math> 有关系 <math>R</math> ，并记作 <math>xRy</math> 或 <math>R(x, y)</math> 。

但经常地我们把关系与其图等价起来，即若 <math>R \subseteq X \times Y</math> 则 <math>R</math> 是一个关系。

话虽如此，我们很多時候索性把集合間的關係 <math>R</math> 定义为 <math>G(R)</math> 而 “有序对 <math> (x,y) \in G(R) </math> ” 即是 “ <math>(x,y) \in R</math> ”。

== 特殊的二元关系 ==

设<math>A</math>是一个集合，则

# 空集<math>\varnothing</math>称作<math>A</math>上的'''空关系'''
# <math>E_{A} = A \times A</math>称作<math>A</math>上的'''全域关系'''（'''完全關係'''）
# <math>I_{A} = \{(x, x)|x \in A\}</math>称作<math>A</math>上的'''恒等关系'''

== 关系矩阵 ==

设<math>X = \{x_1, x_2, \ldots, x_n\}</math>及<math>Y = \{y_1, y_2, \ldots, y_m\}</math>，<math>R</math>是<math>X</math> 和<math> Y</math>上的关系，令
:<math>
r_{ij} = \begin{cases}
 1 & (x_i, y_j) \in R \\
 0 & (x_i, y_j) \notin R
\end{cases}
</math>
则[[0,1矩阵]]
:<math>
(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}
</math>
称为<math>R</math>的'''关系矩阵'''，记作<math>M_{R}</math>。

== 关系图 ==

设<math>A = \{x_1, x_2, \ldots, x_n\}</math>，<math>R</math>是<math>A</math>上的关系，令[[图 (数学)|图]]<math>G=(V, E)</math>，其中[[顶点 (图论)|顶点]]集合<math>V = A</math>，边集合为<math>E</math>，且对于任意的<math>x_i, x_j \in V</math>，满足<math>(x_i, x_j) \in E</math>当且仅当<math>(x_i, x_j) \in R</math>。则称图<math>G</math>是关系<math>R</math>的'''关系图'''，记作<math>G_R</math>。

== 运算 ==

关系的基本运算有以下几种：

* 设<math>R</math>为二元关系，<math>R</math>中所有[[有序对]]的第一元素构成的集合称为<math>R</math>的'''定义域'''，记作<math>\mbox{dom}(R)</math>。形式化表示为
:<math>
\mbox{dom}(R) = \{\, x\,|\,(\exists y)[\, (x, y) \in R\,]\, \}
</math>
* 设<math>R</math>为二元关系，<math>R</math>中所有[[有序对]]的第二元素构成的集合称为<math>R</math>的'''值域'''，记作<math>\mbox{ran}(R)</math>。形式化表示为
:<math>
\mbox{ran}(R) = \{\,y\,|\,(\exists x)[\,(x, y) \in R \,]\, \}
</math>
* 设<math>R</math>为二元关系，<math>R</math>的[[定义域]]和[[值域]]的并集称作<math>R</math>的'''域'''，记作<math>\mbox{fld}(R)</math>，形式化表示为
:<math>
\mbox{fld}(R) = \mbox{dom}(R)\cup\mbox{ran}(R)
</math>
* 设<math>R</math>为二元关系，<math>R</math>的'''逆关系'''，简称<math>R</math>的'''逆'''，记作<math>R^{-1}</math>，其中
:<math>
R^{-1} = \{\,p\,|\,(\exists x)(\exists y)[\,(x, y) \in R \wedge p = (y, x)\,]\,\}
</math>
* 设<math>F, G</math>为二元关系，<math>G</math>與<math>F</math>的'''[[合成關係]]'''记作<math>F \circ G</math>，其中
:<math>
F \circ G = \{ (x, y) | \exists t,~(x, t) \in F \wedge (t, y) \in G \}
</math>
* 设<math>R</math>为二元关系，<math>A</math>是一个集合。<math>R</math>在<math>A</math>上的'''限制'''记作<math>R \upharpoonright A</math>，其中
:<math>
R \upharpoonright A = \{ (x, y) | (x, y) \in R \wedge x \in A\}
</math>
* 设<math>R</math>为二元关系，<math>A</math>是一个集合。<math>A</math>在<math>R</math>下的'''像'''记作<math>R[A]</math>，其中
:<math>
R[A] = \mbox{ran}(R \upharpoonright A)
</math>
* 设<math>R</math>为<math>A</math>上的二元关系，在右复合的基础上可以定义关系的'''幂运算'''：
:<math>R^0 = I_A \ </math> <br><math>R^{n+1} = R^n \circ R \ </math>

== 性质 ==

关系的性质主要有以下五种：

* [[自反关系|自反性]]：<math>\forall x \in A,~(x, x) \in R</math>
:在集合X上的关系R，如对任意<math>x \in X </math>，有<math>(x,x) \in R </math>，则称R是自反的。
* 非自反性（自反性的否定的強型式）：<math>\forall x \in A,~~(x, x) \notin R</math>
:在集合X上的关系R，如对任意<math>x \in X</math>，有<math>(x,x) \notin R</math>，则称R是非自反的。
* [[对称关系|对称性]]：<math>\forall x, y \in A,~(x, y) \in R \implies (y, x) \in R</math>
:在集合X上的关系R，如果有<math>(x,y) \in R</math>且<math>x \neq y</math>必有<math>(y,x) \in R</math>，则称R是对称的。
* [[反对称关系|反对称性]]（不是對稱性的否定）：<math>\forall x, y \in A,~((x, y) \in R \wedge (y, x) \in R) \implies  x = y</math>
* [[非对称关系|非對稱性]]（對稱性的否定的強型式）：<math>\forall x, y  \in A,~(x, y) \in R \implies (y, x) \notin R</math>
:非對稱性是 滿足非自反性的反對稱性。
* [[传递关系|传递性]]：<math>\forall x, y, z \in A, ~((x, y) \in R \wedge (y, z) \in R) \implies (x, z) \in R</math>

设<math>R</math>为集合<math>A</math>上的关系，下面给出<math>R</math>的五种性质成立的充要条件：

# <math>R</math>在<math>A</math>上自反，当且仅当<math>I_A \subseteq R</math>
# <math>R</math>在<math>A</math>上非自反，当且仅当<math>R \cap I_{A} = \emptyset</math>
# <math>R</math>在<math>A</math>上对称，当且仅当<math>R = R^{-1} \ </math>
# <math>R</math>在<math>A</math>上反对称，当且仅当<math>R \cap R^{-1} \subseteq I_{A}</math>
# <math>R</math>在<math>A</math>上非對稱，当且仅当<math>R \cap R^{-1} = \emptyset</math>
# <math>R</math>在<math>A</math>上传递，当且仅当<math>R \circ R \subseteq R</math>

== 闭包 ==

设<math>R</math>是非空集合<math>A</math>上的关系，<math>R</math>的自反（对称或传递）'''闭包'''是<math>A</math>上的关系<math>R'</math>，满足

# <math>R'</math>是自反的（对称的或传递的）
# <math>R \subseteq R'</math>
# 对<math>A</math>上任何包含<math>R</math>的自反（对称或传递）关系<math>R''</math>有<math>R' \subseteq R''</math>

一般将<math>R</math>的自反闭包记作<math>r(R)</math>，对称闭包记作<math>s(R)</math>，[[传递闭包]]记作<math>t(R)</math>。

下列三个定理给出了构造闭包的方法：

# <math>r(R) = R \cup R^0</math>
# <math>s(R) = R \cup R^{-1}</math>
# <math>t(R) = R \cup R^2 \cup R^3 \cup \cdots</math>

对于有限集合<math>A</math>上的关系<math>R</math>，存在一个正整数<math>r</math>，使得
:<math>t(R) = R \cup R^2 \cup \cdots \cup R^r</math>

求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用[[分治法]]降低时间复杂度；但最好的方法是利用基于[[动态规划]]的[[Floyd-Warshall算法]]来求传递闭包。

== 参见 ==

* [[有序对]]
* [[二元集合]]
* [[笛卡儿积]]
* [[偏序关系]]
* [[等价关系]]
* [[相容关系]]

[[Category:数学关系]]