斎藤毅『集合と位相』命題7.1.5(改)

前エントリの証明を簡潔にした。命題3・4を経由せずに命題5を帰納法で直接証明し、命題4はその特別な場合(命題6(1))として証明した。また命題6(2)では自然数の整列性を積極的に用いた。なお、対応が分かりやすいよう、命題番号はそのままとした。

【命題1】単射の定義域と値域とは対等である。

(証明)単射$f:X\to Y$に対し写像$\begin{array}{ccc
}X&\to&f[X]\\x&\mapsto&f(x)\end{array}$は$\mbox{dom}(f)$から$\mbox{ran}(f)$への全単射となる。■

【定義】集合$A\subseteq\mathbb{N}$に対し写像$C_A:\mathbb{N}\to\mathbb{N}$を次のように再帰的に定義する。ただし$n'$は後続数$n\cup\{n\}$を表す。\[C_A(0)=0,\]\[C_A(n')=\left\{\begin{array}{ll}(C_A(n))'&(n\in A)\\C_A(n)&(n\notin A)\end{array}\right.\]

【命題2】任意の$A\subseteq\mathbb{N},n\in\mathbb{N}$に対して$C_A(n)\leq n$であり、等号は$n\subseteq A$のときのみ成立する。

(証明)$A\subseteq\mathbb{N}$を任意にとり、$n$についての帰納法を用いる。まず$C_A(0)=0\leq 0$であり、$0=0$と$0\subseteq A$はともに真である。$C_A(n)\leq n$(等号は$n\subseteq A$のときのみ成立)を仮定すると、$C_A(n')$は$C_A(n)$または$(C_A(n))'$のいずれかの値をとるから、どちらにせよ$n'$以下である。$C_A(n')=n'$となるのは$C_A(n)=n$かつ$C_A(n')=(C_A(n))'$のときのみ、すなわち$n\subseteq A$かつ$n\in A$のときのみであり、これは$n'\subseteq A$とまとめられる。■

【命題5】任意の$A\subseteq\mathbb{N}, n\in\mathbb{N}$に対して、$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である。

(証明)任意に$A$をとって$\varphi(n)$:「$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である」とおき、$n$についての帰納法を用いる。$\varphi(0)$については空写像が単射であり値域が空であることから従う。$\varphi(n)$を仮定して$\varphi(n')$を導く。$C_A\vert_{A\cap n'}$という写像は、$n\notin A$のときは$C_A\vert_{A\cap n}$と同じであり、$n\in A$のときはこれに$n\mapsto C_A(n)$という対応を追加したものである。$\varphi(n)$により値域はそれぞれ$C_A(n)$と$C_A(n)\cup\{C_A(n)\}$であり、いずれにせよ$C_A\vert_{A\cap n'}$は単射であり値域は$C_A(n')$と書ける。■

【命題6】(1)$A\subseteq n\in\mathbb{N}$なる任意の$A,n$について、$C_A\vert_A$は単射であり、その値域は$C_A(n)$である。

(2)$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たない(つまり、いかなる$n\in\mathbb{N}$に対しても$A\backslash n\neq\varnothing$である)とき、$C_A\vert_A$は単射であり、その値域は$\mathbb{N}$である。

(証明)(1)$A\subseteq n$から$A=A\cap n$、これと命題5により従う。

(2)(単射性)$x,y\in A$かつ$x\neq y$を仮定して$C_A(x)\neq C_A(y)$を導く。$x\in y$または$y\in x$が成り立つので、前者の場合について示せば後者も同様である。命題5により、$C_A\vert_{A\cap y}$の値域は$C_A(y)$である。$x$はこの写像の定義域に属すので$C_A(x)\in C_A(y)$、したがって$C_A(x)\neq C_A(y)$である。

(値域)帰納法を用いて$\mathbb{N}\subseteq\mbox{ran}(C_A\vert_A)$を示す。まず$A=A\backslash 0\neq\varnothing$から$k=\mbox{min} A$がとれて、命題5より$C_A(k)=\mbox{ran}(C_A\vert_{A\cap k})=\mbox{ran}(C_A\vert_\varnothing)=\varnothing=0$、したがって$0$は$C_A\vert_A$の値域に属す。次に$n\in\mbox{ran}(C_A\vert_A)$を仮定して$n'\in\mbox{ran}(C_A\vert_A)$を導く。この仮定により$C_A(s)=n$ なる$s\in A$がとれるが、$A\backslash s'\neq\varnothing$により$t=\mbox{min}(A\backslash s')$がとれる。すると$A\cap t=A\cap s'$であり、命題5により$C_A(t)=\mbox{ran}(C_A\vert_{A\cap t})=\mbox{ran}(C_A\vert_{A\cap s'})=C_A(s')=(C_A(s))'=n'$となるから、$n'$は$C_A\vert_A$の値域に属す。■

【命題7】(1)$n\in\mathbb{N}, A\subseteq n$のとき、$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)\leq n$である(等号は$A=n$のときのみ成立)。

(2)$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たないとき、$A$は可算無限集合である。

(証明)(1)命題6(1)と命題1により$A$と$C_A(n)\in\mathbb{N}$は対等であるから$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)$である。また命題2よりこれは$n$以下であり、等号は$n\subseteq A$のとき、すなわち$A=n$のときのみ成立する。

(2)命題6(2)と命題1により$A$と$\mathbb{N}$は対等であるから、$A$は可算無限集合である。■

斎藤毅『集合と位相』命題7.1.5

より簡明な議論が次のエントリにあります。

【命題1】単射の定義域と値域とは対等である。

(証明)単射$f:X\to Y$に対し写像$\begin{array}{ccc
}X&\to&f[X]\\x&\mapsto&f(x)\end{array}$は$\mbox{dom}(f)$から$\mbox{ran}(f)$への全単射となる。■

【定義】集合$A\subseteq\mathbb{N}$に対し写像$C_A:\mathbb{N}\to\mathbb{N}$を次のように再帰的に定義する。ただし$n'$は後続数$n\cup\{n\}$を表す。\[C_A(0)=0,\]\[C_A(n')=\left\{\begin{array}{ll}(C_A(n))'&(n\in A)\\C_A(n)&(n\notin A)\end{array}\right.\]

【命題2】任意の$A\subseteq\mathbb{N},n\in\mathbb{N}$に対して$C_A(n)\leq n$であり、等号は$n\subseteq A$のときのみ成立する。

(証明)$A\subseteq\mathbb{N}$を任意にとり、$n$についての帰納法を用いる。まず$C_A(0)=0\leq 0$であり、$0=0$と$0\subseteq A$はともに恒真である。$C_A(n)\leq n$(等号は$n\subseteq A$のときのみ成立)を仮定すると、$C_A(n')$は$C_A(n)$または$(C_A(n))'$のいずれかの値をとるから、どちらにせよ$n'$以下である。$C_A(n')=n'$となるのは$C_A(n)=n$かつ$C_A(n')=(C_A(n))'$のときのみ、すなわち$n\subseteq A$かつ$n\in A$のときのみであり、これは$n'\subseteq A$とまとめられる。■

【命題3】任意の$A\subseteq\mathbb{N}, n\in\mathbb{N}$に対して$C_A\vert_{n'}=C_{A\cap n}\vert_{n'}$が成り立つ。

(証明)$A\subseteq\mathbb{N}, n\in\mathbb{N}$を任意にとる。$\varphi(m)$:「$m\in n'$ならば$C_A(m)=C_{A\cap n}(m)$」とおき、$m$についての帰納法を用いる。$\varphi(0)$は$C_A(0)=C_{A\cap n}(0)=0$により成り立つ。次に$\varphi(m)$を仮定して$\varphi(m')$を導く。そのために、さらに$m'\in n'$を仮定して$C_A(m')=C_{A\cap n}(m')$を導く。$m\in n$より$m\in A$と$m\in A\cap n$の真偽は一致するから、示したい等式の両辺は、「$(C_A(m))'$と$(C_{A\cap n}(m))'$」にそれぞれ等しくなる($m\in A$のとき)か、さもなくば「$C_A(m)$と$C_{A\cap n}(m)$」にそれぞれ等しくなる($m\notin A$のとき)。いま$m\in n'$と$\varphi(m)$により$C_A(m)=C_{A\cap n}(m)$であるから、いずれの場合においても両者は等しくなる。■

【命題4】$n\in\mathbb{N}, A\subseteq n$のとき、$C_A\vert_A$は単射であり、その値域は$C_A(n)$となる。

(証明)$\varphi(n)$:「$A\subseteq n$ならば$C_A\vert_A$は単射であり、その値域は$C_A(n)$」とおき、$n$に関する帰納法を用いる。$\varphi(0)$については、$A\subseteq 0$ならば$A=\varnothing$から$C_A\vert_A=C_\varnothing\vert_\varnothing$は空写像となり単射、またその値域は$\varnothing=C_\varnothing(0)$となることから成立する。次に$\varphi(n)$を仮定して$\varphi(n')$を導く。そのために、さらに$A\subseteq n'$を仮定して「$C_A\vert_A$は単射であり、その値域は$C_A(n')$」であることを導く。$n\notin A$の場合は$A\subseteq n, C_A(n')=C_A(n)$と$\varphi(n)$から直ちに従う。$n\in A$の場合、$C_A\vert_A$は「$C_A\vert_{A\cap n}$に$n\mapsto C_A(n)$という対応を追加したもの」である。いま$A\subseteq n'$と命題3により$C_A\vert_A=C_{A\cap n}\vert_A$が成り立っており、定義域を$n$未満と$n$に分けて書くと「(1)$C_A\vert_{A\cap n}=C_{A\cap n}\vert_{A\cap n}$かつ(2)$C_A(n)=C_{A\cap n}(n)$」となる。(1)により$C_A\vert_A$は「$C_{A\cap n}\vert_{A\cap n}$に$n\mapsto C_A(n)$という対応を追加したもの」と言い換えられる。$A\cap n\subseteq n$と$\varphi(n)$から$C_{A\cap n}\vert_{A\cap n}$は単射であり、値域は$C_{A\cap n}(n)$である。この値域は(2)により$C_A(n)$と書き直せる。$C_A(n)$は$C_A(n)$自身に属さない(どの要素とも異なる)から、この単射に先ほどの対応を追加しても単射のままであり、値域は$C_A(n)\cup\{C_A(n)\}=(C_A(n))'$となる。いま$n\in A$であるから、これは$C_A(n')$に等しい。■

【命題5】任意の$A\subseteq\mathbb{N}, n\in\mathbb{N}$に対して、$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である。

(証明)$A\cap n\subseteq n$と命題4により、$C_{A\cap n}\vert_{A\cap n}$は単射であり、その値域は$C_{A\cap n}(n)$である。いま$A\cap n\subseteq n'$と命題3より、$C_A\vert_{A\cap n}=C_{A\cap n}\vert_{A\cap n}$かつ$C_A(n)=C_{A\cap n}(n)$が成り立つので、これらを用いて言い直すと、$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である。■

【命題6】$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たないとき、$C_A\vert_A$は単射であり、その値域は$\mathbb{N}$である。

(証明)

・単射性:$x,y\in A$かつ$x\neq y$を仮定して$C_A(x)\neq C_A(y)$を導く。$x\in y$または$y\in x$が成り立つので、前者の場合について示せば後者も同様である。命題5により、$C_A\vert_{A\cap y}$の値域は$C_A(y)$である。$x$はこの写像の定義域に属すので$C_A(x)\in C_A(y)$、したがって$C_A(x)\neq C_A(y)$である。

・値域:帰納法を用いて$\mathbb{N}\subseteq\mbox{ran}(C_A\vert_A)$を示す。まず$A\subseteq 0$でないことから$k\in A$がとれて、命題5より$C_A\vert_{A\cap k'}$の値域は$C_A(k')$である。いま$k\in A$により$C_A(k')=(C_A(k))'\ni 0$であるから、$0$は$C_A\vert_{A\cap k'}$の(ひいては$C_A\vert_A$の)値域に属す。次に$n\in\mbox{ran}(C_A\vert_A)$を仮定して$n'\in\mbox{ran}(C_A\vert_A)$を導く。帰納法の仮定により$C_A(s)=n$ なる$s\in A$がとれるが、$A\subseteq s'$ではないはずなので$t\in A\backslash s'$がとれる。すると$s'< t'$から$A\cap s'\subsetneq A\cap t'$であり、$C_A\vert_{A\cap t'}$は命題5により単射ゆえ$\mbox{ran}(C_A\vert_{A\cap s'})\subsetneq\mbox{ran}(C_A\vert_{A\cap t'})$。この両辺は命題5によりともに自然数となるので$\mbox{ran}(C_A\vert_{A\cap s'})\in\mbox{ran}(C_A\vert_{A\cap t'})$でもある。左辺は命題5と$s\in A$により$\mbox{ran}(C_A\vert_{A\cap s'})=C_A(s')=(C_A(s))'=n'$となるので、$n'$は$C_A\vert_{A\cap t'}$の(ひいては$C_A\vert_A$の)値域に属す。■

【命題7】(1)$n\in\mathbb{N}, A\subseteq n$のとき、$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)\leq n$である(等号は$A=n$のときのみ成立)。

(2)$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たないとき、$A$は可算無限集合である。

(証明)

(1)命題4と命題1により$A$と$C_A(n)\in\mathbb{N}$は対等であるから$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)$である。また命題2よりこれは$n$以下であり、等号は$n\subseteq A$のとき、すなわち$A=n$のときのみ成立する。

(2)命題6と命題1により$A$と$\mathbb{N}$は対等であるから、$A$は可算無限集合である。■

(2026年9月17日追記:命題3は、より一般的な「$X\cap n=Y\cap n$ならば$C_X\vert_{n'}=C_Y\vert_{n'}$」と$A\cap n=(A\cap n)\cap n$からも導かれる。任意に$X,Y\subseteq\mathbb{N}$をとり「」内を$\varphi(n)$とおけば、$\varphi(0)$は$C_X\vert_{\{0\}}=C_Y\vert_{\{0\}}$すなわち$C_X(0)=C_Y(0)$を意味し、これは$C$の定義から成立。$\varphi(n)$を仮定して$\varphi(n')$を導く。$X\cap n'=y\cap n'$と仮定すると$X\cap n=Y\cap n$かつ$X\cap\{n\}=Y\cap\{n\}$、前者と$\varphi(n)$から$C_X\vert_{n'}=C_Y\vert_{n'}$、特に$C_X(n)=C_Y(n)$である。また後者から$n\in X$と$n\in Y$の真偽は一致するため$C_X(n')=C_Y(n')$、以上により$C_X\vert_{n''}=C_Y\vert_{n''}$である。)

20260328集合と位相ゼミの補足

(内輪向けのノートです)

・定理6.32の背理法を用いない証明:
$X$から$\mathcal P(X)$への写像$f$を任意にとり、$f$が全射でないことを示す。そのために$A=\{x\in X\mid x\notin f(x)\}$とおき、任意の$x\in X$をとって$f(x)\neq A$を導く。$x\in A$のとき$x\notin f(x)$から$x\in A\backslash f(x)\neq\varnothing$、$x\notin A$のとき$x\in f(x)$から$x\in f(x)\backslash A\neq\varnothing$、したがっていずれにせよ$f(x)\neq A$である。

・補題6.33の$\varphi$の全射性の証明の通常の書き方の例:
$\varphi$の全射性を示すため、任意の$f:X\to\{0,1\}$をとり、$\varphi(f^{-1}[\{1\}])=f$を示す。左辺は\[X\to\{0,1\}\]\[x\mapsto\left\{\begin{array}{cc}1&(x\in f^{-1}[\{1\}])\\0&(x\notin f^{-1}[\{1\}])\end{array}\right.\]という写像であり、任意の$x\in X$について$x\in f^{-1}[\{1\}]\Leftrightarrow f(x)\in\{1\}\Leftrightarrow f(x)=1\Leftrightarrow f(x)\neq 0$から、これは$f$と同じ写像である。

・特徴関数(特性関数)に関する過去記事
y-bonten.hatenablog.com

手を動かしてまなぶケーリー・ハミルトンの定理

ケーリー・ハミルトンの定理:$n$次正方行列$A$の固有多項式\[\phi_A(x)={\rm det}(xI_n-A)=c_nx^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0\]に対し、
\[\phi_A(X)=c_nX^n+c_{n-1}X^{n-1}+\cdots+c_1X+c_0I_n\]と定義すれば\[\phi_A(A)=O\]が成り立つ。

$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$のとき、$\phi_A(x)={\rm det}(xI_2-A)=x^2-(a+d)x+(ad-bc)$である。まずは素朴に$\phi_A(A)$を成分計算すると

\[\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}a&b\\c&d\end{pmatrix}-(a+d)\begin{pmatrix}a&b\\c&d\end{pmatrix}+(ad-bc)\begin{pmatrix}1&0\\0&1\end{pmatrix}\]\[=\begin{pmatrix}a^2+bc&ab+bd\\ac+cd&bc+d^2\end{pmatrix}-\begin{pmatrix}a^2+ad&ab+bd\\ac+cd&ad+d^2\end{pmatrix}+\begin{pmatrix}ad-bc&0\\0&ad-bc\end{pmatrix}\]\[=\begin{pmatrix}0&0\\0&0\end{pmatrix}\]となって、確かに$n=2$に対しては定理の成立することが分かる。もう少し見通し良く計算するために$C=\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$とおくと、$C+A=(a+d)I_2,CA=(ad-bc)I_2$となるので\[\phi_A(X)=X^2-(C+A)X+CA\]と書ける。したがって$\phi_A(A)=A^2-(C+A)A+CA=O$となる。これは素朴に展開して計算すれば確かめられるが、$n$次行列への拡張を見据えるなら、なぜうまく$O$になるのか、理由が分かるような計算が望ましい。少し工夫すると、この式は$(A-C)(A-A)$と変形できるので、$O$になる理由が見えやすくなる。あるいは、あらかじめ$\phi_A(X)=(X-C)(X-A)$と因数分解しておけば、$X=A$において$O$となるのは明らかである……と言われて騙されてはいけない。一般には$\phi_A'(X)=(X-C)(X-A)$に等しいのは$X^2-(CX+XA)+CA$であって、$XA=AX$とは限らないから、これは不正な因数分解である。しかし今回は他ならぬ$A$を代入するので$\phi_A(A)=\phi_A'(A)=O$となるのである。さらにまた、「非可換性に縛られた精一杯の変形」として$\phi_A(X)=(X-A)X-C(X-A)$までは許されるので、これに$A$を代入したと考えても$O$になることは頷ける。

次に、先ほど天下(あまくだ)ってきた$C$がどこから来たのかを追究しよう。逆行列の議論を思い出すと、一般に$n$次行列$P$の逆行列は存在するとは限らないが、$PQ=QP={\rm det}(P)I_n$を満たす$Q$までは必ず存在する。そこで、$xI_n-A$に対しても\[B(x)(xI_n-A)=\phi_A(x)I_n\]なる$B(x)$をとることができる。$B(x)$の各成分は$xI_n-A$の「余因子」からなり、ここでは省略するが具体的に構成することができる。これに従うと、$xI_2-A=\begin{pmatrix}x-a&-b\\-c&x-d\end{pmatrix}$に対しては$B(x)=\begin{pmatrix}x-d&b\\c&x-a\end{pmatrix}$となる。実際に$B(x)(xI_2-A)$を計算すると\[\begin{pmatrix}x-d&b\\c&x-a\end{pmatrix}\begin{pmatrix}x-a&-b\\-c&x-d\end{pmatrix}=\begin{pmatrix}(x-d)(x-a)-bc&0\\0&-bc+(x-a)(x-d)\end{pmatrix}\]となり、確かに単位行列の${\rm det}(xI_2-A)$倍になっている。

いま議論しているのは$x$についての多項式であるので、$B(x)$も$x$について整理してみよう:
\[B(x)=\underbrace{\begin{pmatrix}1&0\\0&1\end{pmatrix}}_{B_1}x+\underbrace{\begin{pmatrix}-d&b\\c&-a\end{pmatrix}}_{B_0}\]$x$の$1$次の係数(行列)を$B_1$、定数項(行列)を$B_0$とおくと\[B(x)(xI_2-A)=(B_1x+B_0)(I_2x-A)=B_1x^2+(-B_1A+B_0)x+(-B_0A)\]となる。いっぽう$\phi_A(x)=c_2x^2+c_1x+c_0$とおいて$\phi_A(x)I_2$と成分ごとに係数比較することにより\[\phi_A(X)=B_1X^2+(-B_1A+B_0)X+(-B_0A)\]となることが分かる。これに$A$を代入してみると項がスパスパと消えて確かに$O$になる。先ほど見た通り、$\phi_A(X)$自体を$(B_1X+B_0)(X-A)$と因数分解するわけにはいかないが、$X=A$における両者の値は等しいのである。あるいは$\phi_A(X)=B_1(X-A)X+B_0(X-A)$としてから代入してもよい。実際には$B_1=I_2, B_0=-C$だったわけだが、$B(x)=B_1x+B_0$と書くことにより、具体的な成分を求めなくても$\phi_A(A)=O$となることが見通せる。

$3$次行列の場合はどうであろうか?成分計算することはかなり大変になるが、一般に$B(x)$の各成分は$x$の$n-1$次以下の多項式になることが余因子の構成法から分かるので、とにかく\[B(x)=B_2x^2+B_1x+B_0\]という形をしているはずである。すると$2$次の場合と同様に\[B(x)(xI_3-A)=(B_2x^2+B_1x+B_0)(I_3x-A)=B_2x^3+(-B_2A+B_1)x^2+(-B_1A+B_0)x+(-B_0A)\]係数比較を経て
\[\phi_A(X)=B_2X^3+(-B_2A+B_1)X^2+(-B_1A+B_0)X+(-B_0A)\]

これに$A$を代入するとやはりスパスパと項が消えて$O$になる。「因数分解はできないが$X=A$における値は等しい」という事情も同じであり、$\phi_A(X)=B_2(X-A)X^2+B_1(X-A)X+B_0(X-A)$まで変形して代入してもよい。

以上の議論は、$n$次行列でも全く同様に成り立つ。

『数学ガールの秘密ノート/数を作ろう』Rの切断に関する証明

https://www.amazon.co.jp/dp/4815615411

『数学ガールの秘密ノート/数を作ろう』(結城浩著・SBクリエイティブ)のフィナーレとなる、「$\mathbb{R}$の切断は下組が最大元を持つか、上組が最小元を持つ」の証明。p213で$(A_\mathbb{Q},B_\mathbb{Q})$を構成して以降の論証を簡明にしてみた。これはテキストの①②の対偶を証明することに相当する。

(証明)実数$(A_\mathbb{Q},B_\mathbb{Q})$が$A_\mathbb{R}$の上界であり$B_\mathbb{R}$の下界でもあることを示せば、この実数が$A_\mathbb{R},B_\mathbb{R}$のどちらに属しても、目標とする命題の成り立つことが分かる。

上界性を示すために任意の実数$(A,B)\in A_\mathbb{R}$をとり$(A,B)\leq(A_\mathbb{Q},B_\mathbb{Q})$を導く。そのためには任意の有理数$p\in A$をとって$p\in A_\mathbb{Q}$を導けばよい。$p$以下の有理数はすべて$A$に属すから、$\mathbb{Q}$を$p$以下/$p$超に分けた切断は$(A,B)$以下であり、したがって$A_\mathbb{R}$に属す。すると$A_\mathbb{Q}$の定義により$p\in A_\mathbb{Q}$となる。下界性についても同様である。■

2項関係の除算と表現行列

$R:A\leftarrow B, S:A\leftarrow C$に対して、$X:B\leftarrow C$についての条件\[R\circ X\subseteq S\tag{*}\]を考える。表現行列で言えば$RX\leq S$である。ここで$\leq$は「対応する各要素(ブール値)がいずれも$\leq$」と定義される半順序である。$R,S$を列ごとに分けたベクトルをそれぞれ$b_i,c_j$とおくと、(*)は各$j$について\[\bigoplus_i b_iX_{ij}\leq c_j\]が成り立つことと同値である。これは結局、さらに各$i$について\[b_iX_{ij}\leq c_j\]すなわち\[b_i\leq c_j\vee X_{ij}=0\]が成り立つことにほかならない。$b_i\not\leq c_j$のときは$X_{ij}=0$でなければならないが、$b_i\leq c_j$のときは$X_{ij}$は$0,1$のいずれの値もとりうる。各$i,j$について$X_{ij}$のとりうる最大値を並べたものが$R\backslash S$の表現行列となる。

2項関係の除算

$A,B,C$は集合、$S,R$はそれぞれ$B\times C,A\times C$上の2項関係とする。$A\times B$上の任意の2項関係$X$について\[X\circ S\subseteq R\Leftrightarrow\forall a\in A,c\in C[_aX\circ S_c\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,c\in C[\exists b\in B[{}_aX_b\wedge{}_bS_c]\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,c\in C,b\in B[({}_aX_b\wedge{}_bS_c)\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,b\in B,c\in C[{}_aX_b\rightarrow({}_bS_c\rightarrow{}_{a}R_c)]\]\[\Leftrightarrow\forall a\in A,b\in B[{}_aX_b\rightarrow\forall c\in C[{}_bS_c\rightarrow{}_aR_c]]\]\[\Leftrightarrow X\subseteq\{\langle a,b\rangle\in A\times B\mid\forall c\in C[{}_bS_c\rightarrow{}_aR_c]\}\]
この右辺を$R/S$と定義する。すなわち$X\circ S\subseteq R\Leftrightarrow X\subseteq R/S$である。一般に$K=\bigcup\{X\mid X\subseteq K\}$であるので、$R/S$は$\bigcup\{X\mid X\circ S\subseteq R\}$と書くこともでき、これを定義としてもよい。