"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Thursday, December 27, 2012

My independent discovery of the sequence A007526

I came across a rather surprising property of the above recurrence relation which I defined when counting the number of models of conditional logics with Lewis-Stanlaker type semantics, i.e. similarity spheres. Because the structure of nested sphere assignments happens to correspond in its form to permutations of non-empty subsets of some set, the formula, known to combinatorialists since Bernoulli, had emerged.

Below is an example taken from The Encyclopedia of Integer Sequences: sequence A007526 entry.

I say those properties were surprising given the context, for in and of themselves they’re not surprising at all. I simply didn’t expect such interesting properties to be inherent in the structure of the systems I was studying.

The sequence s is related to the number of models, given certain parameters (more precisely, the parameter is the size of the filter which is the set of all subformulae of a formula whose satisfiability is being tested - hence the requirement to generate all and only those models which are sufficient and necessary for that task), and given by the following recursive definition:
And this is the "curious" result, which links the above recursively defined function with Euler's Constant e:
It's easy to show that the explicit solution to the above recursive definition of s is given by the formula:
And considering the well known Taylor series, it's easy to show that the result stated above follows.
It turns out that this is a known sequence A007526., whose earliest references are Izquierdo (1659), Caramuel de Lobkowitz (1670), Prestet (1675) and Bernoulli (1713). So it appears that I've discovered/defined this sequence independently of those great mathematicians.

No comments: