2,863,865,776,682,984,111,284,691,516,675,984,988,123,66. This is the largest Dedekind number known to date! And it is only the ninth (or the tenth if the term with index 0 is included). This extraordinary sequence, listed as A000372 in the OEIS, Neil Sloane's Online Encyclopedia of Integer Sequences, has been taxing number crunchers for over a century. Yet the sequence can be defined from several different perspectives and crops up in fields that, at first glance, seem quite different.
The original approach is to study monotone Boolean functions. A Boolean function takes Boolean variables as inputs—that is, variables whose values are "True" or "False"—and returns a Boolean value.
How can monotonicity be defined here? The simplest approach is to assign 0 to "False" and 1 to "True". Our functions are thus defined on n-tuples of 0s and 1s, and their values are either 0 or 1. Take two n-tuples, x = (x1, x2… *xn ) and y = (y*1, y2… *yn ) such that x*1 ≤ y1, x2 ≤ y2… *xn ≤ yn. We call the Boolean function f monotone if, in this case, f (x) ≤ f ( y), an idea that clearly echoes the usual notion of an increasing function in analysis. A little thought shows that this amounts to considering a function defined on {0, 1} n *such that, if one of the Boolean inputs changes from "False" to "True", the output cannot change from "True" to "False".
In 1897, the German mathematician Richard Dedekind wondered how many such functions there were for a given integer n. He quickly realized that the answer might be very large indeed! There are 2*nn-tuples to consider. Defining a Boolean function on this set means assigning 0 or 1 to each of these n-tuples. That gives possible functions; we are looking for the monotone ones. For n* = 5, that already means examining more than four billion cases!
