■

[小ネタ] \mathbb{N}\times \mathbb{N} \to \mathbb{N}の逆関数を求める

　久々の投稿ではあるが，めっちゃ小ネタである．実は仕事のソフトを書いていてこの問題にぶつかった．

　\mathbb{N}\times \mathbb{N}の濃度が\mathbb{N}の濃度に等しいということの証明として，対応を具体的に (n,m) \mapsto k=(n+m+1)(n+m)/2 + mと与えることができる．(0,0)\to(1,0)\to(0,0)\to(2,0)\to(1,1)\to(0,2)\cdotsという具合に\mathbb{N}\times \mathbb{N}の作る平面を斜めに切るように数える，よく知られたものである．さて，問題はプログラムでループ変数を\mathbb{N}にして，\mathbb{N}\times \mathbb{N}の方を求める，つまり逆関数が欲しいと思ったのである．ところが意外にもこの対応の逆関数を陽に表した公式が Webで見つからないのである．頼みの綱のstack overflowにも『全単射なんだから逆対応の存在は明らか』みたいなのしかなくて困ったが，一つだけ手がかりとして，『 \sqrt(2k)\simeq n+m』というのが見つかった．このヒントは，確かに2k=(n+m+1)(n+m)+2mをにらむと見えては来るが，数値で計算してみると，\sqrt(2k)を切り上げたり切り捨てたりしても合ってはいない．いろいろ試行錯誤の挙句，次のような公式を得た．


n+m = \lceil \sqrt(2k+2) +1/2 \rceil-2


ここに\lceil x \rceilはxを切り上げて整数化する記号である．

ちょっと試してみよう．
(0,0)のときk=0で，\sqrt(2k+2)+1/2 \fallingdotseq 1.91.切り上げて2なので 0.
(1,0)のときk=1で，\sqrt(2k+2)+1/2)=2.5.切り上げて3なので 1.
(0,1)のときk=2で，\sqrt(2k+2)+1/2)\fallingdotseq 2.94.切り上げて3なので 1.
(2,0)のときk=3で，\sqrt(2k+2)+1/2)\fallingdotseq 3.32.切り上げて4なので 2.
(1,1)のときk=4で，\sqrt(2k+2)+1/2)\fallingdotseq 3.56.切り上げて4なので 2.
(0,2)のときk=5で，\sqrt(2k+2)+1/2)\fallingdotseq 3.96.切り上げて4なので 2.

とかなりきわどいもののイケている．もっと先の方を適当にやってみると，
(20,31)のときk=1357で，\sqrt(2k+2)+1/2)\fallingdotseq 52.61.切り上げて53なので 53-2=51=20+31 とこれも正しい．

n+mがわかると m=k-(n+m)(n+m+1)/2なので逆関数は求まったことになる．


さて，上の公式を証明しよう．
n+m+2 = \sqrt(2k+2) +1/2 + \alphaと置く．\sqrt(2k+2) +1/2の切り上げがn+m+2に等しいということは，0 \le \alpha < 1であることと同値である．まず，0 \le \alphaを示す. もし, \alpha < 0ならn+m+2 < \sqrt(2k+2) +1/2で，
n+m+3/2 < \sqrt(2k+2)
\Rightarrow (n+m+3/2)^2 < 2k+2 = (n+m+1)(n+m)+2m+2
\Rightarrow (n+m)^2+ 3(n+m)+(3/2)^2 < (n+m)^2+ (n+m) +2m+2
\Rightarrow 2n+(3/2)^2 < 2
\Rightarrow 2n < -1/4 は矛盾である．よって0 \le \alpha.
同様に 1 \ge \alphaなら，1 \ge n+m+2 - (\sqrt(2k+2) +1/2).

1 \ge n+m+2 - (\sqrt(2k+2) +1/2)
\Rightarrow 1+(\sqrt(2k+2) +1/2) \ge n+m+2
\Rightarrow \sqrt(2k+2) \ge n+m+1/2
\Rightarrow 2k+2=(n+m+1)(n+m)+2m+2 < (n+m+1/2)^2
\Rightarrow (n+m)^2+(n+m)+2m+2 < (n+m)^2+(n+m)+(1/2)^2
\Rightarrow 2m+2 < (1/2)^2
\Rightarrow 2m < -3/4 は矛盾．よって \alpha < 1 □

■

[物理学] Dirac『一般相対性理論』を読んでいた

　えーと，興味が抽象的な数学から具体的な数学に移る波の途中であらぬ方向に逸れて一般相対性理論に行ってしまった今日この頃です．これにはちょっと事情があって，実はHawking & Ellis『The large scale structure of space-time』を読もう（これもまた渋いチョイス）というネット勉強会が立ち上がりつつあって，その予習のために自習でDiracを読むという段取りだったわけです．ちなみにDirac『一般相対性理論』は短い（100ページちょいぐらい）ので有名なテキストですが，最初に読む本ではありませんです．とはいえ，テンソル計算の復習はできるので整理には良いのかもしれません．
　一方，Hawking & Ellisももはや古典で，特異点定理を学ぶのなら今なら Wald 『General Relativity』を読めという情報がネットにありました．まあ，そこは趣味の世界なのでH&Eでもいいかなぁと．

　Dirac『一般相対性理論』に戻ると，なんと『ちくま学芸文庫』にも収録されているとのこと（ちくま文芸文庫は収録のチョイスが謎で面白い）．また，ネット上でも高橋善樹さんという方が，『ディラック　「一般相対性理論」を読む』というタイトルで丁寧なノートを作っておられるので，もし本書を自分でも読みたいという奇特な方がおられたらぜひ参考にすることをお勧めします．

さて，私が本書を読んでいて二か所でハマったので，そのハマリのご紹介を．

最初は，『19. ブラックホール』である．18のシュヴァルツシルトの解でr=2mにある，いわゆる時空地平の特異性を座標変換であたかも何も特異性が無くなってしまうかの如く記述がある．Dirac先生も『特異性は解消である』とか言っているが，(19.1)で作った座標はr=2mで独立変数でなくなるため，数学的にはさっぱりである．まあ，ここはDirac先生の勘違いということで自分は納得した．そもそも計量が定義されていない点がある時点で議論に困ると思うのだが...まあ，H＆Eではさすがにそういう点は最初から除外されていたはずである．

　もう一点は本当にハマったところで，『27. 物質が連続的に分布している場合の作用』である．この中の変分\delta p^\muの形を与える式（27.4）\delta p^\mu=(p^\nu b^\mu-p^\mu b^\nu)_{,\nu}の導出が納得いかなかった．先の高橋ノートでもここはそのまま使われていて参考にはできなかった．これp^\nu b^\mu-p^\mu b^\nuの部分が反対称なので自然に連続の方程式 \delta p^\mu_{,\mu}=0が出るので非常に綺麗な形をしている．それはわかるのだが，Dirac先生の説明はいかにも物理屋な説明である．
　自分でも考えてはみたものの，速度場v^\muの定義が問題で，これって本当に時空座標の関数になっているのかが疑わしい（軌道上でしか定義されていないと思う）．結局『25.物質のエネルギー・運動量テンソル』節での説明がよくわからない（固有時間sは軌道を決めないと決まらない）．ネット情報に救いを求めてみたのだが結構手強かった．
　しかし，数日の調査の結果ついにヒントを見つけましたよ．StackExchangeありがとう．『How to derive equation 27.4 in Dirac's "General Theory of Relativity" book?』というそのままの質問（ググってもなぜか直接出てこないが，ヒットした質問の関連質問というところに載っている）で解答には，単一の質点の運動に対してだが正確な記述があった．それによると速度場は時空座標の関数ではなく，時空座標に関連するのは質量分布m \delta^4(x-x(\lambda))の部分だけである．

p^\mu(x)=m \int d\lambda \frac{dx^\mu(\lambda)}{d\lambda}\delta^4(x-x(\lambda))

では質量が連続分布しているときはどないなんねんと思うが，速度場と言っているものが軌道依存であるので，軌道の連続分布というようなものを考えないといけないのだろうか？ いや待て待て，なんやわからんが 速度場 v^\mu(x)なるものが最初から与えられているとしたら，点\hat{x}を通る軌道はdx^\mu(s)/ds=v^\mu(x(s))かつ\hat{x}=x(0)なる積分曲線であるはずである．ここにsは単なるパラメータであるが，g_{\mu\nu}v^\mu(x(s))v^\nu(x(s))=1であったから，実はsは固有時間に一致している．4次元時空のある三次元空間断面(その点を\hat{x}でパラメタライズすると考える)をs=0での始点の全体と考え，軌道をx^\mu(\hat{x},s)と書いて，

p^\mu(x)=\int d^3 \hat{x} \rho(\hat{x})\int ds \frac{dx^\mu(\hat{x},s)}{ds}\delta^4(x-x(\hat{x},s))

と拡張してみてはどうだろうか．描像としては，初期点\hat{x}にあった密度\rho(\hat{x})の物質が軌道x^\mu(s)に沿ってそのまま流れていく感じである．物質場としての疎密は\delta^4(x-x(s))を通じて，その点に近い軌道の疎密×その軌道上の密度の積分で表現されている．\rho(\hat{x})にs依存性を含めていないため，先の質点の例と同じように連続の方程式 \partial_\mu p^\mu(x)=0を満たしている．変位の場をb^\mu(x)として，軌道の変位を\delta x^\mu(\hat{x},s)=b^\mu(x(\hat{x},s))と定義すれば（ただし，初期点s=0での変位は0 すなわち \forall \hat{x} (b^\mu(\hat{x})=0)は要求しておこう）あとの計算はStackExchangeと同じようなもので，\delta p^\mu=(p^\nu b^\mu-p^\mu b^\nu)_{,\nu}が出る．
　しかし，この変位で軌道の微分方程式は，

d(x^\mu(\hat{x},s)+b^\mu(x(\hat{x},s)))/ds=v^\mu(\hat{x},x(s))+\partial_\nu b^\mu v^\nu(\hat{x},x(s))

に変わっている．この右辺の長さはg_{\alpha\beta}\partial_\nu b^\alpha v^\nu(\hat{x},x(s))v^\beta(\hat{x},x(s))=0でない限り1ではない．なので変位後は左辺は速度場ではなくなっており，またsは固有時間という意味を失ってしまっている...気持ち悪っ！

■

[集合論] Real Numbers　その４（Jech本4章 p.42）

　4章本編の最後に取り上げるのは，Baire空間である．Baire空間 \mathcal{N}:=\omega^\omegaは，記述集合論の道具の一つで無理数全体の集合と位相同型（ここで無理数全体には\mathbb{R}からの相対位相を入れている）で，記述集合論では実直線と同一視されるものらしい．記述集合論についてはJech本では本格的には扱っていないようだが，『公理的集合論のモデルはいろいろありすぎて困るので解析学に関係ありそうなものに絞ってみても結構深い』というような分野であると想像している．
　さて，Baire空間 \mathcal{N}に位相を入れるのに，次の部分集合を開基にして位相を定義する．
任意の自然数の有限列s= < a_k;\ k < n > に対して，
O(s):=\{ < c_k;\ k\in \mathbb{N} > : (\forall k < n) c_k=a_k\}

これは\mathbb{N}に離散位相を入れたときに，無限積\mathbb{N}^\mathbb{N}に入れる位相としてよくある直積位相というやつになっている．ちなみにテキストにはO(s)は閉集合にもなっているというコメントがあるが，O(s)^C=\cup_{s'}O(s')\ ;　ここにs'は(\exists k < n)s'_k\neq s_kなる有限列，だからである．さて，\mathbb{R}-\mathbb{Q}は正と負に分けると(-\infty,0)\mbox{の無理数}\cup (0,\infty)\mbox{の無理数}となるが，負の時 x\to \frac{1}{2-x}，正の時x\to 1-\frac{1}{2+x}で写像すると無理数であることを保ちながらそれぞれ(0,1/2)と(1/2,1)の中の無理数の集合に位相同型に写像される．このことから結局 \mathbb{R}の無理数全体と開区間(0,1)の無理数全体は位相同型であることがわかる．そこで \mathcal{N}から(0,1)の無理数全体への写像を次のように連分数を使って定義する:

f:\mathcal{N}\to (0,1)-\mathbb{Q};

f( < c_k;k\in \mathbb{N} > ):=\frac{1}{1+c_0+\frac{1}{1+c_1+\frac{1}{1+c_2+\frac{1}{1+\cdots}}}}


ちなみにJech本では\mathbb{N}は0を含むので上のように1を足してある．本文ではひっそりとpositive integerと言っていたりするが，そこはBaire空間の定義とずれがあるので気持ちは悪い（もちろん位相同型にはちがいないが）．
　さて，自然数の無限列に対して右辺は収束するのでその極限値を像とするのであるが，(0,1)-\mathbb{Q}の任意の元に対してその連分数展開を作れば展開は無限に続くので左辺の元になっていることがわかる．逆に像が有理数になることはない（∵連分数展開が有限回で止まってしまうため矛盾する）．要するにfは全単射である．さらに位相同型になっていることは，c\in \mathcal{N}に対して c'をcのc_0を外してc_1から以下続けた自然数列としたときに，f(c)=\frac{1}{1+c_0+f(c')}なので，|f(a)-f(b)| = f(a)f(b)|a_0-b_0+f(a')-f(b')|．ここでもし a_0 \neq b_0 なら右辺の絶対値記号の中は0< f(a'),\ f(b') < 1なので0になることができない．そこでもし左辺が十分小さくとれるなら a_0=b_0でなければならないことになる．その場合に今度は |f(a')-f(b')|を同じように評価すれば a_1=b_1となり，以下左辺を十分小さくとれるならいくらでも大きなnに対してa_k=b_k;\ k < nが成立するようにできる．逆に，a_k=b_k;\ k < nなら |f(a)-f(b)| = \prod_{k < n}[f(a^{(k)})f(b^{(k)})] |f(a^{(n)})-f(b^{(n)})| (ここで a^{(0)}=a,\ a^{(1)}=a'等々）で，f(a)f(a')=\frac{f(a')}{1+a_0+f(a')} \le \frac{f(a')}{1+f(a')} \le \frac{1}{2}なので，右辺の積の部分が (1/2)^nのオーダで小さくなっていくことがわかるため，nを大きくすると左辺はいくらでも小さくできる．以上からfもその逆写像も連続であることがわかり，Baire空間と(0,1)-\mathbb{Q}が位相同型であることが証明された．
　テキストのコメントではBaire空間\mathcal{N}を記述集合論では実直線\mathbb{R}と同一視するそうだが，そのありがたみは現時点ではよくわからない．\mathcal{N}と\mathbb{R}が似た性質があるという一つの根拠は定理4.6（Cantor-Bendixsonの定理）と定理4.8（Baireのカテゴリー定理）が成立するとのこと．証明は < J_k >の代わりにすべての開基O(s)の集合を使えばよさそうだ．後者は列の長さをnとすると列の全体の濃度は\mathbb{N}^n\sim \mathbb{N}なので結局 \mathbb{N}\times \mathbb{N}\sim \mathbb{N}で可算集合である．\mathcal{N}に対するCantor-Bendixsonの定理の証明は本節の最後にある．

　さて，Baire空間\mathcal{N}と\mathbb{R}が類似品というような話をする一方で，\mathcal{N}の部分集合が完全集合であるための必要十分条件を以下の木(tree)の概念を使って定式化する Lemma 4.11が結局，本節のミソであるようだ．\mathbb{R}には直接的には木を定義するような自然な構造がないので，そこが\mathcal{N}との差異と言えば差異だろうか．
　Seqを全ての自然数の有限列の集合として，T\subset Seqについて，

T:tree\ \stackrel{\mathrm{def}}{\Leftrightarrow} \ (\forall x\in T)(\forall n\in \mathbb{N}) ( (\exists s\in Seq)(s=x\upharpoonright n) \Rightarrow s\in T)

と定義する．また，\mathcal{N}のTを通る無限の経路という部分集合[T]を
[T]:=\{f\in \mathcal{N}:(\forall n\in \mathbb{N}) f\upharpoonright n \in T\}

と定義する．[T]は閉集合になるのは，f\notin [T]なら，\exists n (f\upharpoonright n \notin T)だが，このときfを含む開集合O(f\upharpoonright n)の元はすべて[T]の元ではないからである．
　逆にFを\mathcal{N}の閉集合として，
T_F:=\{s\in Seq:\ (\exists f\in F)s\subset f\}

と定義するとT_Fは木であり，[T_F]=F（∵木であること，F\subset [T_F]は定義から自明である．逆向きはf\in [T_F]なら(\forall n\in \mathbb{N}) f\upharpoonright n \in T_Fで，T_Fの定義から，nごとに(\exists g \in F)f\upharpoonright n=g\upharpoonright n．ところがもし，f\notin FだとするとFが閉集合だったから，(\exists s\in Seq)(f\in O(s) \wedge O(s)\cap F=\emptyset)となるが，これはsの長さをnとすると，f\upharpoonright n=g\upharpoonright nなるような g\in Fが存在しないといっており，先の条件に矛盾する）．ところで蛇足であるが，T_{[T]}=Tであろうか？ 定義からT_{[T]}\subset Tは明らか．しかし，この逆向きの包含関係は成立しない．例としてはつまらないが T:=\{\emptyset,<1>\}は木だが，[T]=\emptyset (∵ \mathcal{N}には無限列しかない)．T_{\emptyset}=\emptyset \neq T．

さて，\mathcal{N}の完全集合を木の言葉で定式化するために次の定義を行う．
空でない木Tに対して：

T:\mbox{完全 }\stackrel{\mathrm{def}}{\Leftrightarrow}\ (\forall t\in T)(\exists s_1,s_2\in T)(s_1 \supset t \wedge s_1 \supset t \wedge \neg(s_1 \supset s_2)\wedge \neg(s_2 \supset s_1))

この定義は要するに，任意のt\in Tに対して，有限列tから先を伸ばしたs_1,s_2 \in Tがあって，かつその２つは先のどこかで異なっているというものが存在するということである．まず完全でない例としては f\in \mathcal{N}に対して，T_{\{f\}}がある．この例だと常にs_1,s_2 \in T_{\{f\}}\ \Rightarrow \ s_1 \supset s_2 \mbox{ or }s_2 \supset s_1だからである．簡単な完全な木の例は，既出のO(s);\ s\in Seqに対するT_{O(s)}がある（O(s)は閉集合でもあることに注意）．これが完全な木であるのはT_{O(s)}がsの後は勝手な列が取れることから明らかである．これらの例はそれぞれ，\mathbb{R}の孤立点（一点）と閉区間に対応しているような感じである．

以上の準備のもと，Lemma4.11のステートメントは非常にシンプルである．

Lemma 4.11
閉集合F\subset \mathcal{N}に対して：

F:\mbox{完全 }\Leftrightarrow\ T_F:\mbox{完全}

テキストに証明はついていないが，ほぼ定義の言い換えのようなものである．
＜証明＞
F:\mbox{完全 }\Leftrightarrow\ (\forall f\in F)(\forall t\in Seq)(f\in O(t)\Rightarrow (\exists g\in F)(g\neq f \wedge g\in O(t)\cap F))であるが，右辺の全称記号の順番を入れ替えてみると有限列tを伸ばした異なる無限列f,gが存在するのでそれらを適当に有限で切ればT_Fが完全の条件と一致する．逆に任意のf\in Fに対して，fを有限で切ったものをt\in SeqとすればT_Fが完全である条件は，O(t)の中にfと異なるFの元が存在する（∵s_1,s_2のどちらかはfとは異なるg\in Fを有限で切ったものになっている）という主張であり，すなわちfはFの孤立点ではない □

　T\subset Seqに対して，

T':=\{t\in T:(\exists s_1,s_2\in T)(s_1 \supset t\wedge s_2 \supset t \wedge \neg(s_1 \supset s_2) \wedge \neg(s_2 \supset s_1)\}

と定義すると，T=T'はTが完全であることの定義に一致している．また，次に[T]-[T']を考えたいわけだが，定義からT'が木である（∵t\in T'でt\supset sならば s_1,s_2\supset t \supset sなのでs\in T'）ことを注意しておく．
　さて，[T]-[T']が高々可算集合であることを証明する．f\in [T]-[T']とすると任意のn\in \mathbb{N}に対して，f\upharpoonright n\in Tであるが，一方f\notin [T']であるからどこかのnでf\upharpoonright n\notin T'でなければならないので，そうなるような最小のnに対して，s_f:=f\upharpoonright nと定義する．s:[T]-[T']\to Seqである．Seqが可算集合だったのでこの対応がone-to-oneであることを示せれば十分である．f,g\in [T]-[T']で，f\neq gとするとどこかのn\in \mathbb{N}で，f\upharpoonright n\neq g\upharpoonright nとなるが，このような最小のものを改めてnとしておこう．もし，s_f=s_gならばm\in \mathbb{N}があって，f\upharpoonright m=g\upharpoonright mなので，m < nでなければならない．しかし，s_1:=f\upharpoonright n,\ s_2:=f\upharpoonright nとするとs_1 \supset f\upharpoonright nかつs_2 \supset f\upharpoonright nで，s_1とs_2はcompatibleでないので，s_f=f\upharpoonright m\in T'だが，これはs_fの定義に反している．よってsはone-to-oneである □

　以上の準備の上で，例によって

T_0:=T,\ T_{\alpha+1}:=T'_\alpha
T_\alpha:=\cap_{\beta < \alpha}T_\beta (\alphaが極限順序数のとき）

と定義する．T_\alphaは非増加であるが，もともとT\subset SeqなのでTは高々可算集合である．もし，\forall \alpha(T_{\alpha+1}\neq T_\alpha)であるとOrdが集合になるという矛盾が出るといういつもの論法で，T_{\theta+1}= T_\thetaなる順序数\thetaが存在する．また，\alpha < \thetaに対して，T_\alpha-T_{\alpha+1}の最小元を対応させることができるので，\theta \to T_0なるone-to-oneが存在する．よって|\theta| \le \omega. そこでテキストの通りに \theta < \omega_1となる（\theta \le \omegaとは限らない）．T'_\theta=T_{\theta+1}=T_\thetaなので，空でなければ[T_\theta]は完全である．
　ここで補題として，[\cap_{\beta < \theta}T_\beta]=\cap_{\beta < \theta}[T_\beta]を示そう．
f\in [\cap_{\beta < \theta}T_\beta] \Leftrightarrow (\forall n\in \mathbb{N})(\forall \beta < \alpha)f\upharpoonright n \in T_\beta
\Leftrightarrow (\forall \beta < \alpha)f\in [T_\beta]\Leftrightarrow \cap_{\beta < \theta}[T_\beta] □

最後に [T]-[T_\theta]=\cup_{\alpha < \theta}([T_\alpha]-[T'_\alpha])を示す．T_\theta \subset T'_\alpha=T_{\alpha+1}なので 左辺 ⊃ 右辺．逆に左辺の元をfとすると，f\notin [T_\beta]なる最小の\beta \le \thetaが存在する．もし，\betaが後続順序数なら，\beta=\beta'+1として，f\in [T_\beta']-[T_\beta]=[T_{\beta'}]-[T'_{\beta'}]なのでfは右辺に属する．もし，\betaが極限順序数ならば，T_\beta=\cap_{\gamma < \beta}T_\gammaで補題より f\notin [T_\beta]=\cap_{\gamma < \beta}[T_\gamma]. ところが，\betaの最小性から f \in \cap_{\gamma < \beta}[T_\gamma]なので矛盾．つまりこのケースは実は起こらない．□
　さて，[T]-[T_\theta]=\cup_{\alpha < \theta}([T_\alpha]-[T'_\alpha])の右辺は，高々可算集合の高々可算集合個の和であるので，高々可算集合である．Fを\mathcal{N}の非加算な閉集合とするとF=[T_F]と書けるので，先の等式は，Fが完全集合と高々可算集合の和に分解されるというCantor-Bendixsonの定理の\mathcal{N}バージョンである．

■

[集合論] Real Numbers　その３（Jech本4章 p.40）

　今回のネタは定理4.6 (Cantor-Bendixson)『実数の中の任意の非加算な閉集合Fは，完全集合Pと高々可算な集合Sの和集合となる(F=P\cup S)．]』である．系として，定理4.5と組み合わせると『Fを\mathbb{R}の閉集合とすると，|F|は高々可算か，\mathfrak{c}』が得られる．この系は閉集合に限るなら連続体仮説が成立していると言っている．
　さて，独自調査により Cantor-Bendixsonの定理は選択公理を使わなくても証明できるらしいので，テキストの証明をこの観点から眺めてみよう．ところで蛇足ながら，CantorはCantor-Bendixsonの定理を証明しようとして，超限帰納法（超限順序数）をあみ出したそうである（1880年代）．先の系にも連続体仮説との関連がうっすら見えるように，Cantorは生涯にわたり連続体仮説の証明に腐心していたらしく，その証明がうまくできないことと集合論の基礎をめぐってのKroneckerの執拗な攻撃により精神を病んでいったとWikiにある．ちなみにKroneckerはLindemannのπが超越数である証明(1882年)を『美しいが無意味．なぜなら超越数は存在していないから』と言ったそうである．真意はもちろん知らないが，『πが代数方程式を満たさない』ことは認めるが，かといって『代数方程式を満たさない数としての超越数』という概念そのものの構成を否定しているのだと思う（直観主義の人だから，補集合を取る操作だけでも考えている世界からはみ出てしまうかもしれないのである）．

＜定理4.6の証明＞
　limit point の定義は『Fの点xがlimit point \stackrel{\mathrm{def}}{\equiv} xを含む任意の開集合がx以外のFの点を含む 』である．以前の記事で述べたように点列での定義は不採用である．記号 A'でAに含まれるすべてのlimit pointの集合を表す．このA'はAから論理式で表現できるため，すべての位相空間のクラスからそれ自身への関数クラスが定義されていると考えてよい．すると次のような超限再帰的な定義が可能である．

F_0:=F,\ \ F_{\alpha+1}:=F_\alpha'
F_\alpha:=\cap_{\gamma < \alpha}F_\gamma;　\alphaが0でない極限順序数のとき

しかもF_\alphaは非増加である．出来上がったものは順序数全体のクラスOrdからAのベキ集合への関数クラスとなる．これは超限再帰的な定義なのであって集合を単に列挙しているわけでもないので選択公理の出番はない．
さて，以前にもあった論法だが，もしすべての\alphaについて，\alpha > \theta \Rightarrow\ F_\alpha \neq F_\thetaが成立すると，OrdからP(A)への単射となっている．この逆関数の関数クラスを作る（像でないところは0にするとか適当でよい）と集合P(A)からOrdへの全射が得られるが，置換公理よりOrdが集合でなければならないが，これは矛盾である．そこで \theta \le \alpha\ \Rightarrow\ F_\theta=F_\alphaなるような最小な\thetaが存在することになる．このとき，P:=F_\thetaとする．P'=F_{\theta+1}=F_{\theta}=Pなので，もしPが空でないなら，完全集合である．Pが空であろうがなかろうが，F-Pが高々可算集合であることを示そう．
　その準備として，両端が有理数であるような\mathbb{R}の開区間の全ての集合を考えてそれら可算集合でインデックス付けしたものを< J_k; k\in \mathbb{N} > としよう．これは有理数が\mathbb{N}でインデックス付けできるので，両端を考えると\mathbb{N}\times \mathbb{N}への単射が存在するが，\mathbb{N}\times \mathbb{N}\sim \mathbb{N}なので一つの\mathbb{N}でインデックス付けできる理屈である（途中飛ばして番号を付けなおす必要はある）．特に整列集合であるところがミソで，一般的に『XXXの条件を満たす開集合を選ぶ』という選択公理にひっかかるステートメントを『XXXの条件を満たす開集合J_kの内，kの最小なものを選ぶ』とすることで選択公理の使用を避けるという工夫ができるのである．ただ，本証明ではストレートにJ_kらを使うので，そういった工夫はせずとも選択公理は不要となっている．
　さて，F-P=\cap_{\alpha < \theta}(F_\alpha-F_\alpha')を示そう．F_\alpha \supset Pより F_\alpha' \supset P'=Pなので (F_\alpha-F_\alpha')\cap P=\emptysetより 左辺 \supset 右辺はOK．x\in F-Pとして，x \notin F_\alphaなる最小の順序数を改めて\alphaとする．\alphaが後続順序数で\alpha=\beta+1なら\alphaの最小性からx\in F_\betaかつ x\in F_\beta-F_{\beta+1}=F_\beta-F_\beta'. \alphaが極限順序数なら 定義よりx \notin F_\alpha=\cap_{\gamma < \alpha}F_\alphaだが，\alphaの最小性から \forall \gamma < \alpha (x\in F_\gamma)なのでx\in F_\alphaとなり，矛盾してしまう．よってこのケースは実際にはなく，与式は証明された．ちなみに\alpha < \betaならば\alpha+1 \le \betaなので F_\alpha'=F_{\alpha+1} \subset F_\betaとなり，右辺はdisjoint unionになっている．それゆえa\in F-Pとするとa\in F_\alpha-F_\alpha'なる\alphaはユニークに決まり，かつ aはF_\alphaの孤立点であることになる．そこで< J_k > のなかからaを含みかつそれ以外のF_\alphaの点を含まないようなものでkが最小のものが存在するので，そのようなkをk(a)と書く．あとはこの対応がone-to-oneであることが示されれば，F-Pが高々可算であることがわかるので定理の証明は完了である．b\in F-Pでa\neq bとしよう．b\in F_\beta-F_\beta'なる\betaがユニークに存在するが，\alpha \ge \betaと仮定しても一般性を失わない．このときF_\alpha \supset F_\betaなのでk(a)の決め方からa以外のF_\alpha元を含まないため，b\notin J_{k(a)}. なので k(b)\neq k(a)である □


　ついでに定理4.8の証明も補足しておく．これも選択公理を使わない証明となっているが，よくある証明では長さが縮小していく区間を使うがJech本はちょっと違う証明となっている．

定理4.8（Baireのカテゴリー定理）　D_0,D_1,\cdots,D_n,\cdotsを\mathbb{R}の稠密な開集合の可算列とする．このとき D:=\cap_{n=0}^\infty D_nも稠密である．

＜証明＞
稠密であることを示すには任意の空でない開区間IとDが交わることを示せばよい．そこで次のような開区間の減少列を作ってみる：

I_0:=I
I_{n+1}は，I_n \cap D_n \supset \overline{J_k}なるような < J_k; k\in \mathbb{N} > （既出！）の元の中でkが最小のものをk(n)と書いて，そのままI_{n+1}:=J_{k(n)}=(q_{k(n)},r_{k(n)})とする．ちなみにこのようなJ_kが一つでも存在することはI_n \cap D_nがD_nが稠密であることから空ではない開集合なので適当な開区間が含まれるがそれを少し縮めて端点が有理数になるようにすれば条件を満たす< J_k; k\in \mathbb{N} > の元になるからである．
区間が小さくなるという条件を入れていないので，\cap_{n=0}^\infty I_nは一点とは限らないが I_nの左の端点（有界かつ非減少）の極限をa:=lim_n q_{k(n)}としよう．a\in I\cap Dであることを示す．a\in Iなのは明らかなので，a \notin Dとしてみよう．すると\exists n(a\notin D_n)である．作り方から\overline{J_{k(n)}} \subset I_n\cap D_nだったが，a \in [q_{k(n)},r_{k(n)}]=\overline{J_{k(n)}}なので a\in D_nとなり矛盾である □

　ところでなぜこれをカテゴリー定理と呼ぶのかについて調べてみた．まず，内点をもたないような閉集合の可算和（の部分集合）を第一類と呼ぼう．第一類は割とスカスカな感じがするだろう．第一類でない部分集合を第二類と呼ぼう．えらくざっくりな定義ではある．さて，ここで第一類は本当にスカスカだろうかという問題を提起してみよう．『スカスカ＝内点を持たない』と考えると『内点をもたない閉集合の可算和は内点を持たないか？』で，同値な主張としては『内点を持つ部分集合は第二類か？』となる．ところで

Fが内点を持たない⇔任意の開区間にはFでない点が存在する
⇔任意の開区間とF^Cは交点をもつ⇔F^Cは稠密

なので，内点を持たない閉集合の可算和の補集合は，稠密な開集合の可算積となり，定理4.8からこれが稠密であることから，『\mathbb{R}の内点をもたない閉集合の可算和は内点を持たない』ということがわかるのである．

■

[集合論] Real Numbers　その２（Jech本4章 p.40）

　今回のネタは定理4.5『実数の中の任意の完全集合の濃度は\mathfrak{c}』である．

　完全集合とは，孤立点を持たない閉集合のことで，孤立点をもたないとは『任意の点のどんな開近傍もその点以外の点を含む』ことである．これと同値な定義としては，『任意の点に対して，その点に収束する点列でその点以外の点からなるものが存在する』というのがあるが，実はこの同値の証明（『開近傍』⇒『収束点列』の方向）には選択公理が必要なことが知られている．後の話の展開の都合でここでは『開近傍』での定義を孤立点をもたないという定義として採用する．


＜定理4.5の証明（よくあるバージョン）＞
完全集合をPとする．Pを区間[n,\ n+1];n\in \mathbb{Z}で区切っていくと，そのどれかには区間の内点にPの点を含む区間がある（そうでないと区間の端点がPの孤立点になるから）のでそれをI_\phiとする．ちなみにP\cap [n,\ n+1]らは完全集合でないことがあることに注意．たとえば区間[0,1]は完全集合だが，[0,1]\cap[1,2]=\{1\}は完全集合ではない．区間の端点が孤立点になってしまうことがあるからである．I_\phiの端点がP\cap I_\phiの孤立ならI_\phiを少し縮めてP\cap I_\phiが完全集合とできる．
　P\cap I_\phiが有界ならその上限lと下限uが存在し，どちらもP\cap I_\phiの点である（∵P\cap I_\phiが閉集合だから）．さて，l,uはP\cap I_\phiの孤立点ではないので，l,uのそれぞれを中心とした(u-l)/2より小さい半径の開区間を考えれば，l < a < b < uなるようなa,b\in P\cap I_\phiが存在することがわかる．

そこで交わらない2つの閉区間をI_0:=[l,a]，I_1:=[b,u]と定義する．ただし，先に述べたのと同じ理由でaがI_0\cap Pの孤立点になることがあるので，そういった場合はすこしaを小さくとりなおせば，I_0\cap Pが完全集合とできる．bについても同様である．このときI_0,I_1の長さは1/2より小さい．I_0 \cap P，I_1 \cap Pはl,uのいくらでも近くにPの点があるのでそれぞれの区間の内点にPの点が存在する．以下この区間の分割作業を続けていくと，[0,1]からなる長さnの任意の有限列sに対して，

(i) I_s \cap Pは完全集合
(ii) I_sの長さ \le 1/n(上の構成では実際は < 1/{2^n})
(iii) I_{s\frown 0},\ I_{s\frown 1} \subset I_s かつ I_{s\frown 0}\cap I_{s\frown 1}=\phi(s\frown 0は列sの後ろに0を追加した列，等である)
となるような区間I_sが作れる．
さて，f\in \{0,1\}^\omegaに対して，Pの点 P\cap_{n=0}^\infty I_{f\upharpoonright n}を対応させることで，単射 \{0,1\}^\omega\to Pが構成できるので 2^\omega=|\{0,1\}^\omega| \le |P| \le |\mathbb{R}|=2^\omegaと結論が得られる．
　少し戻って，P\cap_{n=0}^\infty I_{f\upharpoonright n}が空でないことを証明しよう（空でなければ一点のみを含むことは区間の長さがいくらでも小さくなるので容易）．P\cap_{n=0}^\infty I_{f\upharpoonright n}=\phiなら (P\cap I_\phi) \cap_{n=0}^\infty I_{f\upharpoonright n}=\phi．これはすなわち P\cap I_\phi \subset \cup_{n=0}^\infty I_{f\upharpoonright n}^C となり，右辺は左辺の開被覆になっている．ところで左辺は有界閉集合であったからコンパクト．ゆえに右辺から有限開被覆が選べるがその中で一番大きなnに対して，P\cap I_{f\upharpoonright n}=\phiとなるので矛盾である□

　とまあ，証明はできるのだがひとつ気にいらないことがある．それはこの証明ではどう見ても『選択公理を使っている』ことである．しかし，Jech本では言及していないが，調べてみると定理4.5は選択公理を仮定しなくても証明できるらしいのである．\mathbb{R}を定義するには選択公理は不要なので，定理4.5の証明に選択公理がいるかいらないかはそれなりの意味がある．上の証明で，選択公理を使っていそうなアヤシイところを検討してみよう．要は有限のところでのI_sの存在はよいのだが，n \mapsto I_{f\upharpoonright n}という対応が列挙なので（集合として）関数になっている保証がないのである．この対応が関数でなければその共通集合は作れない．

① I_\phiの存在は問題ない．
② I_\phiの上限lと下限uの存在は\mathbb{R}の性質なので問題ない．
③ a,bの選び出し部分はNGである．『存在するので一つ取ってくる』を論理式で書けるような規定にしなければならない．証明を少し修正して，ぴったり(u-l)/4の長さの閉区間 [l,l+(u-l)/4]を考えよう．もし右の端点l+(u-l)/4がPの元であってかつP\cap [l,l+(u-l)/4]の孤立点でないならa:=l+(u-l)/4としよう．右の端点がPの元であってもP\cap [l,l+(u-l)/4]の孤立点だったり，Pの点でないときはP\cap [l,l+(u-l)/4]の最大元をaと定める．同様の方法でbも定める．この定義ではa,bがユニークに決まってしまう（かつ定義を論理式で書ける）ので以下の繰り返しのステップでこの手法を使えば，選択公理は不要となる．
④ \mathbb{R}の有界閉集合Cはコンパクト．いわゆるハイネ・ボレルの定理である．この定理の証明に選択公理が不要だというのは私は今回調べてみて初めて認識した．この定理の背理法での証明のプロセスを少し復習してみる．ある開被覆 C\subset \cup \mathcal{O}が存在してこれからどんな有限個を選んでもCを被覆できないとする：

(i)n=1として，Cは有界集合なので長さが1/2^nの有限個の閉区間で覆える．
(ii) この閉区間で区切られたCのどれかは，元と同じように開被覆 \cup \mathcal{O}からどんな有限個を選んでも被覆できないという性質を持っている（∵そうでないなら各々の有限開被覆を全部集めればCの有限開被覆ができてしまう）．
(iii) Cの代わりに(ii)の非コンパクトである集合を選んで，nを一つ増やして (i)のステップに戻る．が，ここで勝手なものを選ぶのではなく，(ii)の非コンパクトな性質をもつ閉区間のうち，一番左にあるものを選ぶと決めると選択公理の使用を避けることができる．
　このように作った有界閉集合の減少列は長さが0に近づくので，その共通集合は一点である．共通集合が空でないのは，各々の有界閉集合の最大値の集合（これが集合になるというのが肝要）は\mathbb{R}の有界な非増加列なのでその極限xが存在し，これはまた各々の有界閉集合の最小値の極限とも一致する．最大値の集合はCの点でCが閉集合だからx\in C．なのでxは常に各々の有界閉集合の最小値と最大値の間に存在し，かつCの点であるので，共通集合に含まれている□

■

[集合論] Real Numbers　その１（Jech本4章 p.37）

　さて，まずは定理4.1『実数の濃度\mathfrak{c}は可算ではない』である．本書の証明は私は初めてみるきれいな形だったので感動した．

　よくある証明は『区間[0,1)の実数を小数展開して対角線論法で矛盾を導く』というものではなかろうか．しかし，この十進でも二進でもいいが『小数展開』できるという部分はなんだか気持ち悪くないだろうか？ この主張は実際のところ

\mathfrak{c}=2^{\aleph_0}

と言ってしまっているのである．ベキ集合は元の集合より濃度が大きい： \aleph_0 < 2^{\aleph_0}は既出だが，先のよくある対角線論法は単に後半のこの事実を証明しているにすぎない．すると実数プロパーな部分は前半の\mathfrak{c}=2^{\aleph_0}が全てなのであって，これはなんだか論点先取ではなかろうか．

　Jech本の定理4.1の証明はそれではない．実数の２つの性質

(i) ２つの実数がa < bなら a < c < bなる実数cが存在する．
(ii) 有界な実数の集合はその上限を実数の中に持つ．
しか使っていないのである（\mathfrak{c}=2^{\aleph_0}は別途証明されている）．蛇足ながら，本書の定理4.1の証明はCantor自身のオリジナルな証明に近いようである．一方，いわゆる『Cantorの対角線論法』なるものは似たような論法をCantorもSecond Proofとして創案しているようであるが，今のポピュラーな形はどうやら別の数学者の作品のようである．

　さて，とわいえ例によってJech先生は証明の最後のところを読者に放り投げているので，それを補完した形で紹介する．

＜定理4.1の証明＞
実数 \mathbb{R}が可算だと仮定して，その可算列を\{c_n:n\in \mathbb{N}\}としよう．以下この列から次のように再帰的に数列 \{a_n\},\ \{b_n\}を定義する：
　・a_0:=c_0，b_0:=c_{k_0}; ここにk_0はa_0 < c_k\mbox{ なるような} c_k \mbox{のうち} \mbox{最小の}k，
　・a_{n+1}:=c_{i_n}; ここにi_nはa_n < c_i < b_n \mbox{ なるような} c_i \mbox{のうち} \mbox{最小の}i，
　・b_{n+1}:=c_{k_n}; ここにk_nはa_{n+1} < c_k < b_n \mbox{ なるような} c_k \mbox{のうち} \mbox{最小の}k.

結局\{c_n:n\in \mathbb{N}\}から a_0 < a_1 < \cdots < a_n < \dots < b_n < \cdots < b_1 < b_0 のような数列ができることになる．
さて，a_nらは有界なので a:=sup\{a_n:n\in \mathbb{N}\} \in \mathbb{R}が存在するが，このaは\{c_n:n\in \mathbb{N}\}のどれとも一致しないので矛盾であるというのである．この部分を補足する．仮に a=c_Nとなったとしてみる．supの定義から \forall n\ (a_n \le c_N)であるが，この等号は実は成立せず（∵ 成立するとa_n=c_N < a_{n+1}となるため aの定義に反する）a_n < c_N．一方で，同じく上限の定義からa \le b_nだがここでも等号は成立しない（∵ 成立するとb_{n+1} < b_n=c_Nとなってしまう）．よって常に a_n < c_N < b_nが成立している．ところがa_{n+1}は a_n < c_i < b_nなるような最小のiと決めたが，すでにc_Nがあるのでi < Nでなければならないため，この操作が高々有限回Nで止まってしまうので矛盾である □


さて，\mathfrak{c}=2^{\aleph_0}の証明も念のため．

\mathfrak{c} \le 2^{\aleph_0}を示す：　\forall r \in \mathbb{R}に\{q\in \mathbb{Q}:q < r\} \subset \mathbb{Q}を対応させるとこれは\mathbb{Q}の\mathbb{R}における稠密性より単射である．\mathbb{Q}が可算無限であることを認めると，\mathfrak{c} \ge |P(Q)|=2^{\aleph_0} □

\mathfrak{c} \ge 2^{\aleph_0}を示す： \mathbb{R}はCantor set と呼ばれる集合Cを含んでいる．具体的には \sum_{n=1}^{\infty}a_n/{3^n}で a_n=0\mbox{, }2と表される実数である．Cantor setの構成は認めるとして，作りかたから|C|=2^{\aleph_0}．C \subset \mathbb{R}なので\mathfrak{c} \ge 2^{\aleph_0} □


N進小数展開を使うよりずっと見通しがいい感じである（個人の感想です）．

■

[集合論] Jech本三章章末問題その2（Jech本p.34-35）

　後半戦はDedekind有限性に関してだが，あまり面白い問題はなかったのでまとめ風にしてみた．

まず定義：
集合SがDedekind有限
　　\overset{\text{def}}{\Longleftrightarrow} \forall S'\subsetneqq Sに対して，上へのone-to-one写像 \psi:S\to S'が存在しない.

集合SがDedekind無限
　　\overset{\text{def}}{\Longleftrightarrow} \exists S'\subsetneqq Sに対して，上へのone-to-one写像 \psi:S\to S'が存在する.

ある集合の真部分集合に対して，元の集合と一対一対応があるという直観的に正しそうな無限の定義である．Jech本での有限順序数へone-to-one写像が存在しないという（Dedekindと断らない）無限性の定義との関係を以前から知りたいと思っていたが今回の章末問題で解消できた．

まず，『有限　⇒ Dedekind有限』（対偶は『Dedekind無限 ⇒ 無限』）である（∵証明は普通の数学的帰納法を使えばよい）．この逆，『Dedekind有限 ⇒ 有限』あるいは『無限 ⇒ Dedekind無限』はどうかというと，選択公理を仮定するとこれは正しい（証明はすぐ後で）．というわけで選択公理があると，Dedekindの有限・無限性は本書の有限・無限性と一致してしまう．一方，選択公理がないとこの逆向きは証明できないとのコメントがある．


＜(AC)『無限 ⇒ Dedekind無限』の証明＞
選択公理を仮定すると任意の集合Sは整列可能で，ある基数\alphaが存在して，|S|=\alpha. Sが無限なら \omega \le \alphaで特に \omega \subset \alphaなので，Sは可算無限集合を含む．この可算無限集合に対しては一つずつずらし，それ以外は同じ要素を対応させる写像はSから0に対応する元を除いた真部分集合への上へのone-to-one写像になっている（問題3.14の左向き）．つまり，SはDedekind無限である □

実際のところ，選択公理を仮定せずに 『S:Dedekind無限 ⇔ Sが可算無限部分集合を含む』（問題3.14）となっている．この右辺の『Sが可算無限部分集合を含む』については以前にネタに取り上げたことがあるが，
(https://kazu-fgf.hatenablog.com/entry/2022/08/04/011920)
選択公理を仮定しない場合に無限集合なのに可算無限部分集合が存在しないという奇妙なことが起こるというのを覚えておられるだろうか？ それはまさに『無限 ⇒ Dedekind無限』の反例になっているというわけである．

右向き（⇒）については，テキストのヒント通り，Dedekind無限の定義を与える上へのone-to-one写像 f:S\to X \subsetneqq Sを使って，x_0 \in S-Xから始めて，x_{n+1}:=f(x_n)と作ればよい．以前のネタでも指摘したように，この無限操作には問題は無く，写像fがあれば可算無限部分集合は再帰的に定義可能なのである．

さて，選択公理を仮定しないときにはこの2つの有限・無限性の定義は異なることが分かったとして，その優劣はあるだろうか？ そもそも優劣を決める基準などは無いが，有限集合から構成されたいろいろな集合が再び有限集合であるかどうかという基準を採用してみよう．つまり集合を作り出す操作で閉じているかどうかである．

＜問題3.15＞

(i) A,B:Dedekind有限 なら A\cup B, A\times BもDedekind有限
(ii) S:Dedekind有限ならば， Sの値の重ならない有限列の全ての集合も Dedekind有限
(iii) 互いに素な Dedekind有限集合のDedekind有限個の族の和集合も Dedekind有限

＜解＞ 問題3.14のDedekind無限と同値な条件『可算無限部分集合を含む』を使えば大体解決する．
(i)はできたものが可算無限集合を含むとすると，AまたはBがそうなるので矛盾する．
(ii)は異なる有限列が可算無限個あるとしよう．それらの有限列からを順に今まで選んでこなかった元を選んでいく．ある有限列でいままで選んだ元しかないときはスキップして次の有限列に行く．この再帰的な作業が止まらなければ，Sの可算無限部分集合が作れるので矛盾．もし途中でN番目以降で元が増えなくなったとすると，すでに集めたN個の元からなる値の重ならない有限列は有限個しかないので可算無限列は途切れるはずなので矛盾である．
(iii)は和集合が可算無限集合を含むとする．族は互いに素なので可算無限集合の元それぞれにそれが属する族のインデックスが対応付けできる．ところがインデックスはDedekind有限なので，すくなくともどれか一つのインデックスに対して，可算無限回この対応が被ることになる．しかし，このことはそのインデックスに対応するDedekind有限集合が可算無限部分集合を含むことになるので矛盾である □


その直後のテキストのコメントによると，projection, ベキ集合，Dedekind有限集合の部分有限集合全体，そして （互いに素を仮定しない）Dedekind有限集合のDedekind有限個の族の和集合 はDedekind有限集合になることが選択公理なしでは証明できないとのことで，Dedekind有限集合の概念は単純な集合演算に対しても閉じていないということになる．テキストでの有限集合の定義ではこれらはすべてふたたび有限集合なので，こちらに軍配が...とはいえ有限順序数がガチガチに構成されている（ので数学的納法が使える）のが効いているでなんとも．

さて最後の問題：
＜問題3.16＞　Aが無限集合なら，P(P(A))はDedekind無限集合

この問題が興味深いのは，『Dedekind無限 ⇒ 無限』なので，AがDedekind無限集合のとき，P(A)はDedekind無限集合にならないことがあると先に述べたが，P(P(A))は再びDedekind無限集合になるということを含意している．

＜証明＞ ヒントにより S:=\{\{X\subset A:|X|=n\}:n < \omega\}を考えてみる．カッコの内側はnを固定するとP(P(A))の元（かつAが無限集合なので空ではない）なので，SはP(P(A))の可算無限部分集合を定義している．よってP(P(A))はDedekind無限集合 □