同値関係とは Euclid 的対応のことである
Udaです．4月に東北大学から富山大学に異動しました．心機一転ということで，数学のアウトプットを少しずつ増やして行こうと思っています．
ここ数年は特に順序集合の周辺に興味を持って研究していました．とは言え，専門を順序集合論と自称するのも色々とおかしい気がするので，とりあえず専門は応用数学全般と名乗ることにしています．応用だの名乗る割には順序に関連する位相であったりそれを上手く扱うのに圏論を持ち出して考えてみたりと，全然応用らしからぬことばかりやっていたりもするのですが，動機が純粋に応用から来ている研究をしているので，依然「自分は応用数学者である」というスタンスでやっています．
同値関係とは Euclid 的対応のことである
さて，本題へ．順序と同じ括りというか，最近一般の二項関係に関することもアンテナを張っていて，先日 同値関係の定義式は減らせる という記事を Twitter で見かけて興味深かったので，これについて取り上げてみます．Euclid 律というのがあってこれを使うと同値関係の定義を簡素にできるという内容ですnote:motcho:20240411．主張を先に簡単に紹介します．
集合 $X$ 上の二項関係 $R$ が同値関係であることと，左 Euclid 的かつ左全域的であることは必要十分である．
このステートメントは，元記事note:motcho:20240411で示されている命題を，本稿でこれから定義していく用語を用いて翻訳し直したものですが，後に改めて正確に解説します．
元記事終盤でも証明はしていますが，本稿ではこれを関係代数，特に全域性の概念を使って整理します．元記事では全域性という用語は出て来ませんが，実は
すべての元に対して関係する元が存在
という条件が全域性に相当します．そして，ここから出てくるとある補題を使うと，証明の骨子は本質的に全く同じですが，関係代数の言葉を使った見通しの良い証明が出来上がったので，これを紹介したいと思います．
基本的な用語の定義
まず，二項関係に関連する基本的な用語を一通り定義しておきます．
$X, Y$ を集合とする．$X \times Y$ の部分集合 $R$ を $X$ と $Y$ の間の二項関係と呼ぶ．$X = Y$ のとき $R$ $(\subset X^2)$ を $X$ 上の二項関係という．$(x, y) \in R$ のときに $x$ と $y$ は $R$ 関係するといい，$x \mathrel{R} y$ と表記する．
ちなみに，$X$ 上の二項関係のことは homogeneous な関係（自己関係）とも言うのですが，これは却って聞き慣れなくてギョッとして「えっ それ何ですっけ？」となるような感じがし，私は単に「〜上の二項関係」とだけ言ってしまうことが多いです．
$X, Y, Z$ を集合とし，$R$ を $X$ と $Y$ の，$S$ を$Y$ と $Z$ の間の二項関係とする．このとき，これらの二項関係の合成を
\begin{equation}
RS \coloneqq \{
(x, z) \in X \times Z \mid \text{$x \mathrel{R} y$ かつ $y \mathrel{S} z$ なる $y \in Y$ が存在する}
\}
\end{equation}
で定める．$RS$ は $X$ と $Z$ の間の二項関係である．
二項関係の合成を表す記法として，関数合成と同じ順で書き記す見慣れた $S \circ R$ や，ちょっとマイナーな $R; S$ のようなものもあります．$RS$ と $R;S$ に関しては，図式で描いたときに図式通りの順番の合成になっていることから，図式順 (diagrammatic order) の合成という呼び方をすることもありますnlab:composition．本稿では $RS$ というもっともシンプルな，「積」のように見える記法を採用します．
「積」を定義したので，次は関係代数の「逆」にあたる演算を定義します．これは単純に，二項関係 $R$ の始域 $X$ と終域 $Y$ を入れ替える操作です．
$X$ と $Y$ の間の二項関係 $R$ に対して，
$R^\top \coloneqq \{(y, x) \in Y \times X \mid x \mathrel{R} y\}$ を $R$ の転置と呼ぶ（逆関係とも呼ばれる）．
転置には色々な別名がありますが，本稿では行列との類推から転置の呼称・記法を採用します．記法も，如何にも逆らしい $R^{-1}$ や，スマイル記号を使って表す $R^\smallsmile$ など，様々なものがあります．まさに逆写像のようなものですが，逆写像と違い転置はどのような二項関係に対してもとれます．
さて，二項関係は集合に関する操作(和集合・共通部分・補集合など)に加えて積(合成)・逆(転置)といった演算を備えている訳ですね．一般にこのような演算を備えた体系を関係代数と呼びますenwp:calc_relenwp:rel_algjawp:rel_alg．関係代数を使うと，反射律・対称律・推移律といった二項関係に関する性質もシンプルに表現できます．例えば，対称律「$x \mathrel R y \Rightarrow y \mathrel R x$」は，二項関係の包含関係と転置を用いて $R^\top \subseteq R$と表すことができます．
左右全域性
基本的な用語の説明はこれで終わりです．次は全域性とこれに関する補題を述べます．
- $R$ が左全域的 (left-total, 単に total とも) であるとは，全ての $x \in X$ に対して $y \in Y$ が存在して $x \mathrel{R} y$ となることである．
- $R$ が右全域的 (right-total, surjective, onto とも) であるとは，全ての $y \in Y$ に対して $x \in X$ が存在して $x \mathrel R y$ となることである．
- （本稿では）左全域的かつ右全域的な二項関係を対応 (correspondence) と呼ぶ．
写像の全射性を想像すると分かりやすいです．左全域性は定義域が全体であること，右全域性は値域が全体であることに対応しています．ただし，今は二項関係の話なので左右の区別に注意してください．
用語についてもいくつかリマークしておきます．まず，homogeneous な二項関係の場合 (つまり $X = Y$ のとき)，左全域的関係は serial relation とも呼ばれますenwp:serial．それから，左を略して単に全域的と言ったりすることもあるようですが，本稿では右全域性も用いますし，さらに英語でも全順序 "total order" の total とまた意味が異なってややこしいなどの問題があります．そこで本稿では左右は省略した用語は使いません．また，実は左全域的関係のことを「対応」と呼ぶ流儀もありますjawp:correspondence．ただ，これは多価写像の文脈で使われるようですし，「全単射＝一対一対応」の一対一の条件を落としたものがまさに対応であるという見方もできますjawp:relation#specific_typesから，本稿では「左全域的かつ右全域的」という大事な性質を持つ二項関係に対応という名前を与えることにします．
補題を見ていきましょう．以下，$X$ 上の恒等関係を $I_X \coloneqq \{(x, x) \mid x \in X\}$ と書くことにします．これは恒等写像の二項関係版ですが，大事なことはこれが二項関係の合成（積）の単位元になっているということです．後で使うので覚えておいてください．
$R$ を $X$ と $Y$ の間の二項関係とする．
- $R$ が左全域的であることと $I_X \subseteq R R^\top$ は必要十分条件である．
- $R$ が右全域的であることと $I_Y \subseteq R^\top R$ は必要十分条件である．
転置で双対な命題なので片方だけ証明すれば十分である．前者の必要条件を示す．定義より，
\begin{equation}
R R^\top = \{ (x, z) \in X^2 \mid \text{$x \mathrel{R} y,\ y \mathrel{R^\top} z$ なる $y \in Y$ が存在する}\}.
\tag{1} \label{eqn:RRT}
\end{equation}
任意に $x \in X$ をとる．$R$ が左全域的とすると，左全域性より $x \mathrel{R} y$ なる $y \in Y$ が存在する．このような $y$ をとれば $x \mathrel{R} y, \ y \mathrel{R^\top} x$ が成り立つ．よって，式\eqref{eqn:RRT} より $x \mathrel{R R^\top} x$ が全ての $x$ に対して成り立つ．すなわち，
\begin{equation}
I_X = \{(x, x) \mid x \in X \} \subseteq R R^\top.
\end{equation}
逆に，この包含関係が成り立つとき，任意にとった $x \in X$ に対して式 \eqref{eqn:RRT} より $y \in Y$ が存在して $x \mathrel{R} y$ が成り立つ．つまり，$R$ は左全域的である．
実際にはこのあと必要条件の方しか使いませんが，一応十分条件の方も示しておきました．同値になるので，性質 $I_X \subseteq R R^\top$ を左全域律とか呼びたいところなのですが，ちょっとこれは語感が悪いし聞いたことないのでやめておきましょう．
小言：英語の Wikipediaenwp:relationではこの命題の必要条件の方が述べられていますが，微妙に不正確です．前者でなぜか serial relation と仮定されていますが，単に left-total だけで十分です．また，matrix を用いて表現できる関係であると暗に仮定して $m \times m$ identity relation のような書き方が出てくるのですが，もちろん有限性も本質的ではないところです．ついでに，いきなり合成演算子がここで省略され始めます．証明してみればすぐにどちらの意味で書いているか分かるとは言え，左右の区別が重要な文脈でこういう雑なことをしないで欲しいですね……
Euclid 律
さて，Euclid 律を復習しておきます．以下，$R$ は $X$ 上の二項関係とします．
- $R$ が左 Euclid 的であるとは，全ての $x, y, z \in X$ に対して $x \mathrel R y$ かつ $z \mathrel R y$ ならば $x \mathrel R z$ が成り立つことである．
- $R$ が右 Euclid 的であるとは，全ての $x, y, z \in X$ に対して $y \mathrel R x$ かつ $y \mathrel R z$ ならば $x \mathrel R z$ が成り立つことである．
- $R$ が左 Euclid 的であることと $R R^\top \subseteq R$ は必要十分である．
- $R$ が右 Euclid 的であることと $R^\top R \subseteq R$ は必要十分である．
よく見ると存在量化と全称量化の違いがありますが，定義からほぼ明らかですから補題の証明は省略します．
単に Euclid 律と言えば右 Euclid 律のことを指すことが多いようですjawp:relation#specific_typesenwp:euclidean_relationjawp:eqv．一方，今回の元になった記事note:motcho:20240411では，左 Euclid 律のことを Euclid 律と呼んでいます：
目的の式の「$a\sim b$ かつ $c \sim b$ $\Rightarrow$$a \sim c$」には名前があります。「ユークリッド律」というのです。
（左右 Euclid 律の区別をご存じなかっただけですかね．）
なお，左 Euclid 律 $R R^\top \subseteq R$ で転置をとれば直ちに $R R^\top \subseteq R^\top$ が分かります（行列の転置と同様に関係の積の転置も積の順序が入れ替わることに注意してください）．よって，実は左 Euclid 的な二項関係 $R$ は $R R^\top \subseteq R \cap R^\top$ を満たします．このため，$R R^\top \subseteq R \cap R^\top$ のことを左 Euclid の定義にすることもあるようですが，もちろんこれらは同値な定義になっています．
※コピペできなかったので手写し引用したのですが書き間違えていました．ご指摘感謝します．
Euclid 的対応
では，定理と証明に入っていきます．
$R$ を $X$ 上の二項関係とする．このとき，以下は互いに必要十分条件である．
- $R$ は同値関係である（つまり，$R$ は反射律・対称律・推移律を満たす）．
- $R$ は左 Euclid 的かつ左全域的である．
- $R$ は右 Euclid 的かつ右全域的である．
- $R$ は左右 Euclid 的対応である．
同値関係ならば左右 Euclid 的対応で，このとき(ii)と(iii)を満たすことは明らかです．また，(ii)または(iii)から(i)を示す方向も，左右の違いで転置をとるだけなので，残りどちらか片方だけ示せば十分です．今回は元記事に合わせて，左 Euclid 的対応が同値関係であることを示してみましょう．
左全域性より補題を $R$ に適用し，左 Euclid 律を使えば，
$$ I_X \subseteq R R^\top \subseteq R.$$
よって，$R$ は反射的である．また，反射律に $R^\top$ を右から合成して再び左 Euclid 律を用いれば，
$$ R^\top = I_X R^\top \subseteq R R^\top \subseteq R. $$
よって，$R$ は対称的である．最後に，対称律 $R \subseteq R^\top$ と左 Euclid 律を組み合わせれば，推移律 $R R \subseteq R$ を得る．よって，$R$ は推移的である．
以上より，左 Euclid 的かつ左全域的な二項関係は同値関係である．
定理から，すぐに以下の系がしたがいます．Wikipedia にもこちらの形の同値命題が書かれている辺り，よく知られているのはむしろこちらなのかもしれません．
$R$ が同値関係であることと，$R$ が反射的かつ Euclid 的であることは必要十分である．
反射律から左右全域性がしたがいますし，同値関係は反射律を満たしますから，当たり前ですね．
最後に，ここまで出てきた性質とその関係代数での言い換えを表にしてまとめておきます．
| 性質/公理の名前 | 定義 | 関係代数での言い換え |
|---|---|---|
| 反射律 | $\forall x.\ x \mathrel R x$ | $I_X \subseteq R$ |
| 対称律 | $\forall x,y. \ x \mathrel R y \imply y \mathrel R x$ | $R \subseteq R^\top$ |
| (対称律の転置) | $R^\top \subseteq R$ | |
| 推移律 | $\forall x,y,z. \ x \mathrel R y,\ y \mathrel R z \imply x \mathrel R z$ | $RR \subseteq R$ |
| 左全域性 | $\forall x.\ \exists y.\ x \mathrel R y$ | $I_X \subseteq RR^\top$ |
| 右全域性 | $\forall y.\ \exists x.\ x \mathrel R y$ | $I_Y \subseteq R^\top R$ |
| 対応 | 左全域右全域的 | $I_X \subseteq RR^\top$, $I_Y \subseteq R^\top R$ |
| 左 Euclid 律 | $\forall x,y,z. \ x \mathrel R y,\ z \mathrel R y \imply x \mathrel R z$ | $RR^\top \subseteq R$ |
| 右 Euclid 律 | $\forall x,y,z. \ y \mathrel R x,\ y \mathrel R z \imply x \mathrel R z$ | $R^\top R \subseteq R$ |
| 同値関係(i) | 反射対称推移的 | $I_X \subseteq R \subseteq R^\top$, $RR \subseteq R$ |
| 同値関係(ii) | 左全域左 Euclid 的 | $I_X \subseteq R R^\top \subseteq R$ |
| 同値関係(系1) | 反射左 Euclid 的 | $I_X \subseteq R$, $R R^\top \subseteq R$ |
※表の左 Euclid 律の定義を書き間違えていました．ご指摘感謝します．
まとめ
関係代数を使ったことで，元を取り出さずに二項関係の包含関係式だけで定理の証明がまとまったのは個人的に面白いところだと思います．圏論的な証明だったとはまでは言いませんが，反射律・対称律・推移律・Euclid 律・左右全域性と登場人物皆を包含関係で書けたので上手くハマった感じですね．まぁ，元をとる証明を補題を使ってカプセル化しただけとも言います．
タイトルでは「同値関係とは Euclid 的対応のことである」と書きましたが，証明を見ていただければ分かるように，実は左 Euclid 律と左全域性の仮定だけから同値関係であると証明できてしまいました．証明には片側だけで十分なんですね．元記事note:motcho:20240411では
すべての元に対して関係する元が存在
と左右無頓着に述べていたり，あと私も途中
「左全域的かつ右全域的」という大事な性質を持つ二項関係に対応という便利な名前を与える
とかドヤ顔で定義していましたが，これらはどちらも実は今回の話では過剰な条件だったのです．左右のうちもう片方は自動的に出てくる性質だったんですね．ぶっちゃけ証明を書き出してみるまで私自身も両方要るものと思い込んでいました．タイトルは短い方がインパクトがあると思うので，このままにしておきます（笑）
オチもついたので（？）今日はこの辺で👋
ところで，この記事は出張帰りに新幹線の中で書いたので，書籍が手元になく参考文献が Wikipedia だらけになっています．確か，allegory とかそういうのが出てくる手持ちの PDF に確か抽象関係代数関係の話が載っていた気がするのですが，残念ながらすぐに見つけられそうにありません…… はて，どの文献でしたかね．そういう訳で，Wikipediaの誤りに小言を投げつつたくさん引用しましたが，正確性のためというよりも，あくまで用語や記法の用例を参照し曖昧さを回避するために引用したものが多いとご理解ください．
ついでに，実は関係代数には「関係代数（数学）」と「関係代数（データベース）」とがあって，概ね日本語でも英語でも後者の方がたくさん出てくるという超絶ググラビリティ低い問題があります．検索してもなかなか辿り着けないので，自分用のリンク集も兼ねています．