2
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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