デデキント数
ブール関数とは、n 個のブール型変数(真か偽かのいずれかの値をとる変数。あるいは等価だが0か1かのビット値をとる変数)を入力とし、別のブール型変数を出力する関数である。ブール関数が単調であるとは、任意の入力の組合せに対して、1個の入力を偽から真に変えるとき、出力が偽から真に変わることはあっても真から偽に変わることはないことを言う。デデキント数 M(n) は、n 個の変数を入力値とする全ての単調なブール関数の個数を表す。
集合の反鎖(antichain, アンチチェイン、反チェイン)とは部分集合の族であって、どの相異なる2元も一方が他方を包含していないものを指す(これはシュペルナー族(英語版)(Sperner family)としても知られる)。今 V を n 個のブール型変数の組とするとき、V の反鎖 A は次のように単調ブール関数 f を定める:真であるような入力変数の集合が、A の元を部分集合として少なくとも1つ持っているとき、f の出力を真とする。そうでないとき偽とする。
逆に、任意の単調ブール関数は同じようにして1つの反鎖を定める:出力が真となるような入力変数の定め方(真である入力変数の指定)の中で、包含関係について極小であるものを全て集めてきて A とする。
数学において、デデキント数(デデキントすう、英: Dedekind numbers)は急激に増大する整数列の一つで、1897年にこれを定義したリヒャルト・デーデキントにちなむ。デデキント数 M(n) は n 変数単調ブール関数の個数に等しい。等価的に、n 元集合の反鎖(英語版)の個数、n 個の生成元から生成される自由分配束(英語版)の元の個数でもあり、また n 元集合の抽象単体複体(英語版)の個数を表す。
M(n) を表す漸近的に正確な式 および総和による表現式が知られている。しかし、M(n) を閉じた式で表すデデキントの問題は未だ難問であり、また M(n) の正確な値は n ≤ 9 の場合にしか知られていない。