Maria João Gouveia ; Luigi Santocanale - $\aleph_1$ and the modal $\mu$-calculus

lmcs:4356 - Logical Methods in Computer Science, October 15, 2019, Volume 15, Issue 4 -
$\aleph_1$ and the modal $\mu$-calculusArticle

Authors: Maria João Gouveia ; Luigi Santocanale

    For a regular cardinal $\kappa$, a formula of the modal $\mu$-calculus is $\kappa$-continuous in a variable x if, on every model, its interpretation as a unary function of x is monotone and preserves unions of $\kappa$-directed sets. We define the fragment $C_{\aleph_1}(x)$ of the modal $\mu$-calculus and prove that all the formulas in this fragment are $\aleph_1$-continuous. For each formula $\phi(x)$ of the modal $\mu$-calculus, we construct a formula $\psi(x) \in C_{\aleph_1 }(x)$ such that $\phi(x)$ is $\kappa$-continuous, for some $\kappa$, if and only if $\phi(x)$ is equivalent to $\psi(x)$. Consequently, we prove that (i) the problem whether a formula is $\kappa$-continuous for some $\kappa$ is decidable, (ii) up to equivalence, there are only two fragments determined by continuity at some regular cardinal: the fragment $C_{\aleph_0}(x)$ studied by Fontaine and the fragment $C_{\aleph_1}(x)$. We apply our considerations to the problem of characterizing closure ordinals of formulas of the modal $\mu$-calculus. An ordinal $\alpha$ is the closure ordinal of a formula $\phi(x)$ if its interpretation on every model converges to its least fixed-point in at most $\alpha$ steps and if there is a model where the convergence occurs exactly in $\alpha$ steps. We prove that $\omega_1$, the least uncountable ordinal, is such a closure ordinal. Moreover we prove that closure ordinals are closed under ordinal sum. Thus, any formal expression built from 0, 1, $\omega$, $\omega_1$ by using the binary operator symbol + gives rise to a closure ordinal.

    Volume: Volume 15, Issue 4
    Published on: October 15, 2019
    Accepted on: August 5, 2019
    Submitted on: March 9, 2018
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,03D70, 03B45, 03B70,F.4.1

    1 Document citing this article

    Consultation statistics

    This page has been seen 1224 times.
    This article's PDF has been downloaded 329 times.