関数のオーダーの上の順序と足し算

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:正確には,有限個を除いてすべて点でこの不等式が成り立つ.以下の不等号も同様.