形式陈述

从 $A$$A$ 到 $B$$B$ 的二元关系是子集 $R\subseteq A\times B$$R\subseteq A\times B$，写作 $aRb$$aRb$ 表示 $(a,b)\in R$$(a,b)\in R$。其定义域、值域和逆关系分别由

$$ \operatorname{dom}R=\{a:\exists b\,aRb\},\quad \operatorname{ran}R=\{b:\exists a\,aRb\},\quad R^{-1}=\{(b,a):aRb\} $$$$\mathrm{dom}R=\{a:\mathrm{\exists }baRb\},\mathrm{ran}R=\{b:\mathrm{\exists }aaRb\},R^{-1}=\{(b,a):aRb\}$$

给出。

直觉

关系只记录哪些对象对被认为相关，不要求每个输入有输出，也不要求输出唯一。函数、偏序和等价关系都是加入额外约束后的关系。

例子与边界

整数上的整除关系、集合上的包含关系都是关系。$R=\{(1,a),(1,b)\}$$R=\{(1,a),(1,b)\}$ 是合法关系，但不是从 $\{1\}$$\{1\}$ 到 $\{a,b\}$$\{a,b\}$ 的函数，因为输入 $1$$1$ 对应两个输出。

推论与应用

关系为图的边集、数据库表、转移系统和语义判断提供统一表示。关系复合与闭包支持可达性和程序分析。

参考资料

• Paul R. Halmos, Naive Set Theory, 1960; Dover reprint 2017, §7。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Relations chapter。