Θ-記法の同値性

前回は $O$-記法が実数関数同士の「ある意味での大小関係」として捉えられることを説明した。今回は $\Theta$-記法が実数関数同士の同値関係であること、つまり $\Theta$-記法が実数関数同士の「ある意味で等しい」ことを表す関係としてとらえられることを示す。そのことにより、シリーズ最初の記事で与えた「$f$ のオーダーと $g$ のオーダーは同程度である」という表現が実態に合っていることを確かめる。

オーダーの定義

ここでは以下の定義を使用する。

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

定義$f$, $g$ をそれぞれ実数関数とする。これらが $f\in O(g)$ と $g\in O(f)$ をともに満たすことを $f\in \Theta(g)$ と書く。

$\Theta$-記法について、シリーズ最初の記事で直感的に「$f$ のオーダーと $g$ のオーダーは同程度である」と表現した。この表現が実態と合っていることを確かめるために、$\Theta$-記法が同値関係であることを示す。

同値関係とは

同値関係は、前回扱った前順序と同様に、ある種のもの同士の関係の一種である。正確な定義は以下の通りだが、簡単に言うと同値関係は「ある意味で同じ・等しい」ことを表す関係である。

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

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

この定義をよく見ると、前順序の定義に対称律を追加しただけである。つまり、同値関係とは前順序のうち対称性を持つものと定義しても差し支えない。

同値関係がどのようなものかをとらえるために、いくつか例を考える。まず「$a$ と $b$ は等しい ($a=b$)」という関係を考えると、これは反射律も対称律も推移律も満たすので同値関係である。他にも『図形の合同』『図形の相似』『整数の合同 ($a\equiv b \mod n$)』『群同型』などもみな同値関係である。

では、同値関係に共通する性質は何かを直感的に説明できないかを考えると、ここで挙げたものはいずれも「ある意味で等しい」関係を表している。たとえば

  • 『図形の合同』は「2つの図形が形と大きさにおいて等しい」ことを表し
  • 『図形の相似』は「2つの図形が形において等しい」ことを表し
  • 『整数の合同 ($a\equiv b \mod n$)』は「2つの整数が $n$ で割った余りという点で等しい」ことを表す。

つまり同値関係とは2つのものが「ある意味で等しい」ことを表す関係になるのである。したがって、$\Theta$-記法も同値関係であることが示されれば、冒頭の「(オーダーが) 等しい」という表現が実態に合っていると言えるであろう。

$\Theta$-記法の同値性

では実際はどうかというと、$f\in\Theta(g)$ を2つの実数関数 $f$,$g$ の関係ととらえると、この関係も以下に示すように反射性、対称性、推移性を持つので同値関係である。

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

(証明) $O$-記法の反射性より $f\in O(f)$。したがって $\Theta$-記法の定義より $f\in\Theta(f)$。

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

(証明) $f\in\Theta(g)$ とすると、$\Theta$-記法の定義より $f\in O(g)$ かつ $g\in O(f)$。これは $g\in O(f)$ かつ $f\in O(g)$ ともいえるので $\Theta$-記法の定義より $g\in\Theta(f)$。

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

(証明) $f\in\Theta(g)$, $g\in\Theta(h)$ とすると、$\Theta$-記法の定義より $f\in O(g)$, $g\in O(f)$, $g\in O(h)$, $h\in O(g)$。このとき、$O$-記法の推移性より $f\in O(h)$, $h\in O(f)$。したがって $\Theta$-記法の定義より $f\in\Theta(h)$。

以上のことから $f\in\Theta(g)$ は同値関係であること、つまり2つの実数関数 $f$, $g$ が「ある意味で同じ」ことを表すことがわかった。この「ある意味」の部分を「オーダー」という語に置き換えることで、冒頭の「$f$ のオーダーと $g$ のオーダーが等しい」に行き着く。このことから、冒頭の表現にある程度の正当性が与えられるだろう。

同値関係についてよく知っている者に向けて補足すると、$\Theta(g)$ を $g$ の同値類と捉えると集合の記号としての $\in$ と良く合致する。集合の記号との整合性についてはここでは深く追究せず、シリーズ内の別の記事で詳しく説明することとする。