集合論を基礎としたオーダー記法

シリーズ本編ではランダウの記法について集合論に基づかない定義をしていた。しかし、その定義の中で集合論の記号 $\in$ を用いておりあたかも $O(g)$ や $\Theta(g)$ が集合であるかのように扱っていた。この記事では、本当に $O(g)$ と $\Theta(g)$ を集合として定義し、いままで定義としていた同値式を集合論的に意味を持つようにする。

定義の変更

この記事シリーズではランダウのオーダー記法を次のように定義していた。

命題実数関数\(f(x), g(x)\)において \begin{eqnarray} f \in O(g) & \Leftrightarrow & \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k \cdot |g(x)|, \\ f \in \Theta(g) & \Leftrightarrow & f \in O(g) \land g\in O(f). \end{eqnarray}

この定義では $f\in O(g)$ 全体を2つの実数関数 $f$, $g$ に対して用いる記号であるとしている。しかし、集合論的にはもっと分解して「$f$ は集合 $O(g)$ の要素である」という意味を持つべきである (さらに言うと $O$ は実数関数から集合を得る写像と捉えられるべきである)。

そこで、ランダウのオーダー記法を次のように定義をし直す。ただし、$\text{Map}(\boldsymbol{R}, \boldsymbol{R})$ はすべての実数関数からなる集合であり、集合 $X$ に対して $\mathfrak{P}(X)$ は $X$ の冪集合である。

定義写像 $O:\text{Map}(\boldsymbol{R},\boldsymbol{R})\to \mathfrak{P}(\text{Map}(\boldsymbol{R}, \boldsymbol{R}))$ を\[g\mapsto \{f \in \text{Map}(\boldsymbol{R}, \boldsymbol{R}) \mid  \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k |g(x)| \}\]と定義し、この写像 $O$ を用いて行う $f\in O(g)$ という表現をランダウの $O$-記法と呼ぶ。

定義写像 $\Theta:\text{Map}(\boldsymbol{R},\boldsymbol{R})\to \mathfrak{P}(\text{Map}(\boldsymbol{R}, \boldsymbol{R}))$ を\[g\mapsto \left\{f \in \text{Map}(\boldsymbol{R}, \boldsymbol{R})\;\middle|\;\begin{array}{r}\exists k_u \gt 0,\exists k_l\gt 0, \exists x_0, \forall x \gt x_0, \\k_l|g(x)|\leq|f(x)| \leq k_u |g(x)| \end{array}\right\}\]と定義し、この写像 $\Theta$ を用いて行う $f\in \Theta(g)$ という表現をランダウの $\Theta$-記法と呼ぶ。

定義が妥当かどうかの確認

定義を変えてしまったのだから、この定義からもともと定義としていた命題が導かれるかどうかを確認するべきであろう。もし導くことが出来るなら、もともとの定義から導いたもろもろの定理は新しい定義からも導くことが出来ることになり、定理であり続けられる。

定理実数関数\(f(x), g(x)\)において

  1. $f \in O(g) \Leftrightarrow \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k \cdot |g(x)|$
  2. $f \in \Theta(g) \Leftrightarrow f \in O(g) \land g\in O(f)$

(証明) 1から示す。写像 $O$ の定義より\[O(g) = \{f \in \text{Map}(\boldsymbol{R}, \boldsymbol{R}) \mid  \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k |g(x)| \}.\]したがって (内包的記法の定義より) $f\in O(g)$ は $\exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k|g(x)|$ と同値である。

2を示す。写像 $\Theta$ の定義より 1 のときと同様に考えると $f\in\Theta(g)$ は\[\exists k_u \gt 0,\exists k_l\gt 0, \exists x_0, \forall x \gt x_0, k_l|g(x)|\leq|f(x)| \leq k_u |g(x)|\tag{1}\] と同値である。したがって式1と $f\in O(g)\land g\in O(f)$ が同値であることを示せばよいので、以下に示す。

式1ならば $f\in O(g)\land g\in O(f)$ であることを示す。式1から \begin{eqnarray}\exists k_u \gt 0, \exists x_0, \forall x \gt x_0, &&|f(x)|\leq k_u|g(x)| \\ \exists k_l\gt 0, \exists x_0, \forall x \gt x_0, &&|g(x)| \leq k_l^{-1} |f(x)|\end{eqnarray}が得られる。ここで $k_l\gt0$ ならば $k_l^{-1}\gt0$ であることと量化された変数記号は置き換え可能であることから \[\begin{array}{ll}\exists k \gt 0, \exists x_0, \forall x \gt x_0, &|f(x)|\leq k|g(x)| \\ \exists k\gt 0, \exists x_0, \forall x \gt x_0, &|g(x)| \leq k |f(x)|\end{array}\tag{2}\]が得られる。式2は 1 より $f\in O(g)$, $g\in O(f)$ となる。

$f\in O(g)\land g\in O(f)$ ならば式1であることを示す。1 より式2が得られる。したがって、量化された変数記号を適当に置き換えると、実数 $k_l'\gt0$, $k_u\gt0$, $x_0'$, $x_0''$ が存在して\begin{eqnarray}\forall x\gt x_0':&&|f(x)|\leq k_u|g(x)|,\\ \forall x\gt x_0'':&&|g(x)|\leq k_l'|f(x)|.\end{eqnarray}したがって、$x_0=\max\{x_0',x_0''\}$, $k_l=k_l'^{-1}\gt0$ とすると\[\forall x\gt x_0:\;k_l|g(x)|\leq|f(x)|\leq k_u|g(x)|\]であるので式1が成り立つ。

以上のように、新しい定義の下で旧定義が証明されるので、旧定義から証明されたあらゆる定理は新しい定義からも証明できることになる。

公理的集合論が基礎になることの補足

今回の新しい定義は集合論の言葉によって行われた。この定義が公理的集合論 (とりわけZFC公理系) のもとでできることを説明しておく。なぜそのような説明をするかというと、ZFC公理系のもとでよく定義されていることがわかると、ZFC公理系に矛盾がない限りはこの定義の下で行われる議論にも矛盾がないといえるからである。数学の論理は矛盾を含むと無意味になるので矛盾を含まないことの確認は大切である。ただし、一階述語論理の言葉だけを使って形式的に証明していくことはあまりにも骨が折れるので、素朴な集合論の言葉を用いて、公理的集合論での定義の手順を大雑把になぞっていく。

まず、実数をすべて要素として持っていてそれ以外の要素を持たない集合 $\boldsymbol{R}$ は次のように作れる。ZFC公理系を含むたいていの公理系では自然数からなる集合を作ることができる。自然数集合と公理を用いて整数集合を定義し、整数集合と公理を用いて有理数集合を定義し、有理数集合から実数集合を定義する方法はよく知られているので、この方法を使えば公理的集合論の中で実数を作ることが出来る。

次に実数関数の集合 (つまり実数から実数への写像からなる集合) $\text{Map}(\boldsymbol{R},\boldsymbol{R})$ は次のように作れる。まず、順序対 $(x,y)$ は公理的集合論の枠組みでも定義できる。そして、実数の順序対からなる集合\[\boldsymbol{R}\times\boldsymbol{R}=\{(x,y)\mid x\in\boldsymbol{R},y\in\boldsymbol{R}\}\]も公理的集合論の枠組みで作ることが出来る。ここで冪集合の公理から、この集合の部分集合からなる集合\[\mathfrak{P}(\boldsymbol{R}\times\boldsymbol{R})=\{R\mid R \subset \boldsymbol{R}\times\boldsymbol{R}\} \]も作れる。この集合の要素を $R$ と表現しているが、これは $\boldsymbol{R}\times\boldsymbol{R}$ の部分集合がシリーズ内の別の記事でも取り上げた『実数同士の関係』を意味することに由来する。つまりこの集合は、実数同士の関係からなる集合である。写像は (前順序や同値関係のように) 関係のうち特別なルールを満たすものとして定義されるので、実数同士の関係からなる集合の部分集合として、実数から実数への写像からなる集合\begin{eqnarray}\text{Map}(\boldsymbol{R},\boldsymbol{R})&=&\{f\in \mathfrak{P}(\boldsymbol{R}\times\boldsymbol{R}) \mid f \text{ は写像のルールを満たす}\}\\&=&\{f\mid \text{$f$ は $\boldsymbol{R}$ から $\boldsymbol{R}$ への写像である}\}\end{eqnarray}も (分出公理を使うことで) 作ることが出来る。

$O$ と $\Theta$ の定義では実数同士の大小関係と実数同士の乗法を用いているので、これらの存在も確かめなくてはならない。ただ、実数同士の大小関係は関係であるので集合 $\mathfrak{P}(\boldsymbol{R}\times\boldsymbol{R})$ の要素として存在する。また、実数同士の乗法は実数の組から実数への写像 $\boldsymbol{R}\times\boldsymbol{R}\to\boldsymbol{R}$ であるので集合 $\text{Map}(\boldsymbol{R}\times\boldsymbol{R},\boldsymbol{R})$ の要素として存在する。(厳密にはこの集合の要素のうち特定のものを大小関係や乗法として指定する方法がなくてはならない。ただ、上述の方法で実数を定義しておけば、実数同士の大小関係や乗法をうまく指定する方法は知られている。)

そして、上と同様の手法で「実数関数」から「実数関数からなる集合」への写像からなる集合 $\text{Map}(\text{Map}(\boldsymbol{R},\boldsymbol{R}), \mathfrak{P}(\text{Map}(\boldsymbol{R},\boldsymbol{R})))$ を作ることができて、写像 $O$ と写像 $\Theta$ はこの集合の元として確かに存在する。したがって、この記事での新たなオーダーの定義は、公理的集合論のもとでもよく定義されている。