有限半順序集合

$\max D$ の相異なる 2 元 $m,m'$ が $m< m'$ を満たせば $m$ は $D$ で極大でないので、$\max D$ は反鎖である。
$A$ を反鎖とし、$\max(\mathord{\downarrow}A)=A$ を示す。$a\in A$ と $z\in\mathord{\downarrow}A$ が $a\le z$ を満たすとする。$z\le a'$ となる $a'\in A$ があり、$a\le a'$ なので、$A$ が反鎖であることから $a=a'$、したがって $a\le z\le a$ から $z=a$ である。よって $a$ は $\mathord{\downarrow}A$ で極大である。逆に $m$ が $\mathord{\downarrow}A$ で極大なら、$m\le a$ となる $a\in A$ があり、$a\in\mathord{\downarrow}A$ と極大性から $m=a\in A$ である。
$D$ を下方集合とし、$\mathord{\downarrow}(\max D)=D$ を示す。$D$ は下方集合なので左辺は $D$ に含まれる。$z\in D$ なら、有限半順序集合 $D$ の中で $z\le m$ となる極大元 $m$ がとれ（極大元 の命題「有限半順序集合の極大元」）、$z\in\mathord{\downarrow}(\max D)$ である。2 つの合成がともに恒等写像なので、2 つの写像は互いに逆な全単射である。$\square$

$|P|=n$ の線形拡大は、$P$ の元の並べ方 $x_1,\dots,x_n$ で、$x_i< x_j$ なら $i< j$ となるものと同じである（離散数学 の定義「線形拡大」の後半）。そのような並べ方では、先頭の $x_1$ より小さい元は並びのどこにも置けないので、$x_1$ は極小元である。また残りの $x_2,\dots,x_n$ は $P\setminus\{x_1\}$ の線形拡大である。逆に、極小元 $m$ と $P\setminus\{m\}$ の線形拡大 $y_2,\dots,y_n$ をとって $m,y_2,\dots,y_n$ と並べると、$m$ より小さい元はないので、これは $P$ の線形拡大である。この 2 つの対応は互いに逆なので、線形拡大は先頭の極小元 $m$ ごとに $e(P\setminus\{m\})$ 個ずつある。$\square$

$x\parallel y$ とする。全順序 の補題「比較不能な一組を比較可能にする拡大」を $a=y$、$b=x$ に使うと、$\le$ を含み $y\le' x$ となる半順序 $\le'$ が得られる。有限半順序集合 $(P,\le')$ の線形拡大 $L$（離散数学 の定理「有限半順序集合の線形拡大の存在」）は $\le$ の線形拡大でもあり、$y\le_L x$、$x\ne y$ なので $y<_L x$ である。よって線形拡大全体は上の言い換えの条件を満たし、実現子である。線形拡大全体は $e(P)$ 個の有限族なので、次元は定まって $e(P)$ 以下である。$P$ が鎖なら $\le$ 自身が全順序で、$\{\le\}$ が実現子である。逆に $\dim P=1$ なら $\le$ は 1 つの全順序に一致するので、$P$ は鎖である。$\square$

$L_1,\dots,L_t$（$t\le d$）を実現子とし、足りない分は $L_t$ を繰り返して $d$ 個にする。$L_i$ で $x$ より前にある元の個数を $\rho_i(x)$ とおくと、$x\le_{L_i}y\iff\rho_i(x)\le\rho_i(y)$ である。$\varphi=(\rho_1,\dots,\rho_d)$ とおけば、実現子の条件がそのまま $x\le y\iff\varphi(x)\le\varphi(y)$ になる。
逆に $\varphi=(\varphi_1,\dots,\varphi_d)$ があるとする。$P$ の線形拡大 $L_0$ を 1 つ固定し、各 $i$ について
$$ x<_i y\iff\varphi_i(x)<\varphi_i(y)\text{、または }\varphi_i(x)=\varphi_i(y)\text{ かつ }x<_{L_0}y $$
と定める。これは $\varphi_i$ の値で並べ、値の等しい元を $L_0$ の順に並べた全順序である。$x< y$ なら $\varphi(x)\le\varphi(y)$ なので $\varphi_i(x)\le\varphi_i(y)$ であり、等号のときも $x<_{L_0}y$ なので $x<_i y$ である。よって各 $<_i$ は線形拡大である。$x\parallel y$ なら $\varphi(y)\le\varphi(x)$ は成り立たないので、ある $i$ で $\varphi_i(y)>\varphi_i(x)$、すなわち $x<_i y$ であり、同様にある $j$ で $y<_j x$ である。よってこの $d$ 個は実現子で、$\dim P\le d$ である。$\square$

$C=\{c_1< c_2<\cdots< c_k\}$ と並べ、$\mathord{\downarrow}c_0:=\emptyset$ として
$$ B_i:=\mathord{\downarrow}c_i\setminus\mathord{\downarrow}c_{i-1}\quad(1\le i\le k),\qquad B_{k+1}:=P\setminus\mathord{\downarrow}c_k $$
とおく。$\mathord{\downarrow}c_1\subset\cdots\subset\mathord{\downarrow}c_k$ なので、$B_1,\dots,B_{k+1}$ は $P$ の分割である。各 $B_i$ の線形拡大（離散数学 の定理「有限半順序集合の線形拡大の存在」）を $B_1,B_2,\dots,B_{k+1}$ の順につないだ並べ方を $L$ とする。
$L$ が $P$ の線形拡大であることを示す。$x< y$、$x\in B_i$、$y\in B_j$ とする。$j\le k$ なら $y\le c_j$ なので $x\in\mathord{\downarrow}c_j$ であり、$x$ の属する $B_i$ は $i\le j$ を満たす。$j=k+1$ なら $i\le j$ は明らかである。$i< j$ なら $x$ は $y$ より前にあり、$i=j$ なら $B_i$ の線形拡大の中で $x$ が $y$ より前にある。
次に $x=c_i\in C$、$x\parallel y$、$y\in B_j$ とする。$j\le i$ なら $y\le c_j\le c_i$ となって $x\parallel y$ に反するので、$j> i$ であり、$y$ は $B_i$ に属する $c_i$ より後にある。$\square$

各 $C_i$ に lem-fposet-chain-low を使って線形拡大 $L_i$ をとる。$x\parallel y$ とし、$x\in C_i$、$y\in C_j$ とする。同じ鎖の 2 元は比較可能なので $i\ne j$ である。$L_i$ では $x\in C_i$ なので $x<_{L_i}y$、$L_j$ では $y\in C_j$ なので $y<_{L_j}x$ である。よって $L_1,\dots,L_k$ は実現子であり（def-fposet-dimension の後の言い換え）、$\dim P\le k$ である。後半は、Dilworthの定理 の定理「Dilworthの定理」により $P$ が $w(P)$ 個の鎖に分割できることから従う。$\square$

1 ⇒ 2。 区間表示 $I$ があり、2 の 4 元があったとする。$a< b$、$c< d$ から $r(a)< l(b)$、$r(c)< l(d)$ である。$a\parallel d$ なので $r(a)< l(d)$ は成り立たず、$l(d)\le r(a)$ である。同様に $b\parallel c$ から $l(b)\le r(c)$ である。すると
$$ l(d)\le r(a)< l(b)\le r(c)< l(d) $$
となって矛盾する。
2 ⇒ 1。 各 $x$ について $D(x):=\{z\in P\mid z< x\}$ とおく。
まず、集合族 $\{D(x)\mid x\in P\}$ が包含について全順序であることを示す。$D(x)\not\subset D(y)$ かつ $D(y)\not\subset D(x)$ とし、$p\in D(x)\setminus D(y)$、$q\in D(y)\setminus D(x)$ をとる。$p< x$、$q< y$ であり、$p< y$ も $q< x$ も成り立たない。4 元 $p,x,q,y$ が相異なり、$p\parallel q$、$p\parallel y$、$x\parallel q$、$x\parallel y$ であることを確かめる。

• 相異なること：$p=y$ なら $q< y=p< x$ となり、$q< x$ でないことに反する。同様に $q\ne x$ である。$p\ne q$ は $q\in D(y)$、$p\notin D(y)$ から、$x\ne y$ は $D(x)\ne D(y)$ から従い、$p\ne x$、$q\ne y$ は明らかである。
• $p\parallel y$：$p< y$ は仮定に反し、$y< p$ なら $q< y< p< x$ となって $q< x$ でないことに反する。同様に $x\parallel q$ である。
• $p\parallel q$：$p< q$ なら $p< q< y$、$q< p$ なら $q< p< x$ となって、どちらも仮定に反する。
• $x\parallel y$：$x< y$ なら $p< x< y$、$y< x$ なら $q< y< x$ となって、どちらも仮定に反する。
  よって $a=p$、$b=x$、$c=q$、$d=y$ が 2 の 4 元になり、仮定に反する。
  そこで相異なる集合 $D(x)$ を $D_1\subsetneq D_2\subsetneq\cdots\subsetneq D_m$ と並べ、$D(x)=D_{l(x)}$ で $l(x)$ を定める。$x\notin D(x)$ なので、$\{j\mid x\notin D_j\}$ は $l(x)$ を含む。$D_j$ は増加するので、この集合は $\{1,\dots,r(x)\}$ の形で、$r(x)\ge l(x)$ である。よって $x\in D_j\iff j> r(x)$ であり、
  $$ x< y\iff x\in D(y)=D_{l(y)}\iff l(y)> r(x) $$
  となる。$I(x):=[l(x),r(x)]$ は区間表示である。$\square$