デデキント数とは？わかりやすく解説

引数0, 1, 2, 3個の単調ブール関数の自由分配束は、それぞれ 2, 3, 6, 20個の元から成る（一番右の束の各元にマウスオーバーすると、その関数を記述する式が読める）。

数学において、デデキント数（デデキントすう、英: Dedekind numbers）は急激に増大する整数列の一つで、1897年にこれを定義したリヒャルト・デーデキントにちなむ。デデキント数 M(n) は n 変数単調ブール関数の個数に等しい。等価的に、n 元集合の反鎖（英語版）の個数、n 個の生成元から生成される自由分配束（英語版）の元の個数でもあり、また n 元集合の抽象単体複体（英語版）の個数を表す。

M(n) を表す漸近的に正確な式^[1] および総和による表現式^[2]が知られている。しかし、M(n) を閉じた式で表すデデキントの問題は未だに難問であり、また M(n) の正確な値は n ≤ 9 の場合にしか知られていない^[3]。

定義

ブール関数とは、n 個のブール型変数（真か偽かのいずれかの値をとる変数。あるいは等価だが0か1かのビット値をとる変数）を入力とし、別のブール型変数を出力する関数である。ブール関数が単調であるとは、任意の入力の組合せに対して、1個の入力を偽から真に変えるとき、出力が偽から真に変わることはあっても真から偽に変わることはないことを言う。デデキント数 M(n) は、n 個の変数を入力値とする全ての単調なブール関数の個数を表す。

集合の反鎖（antichain, アンチチェイン、反チェイン）とは部分集合の族であって、どの相異なる2元も一方が他方を包含していないものを指す（これはシュペルナー族（英語版）（Sperner family）としても知られる）。今 V を n 個のブール型変数の組とするとき、V の反鎖 A は次のように単調ブール関数 f を定める：真であるような入力変数の集合が、A の元を部分集合として少なくとも1つ持っているとき、f の出力を真とする。そうでないとき偽とする。

逆に、任意の単調ブール関数は同じようにして1つの反鎖を定める：出力が真となるような入力変数の定め方（真である入力変数の指定）の中で、包含関係について極小であるものを全て集めてきて A とする。

このように、デデキント数 M(n) は n 元集合の反鎖の個数に等しい^[4]。

これらと同じクラスを記述する3番目の同値な方法は束論を用いるものである。任意の2個の単調ブール関数 f, g から、別の単調ブール関数 f ∧ g（論理積）および f ∨ g（論理和）を作ることができる。全ての n 変数単調ブール関数から成る集合にこれら2つの二項演算を入れたものは分配束をなし、これは n 個の変数の冪集合に包含関係を順序として入れた半順序集合からバーコフの表現定理（英語版）によって得られる束である。このような構成によって n 個の生成子による自由分配束^[5]が得られ、デデキント数はその束の元の数を与える^[6]。

デデキント数は n 元集合の抽象単体複体（n 元集合の冪集合の部分集合であって、性質「x が元で、y が x に包含されるならば y も元である」を持つもの）の個数に1を加えた値でもある。任意の反鎖は、その各元とそれらの全ての部分集合を集めてくることで1つの抽象単体複体を定める。逆に任意の抽象単体複体から、極大な部分集合を全て取り出してくると1つの反鎖になる^[2]。

例

n = 2 の場合、2変数単調ブール関数は6個あり、2元集合 {x,y} の部分集合で反鎖となるものも6個ある。

入力によらずに常に偽を返す関数 f(x,y) = false に対応する反鎖は空集合である。
論理積 f(x,y) = x ∧ y は1個の元 {x,y} のみから成る反鎖 { {x,y} } に対応する。
2番目の引数を無視して1番目の引数を返す関数 f(x,y) = x は1個の元 {x} のみから成る反鎖 { {x} } に対応する。
1番目の引数を無視して2番目の引数を返す関数 f(x,y) = y は1個の元 {y} のみから成る反鎖 { {y} } に対応する。
論理和 f(x,y) = x ∨ y は元 {x} と元 {y} から成る反鎖 { {x}, {y} } に対応する。
入力によらずに常に真を返す関数 f(x,y) = true は空集合のみから成る反鎖 {Ø} に対応する。

値

0 ≤ n ≤ 9 に対する正確なデデキント数が知られている。

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 （オンライン整数列大辞典の数列 A000372）

これらのうち最初の6個は Church (1940) によって与えられた。M(6) は Ward (1946) によって計算された。M(7) は Church (1965) と Berman & Köhler (1976) により、M(8) は Wiedemann (1991) により計算された。M(9) は2023年に Christian Jäkel^[7]^[8] と Lennart Van Hirtum^[9] の二人により同時に計算された。