ブルバキ・ヴィットの定理

数学においてブルバキ・ヴィットの定理（ブルバキ・ヴィットのていり、英: Bourbaki–Witt theorem）は、半順序集合に関する基本的な不動点定理であり、ニコラ・ブルバキとエルンスト・ヴィットの名に因む。この定理は、 $(X,\preceq )$ が空でない半順序集合であって、任意の全順序部分集合に上限が存在するとき、

f : X \to X

が

x\in X\implies f(x)\succeq x

を満たせば、 $f$ は不動点を持つことを述べている。

半順序集合 $X$ が有限であれば、定理の主張は簡単に理解でき、それが直接の証明となる。 $x 0 \in X$ を任意の元として、漸化式

x n +1 = f (x n), n = 0, 1, 2, \dots

が定める点列 ${x n}$ は単調増加である。 $X$ は有限だから、この点列は、

十分に大きい

n

に対して

x n = x \infty

で定常状態に至る。よって、 $x \infty$ は $f$ の不動点である。

定理の証明

$y \in X$ を適当にとって固定し、順序数全体の類 $On$ の上の関数 $K : On \to X$ を、

K (0) = y

K (α + 1) = f (K (α))

と再帰的に定義する。 $β$ が極限順序数のときは、その定義の仕方から

{K (α) | α < β}

は、 $X$ の中の全順序部分集合であるから、

K (β) = sup{K (α) | α < β}

と定義する。 $K : On \to X$ は、単調増加関数である。仮に、 $K$ が狭義単調増加であれば、 $On$ から集合 $X$ の中への単射となり、ハルトークスの補題と矛盾する。順序数 $α, β$ について、 $α < β, K (α) = K (β)$ であれば、

K (α) = K (α + 1) = \dots = K (β)

である。

x = K (α)

とおけば、 $x = K (α) = K (α + 1) = f (K (α)) = f (x)$ である。

ブルバキ・ヴィットの定理には、重要な適用事例が幾つも存在する。選択公理からツォルンの補題を導く証明は、その最もよく知られた適用事案の一つである。ここでは、 $(X,\preceq )$ が空でない半順序集合であって、任意の全順序部分集合に上限が存在する場合について示す。

$(X,\preceq )$ が極大元を持たないと仮定する。選択公理により、 $X$ の空でない部分集合全体の集合 ${\mathfrak {P}}(X)\setminus \{\emptyset \}$ の選択関数 $g$ を取ることができる。 $\emptyset \notin X$ だから、

f(x)=g{\big (}\{y\in X\mid y\succ x\}{\big )}\qquad (x\in X)

により、関数 $f : X \to X$ を定めることができる。 $x \in X$ ならば $f(x)\succ x$ だから、 $f$ は不動点を持たないこととなり、定理に反する。

ツォルンの補題のこの特別な場合は、ハウスドルフの極大原理（英語版）の証明に用いられる。この原理は、任意の半順序部分集合において、任意の全順序部分集合を含む極大全順序部分集合が存在することを述べており、簡単に分かるようにツォルンの補題と同値である。

ブルバキ・ヴィットの定理は、他の適用事例も有する。特に、計算機科学において、計算可能関数の理論で用いる。また、領域理論では、再帰的データ型の定義に用いる。