二項関係
関係の定義
集合Aから集合Bへの二項関係Rは、A \times Bの部分集合である。
(x, y) \in Rのとき、xとyはR-関係にあるといい、
x\ R\ y
と書く。
全体関係/空関係
A上の関係において、R = A \times Aを全体関係と呼び、R = \emptysetを空関係と呼ぶ。
逆関係
AからBへの関係Rの逆関係R^{-1}とは、B からAへの関係であり、以下のように定義される。
R^{-1} = \{(y, x) | (x, y) \in R\}
また、次が成り立つ。
x\ R\ y \iff y\ R^{-1}\ x
関係の合成
RをAからBへの関係、SをBからCへの関係とすると、RとSの合成とは、
R \circ S = \{(x, z) \in A \times C\ |\ \exists y \in B (x\ R\ y \land y\ S\ z)\}
のこと。上記のR \circ SをS \circ Rと書く場合がある。
結合法則が成り立つ。
(R \circ S) \circ T = R \circ (S \circ T)
関係の性質
RをA上の関係とする。
反射性
任意のx \in Aについてx\ R\ xであるとき、Rは反射的である。
対称性
任意のx, y \in Aについてx\ R\ yならばy\ R\ xであるとき、Rは対称的である。
反対称性
任意のx, y \in Aについてx\ R\ yかつy\ R\ xならばx = yであるとき、Rは反対称的である。
推移性
任意のx, y, z \in Aについてx\ R\ yかつy\ R\ zならばx\ R\ zであるとき、Rは推移的である。
同値関係
関係が反射的、対称的、推移的であるとき、その関係は同値関係であるという。
同値類
Rを集合A上の同値関係とする。Aの要素aの同値類とは、a\ R\ xとなる全てのxからなる集合のことである。
[a] = \{x \in A\ |\ a\ R\ x\}
商集合
Rを集合A上の同値関係とする。Rで定まる全ての同値類からなる集合をRによるAの商集合という。
A / R = \{[x] \subset A\ |\ x \in A\}