数学 › 組合せ論 › 半順序集合と Möbius 反転

包除原理

定理 4.1（「半順序集合と Möbius 反転」§4）・ ✓公理まで証明済み

$X$ を有限集合、 $A_1,\dots,A_n\subseteq X$ とし、 $S\subseteq[n]$ に対し $A_S=\bigcap_{i\in S}A_i$ （ $A_\varnothing=X$ ）とおく。このとき

\Bigl|X\setminus\bigcup_{i=1}^nA_i\Bigr|=\sum_{S\subseteq[n]}(-1)^{|S|}\,|A_S|.

したがって $\bigl|\bigcup_iA_i\bigr|=\sum_{S\neq\varnothing}(-1)^{|S|-1}|A_S|$ である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 4 件、定義なども含めて 5 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 2 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

Möbius 反転公式✓定理 3.1・半順序集合と Möbius 反転
ブール束と約数の束の Möbius 関数✓命題 3.3・半順序集合と Möbius 反転
- Möbius 関数定義 2.5・半順序集合と Möbius 反転
- 直積の Möbius 関数✓命題 3.2・半順序集合と Möbius 反転
  - 接続代数は環で、可逆性は対角成分で決まる✓補題 2.4・半順序集合と Möbius 反転

これを使っている定理証明で参照している 4 件

MDS 符号の重み分布✓定理 4.1・重み多項式と MacWilliams 恒等式・Golay 符号
Whitney の展開✓命題 6.4・彩色
全射の個数✓定理 7.1・場合の数
完全順列の個数✓命題 7.2・場合の数

関連するノック 4 問