Logical Approaches to Computational Barriers

Describing the Wadge Hierarchy for the Alternation Free Fragment of $\mu$-Calculus (I): The Levels Below $\omega_{1}$

Author(s): |
Jacques Duparc and Alessandro Facchini |

Slot: |
Array, 12:20-12:40, col. 4 |

The height of the Wadge Hierarchy for the Alternation Free Fragment of $\mu$-calculus is known to be at least $\epsilon_{0}$. It was conjectured that the height is exactly $\epsilon_{0}$. We make a first step towards the proof of this conjecture by showing that there is no $\Delta^\mu_{2}$ definable set in between the levels $\omega^\omega$ and $\omega_{1}$ of the Wadge Hierarchy of Borel Sets.

websites: Arnold Beckmann | 2008-05-18 |