デデキント数

デデキント数とは

デデキント数（Dedekind numbers）とは、急激に増加する整数の列で、リヒャルト・デーデキントによって1897年に定義されました。デデキント数M(n)は、n変数の単調ブール関数の数を表し、さらにn元集合の反鎖や自由分配束の元の個数とも等価です。また、n元集合の抽象単体複体の数とも関連しています。これにより、デデキント数は数学のいくつかの分野に橋を架ける役割を果たしています。

デデキント数の定義

ブール関数とは、n個のブール型変数（真または偽の値を持つ）を入力し、別のブール型変数を出力する関数です。単調ブール関数は、入力の一部が偽から真に変わると、出力も偽から真に変わるが、逆はないという特性を持ちます。デデキント数M(n)は、n個の変数で構成されるすべての単調ブール関数の数です。

また、集合の反鎖とは、相異なる2つの元の間に包含関係がない部分集合の集まりです。n個のブール変数Vがあるとき、Vの反鎖Aは、Aの元を部分集合として持つ入力変数の集まりとして定義されます。それにより、任意の単調ブール関数は、真の出力を持つような入力変数を使って反鎖を定義します。このように、デデキント数M(n)はn元集合の反鎖の数と等しくなります。

さらに、束論を用いる別の見方からもデデキント数を考えることができます。単調ブール関数の集合において、論理積と論理和によって新たな単調ブール関数が作られます。この操作により得られる集合は分配束をなし、デデキント数はこの束の元の数を示します。

デデキント数はさらに、n元集合の抽象単体複体の個数に1を加えた結果とも解釈されます。任意の反鎖は、その元とその部分集合からなる抽象単体複体を構成し、逆に抽象単体複体から取った極大な部分集合は一つの反鎖を形成します。

具体例

n=2の場合、ある2変数の単調ブール関数は6個存在し、反鎖も6個あります。具体的に見ると、常に偽を返す関数f(x,y)=falseに対応する反鎖は空集合、論理積f(x,y)=x∧yに対応する反鎖は{ {x,y} }、また1つの引数のみを返す関数f(x,y)=xは反鎖{ {x} }に、論理和f(x,y)=x∨yは反鎖{ {x}, {y} }に、それぞれ対応します。そして、常に真を返す関数f(x,y)=trueの反鎖は{Ø}になるのです。

デデキント数の値

デデキント数は、nが0から9の範囲である場合に関して正確に知られています。具体的には、M(0)=2、M(1)=2、M(2)=6、M(3)=20、M(4)=168、M(5)=7581、M(6)=7828354、M(7)=2414682040998、M(8)=56130437228687557907788、M(9)=286386577668298411128469151667598498812366です。初めの6個はChurchにより1940年に定義され、他の数値も後の研究で計算されました。

特に、nが偶数のとき、M(n)も偶数でなければならず、数の性質は今なお深い研究の対象です。また、反鎖の論理的な定義を数式に書き直した公式も存在しますが、大きなnに対して計算項数が膨大になるため、実用性には限界があります。

漸近評価

デデキント数の対数については、上界と下界の漸近的評価が可能です。例えば、nが偶数の時、デデキント数は反鎖の数に基づく評価に従うことが知られています。反鎖の元の数はn/2に近いという事実から、多くのケースで一般的な挙がりを見せることがわかっています。

このように、デデキント数は数学の複数の側面を結びつける興味深いテーマであり、数学的探求を通じてますます注目されています。

もう一度検索