ℵ1 AND THE MODAL μ-CALCULUSReport as inadecuate

ℵ1 AND THE MODAL μ-CALCULUS - Download this document for free, or read online. Document in PDF available to download.

1 ULISBOA - Universidade de Lisboa 2 LIF - Laboratoire d-informatique Fondamentale de Marseille

Abstract : For a regular cardinal κ, a formula of the modal µ-calculus is κ-continuous in a variable x if, on every model, its interpretation as a unary function of x is monotone and preserves unions of κ-directed sets. We define the fragment C ℵ 1 x of the modal µ-calculus and prove that all the formulas in this fragment are ℵ 1-continuous. For each formula φx of the modal µ-calculus, we construct a formula ψx ∈ C ℵ 1 x such that φx is κ-continuous, for some κ, if and only if φx is equivalent to ψx. Consequently, we prove that i the problem whether a formula is κ-continuous for some κ is decidable, ii up to equivalence, there are only two fragments determined by continuity at some regular cardinal: the fragment C ℵ 0 x studied by Fontaine and the fragment C ℵ 1 x. We apply our considerations to the problem of characterizing closure ordinals of formulas of the modal µ-calculus. An ordinal α is the closure ordinal of a formula φx if its interpretation on every model converges to its least fixed-point in at most α steps and if there is a model where the convergence occurs exactly in α steps. We prove that ω 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, ω, ω 1 by using the binary operator symbol + gives rise to a closure ordinal.

Author: Maria Joao Gouveia - Luigi Santocanale -

Source: https://hal.archives-ouvertes.fr/


Related documents