理想

偏序集上的下闭子集;主理想由单个元素生成,是 Zeta 变换直接回答的基本查询单位。

标签 数学 / 偏序集 / 理想 / Zeta 变换

定义

设 (𝑃,≤) 是 偏序集,𝐼⊆𝑃。若对任意 𝑥∈𝐼 和 𝑦≤𝑥,都有 𝑦∈𝐼,则称 𝐼 是 𝑃 的一个理想,也叫下集或下闭集。

直观上,理想对“向下走”封闭:一旦包含 𝑥,就包含所有比 𝑥 小的元素。

主理想

对任意 𝑥∈𝑃,所有满足 𝑦≤𝑥 的元素组成一个理想:

𝐼(𝑥)≝{𝑦∈𝑃:𝑦≤𝑥}

称为 𝑥 生成的主理想。

主理想是最小的、包含 𝑥 的理想:任何包含 𝑥 的理想都必须包含 𝐼(𝑥)。

例子

  • 布尔格:𝑃 是 𝐵 位掩码按子集关系构成的偏序集,𝐼(𝑥) 就是 𝑥 的所有子掩码。
  • 链:理想是某个前缀。
  • 树形偏序:若取“后代 ≤ 祖先”,则节点 𝑥 的主理想就是 𝑥 的 子树。
  • 除数格:按整除关系,𝑛 的主理想就是 𝑛 的所有约数。

与 Zeta 变换的关系

Zeta 变换

𝑍ℎ(𝑥)=∑𝑦≤𝑥ℎ(𝑦)

本质上就是把函数 ℎ 在主理想 𝐼(𝑥) 上聚合。因此:

  • 查询一个主理想,只需读 Zeta 表的一个表项;
  • 查询 𝑘 个主理想之并,合并 𝑘 个表项;
  • 一般理想不一定是主理想。但在有限偏序集中,任意非空理想都是其极大元生成的主理想之并;若极大元唯一,它就是主理想。

常见误解

  • 认为理想一定是主理想:不是,下闭只保证它是若干主理想之并。
  • 认为主理想必须由全局最大元生成:𝑥 只是 𝐼(𝑥) 的最大元,不必是整个偏序集的最大元。
  • 把偏序理想和环论理想混淆:这里指对“向下走”封闭的集合,与加法、乘法封闭无关。
  • 把理想和滤子混淆:滤子对“向上走”封闭,方向正好相反。
源码位置