最大元と最小元
概要
最大元と最小元（greatest and least elements）とは、順序集合の部分集合 $A$ の元 $g$ で、$A$ のすべての元 $a$ について $a\leq g$ となるもの（最大元）と、すべての $a$ について $m\leq a$ となる元 $m$（最小元）である。存在すればそれぞれただ 1 つで、$\max A$、$\min A$ と書く。自分より大きい元が $A$ にないだけの極大元とは異なり、整除関係で順序づけた $\{2,3,4,6\}$ は極大元 $4,6$ をもつが最大元をもたない（全順序では極大元と最大元は一致し、空でない有限集合はつねに極大元をもつが、有限集合で極大元がただ 1 つでも無限集合ではそれが最大元とは限らない）。最大元は集合に属する点で上界・上限と異なり、開区間 $(0,1)$ は上限 $1$ をもつが最大元をもたない。
$6$ の正の約数 $\{1,2,3,6\}$ を「$a$ は $b$ を割り切る」という関係で比べると、$1$ はすべての元を割り切り、$6$ はすべての元で割り切れる。$1$ がこの集合の 最小元、$6$ が 最大元 である。ところが $\{2,3,4,6\}$ では事情が変わる。$4$ と $6$ はどちらも自分以外の倍数（真の倍数）を集合の中にもたないので「これより上はない」元（極大元）だが、$4$ は $6$ を割り切らず $6$ も $4$ を割り切らないので、すべての元より上にある元はない。同様に $2$ と $3$ は「これより下はない」元だが、すべての元を割り切る元はない。この集合には最大元も最小元もない。数の大小のように何でも比べられる順序では「一番上」は 1 つに決まるが、比べられない組がある順序では、「一番上」という素朴な言葉が、全体より上にある最大元と、自分より上がないだけの極大元とに分かれる。
定義
$(P,\leq)$ を順序集合（半順序集合）とする。すなわち $\leq$ は反射律・反対称律・推移律を満たす $P$ 上の二項関係である。$x< y$ は「$x\leq y$ かつ $x\neq y$」を表す。以下 $A$ は $P$ の部分集合とする（$A=P$ でもよい）。
$g\in A$ が $A$ の 最大元（greatest element）であるとは、任意の $a\in A$ について $a\leq g$ が成り立つことをいう。$m\in A$ が $A$ の 最小元（least element）であるとは、任意の $a\in A$ について $m\leq a$ が成り立つことをいう。
最大元・最小元は存在すればそれぞれただ 1 つであり（prop-gl-unique）、$\max A$、$\min A$ と書く。$A=P$ のときの最大元を $1$ や $\top$、最小元を $0$ や $\bot$ で表すことがある。
最大元・最小元はそれぞれ $A$ に属していなければならない。$A$ の外にあってすべての元より上にある元は、$A$ の上界であって最大元ではない。
$m\in A$ が $A$ の 極大元（maximal element）であるとは、$m< a$ となる $a\in A$ が存在しないこと、すなわち「$a\in A$ かつ $m\leq a$ ならば $a=m$」が成り立つことをいう。同様に、$a< m$ となる $a\in A$ が存在しないとき、$m$ を $A$ の 極小元（minimal element）という。
最大元は「$A$ のすべての元と比べて上にある」ことを求め、極大元は「$A$ に自分より上の元がない」ことしか求めない。極大元は $A$ の他の元と比較できなくてもよい。4 つの概念と、$A$ の外にあってよい上界・上限を並べると次のようになる（上界と上限の定義は 上限と下限 の記事による）。
| 概念 | $A$ に属するか | 条件 |
|---|---|---|
| 最大元 $g$ | 属する | すべての $a\in A$ で $a\leq g$ |
| 極大元 $m$ | 属する | $m< a$ となる $a\in A$ がない |
| 上界 $u$ | 属さなくてよい | すべての $a\in A$ で $a\leq u$ |
| 上限 $\sup A$ | 属さなくてよい | 上界全体の最小元 |
| 最小元 $m$ | 属する | すべての $a\in A$ で $m\leq a$ |
| 極小元 $m$ | 属する | $a< m$ となる $a\in A$ がない |
$A$ の最大元は、$A$ に制限した順序（順序集合 の記事の命題「部分集合への制限」）で考えた順序集合 $(A,\leq)$ の最大元と同じものである。条件が $A$ の元どうしの比較だけで書かれているからである。空集合 $\emptyset$ には元がないので、最大元・最小元・極大元・極小元はいずれも存在しない。
「最大元」と「極大元」の対比は、順序集合 の記事の定義「最大元・極大元・上界・上限」でも与えられている。本記事は、最大元・最小元とそれらが存在する条件を主題にする。
直感
最大元は「全員より強いチャンピオン」、極大元は「誰にも負けていない選手」にたとえられる（ここでは強さの比較が推移律と反対称律を満たすとする）。全員が互いに対戦した（全順序の）リーグなら、誰にも負けていない選手はチャンピオンそのものである。しかし対戦していない組があるトーナメントでは、誰にも負けていない選手が何人もいて、チャンピオンが決まらないことがある。順序が全順序でないときに最大元が存在しないことが多いのは、このためである。一方、選手が有限人しかいなければ、誰にも負けていない選手は少なくとも 1 人いる（thm-gl-finite-maximal）。選手が無限にいると、全員がより強い誰かに負けていることもありうる（自然数の大小には極大元がない）。
例と反例
正の整数の集合に、$a\leq b$ を「$a$ が $b$ を割り切る」（$a\mid b$）で定めた順序（順序集合 の記事の例「正の整数の整除関係」）を入れる。
- $\{1,2,3,6\}$ では、$1$ が最小元、$6$ が最大元である。極大元は $6$ だけ、極小元は $1$ だけである。
- $\{2,3,4,6\}$ では、極大元は $4$ と $6$、極小元は $2$ と $3$ であり、最大元も最小元もない。$4$ が最大元でないのは $6\mid4$ でないからであり、$2$ が最小元でないのは $2\mid3$ でないからである。
- $\{1,2,\dots,12\}$ では、$1$ が最小元である。極大元は $7,8,9,10,11,12$ の 6 個（どれも $2$ 倍が $12$ を超えるので、集合の中に自分の真の倍数がない）であり、最大元はない。
一般に $n$ の正の約数全体では、$1$ が最小元、$n$ が最大元である。
実数の通常の大小で考える。
- 閉区間 $[0,1]$ は最小元 $0$ と最大元 $1$ をもつ。
- $(0,1]$ は最大元 $1$ をもつが、最小元をもたない。$m\in(0,1]$ をとると $m/2\in(0,1]$ かつ $m/2< m$ だからである。下限 $\inf(0,1]=0$ は存在するが、$(0,1]$ に属さない。
- 開区間 $(0,1)$ は最大元も最小元ももたない。上限 $1$ と下限 $0$ はあるが、どちらも $(0,1)$ に属さない（上限と下限 の記事の例「開区間と閉区間」）。
- 自然数全体 $\mathbb{N}$ は最小元 $0$ をもち、最大元をもたない（$n< n+1$）。整数全体 $\mathbb{Z}$ は最大元も最小元ももたない。
$\mathbb{N}$ に、どの自然数とも比較できない新しい元 $z$ を 1 つ加えた集合 $P=\mathbb{N}\cup\{z\}$ を考える。順序は、$\mathbb{N}$ の中では通常の大小、$z$ については $z\leq z$ だけとする。これは順序である（反射律は明らか、反対称律と推移律は $\mathbb{N}$ の中の関係に帰着する）。
自然数 $n$ は $n< n+1$ なので極大元でない。$z$ は自分以外のどの元とも比較できないので極大元である。したがって $P$ の極大元は $z$ ただ 1 つである。しかし $0\leq z$ が成り立たないので、$z$ は最大元でない。$P$ には最大元がない。
この例は、「極大元がただ 1 つなら、それは最大元である」という含意を破っている。$P$ は無限集合であり、有限集合ではこの含意が成り立つ（cor-gl-finite-unique-maximal）。破れる理由は、$\mathbb{N}$ の側に極大元へ行き着かない無限の上昇列 $0<1<2<\cdots$ があることである。
性質
一意性と極大元との関係
$A\subset P$ の最大元は、存在すればただ 1 つである。最小元についても同じである。
$g,g'$ がともに $A$ の最大元であるとする。$g'$ は最大元で $g\in A$ なので $g\leq g'$、$g$ は最大元で $g'\in A$ なので $g'\leq g$ である。反対称律により $g=g'$ である。最小元については不等号の向きを逆にして同じ議論をすればよい。$\square$
一意性には反対称律が欠かせない。反対称律を要求しない前順序では、$a\leq b$ かつ $b\leq a$ となる相異なる $a,b$ がありうるので、「すべての元より上にある元」が複数ありうる。たとえば $\{a,b\}$ 上のすべての組を関係づけた前順序では、$a$ も $b$ も最大元の条件を満たす。
$A\subset P$ とする。
- $A$ の最大元は $A$ の極大元であり、しかも $A$ のただ 1 つの極大元である。
- $\leq$ が全順序なら、$A$ の極大元は $A$ の最大元である。
最小元と極小元についても同じことが成り立つ。
1：$g$ を最大元とする。$a\in A$ かつ $g\leq a$ なら、$a\leq g$ と反対称律から $a=g$ なので、$g$ は極大元である。$m$ を任意の極大元とすると、$g$ が最大元なので $m\leq g$ であり、$m$ の極大性から $g=m$ である。
2：$m$ を極大元とし、$a\in A$ をとる。全順序なので $a\leq m$ または $m\leq a$ であり、後者なら極大性から $a=m$ である。どちらの場合も $a\leq m$ なので、$m$ は最大元である。
最小元・極小元については、順序を逆にした双対順序（順序集合 の記事の命題「双対順序の構成」。$A$ の双対順序での最大元・極大元は、元の順序での最小元・極小元である）に 1・2 を当てはめればよい。$\square$
この命題は 順序集合 の記事の命題「最大元の一意性と極大元」と同じ内容である。1 の逆は成り立たない。極大元がただ 1 つでも最大元とは限らない（ex-gl-unique-maximal-infinite）。また全順序でなければ 2 は成り立たない（ex-gl-divisibility の $\{2,3,4,6\}$）。
有限集合の場合
$A\subset P$ を空でない有限集合とする。任意の $a\in A$ について、$a\leq m$ を満たす $A$ の極大元 $m$ が存在する。特に $A$ は極大元をもつ。同様に、任意の $a\in A$ について $m\leq a$ を満たす $A$ の極小元 $m$ が存在し、$A$ は極小元をもつ。
$a_0:=a$ とおく。$a_k\in A$ が定まったとき、$a_k$ が $A$ の極大元なら止め、そうでなければ $a_k< a_{k+1}$ となる $a_{k+1}\in A$ を 1 つ選ぶ。
こうして得られる列 $a_0< a_1< a_2<\cdots$ の項はすべて相異なる。実際 $i< j$ とすると、推移律により $a_i\leq a_{i+1}$ かつ $a_{i+1}\leq a_j$ である。もし $a_i=a_j$ なら $a_{i+1}\leq a_j=a_i$ となり、$a_i\leq a_{i+1}$ と反対称律から $a_i=a_{i+1}$ となって $a_i< a_{i+1}$ に反する。$A$ の元は有限個しかないので、相異なる項は高々 $|A|$ 個である。したがって列は $|A|$ 項以内で止まり、止まったときの項 $m:=a_k$ は $A$ の極大元である。推移律により $a=a_0\leq a_k=m$ である。
極小元については、双対順序（順序集合）に同じ議論を当てはめればよい。$\square$
列を作るときの「1 つ選ぶ」は有限回しか行わないので、選択公理は使っていない。有限性の仮定は外せない。$\mathbb{N}$ は空でないが極大元をもたない（ex-gl-intervals）。
$A\subset P$ を空でない有限集合とする。$A$ の極大元がただ 1 つ $g$ だけなら、$g$ は $A$ の最大元である。極小元についても同じである。
$a\in A$ を任意にとる。thm-gl-finite-maximal により $a\leq m$ を満たす極大元 $m$ があり、極大元は $g$ だけなので $m=g$、すなわち $a\leq g$ である。よって $g$ は最大元である。極小元についても同様である。$\square$
KT17 §6.2（p. 120）は、有限の半順序集合の図（Figure 6.13）を例に、ただ 1 つの極大元を「one」と呼んで $1$ で表し、ただ 1 つの極小元を「zero」と呼んで $0$ で表すことがあると述べている。cor-gl-finite-unique-maximal により、有限の場合この $1$ と $0$ はそれぞれ最大元と最小元である。無限の場合には ex-gl-unique-maximal-infinite のように一致しない。
全順序集合の空でない有限部分集合は、最大元と最小元をもつ。特に、有限個の実数 $x_1,\dots,x_n$（$n\ge1$）の中には最大のものと最小のものがあり、それらを $\max\{x_1,\dots,x_n\}$、$\min\{x_1,\dots,x_n\}$ と書く。
thm-gl-finite-maximal により極大元と極小元があり、prop-gl-greatest-maximal の 2 によりそれらは最大元と最小元である。$\square$
全順序 の記事の命題「有限な全順序集合の整列性」は、同じ事実を元の個数に関する帰納法で示している。
$D\subset P$ を空でない有限部分集合とし、任意の $a,b\in D$ について $a\leq c$ かつ $b\leq c$ となる $c\in D$ があるとする（$D$ が有向集合であるということ）。このとき $D$ は最大元をもつ。
$D=\{d_1,\dots,d_n\}$ とする。$k=1,\dots,n$ について、$d_1,\dots,d_k$ のすべてより上にある $u_k\in D$ を順に作る。$u_1:=d_1$ とする。$u_k$ ができたら、仮定により $u_k\leq c$ かつ $d_{k+1}\leq c$ となる $c\in D$ があるので $u_{k+1}:=c$ とする。$i\leq k$ なら推移律により $d_i\leq u_k\leq u_{k+1}$ なので、$u_{k+1}$ は $d_1,\dots,d_{k+1}$ のすべてより上にある。$u_n\in D$ は $D$ のすべての元より上にあるので、$D$ の最大元である。$\square$
上限・整列順序・Zornの補題
$P$ が最小元をもつことと、空集合 $\emptyset\subset P$ が $P$ の中で上限をもつことは同値であり、そのとき $\sup\emptyset=\min P$ である。同様に、$P$ が最大元をもつことと $\inf\emptyset$ が存在することは同値であり、そのとき $\inf\emptyset=\max P$ である。
$u\in P$ が $\emptyset$ の上界であるとは「任意の $a\in\emptyset$ について $a\leq u$」であり、$\emptyset$ には元がないのでこれは空虚な真として成り立つ。よって $\emptyset$ の上界全体は $P$ であり、$\sup\emptyset$ はその最小元、すなわち $P$ の最小元である。一方が存在すれば他方も存在して一致する。下限については順序を逆にすればよい。$\square$
上限と下限 の記事の注意「反例：空集合の上限」も同じことを述べ、$\mathbb{R}$ には最小元がないので $\emptyset$ が上限をもたないことを指摘している。空でない部分集合については、最大元と上限の関係が 上限と下限 の記事の命題「最大元と上限の関係」で示されている。$A$ が最大元をもてばそれは上限であり、逆に上限が存在して $A$ に属すればそれは最大元である。ex-gl-intervals の $(0,1)$ は、上限はあるが最大元はない例である。
全順序集合 $(P,\leq)$ の空でない任意の部分集合が最小元をもつとき、$\leq$ を整列順序という（整列順序 の記事の定義「整列順序の定義」）。$\mathbb{N}$ の通常の順序は整列順序であり（数学的帰納法 の記事の定理「自然数の整列原理」）、これが最小反例をとる論法（背理法）や帰納法の根拠になる。$\mathbb{Z}$ や $[0,1]$ の通常の順序は整列順序でない。$\mathbb{Z}$ 自身が最小元をもたず、$[0,1]$ は最小元 $0$ をもつが部分集合 $(0,1]$ が最小元をもたないからである（ex-gl-intervals）。整列順序では「すべての部分集合」について最小元を要求する点が、単に全体が最小元をもつことと違う。
無限集合では、thm-gl-finite-maximal と違って極大元が存在するとは限らない。極大元の存在を保証する代表的な原理がZornの補題である。空でない順序集合で、どの鎖（どの 2 元も比較できる部分集合）も上界をもつなら、極大元が存在する（Zornの補題 の記事の定理「鎖の上界から得られる極大元」。証明には選択公理を使う）。$\mathbb{N}$ では鎖 $\mathbb{N}$ 自身が上界をもたないので、この仮定が満たされない。Zorn の補題が保証するのは極大元であって最大元ではない。たとえば $\mathbb{R}^2$ の線形独立な部分集合全体を包含で順序づけると、$\{(1,0),(0,1)\}$ と $\{(1,0),(1,1)\}$ はどちらも極大元である（$\mathbb{R}^2$ には 3 個の元からなる線形独立な部分集合がない）。極大元が 2 つあるので、prop-gl-greatest-maximal の 1 によりこの順序集合に最大元はない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
