# Leonardo Pacheco

Mathematical Logic at TU Wien

I'm a postdoctoral researcher at TU Wien working with Juan Aguilera. My research is focused around games in logic. I am working in Modal Logic (especially on the modal $$\mu$$-calculus) and Reverse Mathematics (of Gale–Stewart games).

## Recent Presentations

“The $$\mu$$-calculus’ collapse on variations of $$\mathsf{S5}$$” at Logic Colloquium 2023

The $$\mu$$-calculus is obtained by adding to modal logic the least and greatest fixed-point operators $$\mu$$ and $$\nu$$. The alternation depth of a formula measures the entanglement of its least and greatest fixed-point operators. Bradfield showed that, for all $$n\in\mathbb{N}$$, there is a formula $$W_n$$ such that $$W_n$$ has alternation depth $$n$$ and, over all Kripke frames, $$W_n$$ is not equivalent to any formula with alternation depth smaller than $$n$$.

The same may not happen over restricted classes of frames: Alberucci and Facchini showed that, over frames of $$\mathsf{S5}$$, every $$\mu$$-formula is equivalent to a formula without fixed point operators. In this case, we say the $$\mu$$-calculus collapses to modal logic over frames of $$\mathsf{S5}$$.

We show how Alberucci and Facchini’s proof generalize to the $$\mu$$-calculus’s collapse over frames of intuitionistic $$\mathsf{S5}$$. This generalization can also be done for some non-normal logics and for graded modal logics. We also show that, on the other hand, the $$\mu$$-calculus does not collapse over the bimodal logic $$\mathsf{S5}_2$$.

“Fixed-points in epistemic logic” at MSJ Spring Meeting 2023

We study some consequences of the $$\mu$$-calculus' alternation hierarchy collapse on some variations of epistemic logic with only one agent; and sketch how to prove that the alternation hierarchy is strict if we have more than one agent. Slides.

“The $$\mu$$-calculus collapses to modal logic over frames of $$\mathsf{IS5}$$” at 証明論シンポジウム2022

The $$\mu$$-calculus is obtained by adding fixed-point operators to modal logic. Alberucci and Facchini showed that every $$\mu$$-formula is equivalent to some modal formula over frames of $$\mathsf{S5}$$. The modal logic $$\mathsf{IS5}$$ is an intuitionistic variation of $$\mathsf{S5}$$, first defined by Prior in 1957. We show that, with slight changes, Alberucci and Facchini's proof also works in frames of $$\mathsf{IS5}$$. That is, every $$\mu$$-formula is equivalent to some modal formula over frames of $$\mathsf{IS5}$$. This is joint work with Kazuyuki Tanaka. Slides.

“The alternation hierarchy of the $$\mu$$-calculus over weakly transitive frames” at 28th Workshop on Logic, Language, Information and Computation

It is known that the $$\mu$$-calculus collapses to its alternation-free fragment over transitive frames and to modal logic over equivalence relations. We adapt a proof by D'Agostino and Lenzi to show that the $$\mu$$-calculus collapses to its alternation-free fragment over weakly transitive frames. As a consequence, we show that the $$\mu$$-calculus with derivative topological semantics collapses to its alternation-free fragment. We also study the collapse over frames of $$\mathsf{S4.2}$$, $$\mathsf{S4.3}$$, $$\mathsf{S4.3.2}$$, $$\mathsf{S4.4}$$ and $$\mathsf{KD45}$$, logics important for Epistemic Logic. At last, we use the $$\mu$$-calculus to define degrees of ignorance on Epistemic Logic and study the implications of $$\mu$$-calculus's collapse over the logics above. This is joint work with Kazuyuki Tanaka. Slides.

“Determinacy and reflection principles in second-order arithmetic” at Workshop on Reverse Mathematics and its Philosophy (joint presentation with Keita Yokoyama)

It is well-known that several variations of the axiom of determinacy play important roles in the study of reverse mathematics, and the relation between the hierarchy of determinacy (especially the level of $$\Sigma^0_2$$ and $$\Sigma^0_3$$) and comprehension axioms are revealed by Tanaka, Nemoto, Montalbán, Shore, and others. In this talk, we show variations of a result by Kołodziejczyk and Michalewski relating determinacy and reflection in second-order arithmetic based on a model-theoretic characterization of the reflection principles. Slides. Video.

“Determinacy and reflection principles in second-order arithmetic” at The second Japan-Russia workshop on effective descriptive set theory, computable analysis and automata

Working in second order arithmetic, we characterize determinacy of finite differences of open and $$\Sigma^0_2$$ sets as reflection principles. In order to do so we study sequences of coded $$\beta$$-models. More precisely, we prove that: over $$\mathsf{ACA}_0$$, $$\Pi^1_2$$-$$\mathsf{Ref}(\mathsf{ACA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_1)_n$$-$$\mathsf{Det}^*_0$$, and $$\Pi^1_3$$-$$\mathsf{Ref}(\Pi^1_1$$-$$\mathsf{CA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_1)_n$$-$$\mathsf{Det}$$; over $$\mathsf{ATR}_0$$, $$\Pi^1_3$$-$$\mathsf{Ref}(\Pi^1_2$$-$$\mathsf{CA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_2)_n$$-$$\mathsf{Det}$$. This is joint work with Keita Yokoyama.

“On the degrees of ignorance: via epistemic logic and $$\mu$$-Calculus” at SOCREAL 2022

This is joint work with Kazuyuki Tanaka. The extended abstract is available in the booklet here.

“Sequences of $$\beta_k$$-models and reflection in second-order arithmetic” at RIMS共同研究（公開系）「証明と計算の論理と応用」

We study the reflection axioms of the form: if a $$\Pi^1_n$$ sentence $$\varphi$$ is provable in $$T$$, then $$\varphi$$ is true (for a fixed theory $$T$$). We prove the relation between the existence of sequence of $$\beta_k$$ models and reflection axioms for theories of dependent choices. We also comment on the consequences of these results for determinacy in second-order arithmetic. This is joint work with Keita Yokoyama.

“On the $$\mu$$-calculus between $$\mathsf{S4}$$ and $$\mathsf{S5}$$” at 1o. Enc(ue-o)ntro de Logica Brasil-Col(o-ô)mbia

We investigate the alternation hierarchy of the $$\mu$$-calculus in some modal logics commonly used for epistemic logic.

“Modal semantics for epistemic logic” at 数学基礎論若手の会 2021

Epistemic logic is the logic of knowledge, belief and related notions. In this presentation I define and motivate three different modal semantics for epistemic logic: relational semantics, topological semantics and neighborhood semantics. I also comment on the relation between these semantics and common knowledge. I assume no knowledge of modal logic.

## Publications

L. Pacheco, “Recent Results on Reflection Principles in Second-Order Arithmetic”, RIMS Kôkyûroku No.2228.

Abstract: We survey recent results on reflection in second-order arithmetic. The reflection principles we consider can be roughly divided into two categories: semantic reflection and syntactic reflection. (Survey.)

L. Pacheco, K. Yokoyama, “Determinacy and reflection principles in second-order arithmetic” (arXiv:2209.04082, preprint).

Abstract: It is known that several variations of the axiom of determinacy play important roles in the study of reverse mathematics, and the relation between the hierarchy of determinacy and comprehension are revealed by Tanaka, Nemoto, Montalbán, Shore, and others. We prove variations of a result by Kołodziejczyk and Michalewski relating determinacy of arbitrary boolean combinations of $$\Sigma^0_2$$ sets and reflection in second-order arithmetic. Specifically, we prove that: over $$\mathsf{ACA}_0$$, $$\Pi^1_2$$-$$\mathsf{Ref}(\mathsf{ACA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_1)_n$$-$$\mathsf{Det}^*_0$$; $$\Pi^1_3$$-$$\mathsf{Ref}(\Pi^1_1$$-$$\mathsf{CA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_1)_n$$-$$\mathsf{Det}$$; and $$\Pi^1_3$$-$$\mathsf{Ref}(\Pi^1_2$$-$$\mathsf{CA}_0)$$ is equivalent to $$\forall n.(\Sigma^0_2)_n$$-$$\mathsf{Det}$$. We also restate results by Montalbán and Shore to show that $$\Pi^1_3$$-$$\mathsf{Ref}(\mathsf{Z}_2)$$ is equivalent to $$\forall n.(\Sigma^0_3)_n$$-$$\mathsf{Det}$$ over $$\mathsf{ACA}_0$$. Preprint.

L. Pacheco, K. Tanaka, “The alternation hierarchy of the mu-calculus over weakly transitive frames”, Proceedings of WoLLIC 2022 – 28th Workshop on Logic, Language, Information and Computation, Lecture Notes in Computer Science, vol 12468, 207–220.

Abstract: It is known that the $$\mu$$-calculus collapses to its alternation-free fragment over transitive frames and to modal logic over equivalence relations. We adapt a proof by D'Agostino and Lenzi to show that the $$\mu$$-calculus collapses to its alternation-free fragment over weakly transitive frames. As a consequence, we show that the $$\mu$$-calculus with derivative topological semantics collapses to its alternation-free fragment. We also study the collapse over frames of $$\mathsf{S4.2}$$, $$\mathsf{S4.3}$$, $$\mathsf{S4.3.2}$$, $$\mathsf{S4.4}$$ and $$\mathsf{KD45}$$, logics important for Epistemic Logic. At last, we use the $$\mu$$-calculus to define degrees of ignorance on Epistemic Logic and study the implications of $$\mu$$-calculus's collapse over the logics above. DOI: 10.1007/978-3-031-15298-6_13

L. Pacheco, K. Tanaka, “On the degrees of ignorance: via epistemic logic and mu-calculus”, Proceedings of SOCREAL 2022: 6th International Workshop on Philosophy and Logic of Social Reality (2022), 74–78.

Abstract: Epistemic Logic normally discourses on knowledge, belief, and related concepts. We here study ignorance instead. With the help of the $$\mu$$-calculus, we analyze the degrees of ignorance in which an agent doesn't know whether or not a given proposition is true. Building on the study by Stalnaker, we argue that logics "closer" to $$\mathsf{S4.2}$$ allow greater degrees of ignorance, compared to logics "closer" to $$\mathsf{S5}$$. Extended abstract available here.

L. Pacheco, W. Li, K. Tanaka, “On one-variable fragments of modal mu-calculus”, Proc. of CTFM 2019, World Scientific Publ. (2022), 17–45.

Abstract: In this paper, we study one-variable fragments of modal $$\mu$$-calculus and their relations to parity games. We first introduce the weak modal $$\mu$$-calculus as an extension of the one-variable modal $$\mu$$-calculus. We apply weak parity games to show the strictness of the one-variable hierarchy as well as its extension. We also consider games with infinitely many priorities and show that their winning positions can be expressed by both $$\Sigma^\mu_2$$ and $$\Pi^\mu_2$$ formulas with two variables, but requires a transfinite extension of the $$L_\mu$$-formulas to be expressed with only one variable. At last, we define the $$\mu$$-arithmetic and show that a set of natural numbers is definable by both a $$\Sigma^\mu_2$$ and a $$\Pi^\mu_2$$ formula of $$\mu$$-arithmetic if and only if it is definable by a formula of the one-variable transfinite $$\mu$$-arithmetic. DOI: 10.1142/9789811259296_0002

## Education

• 2020-2023: Mathematics PhD at Tohoku University
Thesis: Exploring the difference hierarchies on $$\mu$$-calculus and arithmetic — from the point of view of Gale–Stewart games

Thesis available here.

Short abstract: In this thesis, we study two problems related to difference hierarchies. The difference hierarchy for a point class $$\Gamma$$ classifies the Boolean combinations of sets in $$\Gamma$$ by their complexity. Gale–Stewart games play essential roles in both problems.

In the first part of this thesis, we study the $$\mu$$-calculus' alternation hierarchy over various semantics. The $$\mu$$-calculus' alternation hierarchy classifies its formulas by how many interdependent fixed-point operators appear in a given formula. Bradfield showed that the alternation hierarchy is strict over arbitrary frames. This may not happen if we modify the semantics.

We refine Alberucci and Facchini's proof of the collapse to modal logic over equivalence relations to show that the alternation hierarchy collapses to modal logic in bigger classes of frames. We use this characterization to study degreees of ignorance in various epistemic logics. Afterwards, we show that, on graded semantics, constructive semantics and modal logic with impossible worlds, the alternation hierarchy collapses to modal logic over equivalence relations. On the other hand, the alternation hierarchy is strict on multimodal $$\mu$$-calculus over equivalence relations. We also show that current proofs of the collapse do not work on the non-monotone $$\mu$$-calculus. Furthermore, we show that the alternation hierarchy collapses to its alternation-free fragment over weakly transitive frames.

In the second part of this thesis, we study the connection between Gale–Stewart games and reflection principles in second-order arithmetic. Gale–Stewart games have been studied in reverse mathematics since its beginning and are central to descriptive set theory. Sets definable by the $$\mu$$-calculus are exactly the winning regions of Gale–Stewart games whose payoffs are Boolean combinations of $$\Sigma^0_2$$ sets.

Kołodziejczyk and Michalewski proved that the determinacy of Boolean combinations of $$\Sigma^0_2$$ sets is equivalent to the reflection principle $$\Pi^1_3$$-$$\mathrm{Ref}(\Pi^1_2$$-$$\mathsf{CA}_0)$$. We use finite sequences of coded $$\beta$$-models to prove that the determinacy of Boolean combinations of $$\Sigma^0_1$$ sets is equivalent to the reflection principle $$\Pi^1_3$$-$$\mathrm{Ref}(\Pi^1_1$$-$$\mathsf{CA}_0)$$. We also use the same method to give a new proof of Kołodziejczyk and Michalewski's result. At last, we use a modified version of the method to prove that the determinacy of Boolean combinations of $$\Sigma^0_1$$ sets of Cantor space is equivalent to the reflection principle $$\Pi^1_2$$-$$\mathrm{Ref}(\mathsf{ACA}_0)$$.

• 2018-2020: Mathematics Masters at Tohoku University
Thesis: On the weak hierarchy of $$\mu$$-calculus

In this thesis we present the weak $$\mu$$-calculus and weak $$\mu$$-arithmetic and their alternations hierarchies. We also prove a refinement of a result in Reverse Mathematics related to the $$\mu$$-arithmetic and the determinacy of the finite levels of the difference hierarchy of $$\Sigma^0_2$$.

• 2014-2017: Mathematics Major at Universidade Federal de Goiás
• 2012-2013: Computer Science Major at Universidade Federal de Goiás (Incomplete)

## Contact

Mail: leonardovpacheco [at] gmail [dot] com
Mail: leonardo.pacheco [at] tuwien [dot] ac [dot] at
CV: available here
Mastodon: @leonardopacheco@mathstodon.xyz

As there are other people on the internet with the same name as mine, here is a picture of me: 