上界

同義語：upper bound

概要

前提知識: 順序集合, 集合, 上限と下限

上界とは

上界（upper bound）は、順序集合の部分集合に対して、そのすべての元より上にある元である。たとえば実数の通常の大小関係では、集合 $(0,1)$ の上界は $1$ 以上の実数すべてである。$1$ だけが上界なのではない。また、$1$ は元の集合に属さない。上界は「この値を超えない」という制約であり、その制約を満たす元は一般に何個もある。
上界を語るときは、どの順序集合の中で上界を探すかを明らかにする必要がある。同じ部分集合でも、周囲の順序集合を変えると、上界の有無や最小の上界の有無が変わる。実数で習う上からの評価と、集合の包含関係や整数の割り切り関係で使う上界は、同じ定義に従う。以下では順序の性質から始め、計算と応用でこの共通点を確かめる。

定義と最初の見分け方

$(P,\le)$ を順序集合、$A\subseteq P$ とする。$u\in P$ が $A$ の上界であるとは、
$$ \forall a\in A,\qquad a\le u $$
が成り立つことである。上界はまず $P$ の元であり、$A$ の元であるとは限らない。上界全体を
$$ \operatorname{UB}_P(A)=\{u\in P:\forall a\in A,\ a\le u\} $$
と書く。$\operatorname{UB}_P(A)$ が空でないとき、$A$ は $P$ の中で上に有界という。表記の添字 $P$ は、周囲の順序集合を確認したいときに付ける。順序が明らかなときは $\operatorname{UB}(A)$ と略してよい。順序を逆にして $u\le a$ をすべての $a\in A$ に要求すると、下界になる。EoMPosetの「upper cone」とEoMZornの定義がこの一般形に対応する。
この定義には二つの量化がある。「$A$ の各元に対して」と「候補 $u$ は $P$ から選ぶ」である。$A=\{2,3\}\subseteq\mathbb R$ なら、$3$ は上界で、$2$ は上界ではない。$10$ も上界である。上界かどうかを調べるには、一つの元を選んで全要素との比較を確かめる。最も小さい候補を最初から探す必要はない。
上界があることは、最大元があることより弱い。最大元は $A$ の元で、なおかつ $A$ の上界である。また、上界の中に最小の元があればそれが上限である。上界、最大元、上限は次のように役割が違う。

対象	属する場所	要求
上界 $u$	$P$	すべての $a\in A$ に $a\le u$
最大元 $m$	$A$	すべての $a\in A$ に $a\le m$
上限 $s$	$\operatorname{UB}_P(A)$	すべての上界 $u$ に $s\le u$

上限の存在は上界の存在から自動的には従わない。上限の性質そのものや実数の完備性は上限と下限で詳しく扱う。この記事では、上界の集まりを使うと何が言えるかに重点を置く。

上界全体の集合

上界の集合は、元の集合に対して逆向きに変化する。$A$ に条件となる元を足せば、上界の候補は減るか、変わらない。これを集合として書くと次の命題になる。EoMPosetにも上方錐の基本性質として掲載されている。

上界の集合の三つの性質

上界の集合の三つの性質。 $A,B\subseteq P$ とする。

$A\subseteq B$ なら $\operatorname{UB}_P(B)\subseteq\operatorname{UB}_P(A)$。
$\operatorname{UB}_P(A\cup B)=\operatorname{UB}_P(A)\cap\operatorname{UB}_P(B)$。
$u\in\operatorname{UB}_P(A)$ かつ $u\le v$ なら $v\in\operatorname{UB}_P(A)$。

上界の集合の三つの性質

第1の主張では、$u\in\operatorname{UB}_P(B)$ を取る。$A$ の各元は $B$ の元なので、すべて $u$ 以下である。したがって $u\in\operatorname{UB}_P(A)$。第2の主張では、$u$ が $A\cup B$ の各元より上にあることと、$A$ の各元および $B$ の各元より上にあることは同値である。第3の主張では、任意の $a\in A$ に対して $a\le u\le v$ と推移律を用いる。ゆえに $v$ も上界である。∎

第3の性質を、$\operatorname{UB}_P(A)$ は上方に閉じているという。ただし、ここでの「閉じている」は順序についての性質で、位相的に閉集合であるという意味ではない。たとえば部分順序では、ある上界から「上」に進める方向が複数あり、上界全体は一本の区間のようには見えない。
空集合では、すべての $a\in\emptyset$ について $a\le u$ という条件は反例を持たない。したがって
$$ \operatorname{UB}_P(\emptyset)=P $$
である。$P$ が空でなければ空集合は上に有界だが、空集合の上限が存在するかは $P$ に最小元があるかに依存する。$P=\mathbb R$ では $\operatorname{UB}_{\mathbb R}(\emptyset)=\mathbb R$ に最小元はない。$P=\mathcal P(X)$ を包含順序で見ると、$\emptyset$ が $P$ の最小元なので、空な族の上限は空集合である。空集合に関する計算を、非空集合に対する実数の上限性質と混同しない。

実数と有理数での上界

実数の通常の順序で $A=(0,1)$ とすると、$u\ge1$ はすべての $a\in A$ 以上である。一方、$u<1$ なら $\max(0,u)< a<1$ を満たす $a$ を選べるので $u$ は上界ではない。従って $\operatorname{UB}_{\mathbb R}(A)=[1,\infty)$。この集合の最小元 $1$ が上限であるが、$1\notin A$ なので最大元はない。閉区間 $[0,1]$ に替えると上界の集合は同じで、今度は $1$ が最大元でもある。上界を求める操作は元の集合の端点を含むかどうかだけでは決まらない。EoMUBは実数の上下界と、開区間・閉区間で上限が集合に属するかという違いを説明している。

上界はあるが上限がない有理数集合

上界はあるが上限がない有理数集合。 $A=\{q\in\mathbb Q:q>0,\ q^2<2\}$ を $\mathbb Q$ の通常の順序で考える。$2$ は上界なので $A$ は $\mathbb Q$ の中で上に有界である。しかし最小の有理数上界はない。実数の中で見れば上限は $\sqrt2$ であり、$\sqrt2\notin\mathbb Q$ だからである。$\mathbb Q$ の上界 $u$ は $u>\sqrt2$ を満たし、$\sqrt2< v< u$ を満たす有理数 $v$ を選べば $v$ も上界となる。周囲を $\mathbb R$ に替えれば $\sqrt2$ が上限になる。

ここで有理数 $A$ の定義に $q>0$ が必要である。単に $q^2<2$ と書いても上限は同じだが、正の平方根に近づく側を明示している。上界の有無を示すには具体的な一つの上界で十分で、最小性がないことには上界をさらに小さくできることを示す。この二段階を区別すると、上限の存在を不用意に仮定せずに済む。
実数上の数列 $(a_n)$ が「上に有界」といわれるときは、値の集合 $\{a_n:n\in\mathbb N\}$ が上に有界であるという意味である。つまり、すべての $n$ に共通の $M\in\mathbb R$ があって $a_n\le M$ となる。$n$ ごとに異なる $M_n$ を選べるだけでは条件を満たさない。たとえば $a_n=n$ は各項について $a_n\le n$ だが、一つの実数で全項を押さえることはできない。EoMUBは関数や数列の上限を値の集合の上限として扱っている。

部分順序では何が変わるか

実数は任意の二元を比較できるが、一般の順序集合では比較不能な元がある。上界は、そのような複数の元をまとめて上から押さえる共通の元である。上界が複数ある場合に、その中の「極小なもの」があっても「最小のもの」があるとは限らない。

割り切りの順序

割り切りの順序。 正の整数で $a\le b$ を「$a$ は $b$ を割り切る」と定め、$A=\{2,3\}$ とする。$A$ の上界は $2$ と $3$ の公倍数、すなわち $6$ の正の倍数である。$6$ はすべての上界を割り切るので、この順序での上限である。しかし $6\notin A$ だから $A$ の最大元ではない。$2$ と $3$ は $A$ の中で互いに比較不能で、両方とも極大元である。

次に周囲を $P=\{2,3,12,18\}$ に制限し、同じ割り切り関係を使う。$A=\{2,3\}$ の $P$ 内の上界は $12$ と $18$ である。$12$ と $18$ は互いを割り切らないので、どちらも上界集合の極小元だが、最小元はない。従って $A$ は $P$ で上に有界でも上限を持たない。正の整数全体では $6$ が上限だったのに、$P$ から $6$ を除くと上限が消えた。同じ $A$ と同じ種類の順序でも、周囲の集合が重要な理由である。
この例から、上界が存在する、極小な上界が存在する、最小の上界が存在するは別の主張だと分かる。全順序なら二つの極小な上界は比較できるため同じ元でなければならないが、部分順序では複数の極小な上界があり得る。逆に、上限が存在すれば上界全体の最小元として一意である。

最大元と上界

最大元と上界。 $m\in A$ が $A$ の最大元であることと、$m\in\operatorname{UB}_P(A)$ であることは同値である。最大元が存在すれば、それは $A$ の上限でもある。

最大元と上界

最大元の定義は、$m\in A$ かつすべての $a\in A$ について $a\le m$ というものであり、後半が上界の定義である。さらに $m$ は $A$ の元なので、任意の上界 $u$ に対して $m\le u$ となる。ゆえに $m$ は上界集合の最小元である。∎

極大元は「その元より真に上にある $A$ の元がない」というだけで、ほかの $A$ の元すべてより上にあるとは言わない。先ほどの $\{2,3\}$ はその違いを示す。なお全順序の部分集合では極大元があれば最大元である。任意の $a$ と極大元 $m$ は比較でき、もし $m< a$ なら極大性に反するから $a\le m$ となる。

包含順序と共通の上界

集合 $X$ の部分集合全体 $\mathcal P(X)$ を、包含関係 $\subseteq$ で順序づける。$\mathcal A\subseteq\mathcal P(X)$ は部分集合からなる族である。このとき $U\subseteq X$ が $\mathcal A$ の上界であるとは、族に属するどの $S$ についても $S\subseteq U$ となることだ。つまり $U$ は族の各集合をすべて含む。数の大小よりも、「共通の入れ物」と考えると直観的である。

包含順序での上界と和集合

包含順序での上界と和集合。 $\mathcal P(X)$ で $\mathcal A$ の上界は $\bigcup_{S\in\mathcal A}S$ を含む集合にちょうど一致する。したがって $\bigcup_{S\in\mathcal A}S$ が $\mathcal A$ の上限である。

包含順序での上界と和集合

$U$ が上界なら、各 $S\in\mathcal A$ は $U$ に含まれる。和集合の任意の元 $x$ はある $S$ に属するので $x\in U$ であり、$\bigcup_{S\in\mathcal A}S\subseteq U$ である。逆にこの包含があれば、各 $S$ は和集合に含まれるから $S\subseteq U$ となり、$U$ は上界である。和集合自身も各 $S$ を含むため上界であり、どの上界にも含まれるので最小の上界である。∎

$\mathcal A=\emptyset$ なら和集合は $\emptyset$ で、$\mathcal P(X)$ の最小元である。数の集合の上限を求めるときには実数の完備性が関わるが、包含順序の冪集合では任意の族の和集合が使える。この違いは、順序集合によって上限を作る仕組みが違うことを示す。とはいえ、この節でまず調べたのは上界が何かであり、和集合はその全体の中から選ばれる特別な元である。
順序集合の一部 $P\subseteq\mathcal P(X)$ だけを許すと、和集合が $P$ に属するとは限らない。たとえば $P$ を $\mathbb N$ の有限部分集合全体とし、$\mathcal A=\{\{1,\ldots,n\}:n\ge1\}$ とする。各 $n$ について $\{1,\ldots,n\}\in P$ だが、これらすべてを含む有限集合はない。従って $\mathcal A$ は $P$ の中では上界を持たない。周囲を $\mathcal P(\mathbb N)$ へ広げれば $\mathbb N$ が上限となる。この例では上界の「候補が属する場所」を変えただけで結論が変わった。

各点で比較する関数

集合 $D$ 上の実数値関数を、$f\le g$ がすべての $x\in D$ で $f(x)\le g(x)$ を意味するように順序づける。これは点ごとの順序である。関数族 $\mathcal F$ の上界となる関数 $g$ は、どの $f\in\mathcal F$ とどの点 $x\in D$ に対しても $f(x)\le g(x)$ を満たす。一つの点だけで優劣が決まるわけではない。EoMPosetも関数の点ごとの順序を順序集合の例に挙げている。
たとえば $D=[0,1]$ 上で $f_n(x)=x^n$（$n\ge1$）とする。定数関数 $g(x)=1$ はすべての $f_n$ の上界である。しかし $g(x)=x$ も上界であり、こちらの方が点ごとに小さい。実際 $0\le x\le1$ なら $x^n\le x$ なので $x$ は上界で、族の中に $f_1(x)=x$ があるから、どの上界 $h$ にも $x=f_1(x)\le h(x)$ が成り立つ。ゆえにこの関数族の上限は $x$ という関数である。ここでは関数の「値の上限」を各点で求めた結果が許された関数空間に属している。
一方、上界を探す関数空間に連続性や可積分性を課すと、点ごとの上限がその空間から外れることがある。たとえば $D=[-1,1]$ で $f_n(x)=\min(1,\max(0,nx))$ と置くと、各 $f_n$ は連続だが、$n$ ごとに点で上限を取った関数は $x\le0$ で $0$、$x>0$ で $1$ となり、$0$ で不連続である。この族には定数関数 $1$ など連続な上界があるが、点ごとの上限そのものは連続関数ではない。従って、連続関数全体の順序で上限を論じるときは、単に各点で上限を取った式を答えとしてよいとは限らない。

点ごとの上限の不連続性

この例で各 $f_n$ が連続であることは、$x\mapsto nx$、$\max(0,\cdot)$、$\min(1,\cdot)$ の連続性から分かる。$x\le0$ ではすべての $f_n(x)$ は $0$ である。$x>0$ では十分大きい $n$ を取ると $nx\ge1$ なので $f_n(x)=1$ となる。従って点ごとの上限の値は述べたとおりで、$0$ における右極限が $1$、値が $0$ だから不連続である。∎

関数について「上に有界」というとき、関数の値域が実数の上界を持つという意味と、関数をある関数空間の順序の元と見て関数族の上界を探す意味がある。一つの関数 $f$ が値として上に有界なら、ある定数 $M$ について $f(x)\le M$ が全点で成り立つ。そのとき定数関数 $M$ が、点ごとの順序で一元集合 $\{f\}$ の上界になる。文脈の対象が「値の集合」か「関数族」かを見て読み分ける。

鎖に上界があるという条件

順序集合 $P$ の鎖とは、その中の任意の二元が比較できる部分集合である。Zorn の補題は、非空の $P$ で「すべての鎖が $P$ 内に上界を持つ」なら、$P$ に極大元があると述べる。EoMZornの定式化もこの形である。ここでいう鎖の上界は $P$ の元であればよく、鎖に属する必要はない。また、空な鎖にも上界が必要だが、$P$ が非空ならその条件は満たされる。
鎖の任意の二元に共通の上界があることと、鎖全体に一つの上界があることも異なる。前節の有限部分集合の例では、各二元 $\{1,\ldots,m\}$ と $\{1,\ldots,n\}$ のうち大きい方が二元の上界になる。しかし鎖全体を押さえる有限集合はない。無限個の条件を同時に満たす元が必要になるからである。このため、Zorn の補題の仮定は二元ごとの上界だけでは置き換えられない。
「任意の二元が集合自身の中に上界を持つ」は有向集合の条件である。$\mathbb N$ は通常の順序で有向であり、任意の二元 $m,n$ は $\max(m,n)$ 以下に収まる。しかし $\mathbb N$ 全体には $\mathbb N$ の中の上界がない。有向であることから集合全体の上界は出ない。これは、局所的な有限個の条件と全体の条件を分けるよい例である。

極大元と最大元の違い

極大元と最大元の違い。 $P=\{p,q\}$ に等号以外の比較がない順序を入れる。鎖は空集合または一元集合だけで、いずれも $P$ 内に上界を持つ。Zorn の補題の結論どおり $p$ と $q$ は極大元である。しかし $P$ 全体の上界は $P$ 内に存在せず、最大元もない。従って「すべての鎖に上界がある」という仮定から「$P$ 全体に上界がある」や「最大元がある」と読み替えてはいけない。

Zorn の補題の証明には選択公理と同等の原理が関わる。ここでは補題を上界の使い方の例として参照した。証明や選択公理との関係はZornの補題で扱う。本文で必要なのは、各鎖の上界をどこに作るのかという仮定の読み方である。

評価・推定で使うとき

上界の目的は、元の集合を一つの値や構造で一括して押さえることにある。たとえば実数値関数 $f$ について $f(x)\le M$ を全点で示せば、$M$ は値域の上界である。これは最適な評価とは限らない。$M=10$ が上界だと分かっても、$M=2$ が上界でないとは言えない。さらに最小の上界を論じるには、候補より小さい値がなぜ上界でないかを示す必要がある。
誤差評価でも、誤差 $e_n$ の集合に対して $e_n\le M$ と書く場合と、絶対値の集合に対して $|e_n|\le M$ と書く場合では内容が違う。前者は大きな負の誤差を許すが、後者は両側から押さえる。上界という語だけでは何の集合に対する上界かが決まらない。集合と順序を明示すれば、式の意味を検査しやすくなる。
別の順序に移すと「上にある」の意味も変わる。包含順序の上界は各集合を含む集合であり、割り切り順序の上界は公倍数である。実数の大小だけを思い浮かべると、この二つで条件の向きを取り違えやすい。定義の $a\le u$ に具体的な順序の意味を代入し、各 $a$ に対して成立するかを確かめるのが確実である。