単調写像
概要
単調写像（monotone map）とは、半順序集合 $P,Q$ の間の写像 $f$ で、$x\le y$ ならば $f(x)\le f(y)$ となるもの、すなわち大小関係を保つ写像のことである。単調性は下集合の逆像が下集合になることと同値であり、整数の区間や有限半順序集合では隣り合う元の組だけで判定できる。単調写像は上限を一般には保たないが、$f(x)\le y\Leftrightarrow x\le g(y)$ を満たす Galois 接続（随伴）の左側の写像は、存在するすべての上限を保つ。有限で最小元をもつ半順序集合では単調な自己写像の最小不動点が反復で求まり、無限の場合の Knaster–Tarski の定理と完備束の特徴づけにつながる。
半順序集合のあいだの写像で、大小関係を保つものを単調写像という。半順序集合を対象とし単調写像を射とする圏 $\mathbf{Poset}$ は 半順序集合 の定義「単調写像と圏 $\mathbf{Poset}$」で導入され、恒等写像と合成についての基本事項もそこで示されている。ここでは、単調性の判定法、上限・下限との関係、単調写像の全体の順序、Galois 接続（順序の随伴）を述べ、最後に不動点の存在（Knaster–Tarskiの定理、完備束）へつなぐ。実数の区間上の単調増加関数はその特別な場合で、実数に特有の性質は 単調関数 が扱う。
定義
以下、$(P,\le_P)$、$(Q,\le_Q)$ は半順序集合とし、混乱のおそれがなければ添字を省いて $\le$ と書く。$x< y$ は $x\le y$ かつ $x\neq y$ を表す。
写像 $f\colon P\to Q$ について、次のように定める。
- $f$ が単調（monotone、order-preserving、isotone）であるとは、任意の $x,y\in P$ に対し $x\le y$ ならば $f(x)\le f(y)$ となることをいう。
- $f$ が反単調（antitone、order-reversing）であるとは、$x\le y$ ならば $f(y)\le f(x)$ となることをいう。
- $f$ が狭義単調（strictly monotone）であるとは、$x< y$ ならば $f(x)< f(y)$ となることをいう。
- $f$ が順序埋め込み（order embedding）であるとは、任意の $x,y\in P$ に対し $x\le y$ と $f(x)\le f(y)$ が同値であることをいう。
前順序集合（反対称律を仮定しないもの）の間の写像についても、1 と 2 を同じ言葉で定義する（前順序）。
$Q$ の順序を逆にした双対順序集合を $Q^{\mathrm{op}}$ と書くと、$f\colon P\to Q$ が反単調であることは、$f$ を $P\to Q^{\mathrm{op}}$ と見て単調であることと同じである。したがって反単調写像についての主張は、単調写像についての主張から双対をとって得られる。順序埋め込みで全射なものは順序同型である。$P,Q$ がともに実数の部分集合で通常の大小関係を入れたとき、単調写像は単調増加関数（広義）、狭義単調写像は狭義単調増加関数にほかならない。
$f\colon P\to Q$、$g\colon Q\to R$ を写像とする（$R$ も半順序集合）。
- $f,g$ がともに反単調なら $g\circ f$ は単調であり、一方が単調で他方が反単調なら $g\circ f$ は反単調である。
- 順序埋め込みは単射であり、狭義単調である。
- 単射な単調写像は狭義単調である。$P$ が全順序集合なら、逆に狭義単調写像は単射である。
1. $f,g$ がともに反単調とし、$x\le y$ とする。$f$ が反単調なので $f(y)\le f(x)$ であり、これに反単調な $g$ を施すと $g(f(x))\le g(f(y))$ となる。よって $g\circ f$ は単調である。$f$ が単調で $g$ が反単調なら、$f(x)\le f(y)$ から $g(f(y))\le g(f(x))$ となり、$g\circ f$ は反単調である。$f$ が反単調で $g$ が単調な場合も同様である。両方が単調な場合は 半順序集合 の命題「半順序集合と単調写像は圏をなす」の 2 である。
2. $f$ を順序埋め込みとし、$f(x)=f(y)$ とする。$f(x)\le f(y)$ と $f(y)\le f(x)$ がともに成り立つので、順序埋め込みの定義から $x\le y$ かつ $y\le x$ であり、反対称律から $x=y$ となる。よって $f$ は単射である。$x< y$ なら $f(x)\le f(y)$ であり、単射性から $f(x)\neq f(y)$ なので $f(x)< f(y)$ である。
3. $f$ を単射な単調写像とし、$x< y$ とすると、$f(x)\le f(y)$ かつ $f(x)\neq f(y)$ なので $f(x)< f(y)$ である。$P$ が全順序で $f$ が狭義単調なら、$x\neq y$ のとき $x< y$ か $y< x$ のどちらかが成り立ち、それぞれ $f(x)< f(y)$、$f(y)< f(x)$ を与えるので $f(x)\neq f(y)$ である。$\square$
全順序集合からの単射な単調写像は、さらに順序埋め込みになる（順序同型 の命題「全順序からの単調単射は順序を反映する」）。定義域に比較できない元があると、この結論は成り立つとは限らない（下の例「単調な全単射でも順序埋め込みとは限らない」）。
例
- 包含写像：半順序集合 $P$ の部分集合 $S$ に誘導順序を入れると、包含写像 $S\to P$ は順序埋め込みである。
- 像と逆像：写像 $\varphi\colon X\to Y$ に対し、$A\mapsto\varphi[A]$ は $(\mathcal{P}(X),\subseteq)$ から $(\mathcal{P}(Y),\subseteq)$ への単調写像であり、$B\mapsto\varphi^{-1}[B]$ は逆向きの単調写像である（部分集合）。$X=\{1,2\}$、$Y=\{0\}$ で $\varphi$ を定数写像とすると $\varphi[\{1\}]=\varphi[\{2\}]$ なので、像の写像は単射でなく、順序埋め込みでもない。
- 補集合：$A\mapsto X\setminus A$ は $\mathcal{P}(X)$ から自分自身への反単調な全単射であり、逆写像も同じ写像である。$\mathcal{P}(X)$ から双対 $\mathcal{P}(X)^{\mathrm{op}}$ への順序同型と見ることができる。
- 約数の個数：正の整数に整除関係 $m\mid n$ で順序を入れた半順序集合から、通常の大小関係の $\mathbb{N}$ への写像 $n\mapsto d(n)$（$n$ の正の約数の個数）を考える。$m\mid n$、$m\neq n$ なら $m$ の約数はすべて $n$ の約数で、$n$ 自身は $m$ の約数でないので $d(m)< d(n)$ である。よってこの写像は狭義単調だが、$d(2)=d(3)$ なので単射でも順序埋め込みでもない。
- 床関数：$x\mapsto\lfloor x\rfloor$ は $\mathbb{R}$ から $\mathbb{Z}$ への単調写像であり、単射でない。
$P=\{a,b\}$ に比較できる組が $a\le a$、$b\le b$ だけの順序（反鎖）を入れ、$Q=\{a,b\}$ に $a< b$ という全順序を入れる。恒等写像 $P\to Q$ は全単射で単調である（$P$ で成り立つ $x\le y$ は $x=y$ だけ）。しかし $Q$ では $a\le b$ なのに $P$ では $a\le b$ でないので、順序埋め込みではない。この例は「単調な全単射は順序同型である」という含意を破る。順序同型 の反例「順序を保つ全単射だけでは足りない」と同じ現象である。
単調性の判定
順序が少数の基本的な関係から生成されている場合には、その関係だけを確かめれば単調性がわかる。
隣り合う元で判定する
$I\subseteq\mathbb{Z}$ を整数の区間（$m,n\in I$、$m\le k\le n$ なら $k\in I$ を満たす部分集合。$\mathbb{N}$、$\mathbb{Z}$、$\{0,1,\ldots,N\}$ など）とし、通常の大小関係を入れる。写像 $f\colon I\to Q$ について、次は同値である。
- $f$ は単調である。
- $n,n+1\in I$ を満たすすべての $n$ について $f(n)\le f(n+1)$ である。
1 から 2 は、$n\le n+1$ に単調性を当てはめればよい。2 を仮定し、$m\le n$ を満たす $m,n\in I$ について $f(m)\le f(n)$ を $n-m$ に関する帰納法で示す。$n-m=0$ なら $m=n$ で、反射律から $f(m)\le f(n)$ である。$n-m=k+1$（$k\ge0$）とすると、$m\le n-1\le n$ と区間の条件から $n-1\in I$ であり、$(n-1)-m=k$ なので帰納法の仮定から $f(m)\le f(n-1)$ である。2 から $f(n-1)\le f(n)$ なので、推移律により $f(m)\le f(n)$ となる。$\square$
数列 $(a_n)$ が単調増加であることを $a_n\le a_{n+1}$ で確かめてよいのは、この命題による。有限半順序集合でも同じことが成り立つ。有限半順序集合では、$x\le y$ であることと、$x=y$ であるか被覆の列 $x=x_0\lessdot x_1\lessdot\cdots\lessdot x_n=y$ があることが同値である（半順序集合 の命題「有限半順序集合における被覆関係からの復元」）。したがって有限半順序集合からの写像は、$x\lessdot y$ のたびに $f(x)\le f(y)$ となれば（被覆の列に沿って推移律を繰り返して）単調である。Hasse 図の辺だけを調べればよい。
有理数全体 $\mathbb{Q}$ に通常の順序を入れると、$p< q$ なら $p< (p+q)/2< q$ なので、被覆関係 $p\lessdot q$ を満たす組は一つもない。したがって $f(x)=-x$ は「$x\lessdot y$ ならば $f(x)\le f(y)$」を空虚に満たすが、$0< 1$ で $f(0)=0> -1=f(1)$ なので単調でない。被覆関係から判定する方法は、有限性（あるいは $\mathbb{Z}$ の区間のように、順序が被覆の列から生成されること）を外すと成り立たない。
下集合による特徴づけ
部分集合 $D\subseteq P$ が下集合（down-set、lower set）であるとは、$y\in D$ かつ $x\le y$ ならば $x\in D$ となることをいう。双対に、$x\in U$ かつ $x\le y$ ならば $y\in U$ となる $U$ を上集合という。$q\in Q$ に対し ${\downarrow}q:=\{y\in Q\mid y\le q\}$ は下集合であり、$q$ が生成する単項下集合と呼ぶ。
写像 $f\colon P\to Q$ について、次の三条件は同値である。
- $f$ は単調である。
- $Q$ の任意の下集合 $D$ について、逆像 $f^{-1}[D]$ は $P$ の下集合である。
- 任意の $q\in Q$ について、$f^{-1}[{\downarrow}q]$ は $P$ の下集合である。
上集合についても同じ主張が成り立つ。
1 ⇒ 2. $D$ を $Q$ の下集合とし、$y\in f^{-1}[D]$、$x\le y$ とする。単調性から $f(x)\le f(y)$ であり、$f(y)\in D$ と $D$ が下集合であることから $f(x)\in D$、すなわち $x\in f^{-1}[D]$ である。
2 ⇒ 3. ${\downarrow}q$ は下集合だから明らかである。
3 ⇒ 1. $x\le y$ とし、$q:=f(y)$ とおく。反射律から $f(y)\le q$ なので $y\in f^{-1}[{\downarrow}q]$ である。3 よりこの集合は下集合なので $x\in f^{-1}[{\downarrow}q]$、すなわち $f(x)\le f(y)$ である。
上集合についても、${\downarrow}q$ の代わりに ${\uparrow}q:=\{y\mid q\le y\}$ を使い、$q:=f(x)$ として同じ議論をすればよい。$\square$
上集合全体は任意個の合併と共通部分で閉じているので位相（Alexandrov 位相）をなし、thm-mm-downset はこの位相について単調写像と連続写像が一致することを述べている。
上限・下限との関係
単調写像は順序を保つが、上限まで保つとは限らない。保たれるのは一方向の不等式だけである。
$f\colon P\to Q$ を単調写像、$S\subseteq P$ とする。
- $P$ における上限 $\bigvee S$ と、$Q$ における像の上限 $\bigvee f[S]$ がともに存在すれば、$\bigvee f[S]\le f\bigl(\bigvee S\bigr)$ である。
- 双対に、下限 $\bigwedge S$ と $\bigwedge f[S]$ がともに存在すれば、$f\bigl(\bigwedge S\bigr)\le\bigwedge f[S]$ である。
- $P,Q$ が束で、写像 $f\colon P\to Q$ がすべての $x,y$ について $f(x\vee y)=f(x)\vee f(y)$ を満たすなら、$f$ は単調である。
1. 各 $s\in S$ について $s\le\bigvee S$ なので、単調性から $f(s)\le f(\bigvee S)$ である。よって $f(\bigvee S)$ は $f[S]$ の上界であり、上限は最小の上界だから $\bigvee f[S]\le f(\bigvee S)$ である。2 は 1 の双対である。
3. $x\le y$ なら $x\vee y=y$ なので、$f(y)=f(x\vee y)=f(x)\vee f(y)$ である。右辺は $f(x)$ 以上なので $f(x)\le f(y)$ である。$\square$
$P=\mathcal{P}(\{a,b\})$ を包含で順序づけ、$Q=\{0< 1\}$ とする。$f(A)=1$（$A=\{a,b\}$ のとき）、$f(A)=0$（それ以外）と定めると、$\{a,b\}$ を含む集合は $\{a,b\}$ だけなので $f$ は単調である。$\mathcal{S}=\{\{a\},\{b\}\}$ に対し、$\bigvee\mathcal{S}=\{a,b\}$ だから $f(\bigvee\mathcal{S})=1$ だが、$\bigvee f[\mathcal{S}]=\bigvee\{0\}=0$ である。prop-mm-sup-inequality の不等式は等号にならない。
一方、次の節の Galois 接続の左側の写像は、存在する上限をすべて保つ（thm-mm-adjunction の 4）。
単調写像の全体の順序
$P$ から $Q$ への単調写像の全体を $\operatorname{Mon}(P,Q)$ と書く。$f,g\in\operatorname{Mon}(P,Q)$ について、すべての $x\in P$ で $f(x)\le g(x)$ となるとき $f\le g$ と定める。これは $\operatorname{Mon}(P,Q)$ 上の半順序であり、点ごとの順序という。
反射律・推移律・反対称律は、$Q$ の順序のそれぞれの性質を各点 $x$ で使えば確かめられる（反対称律では、すべての $x$ で $f(x)=g(x)$ となるので $f=g$）。
$Q$ が完備束なら、$\operatorname{Mon}(P,Q)$ は点ごとの順序に関して完備束である。単調写像の族 $(f_i)_{i\in I}$ の上限と下限は、点ごとの上限と下限
$$
\Bigl(\bigvee_{i\in I}f_i\Bigr)(x)=\bigvee_{i\in I}f_i(x),\qquad\Bigl(\bigwedge_{i\in I}f_i\Bigr)(x)=\bigwedge_{i\in I}f_i(x)
$$
で与えられる（$I=\emptyset$ のときは、それぞれ $Q$ の最小元・最大元への定数写像）。
$g(x):=\bigvee_{i\in I}f_i(x)$ とおく（$Q$ は完備束なので存在する）。まず $g$ が単調であることを示す。$x\le y$ とすると、各 $i$ について $f_i(x)\le f_i(y)\le g(y)$ なので、$g(y)$ は $\{f_i(x)\}_{i\in I}$ の上界であり、$g(x)\le g(y)$ となる。よって $g\in\operatorname{Mon}(P,Q)$ である。
各 $i$ と $x$ について $f_i(x)\le g(x)$ なので、$g$ は族の上界である。$h\in\operatorname{Mon}(P,Q)$ が族の上界なら、各 $x$ で $h(x)$ は $\{f_i(x)\}_{i\in I}$ の上界なので $g(x)\le h(x)$、すなわち $g\le h$ である。よって $g$ は族の上限である。下限についても、上の議論の不等号の向きを逆にすれば同様である。$I=\emptyset$ のとき $g$ は最小元への定数写像で、これは単調写像全体の最小元である。$\square$
$Q$ が完備束でなくても、点ごとの上限が各点で存在すれば同じ議論が通る。この定理は、完備束の上の単調写像を比べて、不動点の大小を論じるときの土台になる（Knaster–Tarskiの定理 の命題「点ごとの比較と最小不動点」）。
Galois 接続（順序の随伴）
単調写像 $f$ について「$f(x)\le y$ を満たす最大の $x$」が各 $y$ でとれる状況を、一つの同値で表すのが随伴である。
写像 $f\colon P\to Q$、$g\colon Q\to P$ の組 $(f,g)$ が随伴（adjunction）であるとは、任意の $x\in P$、$y\in Q$ について
$$
f(x)\le y\quad\Longleftrightarrow\quad x\le g(y)
$$
が成り立つことをいう。このとき $f$ を左随伴（下随伴）、$g$ を右随伴（上随伴）といい、$f\dashv g$ と書く。随伴は単調な Galois 接続とも呼ばれる。$P^{\mathrm{op}}$ と $Q$ の間の随伴、すなわち反単調な写像の組で $y\le f(x)\Leftrightarrow x\le g(y)$ を満たすものを Galois 接続と呼ぶ流儀もある（GvG23 Definition 1.14、p. 14）。
GvG23 は $f,g$ の単調性を定義に含めるが、次の定理の 1 のとおり単調性は同値の条件から従う。順序集合を圏と見れば随伴関手の特別な場合である（同記事の例「順序集合の随伴」）。
$(f,g)$ を $P$ と $Q$ の間の随伴とする。
- $f$ と $g$ はともに単調である。
- 任意の $x\in P$ について $x\le g(f(x))$、任意の $y\in Q$ について $f(g(y))\le y$ である。
- $f\circ g\circ f=f$、$g\circ f\circ g=g$ である。
- $S\subseteq P$ が $P$ で上限 $\bigvee S$ をもてば、$f[S]$ は $Q$ で上限をもち $\bigvee f[S]=f\bigl(\bigvee S\bigr)$ である。双対に、$g$ は $Q$ に存在する下限を保つ。
- 各 $y\in Q$ について、$g(y)$ は集合 $\{x\in P\mid f(x)\le y\}$ の最大元である。特に右随伴 $g$ は $f$ から一意に定まる。
2. 反射律 $f(x)\le f(x)$ に随伴の同値を（$y=f(x)$ として）当てはめると $x\le g(f(x))$ を得る。同様に $g(y)\le g(y)$ から $f(g(y))\le y$ を得る。
1. $x\le x'$ とする。2 から $x'\le g(f(x'))$ なので $x\le g(f(x'))$ であり、随伴の同値（$y=f(x')$）から $f(x)\le f(x')$ となる。$y\le y'$ とすると、2 から $f(g(y))\le y\le y'$ であり、随伴の同値から $g(y)\le g(y')$ となる。
3. 2 の $x\le g(f(x))$ に単調な $f$ を施すと $f(x)\le f(g(f(x)))$ である。一方、2 の後半を $y=f(x)$ に当てはめると $f(g(f(x)))\le f(x)$ である。反対称律から $f\circ g\circ f=f$ となる。$g\circ f\circ g=g$ も同様に $g(y)\le g(f(g(y)))$ と $g(f(g(y)))\le g(y)$ から従う。
4. $s:=\bigvee S$ とおく。各 $t\in S$ について $t\le s$ なので、1 から $f(t)\le f(s)$ であり、$f(s)$ は $f[S]$ の上界である。$y\in Q$ が $f[S]$ の上界なら、各 $t\in S$ について $f(t)\le y$、すなわち $t\le g(y)$ である。よって $g(y)$ は $S$ の上界であり、$s\le g(y)$、随伴の同値から $f(s)\le y$ となる。したがって $f(s)$ は $f[S]$ の最小の上界である。$S=\emptyset$ の場合も含まれ、$P$ に最小元 $\bot$ があれば $f(\bot)$ は $Q$ の最小元である。下限の主張は双対である。
5. 2 から $f(g(y))\le y$ なので $g(y)$ はこの集合に属する。$f(x)\le y$ なら随伴の同値から $x\le g(y)$ なので、$g(y)$ は最大元である。最大元は一意なので、$g$ は $f$ だけで決まる。$\square$
2 と 3 から、$c:=g\circ f\colon P\to P$ は単調で $x\le c(x)$、$c(c(x))=c(x)$ を満たす。このような写像を閉包作用素という。冪集合の上の閉包作用素は、共通部分で閉じた部分集合族と一対一に対応し、完備束を作る標準的な方法になる（完備束）。
- 像と逆像：写像 $\varphi\colon X\to Y$ について、$\varphi[A]\subseteq B$ と $A\subseteq\varphi^{-1}[B]$ は同値である。よって像をとる写像は逆像をとる写像の左随伴であり、thm-mm-adjunction の 4 から、像は任意個の合併を保ち、逆像は任意個の共通部分を保つ。逆像はさらに $\varphi_*(A):=\{y\in Y\mid\varphi^{-1}[\{y\}]\subseteq A\}$ の左随伴でもある。実際 $\varphi^{-1}[B]\subseteq A$ は「$B$ の各元のファイバーが $A$ に含まれる」こと、すなわち $B\subseteq\varphi_*(A)$ と同値である。したがって逆像は合併も保つ。
- 床関数と天井関数：包含 $\iota\colon\mathbb{Z}\to\mathbb{R}$ について、$n\le x\Leftrightarrow n\le\lfloor x\rfloor$ なので $\iota\dashv\lfloor\cdot\rfloor$、$\lceil x\rceil\le n\Leftrightarrow x\le n$ なので $\lceil\cdot\rceil\dashv\iota$ である（$\mathbb{R}$ を $\mathbb{Q}$ に替えた同じ例が GvG23 Example 1.15、p. 14 にある）。右随伴の床関数は下限を保つ。たとえば $S=\{1/n\mid n\ge1\}$ では $\inf S=0$ で、$\lfloor 1/n\rfloor$ の下限も $0$ である。しかし上限は保たない。$S=\{1-1/n\mid n\ge1\}$ では $\lfloor\sup S\rfloor=\lfloor1\rfloor=1$ だが、$\lfloor 1-1/n\rfloor=0$ なので像の上限は $0$ である。左随伴の天井関数では両者はともに $1$ である。
- 関係から作る Galois 接続：関係 $R\subseteq X\times Y$ について、$u(A):=\{y\mid\text{すべての }x\in A\text{ で }xRy\}$、$\ell(B):=\{x\mid\text{すべての }y\in B\text{ で }xRy\}$ と定めると、$B\subseteq u(A)\Leftrightarrow A\subseteq\ell(B)$ である（GvG23 Example 1.16、p. 14）。両辺とも「すべての $x\in A$、$y\in B$ で $xRy$」と言い換えられるからである。$u,\ell$ は反単調で、$\ell\circ u$ は $\mathcal{P}(X)$ の閉包作用素である。体とその自己同型群の間の Galois 対応や、多項式の集合とその共通零点の集合の対応は、この形をしている。
不動点への橋渡し
単調写像 $f\colon P\to P$ の不動点とは $f(p)=p$ となる $p$ である（不動点）。有限の場合は反復だけで不動点が得られる。
$P$ を最小元 $\bot$ をもつ有限半順序集合とし、$f\colon P\to P$ を単調写像とする。$x_0:=\bot$、$x_{n+1}:=f(x_n)$ と定めると、列 $(x_n)$ は単調増加であり、ある番号から先は一定値 $p$ をとる。$p$ は $f$ の不動点であり、$f(x)\le x$ を満たす任意の $x$ について $p\le x$ である。特に $p$ は最小の不動点である。
$\bot$ は最小元なので $x_0\le x_1$ である。$x_n\le x_{n+1}$ なら、単調性から $x_{n+1}=f(x_n)\le f(x_{n+1})=x_{n+2}$ である。よって帰納法により列は単調増加である。
すべての $n$ で $x_n\neq x_{n+1}$ だとすると、$x_0< x_1< x_2<\cdots$ となる。推移律から $m< n$ なら $x_m\le x_n$ であり、$x_m=x_n$ なら $x_m\le x_{m+1}\le x_n=x_m$ と反対称律から $x_m=x_{m+1}$ となって仮定に反する。したがって $x_n$ はすべて相異なり、$P$ が有限であることに反する。よってある $n$ で $x_n=x_{n+1}$ であり、そのとき $x_{n+2}=f(x_{n+1})=f(x_n)=x_{n+1}$ と続くので、列は $n$ から先 $p:=x_n$ で一定である。$f(p)=x_{n+1}=p$ なので $p$ は不動点である。
$f(x)\le x$ とする。$x_0=\bot\le x$ であり、$x_k\le x$ なら $x_{k+1}=f(x_k)\le f(x)\le x$ である。帰納法によりすべての $k$ で $x_k\le x$、特に $p\le x$ である。不動点 $q$ は $f(q)=q\le q$ を満たすので $p\le q$ であり、$p$ は最小の不動点である。$\square$
prop-mm-finite-fixpoint は束であることを使わない。たとえば $P=\{\bot,a,b\}$（$\bot< a$、$\bot< b$、$a$ と $b$ は比較できない）は $a,b$ の上限をもたないので束でないが、その上の単調写像はすべて不動点をもつ。
無限の場合には、反復が止まるとは限らない。そこで使うのが上限であり、完備束（任意の部分集合が上限と下限をもつ半順序集合）の上の単調写像は最小不動点と最大不動点をもつ。これが Knaster–Tarskiの定理 の定理「Knaster–Tarski の定理」（Tar55 Theorem 1、pp. 286–287）である。逆に、束であって、その上のすべての単調写像が不動点をもつものは完備束である（Dav55 Theorem 2、p. 313）。この逆の主張と証明は 完備束 にある。上の $P=\{\bot,a,b\}$ は、束であるという仮定を外すとこの逆が成り立たないことを示している。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 単調性 | $\{0< 1\}$ 上の $x\mapsto 1-x$（反単調） | 有限で最小元をもつときの不動点の存在 |
| 最小元をもつこと | 二元の反鎖 $\{a,b\}$ 上の $a\leftrightarrow b$ の入れ替え（単調） | 有限のときの不動点の存在 |
| 有限性 | $\mathbb{N}$ 上の $n\mapsto n+1$（最小元 $0$ をもつ） | 不動点の存在 |
| 順序が被覆の列から生成されること | $\mathbb{Q}$ 上の $x\mapsto -x$ | 被覆関係だけによる単調性の判定 |
| 定義域が全順序であること | 反鎖から二元の鎖への恒等写像 | 単射な単調写像が順序埋め込みであること |
| 随伴の左側であること | 床関数と $\{1-1/n\}$ の上限 | 上限の保存 |
補足
- 単調写像の定義は BS12 I §2 Definition 2.2（p. 8）。同じ頁の Theorem 2.3 は、束の間の全単射が束の同型であることと、それと逆写像がともに単調であることの同値を示す。
- 単射な単調写像と順序埋め込みの違いは GvG23 Exercise 1.1.4（p. 15）、随伴の基本性質（thm-mm-adjunction の 2〜4 にあたる主張）は同書 Exercise 1.1.8（p. 16）に演習として挙げられている。この記事ではそれらを記事の記法で証明した。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
