Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We have that S5 modal logic is characterized by the modal axioms $K$, $M$ (reflexive), $4$ (transitive), and $B$ (symmetric). That is, an equivalence relation on a set of possible world (which can be thought of as a digraph if you don't like Kripke semantics) generates S5 modal logic. There is a result of Hardy and Ramanujan which states that the number of equivalence classes of a fixed set of $n$ elements is asymptotically: $$\frac{1}{4\sqrt{3}n}e^{\pi \sqrt{2/3}\sqrt{n}}$$

So, we can asymptotically upper bound the number of distinct Kripke frames with $n$ possible world that generate S5 modal logic by the Hardy-Ramanujan number. There are other modal logics that are characterized by similar axioms, for example, consider a Kripke frame which satisfies antisymmetry, antireflexivity, and transitivity. Then there are some number of distinct Kripke frames with strict partial orderings. Are there any bounds asymptotically on the number of strict partial orderings on a set with $n$ elements similar to the Hardy-Ramanujan number? In general, given any property which can be satisfied in a frame by a modal axiom, do corresponding asymptotic bounds exist on how many Kripke frames can satisfy that modal axiom of size $n$? If not, I would be interested in writing a paper about this topic and would appreciate any references to asymptotic bounds on the number of relations of a certain type on a set of size n.

share|improve this question

1 Answer 1

This paper appears to provide some results relevant for an analogous analysis of S4. I don't know of any work that examines such results in the context of the corresponding axioms, but you might get some useful leads by looking through the references in the OEIS for the sequences mentioned in this table.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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