10.9 直積順序

既存の二項関係から新しく二項関係を作る有用な手段として、二項関係の直積がある:

定義 10.9.1

二項関係 \(R_{1}\), \(R_{2}\) に対して次の規則で定義される二項関係 \(R_{1} \times R_{2}\) を \(R_{1}\) と \(R_{2}\) の直積 (product) と呼ぶ:

\[ \begin{aligned} \operatorname{domain}(R_{1} \times R_{2}) &::= \operatorname{domain}(R_{1}) \times \operatorname{domain}(R_{2}) \\ \operatorname{codomain}(R_{1} \times R_{2}) &::= \operatorname{codomain}(R_{1}) \times \operatorname{codomain}(R_{2}) \\ (a_{1}, a_{2})\; (R_{1} \times R_{2})\; (b_{1}, b_{2}) &\ \ \overset{\text{def}}{\longleftrightarrow}\ \ (a_{1} \mathrel{R_{1}} b_{1}) \ \operatorname{\text{\footnotesize AND}} \ (a_{2} \mathrel{R_{2}} b_{2}) \end{aligned} \]

この定義が推移性、反射性、非反射性、反対称性を保存することは容易に分かる (問題 10.52)。つまり \(R_{1}\), \(R_{2}\) が両方ともいずれかの性質を持つなら、\(R_{1} \times R_{2}\) もその性質を持つ。例えば \(R_{1}\) と \(R_{2}\) が半順序なら \(R_{1} \times R_{2}\) も同じ半順序となる。

例 10.9.2

年齢 (月換算) を表す非負整数 \(y \leq 2400\) と身長 (インチ) を表す非負整数 \(h \leq 120\) の組 \((y, h)\) 全体の集合上の二項関係 \(Y\) を、年齢と身長が両方とも低い場合に成り立つものとして定義する。つまり \(Y\) は次の規則で定義される:

\[ (y_{1}, h_{1}) \mathrel{Y} (y_{2}, h_{2}) \ \ \longleftrightarrow \ \ y_{1} \leq y_{2} \ \operatorname{\text{\footnotesize AND}} \ h_{1} \leq h_{2} \]

この \(Y\) は年齢に関する \(\leq\) 関係と身長に関する \(\leq\) 関係の直積である。

年齢と身長はどちらも数値的に並んでいるので、年齢と身長に関する二項関係 \(Y\) は弱半順序である。教室に学生が \(101\) 人いるとする。このとき Dilworth の補題 (補題 10.5.12) からは、\(11\) 人の学生からなる鎖 (身長が低い順位並べると年齢が低い順になる学生の集合)、または \(11\) 人の学生からなる反鎖 (身長が低い順に並べると年齢が高い順になる学生の集合) が存在すると分かる。講義の余興としてはピッタリだろう。

なお、直積は「線形順序である」という性質を保存しない。例えば年齢と身長に関する二項関係 \(Y\) は二つの線形順序の直積であるものの、\(Y\) 自体は線形順序でない: 例えば組 \((240, 68)\) と組 \((228, 72)\) は \(Y\) で比較可能でない。