---
tag: 481ZPQ0GC3
kind: concept
name: Dedekind number
msc: ["06A07", "05A15", "06E30"]
sources:
  - url: https://en.wikipedia.org/wiki/Dedekind_number
same_as:
  wikidata: Q5249753
  wikipedia: Dedekind number
---

## Summary

The Dedekind number $M(n)$ is the number of monotone [[Boolean functions|0X05GS525E]] of $n$ variables.
It also counts the [[antichains|03HF498P1J]] of subsets of an $n$-element set.
For $n \ge 1$, $M(n) - 2$ is the number of elements of the [[free distributive lattice|T5GK6DH8BR]] on $n$ generators.
The first values are $M(0) = 2$, $M(1) = 3$, $M(2) = 6$, $M(3) = 20$, $M(4) = 168$ and $M(5) = 7581$.
The numbers grow very fast, and no closed formula for them is known; finding one is [[Dedekind's problem|RM64J2CP1M]].

## Explanations

### L1 human

A monotone Boolean function is a yes/no rule on $n$ switches.
In such a rule, turning a switch on can never change the answer from yes to no.
The Dedekind number counts these rules.
For two switches $x$ and $y$ there are six: always no, always yes, $x$, $y$, "$x$ and $y$", and "$x$ or $y$".
The rule "exactly one of $x$, $y$" is not monotone.
With $x$ on, turning on $y$ changes the answer from yes to no.