不動点定理によるZornの補題の証明
はじめに
こんにちは. 本稿では, 証明が長いでお馴染みのZornの補題をよく知られた証明(初等的な証明)とは違う方法で証明していこうと思います. まずは諸々の定義の確認から入ります. 以下順序集合といった場合半順序集合のことを指します.
$S$を順序集合で$T\subset S$とする. このとき
$\cdot\ a\in S$で任意の$x\in S$に対して$a\le x$なるものを$S$の最小元(least element)という.
$\cdot\ m\in S$で$x\in S$かつ$m\le x$なら$x=m$となるものを$S$の極大元(maximal element)という.
$\cdot\ b\in S$で任意の$x\in T$に対して$x\le b$なるものを$T$の上界(upper bound), その中でも最小のものを上限(least upper bound)という.
$\cdot\ T$が$S$の順序によって全順序集合となるとき$T$を$S$の鎖(chain)という.
$\cdot\ S$の任意の鎖が上界をもつならば$S$をinductive poset(IPS), 上限をもつならばchain complete poset(CCPS)という.
Bourbaki-Witt theorem
さて, 定義の確認が終わったところで, Bourbaki-Witt theoremという順序集合における不動点定理について紹介します. その前に, 2つほど定義をします.
$A$を空でないCCPSで$B\subset A$とする. このとき
$\cdot\ $全ての$x\in A$に対して$x\le f(x)$となるような$f:A\rightarrow A$をincreasing map(IM)という.
$\cdot\ f:A\rightarrow A$をIMとするとき, 以下の$(1)〜(3)$を満たすならば$B$を$a\in A$に対するadmissible subset(AS)であるという:
$(1)\ a\in B;$
$(2)\ f(B)\subset B;$
$(3)\ T$を$B$の空でない鎖とするとき$T$の上限は$B$に属す.
では、紹介に移ります.
$A$を空でないCCPS, $f:A\rightarrow A$をIMとする. このとき$x_{0}\in A$で$f(x_{0})=x_{0}$を満たすものが存在する.
証明に入る前に, まずはこの事実を確認しておきます:
「$A$を空でないCCPSとしたとき$A$は最小限をもつ」
実際, $\emptyset$は$A$の鎖ですから上限$b$が存在します. このとき任意の$a\in A$は$\emptyset$の上界です. つまり任意の$a\in A$に対して$b\le a$となるので$b$が求める最小元となります.
以下$a$を$A$の最小元としASは$a$に対するものであるとします. では, 証明に入ります.
$M$を$A$の全てのASの共通部分とする. このとき$M$はASであって(定義からすぐに分かる), $M$が全順序集合であれば$M$の上限$b\in M$が存在して$b\le f(b)\le b$が成り立つから$x_{0}=b$として証明が終わる. これを示すためにいくつかの補題を示す(下に続く).
$\cdot\ c\in M$とする. このとき$x\in M$かつ$x< c$ならば$f(x)\le c$が成り立つとき$c$を$M$の極限点(extreme point)という.
$\cdot\ E$を$M$の極限点全体の集合とする.
$\cdot\ M$の極限点$c$に対して$M_{c}=\{x\in M\mid x\le c\lor f(c)\le x\}$とする.
$M$の各極限点$c$に対して$M_{c}=M.$
$M_{c}$が$M_{c}\subset M$なるASであれば$M$の構成から$M_{c}=M$がいえる. $x\in M_{c}$とする. このとき
$(1)\ a\le c$より$a\in M_{c}.$
$(2)$
$\quad (2)'\ x< c$なら$f(x)\le c$だから$f(x)\in M_{c},$
$\quad (2)''\ x=c$なら$f(x)=f(c)$より$f(x)\in M_{c},$
$\quad (2)'''\ f(c)\le x$なら$f(c)\le x\le f(x)$より$f(x)\in M_{c}.$
$\quad$よって$f(M_{c})\subset M_{c}.$
$(3)\ T$を$M_{c}$の空でない鎖で$b$を$T$の上限とする.
$\quad (3)'\ $すべての$x\in T$に対して$x\le c$なら$b\le c$だから$b\in M_{c},$
$\quad (3)''\ $いくつかの$x\in T$に対して$f(c)\le x$なら$f(c)\le x\le b$より$b\in M_{c}.$
よって$M_{c}$はASとなる. //
$E=M.$
$E$が$E\subset M$なるASであればよい. $c\in E$とする. このとき
$(1)$「$x\in M$かつ$x< a$」は常に偽であるから$a\in E.$
$(2)\ x< f(c)$なる$x\in M$をとる. このとき補題2から$x\in M_{c}$であるから$x\le c$である.
$\quad (2)'\ x< c$なら$f(x)\le c\le f(c)$より$f(c)\in E,$
$\quad (2)''\ x=c$なら$f(x)=f(c)$より$f(c)\in E.$
$\quad$よって$f(E)\subset E.$
$(3)\ T$を$E$の空でない鎖で$b$を$T$の上限とし, $x< b$なる$x\in M$をとる. もしすべての$c\in T$に対して$f(c)\le x$なら$c\le f(c)\le x$より$x$は$T$の上界となるから$b\le x$となり矛盾する. よって$(2)$と同様にいくつかの$c\in T$に対して$x\le c$である.
$\quad (3)'\ x< c$なら$f(x)\le c\le b$より$b\in E,$
$\quad (3)''\ x=c$なら$c< b$かつ$M_{c}$はASだから$b\in M_{c}$である. よって$f(x)=f(c)\le b$より$b\in E.$
よって$E$はASとなる. //
補題2,3により$x,y\in M$とすれば$y\in M_{x}$である. つまり$y\le x$か$x\le f(x)\le y$のいずれかが成り立つから$M$は全順序集合である. //
Zornの補題の証明
ようやくここからZornの補題の証明に入ります.
$A$を空でないCCPSとする. このとき$A$は極大元をもつ.
$A$が極大元を持たないとする. このとき各$x\in A$に対してある$y_{x}\in A$が存在して$x< y_{x}$である. $f:A\rightarrow A$を$x\mapsto y_{x}$なる写像とすると$f$はIMだから定理1の条件を満たすが, $x_{0}=y_{x_{0}}$なる$x_{0}\in A$は存在しないので矛盾. //
$S$を空でないIPSとする. このとき$S$は極大元をもつ.
$\mathcal{A}$を$S$の鎖で空でないものの族とする. このとき$S$の一点集合は鎖だから$\mathcal{A}$は空でなく, 集合の包含関係により順序集合となる. さらに$\mathcal{T}=\{X_{i}\}_{i\in I}(I\ne\emptyset)$を$\mathcal{A}$の鎖とせよ. このとき$U=\bigcup_{i\in I} X_{i}$は$S$の鎖である. 実際$x,y\in U$ならある$i,j\in I$が存在して$x\in X_{i},y\in X_{j}$である. さらに$\mathcal{T}$は全順序集合だから$x,y\in X_{j}$としてよい. また$X_{j}$も全順序集合だから$x\le y$または$y\le x$となる. よって$U$は$\mathcal{T}$の上限である. つまり$\mathcal{A}$はCCPSとなるから定理4から$\mathcal{A}$は極大元$X_{0}$をもつ. ここで$m$を$X_{0}$の上界とする. $m\le x$なる$x\in S$をとると$X_{0}\cup\{x\}$は$X_{0}$の順序により自然に全順序集合となるから$\mathcal{A}$の要素である. よって$X_{0}$の極大性から$X_{0}=X_{0}\cup\{x\}$となる. つまり$x\in X_{0}$かつ$x\le m$となるから$m=x.$ よって$m$は$S$の極大元である. //
これにて証明は終了です. お疲れさまでした. なお, 定理5の証明中鎖が空である場合についてはすぐに成り立つと分かるので言及していません. また, 定理4,5における"空でない"という条件はなくても同値です(上の黒枠を参照). また, 間違っている箇所等ある場合にはお知らせ願います.
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
