"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

Mad Hatter Paradox.

DEFINITION: Mad as a Hatter  – someone is said to be mad as a hatter iff there exists a mental illness (madness) from which they suffer, and they’re ignorant of its existence.


Now, consider someone asserting “I know that I’m mad as a hatter”. Call it the Mad Hatter sentence, and denote it with MH.

Is MH true or false?

Suppose MH is true. So it’s true that the person uttering it knows that they’re mad as a hatter. But by knowing that they are mad as a hatter they’re aware of the illness they purport to be suffering from, i.e. being mad as a hatter and so by definition fail to satisfy the conditions for being mad as a hatter. Hence MH is false, it seems.

But if they are not mad as a hatter, and assert a knowledge of being such, the person asserting MH is oblivious of that ignorance (them in fact not being mad as a hatter), a delusion of sorts, and hence qualifies them for being mad as a hatter, thus rendering MH true - but we know where that leads.

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.

Wednesday, December 26, 2012

Combinations, permutation matrices, and a solution to n-valued valuations (truth value assignments for many-valued logics).

This result can be interpreted as a solution to n-valued valuations (truth value assignments for many-valued logics). A detailed proof is given in a later post.

First we define and construct the extensional valuation function , (intuitively, it can be thought of as the generating function for the classical truth table). The valuation function θ will have dimensions (k = 2i rows by i columns), and the value of each binary entry is given by the following formula, as can easily be checked.
Example θ(7,2), represented on a truth table exhausting all valuations (truth value assignments) for 3 propositional variables (atomic formulae). CORRECTION --- the formula works for the table generated such that zeros come before ones, i.e. with the ones and zeros inverted, so the table below is generated incorrectly for this formula, as we should start with zeros first. (Consequently all the m-valued generalizations should be generated analogously --- starting with the smallest value.)
This map, i.e. θ can be generalized to m-ary truth values. The explicit formula is given below:
I've skipped examples here, naturally since the truth matrices get very large, very quick.

Those explicit solutions to the recursive definitions (truth tables) make computation significantly more efficient. They also turn out to be handy (they're both elegant and compact) when writing algorithms for k combinations on n sets, or k partitions on n sets. They should prove useful to anyone working in writing algorithms for systems based on multiple value assignments.

Proof (sketch) --- a detailed proof is given in a later post.
First we express the truth tables as recurrence relations of congruences modulo the number of truth values in that given logic, then solve them by iteration, i.e. see the pattern. Finally give the solutions an elegant form (ceiling notation) using some useful number theoretic identities. QED