The modal logic of the countable random frame (Q1407589)

The modal logic \(\text{ML}_r\) of the countable random frame, which is contained in and ``approximates'' the modal logic of almost sure frame validity (valid with asymptotic probability 1 in a randomly chosen finite frame), is studied. A sound and complete (canonical) axiomatization of \(\text{ML}_r\) is given and it is shown that the logic is not finitely axiomatizable but has the finite frame property via filtration, and that the finite models are easily recognizable, which establishes an EXPSPACE upper bound for the complexity of its satisfiability. Special modally definable properties expressing non-existence of certain partitions, called kernel partitions in random frames, are discussed. It is shown that there are modal formulas corresponding to simple partitions of this kind, which are almost surely valid in the finite, yet fail in the countable random frame.