ホーム > 記事 > 数学 > シリーズ: ランダウのオーダー記法

記事

シリーズ: ランダウのオーダー記法

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

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

Θ-記法の同値性

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

O-記法の前順序性

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