関数のオーダーの上の順序と足し算 - 論理とか計算機とか数学とか

https://twitter.com/yoshihiro503/status/920979507053412353 から始まってなんか議論になっている感じだったのを見て，ちょっと考えてみた話．要するに，関数のオーダー全体の集合は自然な順序が入って join-semilattice になる．あと足し算もできる（実は join と一致する）．

以下詳細．

$\mathbb{R}_+$ は正の実数全体の集合として， $f: \mathbb{N} \to \mathbb{R}_+$ に対してそのオーダーを
$O(f) = \{g : \mathbb{N} \to \mathbb{R}_+ \mid \exists n_0, \exists c > 0, \forall n \ge n_0, g(n) \le cf(n)\}$
とする．オーダー全体の集合を $\mathbb{O}$ と書くことにする．この集合には包含関係で半順序が入る．

$\mathbb{O}$ は全順序ではない*1が，任意の二元は最小上界をもち，それは $O(f) \vee O(g) = O(\max(f, g)) = O(f+g)$ で与えられる（ $\max(f, g)$ は各点ごとのmax）．

証明: $O(f), O(g) \subseteq O(\max(f,g))$ は明らか．もし $O(f), O(g) \subseteq O(h)$ とすると， $f \le ch$ , $g \le ch$ *2となる $c$ がとれる（この $c$ は共通にとれる）．このとき $\max(f,g) \le ch$ であるから $\max(f,g) \in O(h)$ すなわち $O(\max(f,g)) \subseteq O(h)$ である． $O(\max(f,g)) = O(f+g)$ であることは $\max(f,g) \le f+g \le 2\max(f,g)$ だから明らか．

オーダーの和を $O(f) + O(g) = \{ h \mid \exists h_1 \in O(f), \exists h_2 \in O(g), h = f + g\}$ と定義すると， $O(f) + O(g) = O(f+g)$ が成り立つ．

証明: 左から右への包含関係は明らか．逆にもし $h \in O(f+g)$ ならば，ある $c$ が存在して $h \le c(f+g)$ となる．このとき $h = \frac{f}{f+g}h + \frac{g}{f+g}h$ と分解してやればそれぞれ $\frac{f}{f+g}h \le cf$ , $\frac{g}{f+g}h \le cg$ となるので $h \in O(f) + O(g)$ である．

*1:証明は簡単な演習問題

*2:正確には，有限個を除いてすべて点でこの不等式が成り立つ．以下の不等号も同様．