O-記法の前順序性

シリーズの最初の記事で、2つの実数関数 $f$, $g$ 同士の比較方法として $O$-記法 ($f\in O(g)$) を定義し、直感的に「$f$ のオーダーは $g$ のオーダー以下である」という表現を与えた。この記事では、このまるで大小関係であるかのような直感的表現が実態とかけ離れていないことを説明する。

$O$-記法の定義

シリーズ内の記事ですでに行った定義を確認する。

定義$f$, $g$ をそれぞれ実数関数とする。これらが\[\exists k\gt0:\exists x_0:\forall x\gt x_0: |f(x)|\leq k|g(x)|\]を満たすことを $f\in O(g)$ と書く。

前回の記事ではこの $f\in O(g)$ であることを直感的に「$f$ のオーダーは $g$ のオーダー以下である」と表現した。まるで大小関係のようなこの直感的表現を裏付けるため、以下では $O$-記法が前順序であることを示していく。

前順序とは

正確な定義は後述するが、前順序 (“全”順序とは異なる) とは物同士の関係のうち特定の条件を満たすものである。たとえば、2つの自然数 $n$, $m$ の間の関係として、「$n$ で $m$ を割り切れる」という関係を考えることができる。この関係は後述する条件を満たすので前順序である。この例では自然数同士の関係を挙げたが、他にも実数同士の関係、集合同士の関係、関数同士の関係などについても考えることができる。

さて、ここで前順序をより正確に定義しておく。

定義ある種の2つの物 $a$, $b$ に対して $aRb$ と書き表される関係があるとする。この関係が

  • (反射律) $aRa$
  • (推移律) $aRb$, $bRc$ であれば $aRc$ である
を満たすとき、この関係は前順序である。

この定義に則ると、上で挙げた「$n$ で $m$ を割り切れる」という関係は前順序であるが、これを確かめてみる。「$n$ で $m$ を割り切れる」という関係を $n|m$ と書き表すことにする (この書き方はよく用いられる)。すると、$a$ がどんな自然数であっても「$a$ で $a$ を割り切れる」(つまり $a|a$) ので反射律を満たす。そして、3つの自然数 $a$, $b$, $c$ について「$a$ で $b$ を割り切れ」て「$b$ で $c$ を割り切れる」(つまり $a|b$, $b|c$) とすると、「$a$ で $c$ を割り切れる」(つまり $a|c$) ことは (ここでは詳しく書かないが) 証明できるので推移律を満たす。以上より、この関係は前順序である。

他にも、中学で普通に扱う『実数の大小関係 ($\leq$)』や高校数学で扱う『集合の包含関係 ($\subseteq$)』なども前順序である。このように前順序は、2つのものが「ある意味で同程度かそれより小さい」ことを表す関係となる。したがって $O$-記法も前順序であることが示せれば冒頭に述べた「以下である」という表現を与えることができるだろう。

$O$-記法の前順序性

では実際はどうかというと、$O$-記法も実数関数同士の関係であり前順序である。現に、2つの実数関数 $f$, $g$ に対して $f\in O(g)$ であるという関係を考えると、この実数関数同士の関係は以下で確認するように反射性と推移性を有する。そのため、$f\in O(g)$ であるという関係を前順序として捉えることができる。

定理$f$ を実数関数とする。このとき $f\in O(f)$。

(証明) $f$ を実数関数とすると\[\forall x\gt 0:\;|f(x)|\leq 1|f(x)|\]であるから $f\in O(f)$ である。

定理$f$,$g$,$h$ を実数関数とする。このとき $f\in O(g)$, $g\in O(h)$ ならば $f\in O(h)$ である。

(証明) $f\in O(g)$, $g\in O(h)$ を仮定して $f\in O(h)$ を示す。仮定より4つの実数 $k'>0$, $k''>0$, $x_0'$, $x_0''$ が存在して\begin{eqnarray}\forall x \gt x_0':\;|f(x)|\leq k'|g(x)|, \\ \forall x \gt x_0'':\;|g(x)|\leq k''|h(x)|. \end{eqnarray}このとき $k=k'k''$, $x_0=\max\{x_0',x_0''\}$ とすると $k\gt 0$ であり、任意の $x\gt x_0$ に対して\begin{eqnarray}|f(x)| &\leq& k'|g(x)| \\ &\leq& k'k''|h(x)| \\ &=& k|h(x)| \end{eqnarray}であるから $f\in O(h)$。

以上のことから $f\in O(g)$ は前順序であり、すなわち「$f$ が $g$ とある意味で同程度であるかそれより小さい」ことを意味するといえる。この「ある意味」の部分を「オーダー」という語に置き換えることで、冒頭の「$f$ のオーダーは $g$ のオーダー以下である」に行き着く。このことから、大小関係っぽい冒頭の表現にある程度の正当性が与えられるだろう。

$O$-記法は半順序ではないのか

ここまでで前順序とは何かということ、$O$-記法が前順序であることを確認した。さて、一般には前順序の中でも以下のように特定の条件を満たすものは半順序と呼ばれる。

定義ある種の2つの物 $a$, $b$ に対して $aRb$ と書き表される関係があり、それが前順序であるとする。この前順序について

  • (反対称律) $aRb$, $bRa$ ならば $a=b$
を満たすとき、この前順序は半順序である。

既に前順序の例として挙げた「$n$ で $m$ を割り切れる」や『実数の大小関係』や『集合の包含関係』はどれも反対称律を満たすので半順序でもある。

しかし、$O$-記法は反対称律を満たさない。これは以下のように反例を考えてみれば明らかである。

定理$O$-記法は反対称性を持たない。つまり、$f\in O(g)$, $g\in O(f)$ を満たすが $f\neq g$ であるような実数関数 $f$, $g$ が存在する。

(証明) まず (i) を示す。$f(x)=x$, $g(x)=2x$ とすると、\begin{eqnarray}&&\forall x\gt 0:\;|f(x)|\leq 1|g(x)| \\ &&\forall x\gt 0:\;|g(x)|\leq 2|f(x)|\end{eqnarray}であり、$f\neq g$ である。このように確かに反例が存在する。

このように$O$-記法については反対称律が満たされないため、これは半順序ではない。

全順序律を満たさないのか

もう一つ、順序について議論するときに持ち出される規則に全順序律がある。全順序律とは「常に $aRb$ か $bRa$ の少なくとも一方が成り立つ」という規則のことで、例えば実数の大小関係については $a$, $b$ がいかなる実数であっても $a\leq b$, $b\leq a$ の少なくとも一方は成り立つので、実数の大小関係は全順序律を満たす。一方で、「$n$ で $m$ を割り切れる ($n|m$)」は全順序律を満たさず (実際に $2|3$ も $3|2$ も成り立たない)、集合の包含関係も全順序律を満たさない。

では$O$-記法はどうかというと、これらも全順序律を満たさない。これは次のように反例を挙げることで証明できる。

定理$O$-記法は全順序性を持たない。つまり、$f\in O(g)$, $g\in O(f)$ のいずれも満たさない実数関数 $f$, $g$ が存在する。

(証明) まず (i) を示す。$f(x)=\cos x$, $g(x)=\sin x$ とする。このとき、いかなる実数 $k>0$, $x_0$ に対しても、実数 $x=|2\pi\lceil x_0 \rceil|\gt x_0$ が存在して $|f(x)|\gt k|g(x)|=0$ となるので $f\in O(g)$ を満たさない。また、いかなる $k>0$, $x_0$ に対しても、実数 $x=2\pi|\lceil x_0 \rceil|+\pi/2\gt x_0$ が存在して $|g(x)|\gt k|f(x)|=0$ となるので $g\in O(f)$ も満たさない。

以上から$O$-記法は『実数の大小関係』とは違って、反対称性も全順序性も持っていない。このことはオーダーを直感的に「大小のようだ」と捉えていると忘れかねないのでよくよく注意しなければならない。