GLのフレーム定義性
Thm 1: $ \bf GLのフレーム定義性 pt.1
proof
Thm 2: $ \bf GLのフレーム定義性 pt.2
proof
次を示せば十分
推移的な有限フレームについて:非反射的$ \iff逆整礎
$ Wは有限個の要素しか持っておらず($ |W|個とする),$ \precは推移的かつ非反射的とする.
$ \implies
次の議論
$ Wの中で$ w_1 \prec w_2 \prec \cdots \prec w_nという$ w_i \in Wの列が構成できたとする.
このとき任意の$ i,jについて$ i < jのとき$ w_i \neq w_jとなる.
$ i < jなので推移律より$ w_i \prec w_jだが,このときもし$ w_i = w_jだとすると$ w_i \prec w_i及び$ w_j \prec w_jが言えてしまって非反射性に反する.
よって$ w_1 \neq w_2 \neq \cdots \neq w_nだから,$ Wの中には最低でも$ n個の要素が含まれることになる.
さて$ \precが逆整礎でない(すなわち↓)と仮定して背理法を用いる.
ある非空集合$ X \sube Wが存在し$ Xは極大元を持たない.
$ \forall x \in X,\exists x' \in X, x \prec x'
このとき,任意の$ n \ge 1に対して列$ x_1 \prec \cdots \prec x_n を構成できる.
$ n = 1のときは非空性より.
$ n = k + 1のときは
帰納法の仮定より$ x_1 \prec \cdots \prec x_kが存在する
このとき極大元を持たないことから$ x_kに対して$ x_k \prec x_k'となる$ x_k'を取ってこれるので$ x_{k+1} = x_k'とすれば列を構成出来る.
もちろん$ x_i \in Wだから,上の議論より$ Xは最低でも$ n個の要素を含む.
更に$ X \sube Wだから$ Wも$ n個の要素を含む.
ところで$ nは任意だったから$ n = |W| + 1とでもすれば矛盾する.
よって仮定がおかしく,$ \precは逆整礎.
$ \impliedby
背理法.非反射的でない(すなわち反射的)と仮定すると適当な部分集合$ X \sube Wの極大元$ x_Mも$ x_M \prec x_Mとなるが,これは極大性の定義に反する($ x_M \prec yとなる$ yは存在しない)のでおかしい.
Memo
$ \bf GLの分析に置いて一般には(?),Thm.2の条件の方が使いやすい.
更にこの他にもフレームを有限木に拡張/調整したものもある.