在数学中，二元关系描述两个元素之间的关联。在集合论中，从集合 (A) 到集合 (B) 的关系，是它们的笛卡尔积中的一个子集 (R\subseteq A\times B)。记号 (aRb) 表示 ((a,b)\in R)。相等关系、数值大小关系和函数都可以在这一框架下描述。“二元”指的是关系中每个元组所含的位置数，而非二进制数。(ocw.mit.edu)
定义与记号
关系的组成元素是有序对：第一位置和第二位置各有不同的作用。集合 (A) 上的关系是 (A\times A) 的子集，而不同集合之间的关系所关联的对象不必属于同一类。例如，学生与课程之间的关系可以记录选课情况，允许一名学生与多门课程相关联。这说明，关系不必为每个输入指定唯一的输出。(ocw.mit.edu)
函数 (f:A\to B) 是一种特殊的关系，其中 (A) 的每个元素都恰好与 (B) 的一个元素配对。一般的关系则可以将一个元素与零个、一个或多个元素配对。函数在集合论意义下的图为 [ {(a,f(a)):a\in A}. ] 因此，关系的定义比函数的定义限制更少。(cs.cornell.edu)
对于给定的集合 (A,B)，它们之间的所有关系构成幂集 (\mathcal P(A\times B))。因此，如果 (A) 和 (B) 分别有 (m) 个和 (n) 个元素，就有 (2^{mn}) 个可能的关系：每个可能的有序对都可以包含在关系中，也可以不包含在其中。(ocw.mit.edu)
集合上关系的性质
关系 (R\subseteq A\times A) 可以按以下性质分类：
- 自反性： 对每个 (a\in A)，都有 (aRa)。
- 反自反性： 对任何 (a\in A)，(aRa) 都不成立。
- 对称性： 若 (aRb)，则 (bRa)。
- 反对称性： 若 (aRb) 与 (bRa) 同时成立，则 (a=b)。
- 非对称性： 若 (aRb)，则 (bRa) 不成立。
- 传递性： 若 (aRb) 且 (bRc)，则 (aRc)。(cs.cornell.edu)
反对称性并不是对称性的否定：它只禁止不同元素之间存在双向关联。非对称性还禁止元素与自身关联。例如，(\leq) 具有自反性、反对称性和传递性，而 (<) 具有反自反性、非对称性和传递性。相等关系既具有对称性，也具有反对称性。(cs.cornell.edu)
这些条件都采用全称量化，因此，缺少某些有序对并不一定违反这些条件。空关系具有对称性和传递性，因为相应条件的前提从不成立。在非空的底集上，空关系不具有自反性；但在空集上，自反性也因空真而成立。(cs.cornell.edu)
等价与序
等价关系具有自反性、对称性和传递性。它表达的是按某个选定标准来看相同，而不一定意味着对象本身完全相同。每个元素 (a) 都确定一个等价类 [ [a]_R={b\in A:aRb}. ] 各个不同的等价类构成 (A) 的一个集合划分：每个元素恰好属于一个等价类。这些等价类组成的集合就是商集 (A/R)。(cs.cornell.edu)
例如，在整数上，被某个固定的正整数除后余数相同，是一种等价关系。它给出了模算术中使用的等价类。(cs.cornell.edu)
预序具有自反性和传递性。偏序还满足反对称性。如果任意两个元素都可比较，即 (aRb) 或 (bRa)，那么它就是全序。偏序允许存在不可比较的元素，集合的包含关系就是一个例子。严格偏序具有反自反性和传递性。(cs.cornell.edu)
关系的运算
由于关系是集合，同一个笛卡尔积中的关系可以进行并、交、差运算，以及相对于该笛卡尔积的补运算。并集包含属于任一关系的有序对；交集包含同时属于两个关系的有序对。逆关系将每个有序对的次序颠倒： [ R^{-1}={(b,a):(a,b)\in R}. ] 这一记号并不意味着 (R) 是可逆函数。(cs.cornell.edu)
对于 (R\subseteq A\times B) 和 (S\subseteq B\times C)，关系复合通过一个中间元素将元素关联起来： [ S\circ R={(a,c):\exists b\in B,\ aRb\text{ 且 }bSc}. ] 这里先应用 (R)，遵循函数复合的惯例；有些文献采用相反的顺序。复合满足结合律，但通常不满足交换律。恒等关系 (I_A={(a,a):a\in A}) 是相应复合运算的单位元。(cs.cornell.edu)
图、闭包与计算
集合 (A) 上的关系可以用有向图表示：元素对应顶点，每个有序对 ((a,b)) 对应一条箭头 (a\to b)。自反性要求每个顶点都有自环；对称性要求每条箭头都有一条反向箭头；传递性要求，只要两条首尾相接的箭头形成一条路径，这条路径的起点和终点之间就必须有一条直接相连的箭头。(cs.cornell.edu)
传递闭包 (R^+) 恰好补入所有通过一步或多步关系连接起来的有序对。自反传递闭包 (R^) 还允许零步： [ R^+=\bigcup_{n\geq1}R^n,\qquad R^=\bigcup_{n\geq0}R^n,\qquad R^0=I_A. ] 它们分别是包含 (R) 的最小传递关系和最小自反传递关系。(cs.cornell.edu)
在形式验证中，程序可以被解释为初始状态与最终状态之间的关系。复合用于建模顺序执行，自反传递闭包则用于建模任意次数的重复执行，包括零次。这种解释不仅适用于确定性函数，也能涵盖具有多种可能结果的计算。(cs.cornell.edu)