The μ \mu -calculus’ Alternation Hierarchy is Strict over Non-Trivial Fusion Logics

Leonardo Pacheco · 2025

Read The μ \mu -calculus’ Alternation Hierarchy is Strict over Non-Trivial Fusion Logics by Leonardo Pacheco (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02597.txt.

Description

Leonardo Pacheco, a logician, settles a structural question about one of modal logic's most powerful extensions. The modal mu-calculus adds least and greatest fixed-point operators to modal logic, and its formulas are ranked by alternation depth, how deeply those two kinds of fixed point depend on each other. Over arbitrary frames the resulting hierarchy is strict: every level says something the level below cannot. But restrict the frames, and the hierarchy can collapse entirely.

Pacheco proves the hierarchy stays strict over non-trivial fusion logics, the multimodal logics formed by fusing simpler modal logics together without interaction axioms. So for that broad and natural class of logics, no amount of clever rewriting compresses a formula's alternation depth. Two examples where the mu-calculus does collapse back to plain modal logic are discussed for contrast, marking where the boundary of the phenomenon lies.

Catalog record

CREATORLeonardo Pacheco
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02597

Browse the full library · About the Tower of Babel