順序同型

同義語：順序同型写像order isomorphism

概要

順序同型（order isomorphism）とは、二つの順序集合の間の全単射で、その写像と逆写像がともに順序を保つもののことである。同値に、$x\le_Py$ と $f(x)\le_Qf(y)$ が常に同値となる全単射である。順序同型は元の名前を除いて同じ順序構造を持つことを表し、最大元・最小元や元の間に別の元が存在するかどうかなどを保つ。有限全順序集合は要素数が等しいとき、またそのときに限り順序同型だが、無限集合では濃度が同じでも順序型が異なることがある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 順序集合, 単調写像, 全単射

定義

二つの順序集合が、元の名前を除いて同じ並び方をしていることを表すのが順序同型である。以下では $(P,\le_P)$ と $(Q,\le_Q)$ を順序集合とする。

順序同型

写像 $f\colon P\to Q$ が順序同型写像（order isomorphism）であるとは、次の二条件を満たすことをいう。

  1. $f$ は全単射である。
  2. $f$ と逆写像 $f^{-1}\colon Q\to P$ はともに順序を保つ。すなわち
    $$ x\le_Py\Longrightarrow f(x)\le_Qf(y) $$
    および
    $$ u\le_Qv\Longrightarrow f^{-1}(u)\le_Pf^{-1}(v) $$
    が成り立つ。
    順序同型写像 $P\to Q$ が存在するとき、$P$ と $Q$ は順序同型であるといい、$P\cong Q$ と書く。

順序を保つ全単射であることだけでは、一般の半順序集合の間の順序同型を保証しない。逆写像も順序を保つという条件が、比較不可能な元の情報を失わないことを保証する。

順序同型の同値な特徴付け

写像 $f\colon P\to Q$ について、次は同値である。

  1. $f$ は順序同型写像である。
  2. $f$ は全単射であり、すべての $x,y\in P$ に対して
    $$ x\le_Py\quad\Longleftrightarrow\quad f(x)\le_Qf(y) $$
    が成り立つ。
証明

1を仮定する。$f$ は順序を保つので、$x\le_Py$ ならば $f(x)\le_Qf(y)$ である。逆に $f(x)\le_Qf(y)$ ならば、$f^{-1}$ が順序を保つことから
$$ x=f^{-1}(f(x))\le_Pf^{-1}(f(y))=y $$
を得る。従って2が成り立つ。
2を仮定する。右向きの含意から $f$ は順序を保つ。$u,v\in Q$ が $u\le_Qv$ を満たすとする。$f$ は全単射なので $u=f(x)$、$v=f(y)$ となる $x,y\in P$ が存在する。2の左向きの含意から $x\le_Py$、すなわち
$$ f^{-1}(u)\le_Pf^{-1}(v) $$
である。従って $f^{-1}$ も順序を保ち、$f$ は順序同型写像である。

基本性質

恒等写像・逆写像・合成

順序同型写像について次が成り立つ。

  1. 恒等写像 $\operatorname{id}_P\colon P\to P$ は順序同型写像である。
  2. $f\colon P\to Q$ が順序同型写像ならば $f^{-1}\colon Q\to P$ も順序同型写像である。
  3. $f\colon P\to Q$ と $g\colon Q\to R$ が順序同型写像ならば $g\circ f\colon P\to R$ も順序同型写像である。
    従って、順序集合の間の「順序同型である」という関係は同値関係である。
証明

恒等写像は全単射であり、それ自身と逆写像が同じ恒等写像なので順序を保つ。従って1が成り立つ。
$f$ が順序同型なら、$f^{-1}$ は全単射である。定義から $f^{-1}$ は順序を保ち、その逆写像 $f$ も順序を保つので2が成り立つ。
$f,g$ が順序同型なら、$g\circ f$ は全単射である。$f$ と $g$ は順序を保つので、その合成 $g\circ f$ も順序を保つ。また
$$ (g\circ f)^{-1}=f^{-1}\circ g^{-1} $$
であり、$g^{-1}$ と $f^{-1}$ も順序を保つので、この合成も順序を保つ。従って3が成り立つ。1、2、3はそれぞれ順序同型関係の反射性、対称性、推移性を与える。

順序同型は、順序関係だけで記述される性質を両方向に移す。以下では最大元・最小元の保存を証明し、後の反例では「直後の元」の保存を用いる。

最大元・最小元の保存

$f\colon P\to Q$ を順序同型写像とする。$m\in P$ が $P$ の最大元ならば $f(m)$ は $Q$ の最大元である。最小元についても同じことが成り立つ。

証明

$y\in Q$ を任意に取る。$f$ は全射なので $y=f(x)$ となる $x\in P$ が存在する。$m$ は最大元だから $x\le_Pm$ である。$f$ は順序を保つので
$$ y=f(x)\le_Qf(m) $$
となる。従って $f(m)$ は $Q$ の最大元である。最小元の場合は不等号の向きを逆にした同じ議論で示される。

有限全順序集合の分類

$P,Q$ を有限な全順序集合とする。このとき
$$ P\cong Q\quad\Longleftrightarrow\quad |P|=|Q| $$
である。

証明

順序同型写像は全単射なので、$P\cong Q$ ならば $|P|=|Q|$ である。
逆に $|P|=|Q|=n$ とする。$n=0$ ならば空写像が順序同型を与える。$n>0$ とする。まず、空でない有限全順序集合が最小元を持つことを要素数に関する帰納法で示せる。要素が一つなら明らかである。$r+1$ 個のとき、一つの元 $a$ を除いた $r$ 個の集合の最小元を $b$ とする。全順序性により $a\le b$ または $b\le a$ であり、前者なら $a$、後者なら $b$ が全体の最小元である。
従って、最小元を取り除く操作を繰り返すことにより
$$ p_1<_Pp_2<_P\cdots<_Pp_n, \qquad q_1<_Qq_2<_Q\cdots<_Qq_n $$
と全要素を順番にただ一通り並べられる。$f(p_i):=q_i$ と定めれば $f$ は全単射である。また任意の $i,j$ に対して
$$ p_i\le_Pp_j \quad\Longleftrightarrow\quad i\le j \quad\Longleftrightarrow\quad q_i\le_Qq_j $$
である。従って順序同型の特徴付けにより $f$ は順序同型写像である。

例

自然数と非負偶数

$\mathbb{N}=\{0,1,2,\ldots\}$ と非負偶数全体 $E=\{0,2,4,\ldots\}$ に通常の大小関係を入れる。写像
$$ f\colon\mathbb{N}\to E,\qquad f(n)=2n $$
は全単射であり、
$$ n\le m\quad\Longleftrightarrow\quad 2n\le2m $$
を満たす。従って $f$ は順序同型であり、$\mathbb{N}\cong E$ である。無限順序集合は真部分集合と順序同型になり得る。

べき集合の順序同型

全単射 $h\colon X\to Y$ に対し
$$ \mathcal{P}(X)\to\mathcal{P}(Y),\qquad A\mapsto h(A) $$
は包含関係で順序付けたべき集合の間の順序同型である。実際、$A\subseteq B$ と $h(A)\subseteq h(B)$ は同値であり、逆写像は $C\mapsto h^{-1}(C)$ である。

積順序

$f\colon P\to P'$ と $g\colon Q\to Q'$ が順序同型ならば、
$$ (x,y)\mapsto(f(x),g(y)) $$
は積順序を入れた $P\times Q$ と $P'\times Q'$ の間の順序同型である。これは
$$ (x,y)\le(x',y') \quad\Longleftrightarrow\quad x\le_Px'\text{ かつ }y\le_Qy' $$
という積順序の定義と、$f,g$ が両方向に順序を保つことから従う。

反例

順序を保つ全単射だけでは足りない

$P=\{a,b\}$ に $a,b$ が比較不可能な離散順序を入れ、$Q=\{u,v\}$ に $u<_Qv$ という全順序を入れる。$f(a)=u$、$f(b)=v$ と定めると $f$ は全単射である。
$P$ で $x\le_Py$ が成り立つのは $x=y$ の場合だけなので、$f$ は順序を保つ。しかし $u\le_Qv$ であるのに
$$ f^{-1}(u)=a\not\le_Pb=f^{-1}(v) $$
だから、$f^{-1}$ は順序を保たない。従って $f$ は順序同型ではない。この例は「順序を保つ全単射ならば順序同型である」という含意を破る。

同じ濃度でも順序同型とは限らない

$\mathbb{Z}$ と $\mathbb{Q}$ はともに可算無限集合であるが、通常の大小関係を入れると順序同型ではない。
$\mathbb{Z}$ では、各整数 $n$ に直後の元 $n+1$ がある。すなわち $n< n+1$ であり、$n< r< n+1$ を満たす整数 $r$ は存在しない。一方、$\mathbb{Q}$ では $p< q$ なら
$$ p<\frac{p+q}{2}< q $$
なので、どの元にも直後の元が存在しない。
順序同型は直後の元を保つ。実際、$y$ が $x$ の直後の元で、$f(x)< z< f(y)$ となる $z$ があれば、全射性により $z=f(w)$ と書け、順序の両方向の保存から $x< w< y$ となって矛盾する。従って $\mathbb{Z}$ と $\mathbb{Q}$ の間に順序同型は存在しない。この例は「濃度が等しいなら順序同型である」という含意を破る。

近接概念との違い

順序埋め込みは、写像 $f\colon P\to Q$ が単射であり
$$ x\le_Py\quad\Longleftrightarrow\quad f(x)\le_Qf(y) $$
を満たすことをいう。全射性は要求しないので、順序埋め込みは $P$ を $Q$ の部分順序集合と同じ形で実現する。順序同型は全射な順序埋め込みにほかならない。
反同型は順序の向きを逆転させる全単射であり、$P$ と双対順序集合 $Q^{\mathrm{op}}$ の間の順序同型と同じものである。順序同型は向きを保つので、両者を混同してはいけない。

関連項目

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
順序同型