R^dのある点列の集積点全体となる集合は？

定義

$\mathbb{R}^d$の点列$\{x_n\}$に対し、この点列の収束する部分列の極限となる点を点列$\{x_n\}$の集積点という。

問題

$\mathbb{R}^d$のある点列の集積点全体となる集合はどんな集合か。

答え

$\mathbb{R}^d$の閉集合である。

必要性の証明

$A \subset \mathbb{R}^d$が点列$\{x_n\}$の集積点全体とする。$A$が閉集合であることを示す。まず、

$a \in A \iff$ 任意の$\epsilon > 0$に対し無限個の自然数$n$が存在して$|x_n - a| < \epsilon$

が成り立つ。

$A$が閉集合であることを示すには$A$の閉包$\bar A$が$A$に含まれることをいえばよい。 $a \in \bar A$, $\epsilon > 0$とする。 閉包の定義より$a$の$\epsilon / 2$近傍に$A$の点$b$が存在する。 $b \in A$より無限個の自然数$n$が存在して$|x_n - b| < \epsilon/2$である。すると$|x_n - a| < \epsilon$が無限個の$n$で成立するので$a$は$A$に属する。したがって$\bar{A} \subset A$である。

十分性の証明

$\mathbb{R}^d$の部分集合に対して、「ある点列$\{x_n\}$の集積点全体と一致する」という条件を(P)とする。

証明したいことは任意の閉集合が(P)を満たすことである。

(P)を満たす集合が可算個あったとき、それらの和集合もまた(P)を満たす。 実際、(P)を満たす集合$A_n (n = 1, 2, 3, \cdots)$があったとき、各集合に対応する点列をうまく一列に並べればよい。

$\mathbb{R}^d$の閉集合は有界閉集合の可算個の和として書けるので有界閉集合が条件(P)を満たすことを言えばよい。

そこで$A$を$\mathbb{R}^d$の有界閉集合とする。このとき点列$\{x_n\}$が存在して$A$はその集積点全体と一致することを示す。

$\epsilon > 0$とする。このとき $$ A \subset \bigcup_{a \in A} U_\epsilon(a) $$ が成り立つ ($U_\epsilon(a)$は$a$の$\epsilon$近傍)。

$\mathbb{R}^d$の有界閉集合$A$はコンパクトなので、有限個の点$a_1, \cdots, a_n \in A$が存在して $$ A \subset \bigcup_{k=1}^n U_\epsilon(a_k) $$ となる。

正整数$m $に対して$\epsilon = 1/m $として上の方法で得られる$A$の有限列$\{a_1, \cdots, a_n\}$を各$m $に対して選び$S_m $とする。すると$A$の任意の点は有限列$S_m $の中のどれかの点との距離が$1/m $未満となる。

有限列$S_1, S_2, S_3, \cdots$を順につなげてできる点列を$\{x_n\}$とする。 このとき点列$\{x_n\}$の集積点全体は$A$となる。

実際、$x_n \in A (n \in \mathbb{N})$で$A$は閉集合だから、$\{x_n\}$のどんな収束する部分列の極限も$A$に属する。

逆に任意の$a \in A$に対して$a$は$\{x_n\}$の集積点である。 実際、各$m \in \mathbb{N}$に対して有限列$S_m $の要素で$a$にもっとも近いものを$y_m $として点列$\{y_m\}$をとればよい。 $\{y_m\}$は$\{x_n\}$の部分列であり、$|y_m - a| < 1/m (m = 1,2,3,\cdots)$なので$\lim_{m \to \infty} y_m = a$である。

(証明終わり)

{a_n}の第n項のn乗根がある値に収束するとき隣り合った項の比も同じ値に収束するか

背景

微分積分学においてべき級数の収束半径というものがありますが、この求め方として次の二つがあります。

• (係数比判定法) $\lim_{n \to \infty} |\frac{a_{n+1}}{a_n}| = l$ が存在すればべき級数$\sum_{n=0}^\infty a_n z^n$の収束半径$\rho$は$\rho = 1/l$である
• (コーシー・アダマールの公式) べき級数$\sum_{n=0}^\infty a_n z^n$の収束半径$\rho$は常に$1/\rho = \limsup_{n \to \infty} \sqrt[n]{|a_n|}$で与えられる

また、これに関連して、次が成立します。

$a_n \ge 0, \lim_{n \to \infty} \frac{a_{n+1}}{a_n} = l$ ならば $\lim_{n \to \infty} \sqrt[n]{a_n} = l$

問題

では逆に次は成立するのか、気になるのは当然のことです。

(1) $a_n \ge 0, \lim_{n \to \infty} \sqrt[n]{a_n} = l$ ならば $\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = l$

これについて考えます。

$a_n \ge 0$で $$ \lim_{n \to \infty} \sqrt[n]{a_n} = l $$ と仮定します。 このとき、両辺の対数を取ると $$ \lim_{n \to \infty} \frac{\log a_n}{n} = \log l $$ となります。 $b_n = \log a_n$, $k = \log l$とおきます。すると上の等式は $$ \lim_{n \to \infty} \frac{b_n}{n} = k $$ と書き換わります。

今考えているのは $$ \lim_{n \to \infty} \frac{a_{n+1}}{a_n} = l $$ が成り立つかどうかですが、これは両辺の対数を取ることにより次と同値です。 $$ \lim_{n \to \infty} (\log a_{n+1} - \log a_n) = \log l $$ すなわち $$ \lim_{n \to \infty} (b_{n+1} - b_n) = k $$ です。 したがって、(1)は次の(2)に帰着されました。

(2) $\lim_{n \to \infty} \frac{b_n}{n} = k$ ならば $\lim_{n \to \infty} (b_{n+1} - b_n) = k$

では(2)が成り立つか考えましょう。 $\lim_{n \to \infty} \frac{b_n}{n} = k$ より、$\frac{b_n}{n} = k + c_n$とおくと、$c_n \to 0 (n \to \infty)$ です。 今考えていることは $$ \lim_{n \to \infty} (b_{n+1} - b_n) = k $$ が成り立つかどうかですが、これを$c_n$を使って書き換えると $$ \lim_{n \to \infty} [\{(n+1)k + (n+1)c_{n+1}\} - (nk - nc_n)] = k $$ です。$c_n \to 0 (n \to \infty)$であることに注意して書き直すと $$ \lim_{n \to \infty} n(c_{n+1} - c_n) = 0 $$ です。

したがって(2)は次の(3)に帰着されました。

(3) $\lim_{n \to \infty} c_n = 0$ ならば $\lim_{n \to \infty} n(c_{n+1} - c_n) = 0$

$d_n = c_{n+1} - c_n$とおくと、$c_n = c_0 + \sum_{i=0}^{n-1} d_i$です。 (3)の前件において$= 0$は重要ではなく、$c_n$が収束するという条件に置き換えてもかまいません。よって(3)は次の(4)と同値です。

(4) $\sum_{n = 1}^\infty d_n$ が収束するならば $\lim_{n \to \infty} nd_n = 0$

この(4)にはすぐ反例が見つかります。 $$ d_n = \frac{(-1)^{n-1}}{n} $$ です。 実際、無限級数 $$ \sum_{n=1}^\infty \frac{(-1)^{n-1}}{n} = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} \cdots $$ は$\log 2$に収束することが知られています。

さて、振り返ってみましょう。我々は問題を次のように変形していきました。

• (1) $a_n \ge 0, \lim_{n \to \infty} \sqrt[n]{a_n} = l$ ならば $\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = l$
• (2) $\lim_{n \to \infty} \frac{b_n}{n} = k$ ならば $\lim_{n \to \infty} (b_{n+1} - b_n) = k$
• (3) $\lim_{n \to \infty} c_n = 0$ ならば $\lim_{n \to \infty} n(c_{n+1} - c_n) = 0$
• (4) $\sum_{n = 1}^\infty d_n$ が収束するならば $\lim_{n \to \infty} nd_n = 0$

(4)に反例が見つかったので、結局(1)から(4)のどれもが成立しないことがわかりました。

(4)の反例$d_n = \frac{(-1)^{n-1}}{n}$より、議論を逆向きにたどって(1)の反例を構成すると次のようになります。

$$ a_n = e^{n (1 + \sum_{k=1}^n \frac{(-1)^{k -1}}{k} - \log 2)} $$

これが本当に反例になっているのか確認しておきましょう。まず、

$$ \lim_{n \to \infty} \sqrt[n]{a_n} = \lim_{n \to \infty} e^{1 + \sum_{k=1}^n \frac{(-1)^{k -1}}{k} - \log 2} = e $$ より$\sqrt[n]{a_n}$は$n \to \infty$で$e$に収束します。次に、 $$ \lim_{n \to \infty} \frac{a_{n+1}}{a_n} = e^{(-1)^n} $$ より、$\frac{a_{n+1}}{a_n}$は$n \to \infty$で発散します。確かに(1)は成立しません。

答え

(1) $a_n \ge 0, \lim_{n \to \infty} \sqrt[n]{a_n} = l$ ならば $\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = l$

これは成立しない。

R上の閉集合はすべて閉区間の加算個の和で表せるか？

$\mathbb{R}$上の閉集合はすべて閉区間の加算個の和で表せるか？

答え: No.

カントール集合が反例となる。

カントール集合の定義

区間$I = [0,1]$を3等分して中央の開区間$(\frac{1}{3}, \frac{2}{3})$を除く。残りの二つの区間をまた3等分して中央の開区間$(\frac{1}{9}, \frac{2}{9})$, $(\frac{7}{9}, \frac{8}{9})$を除く。この操作を無限回繰り返すとき残った点の集合$C$をカントール集合という。

カントール集合の性質

カントール集合は無限個の閉集合の共通部分なので閉集合である。

区間を除く操作を$n$回行った直後の集合は互いに重なり合わない長さ$1/3^n$の閉区間の和である。どんな正の数$\epsilon$に対しても$1/3^n < \epsilon$となる正整数$n$をとれるので、カントール集合はどんなに小さい長さ$\epsilon > 0$の区間をも含まない。

カントール集合は$0$以上$1$以下の実数のうち三進表示に$1$が現れないもの全体である。 したがって、三進表示が一意でない実数が存在することを無視すれば、カントール集合の元は各項が$\{0, 2\}$の元をとる数列と一対一に対応付けられる。 そのような数列全体の濃度は明らかに$2^{\aleph_0}$である。三進表示が一意でないものは可算個しかないのでカントール集合の濃度も$2^{\aleph_0}$である。

主張の反証

以上のことより、カントール集合$C$は閉集合であり、これは閉区間の加算個の和で表せないので主張が反証された。

参考文献

• 杉浦光夫(1980)『解析入門Ⅰ』東京大学出版会

Ax = bが解を持つようなb

『代数の考え方』 (梅田 亨)に未証明で載っていた事実を証明してみようとしたところ,なかなか手こずった.

内積と直交補空間を使って証明したが、内積を使わずに証明できるのだろうか？

$A$を$(m,n)$型複素行列とする. このとき,

\( \qquad\begin{align} 1次方程式系 A{\bf x} = {\bf b} が解を持つ &\Leftrightarrow {\bf b} \in \rm{Im} A \\ &\Leftrightarrow \{\{{\bf b}\}\} \subset \rm{Im} A \\ &\Leftrightarrow (\rm{Im} A)^\perp \subset \{\{{\bf b}\}\}^\perp \\ &\Leftrightarrow \rm{Ker} A^* \subset \{\{{\bf b}\}\}^\perp \\ &\Leftrightarrow (\forall {\bf y} \in \mathbb{C}^m)(A^*{\bf y} = {\bf o} \Rightarrow {}^{t}\bar{\bf b}{\bf y} = 0) \\ &\Leftrightarrow (\forall {\bf y} \in \mathbb{C}^m)({}^t\bar{A}\bar{\bf y} = {\bf o} \Rightarrow {}^{t}\bar{\bf b}\bar{\bf y} = 0) \qquad\cdots{\bf y}が\mathbb{C}^m全体を動くとき\bar{\bf y}も\mathbb{C}^m全体を動くから \\ &\Leftrightarrow (\forall {\bf y} \in \mathbb{C}^m)({}^t{\bf y}A = {{}^t\bf o} \Rightarrow {}^{t}{\bf y}{\bf b} = 0). \end{align} \)

合成函数の極限

$\require{color}$

$\begin{eqnarray}\lim_{x \to a} f(x) = b \end{eqnarray}$, $\begin{eqnarray}\lim_{y \to b} g(y) = c \end{eqnarray}$であっても、$\begin{eqnarray}\lim_{x \to a} g(f(x)) = b \end{eqnarray}$とは限らない。*1

• 仮定($\lim_{x \to a} f(x) = b$をεδ論法で書いたもの)
  ①: $(\forall \epsilon_2 > 0)(\exists \epsilon_1 > 0)(\forall x)(0 < |x - a| < \epsilon_1 \implies \textcolor{red}{|f(x) - b| < \epsilon_2})$

• 仮定($\lim_{y \to b} g(y) = c$をεδ論法で書いたもの)
  ②: $(\forall \epsilon_3 > 0)(\exists \epsilon_2 > 0)(\forall y)(\textcolor{blue}{0 < |y - b| < \epsilon_2} \implies |g(y) - c| < \epsilon_3)$

• 導き出したいこと($\lim_{x \to a} g(f(x)) = c$をεδ論法で書いたもの)
  ③: $(\forall \epsilon_3 > 0)(\exists \epsilon_1 > 0)(\forall x)(0 < |x - a| < \epsilon_1 \implies |g(f(x)) - c| < \epsilon_3)$

それは赤と青で示した部分での"$0 < $"の有無でギャップが出ているからだ。

もしここで($a$の十分小さな近傍内の$x$について)$x \ne a \implies f(x) \ne b$という仮定を付け加えると、①は次の①'に変わる。

• ①': $(\forall \epsilon_2 > 0)(\exists \epsilon_1 > 0)(\forall x)(0 < |x - a| < \epsilon_1 \implies \textcolor{red}{0 < |f(x) - b| < \epsilon_2})$

するとギャップはなくなり、①', ②から目的の③は導かれる。

あるいは、$g$が$b$でも定義されていてしかも$g$が$b$で連続であったという仮定を付け加えた場合は、②は次の②'に変わる。

• ②': $(\forall \epsilon_3 > 0)(\exists \epsilon_2 > 0)(\forall y)(\textcolor{blue}{|y - b| < \epsilon_2} \implies |g(y) - c| < \epsilon_3)$

この場合も同様ギャップはなくなって、①, ②'から③が導ける。

*1:この記事ではこのことの証明はしていません。証明するのであれば、そのような具体的な例を作る必要があります！

Rubyの配列のsharedフラグ (その1)

この記事では執筆時点最新のCRuby trunk リビジョン45349のソースを参照して書いています。

CRubyの配列の実装にはsharedフラグというものがあります。これは複数の異なる配列オブジェクトが実体メモリを共有するためのものです。

特別にフラグの立っていない配列オブジェクト

この記事ではVALUEやstruct RBasicなどの構造については既知とします。知らない方は以下を読みましょう。

• RHG 第2章 オブジェクト

まず、これがRArray構造体です。

struct RArray {
    struct RBasic basic;
    union {
	struct {
	    long len;
	    union {
		long capa;
		VALUE shared;
	    } aux;
	    const VALUE *ptr;
	} heap;
	const VALUE ary[RARRAY_EMBED_LEN_MAX];
    } as;
};

#define RARRAY(obj)  ((struct RArray*)(obj))

特別になんのフラグも立っていない通常の配列の場合を最初に確認しておきます。これをこの記事では通常モードとでも呼びましょう。

通常モードの配列では、RARRAY(ary)->as.heap.ptrに実体メモリのポインタが格納され、この所有権を持ちます。所有権とは、このポインタをfreeする責任は自分が持ちますよ、ということです。
そしてRARRAY(ary)->as.heap.lenに配列の長さが、RARRAY(ary)->as.heap.aux.capaに確保したメモリの大きさが格納されます。とっても普通ですね。

なお、embedフラグの立った配列オブジェクトというものがあって、これは要素数が3以下の配列はRArray構造体の中に実体を格納してしまうというものです。しかしこれはsharedフラグを理解する上で本質的ではないので無視します。

sharedフラグの基礎

"sharedフラグのついた配列オブジェクト"のことを単にsharedオブジェクトと呼ぶことにします。
sharedフラグには次の性質があります。

• sharedオブジェクトは実体ptrの所有権をもたない
• sharedオブジェクトの"sharedメンバ" にはfrozenな配列オブジェクト(への参照)が格納される。

ここで配列aryのsharedメンバとはRARRAY(ary)->as.heap.aux.sharedのことをいうことにします。

実際の実装はちょっと複雑なので、少し簡略化したものをここでは紹介します。

まずfrozenな配列オブジェクトをdupすると、このオブジェクトを指したsharedオブジェクトが作られメモリが共有されます。
たとえばfrozenな配列aをdupしてbを得たとしたとしたら以下のようになります。

さて、aとbは実体メモリを共有しているわけですが、このままではbを書き換えた時にaにもそれが反映されてしまいます。
そこでsharedオブジェクトを書き換えるときには、実体メモリをコピーしそれへの所有権を持ち通常モードの配列に変化させます。これを行うためRubyでは配列への破壊的なメソッドでは必ずrb_ary_modify()を呼んでいます。

なお、aはfrozenなので、aが書き換わってbにも反映される、という心配はありません。

sharedオブジェクトは実体メモリの所有権を持っていませんが、だからといってオブジェクトは生きているのにGCによって実体メモリが解放されてしまうということはありません。なぜなら、sharedメンバにメモリの所有権を持っているオブジェクトへの参照を持っているからです。

ところでfrozenオブジェクトaを指すsharedオブジェクトbがすでにあって、さらにbをdupして新しい配列cを得るときはどうすればいいでしょう。これは単にaを指すsharedオブジェクトつまりbと同様のものを作ればよいだけですね。

以上の方法でfrozenな配列のdupが定数時間で済みます。
ここまで簡略化したものを紹介しましたが、実はfrozenではない配列をdupしたときにも実体メモリのコピーが起きないように実装されているのです。その仕組みを「その2」の記事で書こうかと思います。

追記(2015/11/29)

この記事を書くために次のような拡張ライブラリを作って動作を確かめました。

dump.c

#include <ruby.h>

#define RARRAY_SHARED_ROOT_FLAG FL_USER5

VALUE dump(VALUE self, VALUE ary){
	Check_Type(ary, T_ARRAY);
	printf("<%" PRIxVALUE, ary);
	if (FL_TEST(ary, RARRAY_EMBED_FLAG)) {
		printf(" embed");
	} else if (FL_TEST(ary,ELTS_SHARED)) {
		printf(" shared ptr=%p, shared=%" PRIxVALUE, RARRAY(ary)->as.heap.ptr, RARRAY(ary)->as.heap.aux.shared);
	} else if (FL_TEST(ary, RARRAY_SHARED_ROOT_FLAG)) {
		printf(" shared_root ptr=%p num=%ld", RARRAY(ary)->as.heap.ptr, RARRAY(ary)->as.heap.aux.capa);
	} else {
		printf(" normal ptr=%p", RARRAY(ary)->as.heap.ptr);
	}
	if (OBJ_FROZEN(ary)) {
		printf(" frozen");
	}
	puts(">");
	return Qnil;
}

VALUE shared(VALUE ary) {
	if (FL_TEST((ary),ELTS_SHARED)!=0) {
		return RARRAY(ary)->as.heap.aux.shared;
	} else {
		return Qnil;
	}
}

void Init_dump(void){
	rb_define_global_function("dump", dump, 1);
	rb_define_method(rb_cArray, "shared", shared, 0);
}

この拡張ライブラリを使うと

dump(ary)

でArrayオブジェクトaryの情報を出力することができます。

ary.shared

でsharedメンバを参照することができます。