関係

2 つの集合の要素の間の対応。 直積の部分集合として定義する。

$$R\subseteq A\times B$$

$(a,b)\in R$ を $aRb$ と書く。

二項関係の性質#

性質	条件
反射律	$\forall a:aRa$
対称律	$aRb\Rightarrow bRa$
推移律	$aRb\wedge bRc\Rightarrow aRc$
反対称律	$aRb\wedge bRa\Rightarrow a=b$

2 つの重要な型#

同値関係 = 反射 + 対称 + 推移。 集合を互いに交わらない同値類に分割する。 「同じとみなす」という操作の数学的な定式化。

半順序 = 反射 + 反対称 + 推移。 包含関係 $\subseteq$、整除関係など。 すべての対が比較可能とは限らない点が全順序と違う。

多目的最適化のパレート優越も半順序で、 だから「最良の 1 点」が定まらずパレート面になる。

参考文献#

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• MIT OCW 6.042J Mathematics for Computer Science https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/