Can anyone explain--in understandable English--what the heck a Dedekind number is?
Well, perhaps if we start small and try to understand D(2) we can see what D(9) might mean. From the Wikipedia page on Dedekind numbers we find:
"
The Dedekind number D(n) is the number of different monotonic Boolean functions on n variables."
which raises the question, what is a Boolean function on n variables? Such functions can be defined by a lookup table. Here are just three of the Boolean functions on 2 variables:
0,0 → 0 ... 0,0 → 0 ...0,0 → 0
0,1 → 1 ... 0,1 → 0 ...0,1 → 1
1,0 → 1 ... 1,0 → 0 ...1,0 → 1
1,1 → 1 ... 1,1 → 1 ...1,1 → 0
These functions take as input pairs of Boolean values (0 or 1) and for each such pair, produces another Boolean value. Of the three functions I gave, you may recognize the first one as the logical OR function, the second one as the logical AND function, and the third one as the EXCLUSIVE OR function. But there are many more. The output column of each function can be filled in with either a 0 or 1 and the result will be another Boolean function. Since there are four entries, the number of ways of filling them in is 2⁴ = 16. So I have shown 3 out of the possible 16 different Boolean functions of two variables. Therefore whatever the Dedekind number for 2 is, it must be less than 16. All that remains is to figure out what "monotonic" means for Boolean functions. I know what monotonic means in regard to real number functions of one variable. It means a function that can increase or stay the same, but never decrease as the input increases. "Mono"=one and "tonic" means "direction". But whatever can it mean for Boolean functions? Well, the same Wikipedia page explains:
It is monotonic if, for every combination of inputs, switching one of the inputs from false(0) to true(1) can only cause the output to switch from false(0) to true(1) and not from true(1) to false(0).
Looking at the three functions I listed above, the first two are monotonic. Any time either input is changed from 0 to 1 the output either stays the same or else moves from 0 to 1. It never goes backwards. But the third function, the EXCLUSIVE OR function, is not monotonic because changing from 1,0 to 1,1 causes the output to switch from 1 to 0, even though all we did on the input was to change the second input from 0 to 1. At this point you can try your hand at examining all 16 ways to fill out the function table and see which ones are monotonic. The Wikipedia page for Dedekind numbers says D(2) = 6, so you should be able to find just 6 out of the 16 total functions are monotonic. Then you can say you have verified by hand that D(2)=6.
Going down to D(1), we see there are only 4 total functions of one Boolean variable:
0 → 0 ...0 → 0 ...0 → 1 ...0 → 1
1 → 0 ...1 → 1 ...1 → 0 ...1 → 1
If the input variable is A, we can call these functions "always 0", "A", "not A", and "always 1". It is easy to see that they are all monotonic except for "not A" which goes backwards. Therefore the Dedekind number D(1) must be 3. (And sure enough, the Wiki says so too).
If we try to go up to D(3) things get a lot harder. A function of 3 variables has 8 different combinations of inputs (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). And for each of these combinations the lookup table for a function gives a value of 0 or 1. Therefore we know that the total number of functions of three variables is 2⁸ = 256. Then you would have to examine each of the 256 functions to see which ones are monotonic. The Wikipedia page says D(3) = 20, so I guess only 20 out of those 256 will be monotonic.
For D(4), each input is a 4-tuple of Boolean values, There are 16 such 4-tuples, to each function lookup table has 16 entries that can be filled in with either 0 or 1. That means there are 2¹⁶=65536 different such functions. How many of them are monotonic? D(4)=168. So it looks like monotonic functions are harder and harder to find, the higher we go in the Dedekind numbers.
We started out with D(2)= 75% of the total functions. D(3) = 37% of the total possible functions. D(4)=0.3%. It is dropping like a rock!
Edit: This should be D(1)=75% of the total number of functions, D(2)=37% of the total, D(3)=7.8% of the total, D(4)=0.3%.
Generalizing we can see that for D(n), the total number of functions that need to be examined is 2ᴬ where A=2ⁿ. So for D(9) they had to look through 2⁵¹² different functions of 9 variables. That is approximately 134 with 151 zeroes after it, making it a 154 digit number. And out of that many functions, only a 43-digit D(9) of them are monotonic.
As for why anyone would care, I have absolutely no idea!
