Dedekind number
E634841
A Dedekind number is the count of distinct monotone Boolean functions (or equivalently, antichains) on an n-element set, forming a rapidly growing sequence studied in combinatorics and lattice theory.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Dedekind number canonical | 1 |
| Dedekind’s problem sequence | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7011066 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Dedekind number Context triple: [Richard Dedekind, hasConceptNamedAfter, Dedekind number]
-
A.
Bell numbers
Bell numbers are a sequence in combinatorics that count the number of ways to partition a finite set into nonempty, unlabeled subsets.
-
B.
Sperner family
A Sperner family is a collection of subsets of a finite set in which no subset is contained within another, central in extremal set theory and combinatorics.
-
C.
Bernoulli numbers
Bernoulli numbers are a sequence of rational numbers that play a central role in number theory and analysis, especially in formulas for sums of powers of integers and in the study of special functions like the Riemann zeta function.
-
D.
Erdős–Kac theorem
The Erdős–Kac theorem is a fundamental result in probabilistic number theory stating that the number of distinct prime factors of a typical integer behaves like a normally distributed random variable.
-
E.
Catalan numbers
Catalan numbers are a sequence of natural numbers that count a wide variety of combinatorial structures, such as correctly matched parentheses, binary tree shapes, and lattice path configurations.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Dedekind number Target entity description: A Dedekind number is the count of distinct monotone Boolean functions (or equivalently, antichains) on an n-element set, forming a rapidly growing sequence studied in combinatorics and lattice theory.
-
A.
Bell numbers
Bell numbers are a sequence in combinatorics that count the number of ways to partition a finite set into nonempty, unlabeled subsets.
-
B.
Sperner family
A Sperner family is a collection of subsets of a finite set in which no subset is contained within another, central in extremal set theory and combinatorics.
-
C.
Bernoulli numbers
Bernoulli numbers are a sequence of rational numbers that play a central role in number theory and analysis, especially in formulas for sums of powers of integers and in the study of special functions like the Riemann zeta function.
-
D.
Erdős–Kac theorem
The Erdős–Kac theorem is a fundamental result in probabilistic number theory stating that the number of distinct prime factors of a typical integer behaves like a normally distributed random variable.
-
E.
Catalan numbers
Catalan numbers are a sequence of natural numbers that count a wide variety of combinatorial structures, such as correctly matched parentheses, binary tree shapes, and lattice path configurations.
- F. None of above. chosen
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial invariant
ⓘ
integer sequence ⓘ mathematical concept ⓘ |
| alternativeName |
Dedekind’s problem sequence
ⓘ
linked to:
Dedekind number
|
| appearsIn |
enumerative combinatorics
ⓘ
theory of partially ordered sets ⓘ |
| computationalComplexity | exact computation is extremely difficult for large n ⓘ |
| counts | number of monotone Boolean functions f : {0,1}^n → {0,1} ⓘ |
| describes |
number of antichains of subsets of an n-element set
ⓘ
number of monotone Boolean functions on an n-element set ⓘ |
| equivalentDescription |
number of antichains in the power set of an n-element set ordered by inclusion
ⓘ
number of order ideals of the Boolean lattice B_n ⓘ |
| equivalentDescription | number of monotone subsets of {0,1}^n under product order ⓘ |
| field |
Boolean function theory
ⓘ
combinatorics ⓘ lattice theory ⓘ |
| firstTerms |
M(0) = 2
ⓘ
M(1) = 3 ⓘ M(2) = 6 ⓘ M(3) = 20 ⓘ M(4) = 168 ⓘ M(5) = 7581 ⓘ M(6) = 7828353 ⓘ M(7) = 2414682040996 ⓘ |
| growthRate | super-exponential ⓘ |
| hasLowerBound | 2^(binomial(n,⌊n/2⌋)) ⓘ |
| hasUpperBound | 2^(binomial(n,⌊n/2⌋)(1+o(1))) ⓘ |
| historicalNote | introduced in the 19th century by Richard Dedekind in work on lattices and logic ⓘ |
| namedAfter | Richard Dedekind ⓘ |
| OEISID | A000372 ⓘ |
| openProblem |
asymptotic behavior is only partially understood
ⓘ
exact formula for general n is unknown ⓘ |
| property |
sequence is strictly increasing in n
ⓘ
values are known only for small n ⓘ |
| relatedConcept |
Bell number
ⓘ
Boolean algebra ⓘ Sperner’s theorem ⓘ
linked to:
Sperner family
|
| relatedTo |
Boolean lattice
ⓘ
Sperner family ⓘ antichain ⓘ distributive lattice ⓘ monotone Boolean function ⓘ |
| sequenceNotation |
D(n)
ⓘ
M(n) ⓘ |
| usedIn |
enumeration of closure systems
ⓘ
study of free distributive lattices ⓘ theory of monotone Boolean circuits ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Dedekind number Description of subject: A Dedekind number is the count of distinct monotone Boolean functions (or equivalently, antichains) on an n-element set, forming a rapidly growing sequence studied in combinatorics and lattice theory.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Dedekind number