The undecidability of iterated modal relativization (Q2574887)

The operation of iterated relativization appears in dynamic epistemic logic. This operation is motivated by the notion of an epistemic program: an algorithm whose steps use and change the epistemic states of agents. The presented paper deals also with the transitive closure operation, due to its connection to common knowledge. It is shown that, for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are \(\Sigma^1_1\)-complete. Two of these fragments do not include transitive closure. It is also shown that the question of whether a sentence in these fragments has a finite (tree) model is \(\Sigma^0_1\)-complete.