2015-08-15

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)『解析入門Ⅰ』東京大学出版会

2014-04-30

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

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

f:id:fujidig:20150818232416j:plain

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

$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} $

2014-04-17

合成函数の極限

$\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:この記事ではこのことの証明はしていません。証明するのであれば、そのような具体的な例を作る必要があります！

2014-03-17

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メンバを参照することができます。