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\}$と書くこともでき、これを定義としてもよい。

エンダートン『論理学への数学的手引き』演習問題1.2.10

【補題】整式の集合$\Sigma_1,\Sigma_2$について、(A)「$\Sigma_1\vDash\sigma$ならば$\Sigma_2\vDash\sigma$」と(B)「$\Sigma_1\ni\sigma$ならば$\Sigma_2\vDash\sigma$」とは同値である。

（証明）$\Sigma_1\vDash\sigma$は$\Sigma_1\ni\sigma$よりも弱い仮定であるので(A)⇒(B)である。また(B)は「$\Sigma_1$の要素はすべて、$\Sigma_2$を充足するいかなる割り当てによっても真となる」、つまり「$\Sigma_2$を充足する割り当ては$\Sigma_1$をも充足する」ということを主張しているから、(B)⇒(A)も成り立つ。□

【演習10】(a)「整式の有限集合でサイズ$n$のものは、自身と同値で独立な部分集合を持つ」という命題を$\varphi(n)$とし、すべての自然数$n$に対して$\varphi(n)$が成り立つことを数学的帰納法により示す。$\varphi(0)$は、整式の空集合が独立の定義を満たすことから成立する。任意に自然数$n$をとって$\varphi(n)$を仮定し、$\varphi(n+1)$を導く。整式の有限集合でサイズ$n+1$のもの$\Sigma$を任意にとると、$\Sigma$が独立であれば自身が所期の部分集合となる。$\Sigma$が独立でないとき、$\alpha\in\Sigma$かつ$\Sigma\backslash\{\alpha\}\vDash\alpha$なる整式$\alpha$がとれる。$\Sigma\backslash\{\alpha\}
$は$\Sigma$と同値であり（上の補題に注意）、またサイズ$n$であるので、帰納法の仮定$\varphi(n)$により、同値で独立な部分集合を持つ。この集合はもとの$\Sigma$から見ても同値で独立な部分集合となる。

(b)整式の無限集合$\Sigma=\{A_1,A_1\wedge A_2,A_1\wedge A_2\wedge A_3,\ldots\}$が反例となることを示す。$\Sigma$の部分集合が独立であるのは一点集合か空集合のときだけである（さもないと「最も短い整式」が他から含意される）が、いずれにしても$\Sigma$と同値ではあり得ない。

(c)各$n\in\mathbb{N}$に対し$\sigma_0\rightarrow(\sigma_1\rightarrow(\sigma_2\rightarrow\cdots\rightarrow(\sigma_{n-1}\rightarrow\sigma_n)\cdots))$のことを$\gamma_n$と書く。$\Gamma=\{\gamma_n\mid n\in\mathbb{N}\}$からトートロジーをすべて除いたもの$\Gamma'$が所期の集合となることを示す。

・$\Sigma$との同値性：どの$\gamma_n\in\Gamma$に対しても$\Sigma\supseteq\{\sigma_n\}\vDash\gamma_n$、一方どの$\sigma_n\in\Sigma$に対しても$\Gamma\supseteq\{\gamma_0,\gamma_1,\ldots\gamma_n\}\vDash\sigma_n$であるから、$\Sigma$と$\Gamma$は同値である。さらに、トートロジーは整式のいかなる集合によっても含意されるから、$\Gamma(\supseteq\Gamma')$と$\Gamma'$も同値である。

・独立性：$\gamma_i\in\Gamma'$を任意にとり、$\Gamma'\backslash\{\gamma_i\}\not\vDash\gamma_i$を示す。$\gamma_i$はトートロジーではないため、これを偽にする真理値割り当て$v$が存在する。$\gamma_i$の定義から、$v$により$\sigma_0,\ldots,\sigma_{i-1}$はすべて真に、$\sigma_i$は偽になるので、$v$は$\Gamma'\backslash\{\gamma_i\}$を充足する。

20230531輪講の復習用問題

●写像$f:X\to Y$と$A\subseteq X, B\subseteq Y$について、$A$の$f$による像$f[A]$の定義は\[\{f(x)\in Y\mid x\in A\}\]あるいは\[\{y\in Y\mid\exists x\in A[y=f(x)]\}\]です。$B$の$f$による原像$f^{-1}[B]$の定義を答えてください。

●写像$f:\mathbb{R}\to\mathbb{R}, x\mapsto x^2$による、
(1)$\{2\}$の像、
(2)$\{-2,2\}$の像、
(3)$\{4\}$の原像、
(4)$\{-1,4\}$の原像
を、それぞれ答えてください。

●正誤を答えてください。一般に(1)像の原像は、(2)原像の像は

(A)もとの集合に等しくなる、
(B)もとの集合を包含する、
(C)もとの集合に包含される。

(20230623追記）
$A\subseteq f^{-1}[f[A]]$の証明：
任意に$a\in A$をとると、像の定義から$f(a)\in f[A]$である。すると原像の定義から$a\in f^{-1}[f[A]]$である。

$f[f^{-1}[B]]\subseteq B$の証明：
任意に$y\in f[f^{-1}[B]]$をとると、像の定義により、$y=f(x)$なる$x\in f^{-1}[B]$がとれる。原像の定義により$f(x)\in B$であるから$y\in B$である。