クラトフスキの閉包・補集合定理

定理整数整数-14

定理 (Kuratowski, 1922) $(X,\mathcal{O})$ を位相空間とする。このとき、 $X$ の部分集合 $A$ に対して閉包および補集合を取る操作を繰り返しても高々14個の集合しか得られない。また、実際に相異なる14個の集合が得られる例がある。

この定理の証明を解説します。

Kuratowskiモノイド

位相空間 $(X,\mathcal{O})$ に対する閉包、補集合を取る写像 $2^X\to 2^X$ をそれぞれ $b, c$ と表す*1。また、 $\mathrm{id}\colon 2^X\to 2^X$ は恒等写像とする。合成を積、 $\mathrm{id}$ を単位元とし、 $b,c$ が生成するモノイドを $K(X,\mathcal{O})$ と表すことにする。

$b^2=b$ , $c^2=\mathrm{id}$ である。

$f,g \in K(X,\mathcal{O})$ に対して大小関係 $f\leq g$ を、任意の $A\subset X$ に対して $f(A)\subset g(A)$ が成り立つことと定める。 $f\leq g$ かつ $f\geq g$ であれば $f=g$ である。

$b$ は包含順序を保つので ( $A\subset B\subset X \Longrightarrow b(A)\subset b(B)$ )、 $g_1\leq g_2$ であれば $bg_1\leq bg_2$ が成り立つ。

$c$ は包含順序を逆転させるので ( $A\subset B\subset X \Longrightarrow c(A)\supset c(B)$ )、 $g_1\leq g_2$ であれば $cg_1\geq cg_2$ が成り立つ。

内部を取る写像を $i$ とすると、 $i=cbc$ である。任意の $f\in K(X,\mathcal{O})$ に対して $if\leq f$ である。

補題 $bcbcbcb=bcb$ である。

証明. $cbcbcb=ibcb$ なので、

$cbcbcb \leq bcb.$

よって、 $b$ の性質より

$bcbcbcb\leq bbcb=bcb \tag{1}$

が成り立つ。 $cbcb=ib\leq b$ なので、 $b$ の性質より

$bcbcb\leq bb=b.$

$c$ の性質より、

$cbcbcb\geq cb.$

よって、 $b$ の性質より

$bcbcbcb\geq bcb \tag{2}$

が成り立つ。 $(1)$ 、 $(2)$ より $bcbcbcb=bcb$ が示された。 Q.E.D.

高々14個であることの証明。

命題 $K(X,\mathcal{O})=\{\mathrm{id},b,c,bc,cb,bcb, cbc,bcbc,cbcb,bcbcb,cbcbc,bcbcbc,cbcbcb,cbcbcbc\}$ である。

証明. $b^2=b$ , $c^2=\mathrm{id}$ という性質から $K(X,\mathcal{O})$ の $\mathrm{id}$ 以外の任意の元は $b$ と $c$ を交互に繰り返す文字列に還元される。 $bcbcbcb$ および8文字以上を使うこのような文字列は補題によって必ず長さを短く還元できるので証明が完了する。 Q.E.D.

14個得られる実例

$X=\mathbb{R}$ として通常の位相を考える。

$A:=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})$

とせよ。

$\begin{align} A&=(0,1)\cup (1,2)\cup \{3\} \cup ([4,5]\cap\mathbb{Q})\\ b(A)&=[0,2]\cup\{3\}\cup[4,5]\\ c(A)&=(-\infty,0]\cup\{1\}\cup[2,3)\cup(3,4)\cup([4,5]\setminus\mathbb{Q})\cup (5,\infty)\\ bc(A)&=(-\infty,0]\cup\{1\}\cup[2,\infty)\\ cb(A)&=(-\infty,0)\cup(2,3)\cup(3,4)\cup(5,\infty)\\ bcb(A)&=(-\infty,0]\cup[2,4]\cup[5,\infty)\\ cbc(A)&=(0,1)\cup(1,2)\\ bcbc(A)&=[0,2]\\ cbcb(A)&=(0,2)\cup(4,5)\\ bcbcb(A)&=[0,2]\cup[4,5]\\ cbcbc(A)&=(-\infty,0)\cup(2,\infty)\\ bcbcbc(A)&=(-\infty,0]\cup[2,\infty)\\ cbcbcb(A)&=(-\infty,0)\cup(2,4)\cup(5,\infty)\\ cbcbcbc(A)&=(0,2) \end{align}$

の14個は全て相異なっている。

*1:閉包(closure)、補集合(complement)ともに頭文字はcであるが、閉包の方はよく $\overline{A}$ で表すので、barのbを採用した。

2019-08-14

わにたろうとわに子のぼうけん

その他

これは私が1997年12月18日に執筆した物語を記録するものである。

登場人物

わにたろう
わに子
わにみ（おかあさん）
わにさぶろう（おとうさん）
ちゅん（すずめ）
スーパーきょうわくわるわるくじら王

f:id:integers:20190814202953p:plain

わにたろうとわに子のぼうけん

「わにたろうくんおきて」

わに子はぼうけんのすきな女のわにです。

「またぼうけんか。」

わにたろうはねむそうに言いました。

「わるい。」

わに子がおこって言いました。

「そうだ海できょうそうしない。」

わに子がたずねました。

「うん。いくよ。」

わにたろうが答えました。

「じゃあ行こう。」

わに子がうれしそうに言いました。

二人は北のしままできょうそうしましたが、わにたろうがとちゅうで、

「もうおよげないよう。」

となきました。

わに子は

「もう、しょうがないな。」

といってせなかにのせました。

なんとかしままでつきました。

二人はつかれたのでねむってしまいました。

「わに子なんか音しない。」

わにたろうが言いました。

「え、あ火山だよ。」

f:id:integers:20190814203123p:plain

二人はおきました。

二人はいそいで南のしまにいこうとしました。

二人は海に入っておよぎました。

南のしまにつきました。

「あれ、火山は、ゆめだったの。」

二人はいっしょに言いました。

「でもおよげたじゃん。」

わに子が言いました。

「まあね。」

わにたろうがじまんそうに言いました。

「あ、はちのすふんじゃった。」

とわにたろうが言いました。

f:id:integers:20190814203238p:plain

二人はおおいそぎでにげ回りました。

はちはにげました。でも、

「いたいよー。」

わにたろうがさされてしまいました。

がすぐなおりました。

そこへすずめのちゅんがきました。

「いっしょにあそばない。」

わに子が言いました。

「いいよ。」

ちゅんが言いました。

「遠足にいくんじゃなかったの。」

「ちゅうしになったの。」

「じゃんけんしない。」

「でももうおそいから帰るよ。」

ちゅんが言いました。

「バイバイ。」

わに子とわにたろうが言いました。

二人はふねにのって家に帰りました。

f:id:integers:20190814203403p:plain

f:id:integers:20190814203622p:plain

「今日はすごいぼうけんだったね。」

わに子が言いました。

「ねえ、おかあさん。」

わに子が言いました。

「なんだい。」

おかあさんのわにみが言いました。

「あのね今日、すごいぼうけんしたんだよ。」

わにたろうが言いました。

f:id:integers:20190814203453p:plain

「もうわたしがいおうとしたのに。」

わに子がおこりました。

「けんかしちゃだめよ。」

とおかあさんにいわれ

「はい。」

と二人はちいさいこえで言いました。

二人は家ではなく外でまたねてしまいました。

f:id:integers:20190814203424p:plain

「ねえ、海にもぐらない。」

わにたろうは言いました。

「うん、いいよ。」

わに子が言いました。

二人はゆめのなかで海にもぐりました。

「ねえねえなにか光ってるよ、いってみない。」

「うんそうだね」

「あっおかねだ。」

f:id:integers:20190814203524p:plain

二人はよろこんだけどそのとき

「うわー。」

f:id:integers:20190814203824p:plain

二人はスーパーきょうわくわるわるくじら王にくわれてしまいました。

二人はおなかのなかでないているとさかなたちがきました。

f:id:integers:20190814203845p:plain

「どうしたんだい、スーパーきょうわくわるわるくじら王にたべられたのかい。」

わにたろうが言いました。

「うんそうなんだよ。」

さかなたちもないてしまいました。

「そうだ、計画をた(て)るんだ。」

さかなたちとわに子とわにたろうは計画をたてています。

f:id:integers:20190814203701p:plain

「まずしんでいるさかなをつなげてくじらのおなかをたたけばいいと思うけど。」

わにたろうがしんけんになって言いました。

「どうやってつなげるの。」

わに子が言いました。

みんな考えていると

「そうだ、くじらのよだれでひっつけたらいいんだよ。」

さかなたちが言いました。

みんな一づつつくりました。

たたいてみるとまるいあながあいてみんなあなからでると

「やったー。」

とみんな言いましたが、そこはまだくじらのはのところでした。

みんながっかりしたけどつぎのさくせんをきめました。

「わにたろうくんがくじらのはをかんではをおったらいいと思うけど。」

とさかなたちが言いました。

みんなでれました。その時二人はゆめからおきました。

「またゆめだったのか」

二人はいっしょに言いました。

そのときおとうさんのわにさぶろうがしごとから帰ってきて

「こらなにしてんの。」

とおこられました。

「ごめんなさい。」

二人はおとうさんにいってわらいながら帰りました。

f:id:integers:20190814203917p:plain

2019-05-08

Chebyshevによる(素数計数関数についての)Legendre予想の否定的解決について

定理解説

Chebyshevは素数定理の弱い版である

$\displaystyle c_1\frac{x}{\log x} \leq \pi(x) \leq c_2\frac{x}{\log x}$

を示しており( $c_1, c_2$ は正の定数), 極限 $\displaystyle \lim_{x\to \infty}\frac{\pi(x)\log x}{x}$ が存在するならば $1$ でなければならないということを示していました.

実は彼はLegendre予想の否定という仕事もやっています( $x$ に関する漸近挙動は $x\to \infty$ を考える).

Legendre予想 (1798/1808) $\pi(x)$ は

$\displaystyle \pi(x)=\frac{Bx}{\log x-A+o(1)}\tag{1}$

を満たし, 更に $A=1.08366...$ , $B=1$ が成り立つであろう.

とりあえず, これは素数定理より強い予想ですが, $A$ の値は間違えており, Chebyshevが次を示しました.

定理 (Chebyshev, 1848) $(1)$ が成り立つのであれば, $A=B=1$ でなければならない.

実はGaussは正しく予想していたようです. Chebyshevは $\zeta^{(m)}(s)$ の $s\to 1+0$ の挙動を使って少し強い形で定理を証明し, 実際に極限が存在するという難しい部分はde la Valée Poussinが1899年に証明しています(素数定理の証明は1896年).

さて, 実は上記Chebyshevの定理は非常に簡単に証明できることがPintzによって指摘されています.

J. Pintz, On Legendre's prime number formula, Amer. Math. Monthly 87 (1980), 733-735.

その証明を紹介したいのですが, ちょうど私が執筆した素数定理の証明の本

note.mu

の中で示されている公式達を使わせていただくと簡単に紹介できるのでそうさせていただきます. この本では第一世代・第二世代・第三世代のビッグ・オー不等式があって, 第三世代まで行くと素数定理の証明が可能となったということが書かれています(なお, この記事ではビッグ・オー不等式としてではなく漸近公式のみを考えれば十分です).

一言で述べると, 上記Chebyshevの定理は第二世代の(von-Mangoldt関数版の)Mertensの第一定理から瞬殺されます. Pintzが

So it is curious that Legendre's conjecture (1.2) had remained open for 40 years.

とコメントしているのは納得です.

PintzによるChebyshevの定理の証明

$\Lambda(n)$ はvon-Mangoldt関数(素数定理本定義6.9). $\psi(x)$ は第二Chebyshev関数(素数定理本定義6.13). 実際には次を示す.

定理 (Pintz) $\psi(x)$ が

$\displaystyle \psi(x)=Cx+\frac{(D+o(1) )x}{\log x}\tag{2}$

を満たすのであれば, $C=1$ かつ $D=0$ でなければならない.

補題 $f(x)=o(g(x))$ であり, $f(x), g(x)$ は任意の $x\geq a$ に対して $[a,x]$ でリーマン積分可能であるとする( $a \in \mathbb{R}$ ). $\int_a^xg(t)\mathrm{d}t\to\infty \ (x \to \infty)$ であれば,

$\displaystyle \int_a^xf(t)\mathrm{d}t=o\left(\int_a^xg(t)\mathrm{d}t\right)$

が成り立つ.

証明. 任意に $\varepsilon > 0$ をとり, $t\geq c$ であれば $\left|f(t)\right|\leq \varepsilon g(t)$ が成り立つとする. このとき,

$\displaystyle \left|\int_a^xf(t)\mathrm{d}t\right| \leq \int_a^c\left|f(t)\right|\mathrm{d}t+\int_c^x\left|f(t)\right|\mathrm{d}t\leq A+\varepsilon\int_c^x\left|g(t)\right|\mathrm{d}t$

と評価できる. ここで, $A:=\int_a^c\left|f(t)\right|\mathrm{d}t$ . 仮定より $x$ が十分大きければ

$\displaystyle \left.\left|\int_a^xf(t)\mathrm{d}t\right|\right/\int_a^xg(t)\mathrm{d}t \leq 2\varepsilon$

とできる. Q.E.D.

Pintzの定理からChebyshevの定理が出ること(この部分は基本的ということでPintzの論文には書かれていない): Abelの総和公式(素数定理本命題5.1)において $a_n=\frac{\Lambda(n)}{\log n}$ , $\varphi(x)=\log x$ とすると, $\displaystyle \sum_{2\leq n\leq x}a_n\varphi(n)=\psi(x)$ であり,

$\displaystyle \sum_{2\leq n \leq x}a_n=\sum_{p^k\leq x}\frac{\log p}{k\log p}=\sum_{k=1}^{\infty}\frac{1}{k}\pi(x^{\frac{1}{k}}),$

$\displaystyle \sum_{k=2}^{\infty}\frac{1}{k}\pi(x^{\frac{1}{k}}) \leq\sum_{k=2}^{[\log_2x]}\sqrt{x}=O(\sqrt{x}\log x)=o\left(\frac{x}{\log^2x}\right)$

なので, 補題より

$\displaystyle \psi(x)=\pi(x)\log x+o\left(\frac{x}{\log x}\right)-\int_2^x\frac{\pi(t)}{t}\mathrm{d}t+o\left(\int_2^x\frac{\mathrm{d}t}{\log^2t}\right)$

を得る. Chebyshevの定理を証明するために $(1)$ が成立すると仮定する. $\frac{1}{1-X}=1+X+o(X), (X\to 0)$ に注意すれば,

$\displaystyle \pi(x)\log x=\frac{Bx}{1-\frac{A+o(1)}{\log x}}=Bx+\frac{B(A+o(1) )x}{\log x}+o\left(\frac{x}{\log x}\right).$

$\pi(t)=\frac{Bt}{\log t}+O\left(\frac{t}{\log^2t}\right)$ より, 素数定理本補題4.4によって

$\displaystyle \int_2^x\frac{\pi(t)}{t}\mathrm{d}t=B\int_2^x\frac{\mathrm{d}t}{\log t}+O\left(\int_2^x\frac{\mathrm{d}t}{\log ^2t}\right)$ .

素数定理本補題4.5(4), (6)より

$\displaystyle O\left(\int_2^x\frac{\mathrm{d}t}{\log^2t}\right)=o\left(\frac{x}{\log x}\right), \quad \int_2^x\frac{\pi(t)}{t}\mathrm{d}t=\frac{Bx}{\log x}+o\left(\frac{x}{\log x}\right).$

である. 以上をまとめると,

$\displaystyle \psi(x)=Bx+\frac{(B(A-1)+o(1) )x}{\log x}$

の成立がわかった. よって, Pintzの定理が正しければ, $B=1$ および $B(A-1)=0$ が従い, $A=B=1$ となる. Q.E.D.

Pintzの定理の証明. $(2)$ の成立を仮定する. 素数定理本命題6.18(17)より

$\displaystyle \sum_{n\leq x}\frac{\Lambda(n)}{n}=\log x+O(1)\tag{3}$

が成り立つ(今は $(2)$ の成立を仮定しているため $\psi(x)=O(x)$ が使用可能であり, 従って命題6.18(17)の証明(=シャピロのタウバー型定理の証明)で比較的難しかった部分の議論は全て不要であることに注意). また, Abelの総和公式を $a_n=\Lambda(n) \ (n\geq 2), \varphi(x)=\frac{1}{x}$ として適用すれば