二項関係を保つ/反映する写像

集合\(A,B\)が、それぞれ二項関係\(R,S\)を備えており、\(f\)を\(A\)から\(B\)への写像とする。
【定義】
任意の\(x,y\in A\)について\(xRy\rightarrow f(x)Sf(y)\)が成り立つとき、「\(f\)は関係を保つ(preserves)」あるいは「\(f\)は準同型写像である」という。
任意の\(x,y\in A\)について\(f(x)Sf(y)\rightarrow xRy\)が成り立つとき、「\(f\)は関係を反映する(reflects)」という。
【例】\(R,S\)として特に等号を考えると、「\(f\)は単射である」は「\(f\)は『\(\neq\)』を保つ」とも「\(f\)は『\(=\)』を反映する」とも言い換えられる。
【定義】\(f\)が全単射であり、\(f\)および\(f^{-1}\)がともに関係を保つとき、「\(f\)は同型写像である」という。
\(f\)が全単射のとき、「\(f\)が関係を反映する」ことと「\(f^{-1}\)が関係を保つ」こととは同値である。したがって、上の定義は「全単射\(f\)が関係を保ってしかも反映するとき……」と言い換えてもよい。

以下、特に\(R,S\)が全順序関係である場合を考える。
\(f\)が\(\leq\)を保つことと、\(f\)が\( < \)を反映することは同値である。これらを(1)とする。
\(f\)が\( < \)を保つことと、\(f\)が\(\leq\)を反映することは同値である。これらを(2)とする。
「(1)かつ『\(f\)は単射である』」と、(2)とは同値である。つまり、(2)は\(f\)の単射性を含意しており、(1)より強い条件である。
このことから、単射においては「保たれる/反映される関係が\(\leq\)なのか\( < \)なのか」に注意を払う必要が無いことも分かる。
さらに\(f\)が全単射ならば、上記の議論により(1)のみで\(f\)が同型写像であることが言える。

線形変換の冪の核に対して特徴的な基底

竹山美宏『ベクトル空間』16.2節に相当する議論。

\(\varphi\)を有限次元ベクトル空間\(V\)上の線形変換とし、自然数\(i\)に対して\({\rm Ker}\ \varphi^i\)を\(Z_i\)と書く。\(Z_i\)に対して特徴的な基底がとれることを議論する。

補題1】任意の自然数\(i\)に対し、以下が成り立つ。
(1)\(Z_i\subseteq Z_{i+1}\)
(2)\(\varphi[Z_{i+2}\backslash Z_{i+1}]\subseteq Z_{i+1}\backslash Z_i\)
(証明)(1)\(x\in Z_i\)とすると\(\varphi^i(x)=0\)、この両辺に\(\varphi\)を作用させると\(\varphi^{i+1}(x)=0\)、したがって\(x\in Z_{i+1}\)である。
(2)\(x\in\varphi[Z_{i+2}\backslash Z_{i+1}]\)とすると、\(x=\varphi(y)\)かつ\(\varphi^{i+1}(y)\neq0\)かつ\(\varphi^{i+2}(y)=0\)を満たす\(y\in V\)が存在する。後2者はそれぞれ\(\varphi^i(\varphi(y))\neq0,\varphi^{i+1}(\varphi(y))=0\)と書けるので、これと\(x=\varphi(y)\)から\(x\in Z_{i+1}\backslash Z_i\)である。■

補題2】\(i\)を任意の自然数とする。\(Z_{i+2}\)が\(Z_{i+1}\oplus W\)を部分空間に持つとき、\(Z_{i+1}\)は\(Z_i\oplus\varphi[W]\)を部分空間に持つ。
(証明)補題1(1)を考慮すれば、\(W\subseteq (Z_{i+2}\backslash Z_{i+1})\cup\{0\}\)を仮定して\(\varphi[W]\subseteq (Z_{i+1}\backslash Z_i)\cup\{0\}\)を導けばよいことがわかる。集合の像の性質と仮定により\(\varphi[W]\subseteq\varphi[(Z_{i+2}\backslash Z_{i+1})\cup\{0\}]=\varphi[Z_{i+2}\backslash Z_{i+1}]\cup\varphi[\{0\}]\)、ここで補題1(2)と\(\varphi(0)=0\)を用いると、さらに\(\subseteq(Z_{i+1}\backslash Z_i)\cup\{0\}\)となる。■

補題3】\(W\)を\(V\)の部分空間とする。\({\rm Ker}\ \varphi\upharpoonright_W=\{0\}\)かつ\(W=A\oplus B\)のとき、\(\varphi[W]=\varphi[A]\oplus \varphi[B]\)である。
(証明)略。■

以下、\(Z_4\)の場合について述べるが、一般の\(Z_i\)についても同様である。
\(Z_4\)における\(Z_3\)の補空間のひとつをとって\(W_4\)とすると、\[Z_4=Z_3\oplus W_4\]と書ける。すると補題2から\(Z_3\)は\(Z_2\oplus\varphi[W_4]\)を部分空間に持つ。この空間の\(Z_3\)における補空間のひとつをとって\(W'_3\)とし、さらに\(\varphi[W_4]\oplus W'_3\)を\(W_3\)と書けば\[Z_3=Z_2\oplus\varphi[W_4]\oplus W'_3=Z_2\oplus W_3\]となる。全く同様にして\[Z_2=Z_1\oplus\varphi[W_3]\oplus W'_2=Z_1\oplus W_2\]\[Z_1=Z_0\oplus\varphi[W_2]\oplus W'_1=Z_0\oplus W_1\]を得る。\(Z_0=\{0\}\)から、\(Z_4=W_1\oplus W_2\oplus W_3\oplus W_4\)である。
\(W_4\)を\(W'_4\)とも書くことにし、\(W_1\)~\(W_4\)を順次計算すると\[W_4=W'_4\]\[W_3=\varphi[W_4]\oplus W'_3=\varphi[W'_4]\oplus W'_3\]\[W_2=\varphi[W_3]\oplus W'_2=\varphi^2[W'_4]\oplus\varphi[W'_3]\oplus W'_2\]\[W_1=\varphi[W_2]\oplus W'_1=\varphi^3[W'_4]\oplus\varphi^2[W'_3]\oplus\varphi[W'_2]\oplus W'_1\]途中の計算では、\(k\geq 2\)のとき\({\rm Ker}\ \varphi\upharpoonright_{W_k}=\{0\}\)より、補題3を用いた。

\(k\geq 1\)に対し\(W'_k\)の基底を\(T'_k\)とすると、\(k\)未満の任意の自然数\(n\)について\({\rm Ker}\ \varphi^n\upharpoonright_{W'_k}=\{0\}\)から、\(\varphi^n[T'_k]\)は\(\varphi^n[W'_k]\)の基底となる。したがって、\[T'_4,\varphi[T'_4],\varphi^2[T'_4],\varphi^3[T'_4],\ T'_3,\varphi[T'_3],\varphi^2[T'_3],\ T'_2,\varphi[T'_2],\ T'_1\]を連ねたものは\(Z_4\)の基底である。また\(W'_k\subseteq Z_k\)より\(\varphi^k[W'_k]=\{0\}\)、つまり\(T'_k\)の各ベクトルを\(\varphi^k\)でうつすといずれも\(0\)になる。

娘への手紙

「ある数を3倍しても、同じ数に10を足しても、結果は同じになりました。もとの数は何だったでしょう?」

という問題を小学校1年生の娘に出した。娘は1から順に始めて「1×3=3、1+10=11だからダメ、2×3=6、2+10=12ダメ、……」と試してゆき、ほどなく5×3=5+10=15を見つけた。

以下の半分くらいはすでに本人に伝えたが、これから伝えたいことも含めて手紙にした。


よく見つけたね。

これ、答えが5でラッキーだったね。30とかだったら、今のを30回やらないといけなくて大変だね。

もし50まで試しても見つからなかったら、「そもそもそんな数なんて、ないんじゃないの?」って、不安になる。

でも、どこまで試しても「そんな数はない」って言いきることはできない。「自分で見つけられなかっただけじゃないの?」って言われたら、言いかえせない。

それに、答えは5だけかな?そんなことを言われたら、また6も7も試さないといけなくなるね。

1から順番に試す方法は、

・ものすごくたくさん試さないと見つからないかもしれない
・いくら試して見つからなくても、「そんな数はない」とは言いきれない
・ひとつ見つかったとしても、「それ以外に答えはない」とは言いきれない

という心配がある。もし、

・ひとつひとつ試さなくてもよくて、
・答えがないときはそう言いきれて、
・答えがこれ以外にはない、ということも分かる

ような、そんな方法があったら便利だね。

あるんだ。

今は説明しないけれど、そのうちどこかで習うかもしれない。

その解き方を身につけたら、ひとつひとつ試す人がばかに見えるかもしれない。

これからいろんな先生に算数を習って、

「この方法でできるようになりなさい」

とか、

「こっちのほうが良い解き方です」

とか、そんな言葉を聞くこともあるだろう。

自分と違う方法を習ったら、どんどん身につければいい。

でも、これだけは忘れないでほしい。

算数にはいろんな解き方があって、正しければどんな方法でもいいんだ。

それぞれに良いところや弱いところがあったりするけれど、

「いちばんいい方法」がひとつだけきまっているわけじゃない。

「まだ習ってませーん」なんて言わずに1から順番に試したのは、

本当に、本当にかしこいことなんだよ。

平方数でない自然数の平方根による、有理数の切断

デデキントによる議論を見通し良く。

\(D\)を平方数でない自然数とし、\[A_1=\{x\in\mathbb{Q}\mid x\leq0\vee x^2 < D\},\\A_2=\mathbb{Q}\backslash A_1=\{x\in\mathbb{Q}\mid x > 0\wedge x^2\geq D\}\]とする。\(A_1\)は最大元を持たず、\(A_2\)は最小元を持たないことを示す。

\(x\in\mathbb{Q}\)に対し\(\bar{x}=x(x^2+3D)/(3x^2+D)\)と定めると、\(\bar{x}^2-D=(x^2-D)^3/(3x^2+D)\)である。\(x^2+3D > 0,3x^2+D > 0\)により、\(x\)と\(\bar{x}\)の正負は一致し、また「\(x^2\)と\(D\)の大小」と「\(\bar{x}^2\)と\(D\)の大小」も一致する。これと\(A_1,A_2\)の定義から、\(x,\bar{x}\)は同時に\(A_1\)に属すか、または同時に\(A_2\)に属す。

さらに\(x-\bar{x}=2x(x^2-D)/(3x^2+D)\)であるから、「\(x\)と\(\bar{x}\)の大小」は「\(x(x^2-D)\)の正負」に一致する。

任意の\(a_1\in A_1\)をとる。
・\(a_1\leq0\)のとき:\(1\in A_1\)から、\(a_1\)は\(A_1\)の最大元ではない。
・\(a_1 > 0\)のとき:\(a_1^2 < D\)となるから\(a_1(a_1^2-D) < 0\)、したがって\(a_1 < \bar{a_1}\in A_1\)となり、やはり\(a_1\)は\(A_1\)の最大元でない。
以上により、\(A_1\)は最大元を持たない。

次に任意の\(a_2\in A_2\)をとると、\(a_2^2\geq D\)が成り立つが、実際は等号が成立することはなく\(a_2^2 > D\)であるので[*1]、これと\(a_2 > 0\)から\(a_2(a_2^2-D) > 0\)、したがって\(a_2 > \bar{a_2}\in A_2\)となり、\(a_2\)は\(A_2\)の最小元でない。ゆえに\(A_2\)は最小元を持たない。

中間値の定理の証明・改

高木『解析概論』の中間値の定理の証明が理解しづらかったため、書き直した。

同じ目的で
中間値の定理の証明 - y_bonten's blog
を書いていたが、これも煩雑であったので改良した。

【定理】(中間値の定理)\(a < b\)とする。区間\([a,b]\)において連続な関数\(F(x)\)について、\(F(a) < 0, F(b) > 0\)が成り立つとき、\(F(c)=0\)なる\(c\in(a,b)\)が存在する。

(証明)\(X=\{\xi\in[a,b]\mid\forall x\in[a,\xi]\ [F(x) < 0]\}\)とすれば、\(X\)は以下の性質を満たしている。
(1)\(a\in X,b\notin X\)
(2)\([a,b]\)において下に閉じている。
(3)最大元を持たない。

(1)(2)は\(X\)の定義から直ちに言える。(3)は、任意の\(p\in X\)に対し、\(p\in[a,b),F(p) < 0\)と\(F\)の連続性から、\(p\)のじゅうぶん小さな右近傍で\(F(x) < 0\)となり、\(p < q\)なる\(q\in X\)が存在することから従う。

以上により\([a,b]\)は、\(X\)と「\([a,b]\)における\(X\)の上界全体」とに切断されており、各々\(a,b\)を要素に持つ。\(\mathbb{R}\)の完備性により\(X\)は最小上界\(c\)(ただし\(c\in(a,b]\))を持ち、\([a,c)\subseteq X\)かつ\(c\notin X\)であるから\(F(c)\geq0\)である。

\(F(c) > 0\)と仮定すると矛盾することを示す。このとき、\(c\in(a,b]\)と\(F\)の連続性から、\(c\)のじゅうぶん小さな左近傍で\(F(x) > 0\)となる。すると\(d < c\)なる\(d\in[a,b]\backslash X\)が存在することになり、これは\(c\)が\(X\)の最小上界であることに反する。

以上により\(F(c)=0\)であり、\(F(b) > 0\)から\(c\neq b\)、これと\(c\in(a,b]\)から\(c\in(a,b)\)である。■

キューネン数学基礎論p46、演習I.7.21

\(R\)が\(A\)を整列順序づけすることから\[\forall x,y,z\in A[xRy\wedge yRz\rightarrow xRz]\]\[\forall x,y\in A[x=y,xRy,yRxのうちちょうどひとつが成立する]\]\[\forall Y\subseteq A\exists y\in Y\neg\exists z\in Y[zRy]\]が成り立つ。\(X\subseteq A\)のとき、上記の\(A\)を\(X\)に書き換えたものがすべて成立するから、\(R\)は\(X\)を整列順序づける。

キューネン数学基礎論p151、演習問題II.7.5

\(\mathfrak{A}\)を語彙\(\mathcal{L}\)に対する構造とし、その台集合を\(A\)とする。\(\mathcal{L}\)の項\(\tau\)に対し、「\(\tau\)に対する\(A\)への任意の割り当て\(\sigma',\sigma\)について、\(\sigma'\upharpoonright V(\tau)=\sigma\upharpoonright V(\tau)\)ならば\({\rm val}_\mathfrak{A}(\tau)[\sigma']={\rm val}_\mathfrak{A}(\tau)[\sigma]\)」という条件を\(\varphi(\tau)\)と置く。帰納法により\(\mathcal{L}\)の任意の項\(\tau\)について\(\varphi(\tau)\)が成り立つことを示す。

(1)\(\tau\in VAR\)のとき:\(\tau\)に対する\(A\)への割り当てで、\(\sigma'\upharpoonright V(\tau)=\sigma\upharpoonright V(\tau)\)を満たす任意の\(\sigma',\sigma\)をとる。\({\rm val}_\mathfrak{A}(\tau)[\sigma']=\sigma'(\tau)\)、\({\rm val}_\mathfrak{A}(\tau)[\sigma]=\sigma(\tau)\)であるが、\(\tau\in V(\tau)\)により両者は等しい。
(2)\(\tau\in\mathcal{F}_0\)のとき:(1)と同様に\(\sigma',\sigma\)をとると、\({\rm val}_\mathfrak{A}(\tau)[\sigma']\)も\({\rm val}_\mathfrak{A}(\tau)[\sigma]\)も共に\(\tau_\mathfrak{A}\)に等しい。
(3)\(n > 0\)に対し\(f\in\mathcal{F}_n\)かつ項\(\tau_0,\dots,\tau_{n-1}\)がすべて\(\varphi\)を満たすと仮定し、\(\tau=f\tau_0\ldots\tau_{n-1}\)も\(\varphi\)を満たすことを導く:(1)と同様に\(\sigma',\sigma\)をとると、これらは\(\tau_0,\dots,\tau_{n-1}\)のいずれに対しても\(A\)への割り当てとなっており、またどの\(\tau_i\)についても\(\sigma'\upharpoonright V(\tau_i)=\sigma\upharpoonright V(\tau_i)\)が成り立っているから、\(\varphi(\tau_i)\)により\({\rm val}_\mathfrak{A}(\tau_i)[\sigma']={\rm val}_\mathfrak{A}(\tau_i)[\sigma]\)である。すると\({\rm val}_\mathfrak{A}(\tau)[\sigma']\)および同\([\sigma]\)はその定義から等しくなる。■