格代数中的Fibonacci数列

降集：令L 是一个格代数， A⊆L ，定义 A↓＝{x∈L：∃α∈A，x≤ʟ α} 是 A 的降集。令 𝕺(L)表示 L 的全部降集。

定理：定义如下格代数Lₙ＝{α₁，· · ·，αₙ，b₁，· · ·，bₙ}，满足对于任意 i≤n ，都有αᵢ＜bᵢ 和 αᵢ＜bᵢ₊₁ 。求证： |𝕺(Lₖ)|＝fₖ₊₂ ，其中 f₁＝f₂＝1 且 fₖ₊₂＝fₖ₊₁＋fₖ 是Fibonacci数列。

证明：首先给出上述格代数Lₙ 的Hase图

b₁ b₂ b₃ bₙ

↓↗↘↗ · · · ↙↘

α₁ α₂ bₙ₋₁ αₙ.

为了证明定理，我们首先证明如下引理：对于任意格代数L ，都有 |𝕺(L)|＝|𝕱|，其中 𝕱 表示 L 中全体反链构成的集合。引理的证明很简单：必要性，每个反链都唯一地诱导一个降集；反过来假设 A⊆L 是一个降集，令 ℭᴀ＝{B⊆A：B↓＝A↓}，定义 ℭᴀ 的偏序为 P⊆Q ↔ Q ≤ ℭᴀ P，根据佐恩引理，我们可以得到 (ℭᴀ，ℭᴀ) 的一个极大元 B ，如果 B 不是反链，那么存在 x，y∈B 满足 x＜ʟ y，因此 (B−{y})↓＝B↓ ，这与 B 是极大元矛盾，反证充分性成立。因此引理成立。（根据格论的对偶原理，我们还可以定义“升集”，并证明升集的数量和反链的数量一样）。

根据引理，定理就转化为Lₖ 的反链的个数是多少。下面利用数学归纳法证明： k＝1 时显然定理成立。假设 Lₖ 满足定理，求 Lₖ₊₁ 满足定理。设 A⊆Lₖ₊₁ 是一条反链，如果 αₖ₊₁∉ A，那么 A∈𝕱(Lₖ)，其中 𝕱(Lₖ) 是 Lₖ 的全体反链；如果 bₖ₊₁∉A 但 αₖ₊₁∈A ，那么由于 αₖ₊₁ 与 Lₖ 中全部元素都没有序关系，因此这样的 A 有 |𝕱(Lₖ)| 个；如果 bₖ₊₁∈A ，此时 αₖ∈A ，不能看出，这样的反链 A 的个数＝│{B∈𝕱(Lₖ)：αₖ∈B}│ ，即 |𝕱(Lₖ₋₁)| ，那么 |𝕱(Lₖ)|＝2|𝕱(Lₖ)|＋|𝕱(Lₖ₋₁)| ，由递归可得 |𝕱(Lₖ)|＝fₖ₊₁＋2fₖ₊₂＝fₖ₊₄ ，由数学归纳法可得定理成立。