MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
up vote 0 down vote accepted

I happened to end up writing a paper which answered my question if anyone else is ever interested in this topic or comes across this question:

"On Generalizing a Temporal Formalism for Game Theory to the Asymptotic Combinatorics of S5 Modal Frames" (arXiv link)

share|cite|improve this answer

Your Answer


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.