3
$\begingroup$

Dedekind's problem is about enumerating antichains in the Boolean lattice. Is there an explicit reference where Dedekind stated this problem? Is there a good motivation to study this problem except that it is an old open problem stated by a famous mathematician?

$\endgroup$
  • 1
    $\begingroup$ I don't know an exact reference (probably OEIS may provide some). However, for motivation, I can say that I struggled with some computations that have this problem as a particular case. For example, see here arxiv.org/abs/1902.00864 an article on which Bruns, Garcia and Moci try to compute the number of irreducible elements on the monoid Q(M) when M is a uniform matroid (I can't add the details here, but if M is the uniform matroid with rank n and n elements, this number reduces to Dedekind's problem). Being able to compute them would be very interesting. $\endgroup$ – Luis Ferroni Feb 12 at 14:13
  • $\begingroup$ Richard Dedekind, Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler, Gesammelte Werke, 2, pp. 103–148 (1897). regrettably behind a paywall $\endgroup$ – Carlo Beenakker Feb 12 at 14:18
2
$\begingroup$

Speaking as a nonexpert, the enumeration and classification of monotone Boolean functions can give insight into optimization problems in logic, for instance by considering how far off an arbitrary function is from a monotone one. Doing a web search should reveal other motivations for studying Dedekind's problem.

Gerhard "Who Doesn't Like Enumeration Problems?" Paseman, 2020.02.12.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.