Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T18:40:49.914Z Has data issue: false hasContentIssue false
  • English
  • Français

Free Heyting algebra endomorphisms: Ruitenburg’s Theorem and beyond

Published online by Cambridge University Press:  21 January 2020

Silvio Ghilardi Open the ORCID record for Silvio Ghilardi [Opens in a new window]  and
Luigi Santocanale
Silvio Ghilardi*
Affiliation:
Dipartimento di Matematica, Università degli Studi di Milano
Luigi Santocanale
Affiliation:
LIS, CNRS UMR 7020, Aix-Marseille Université
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Ruitenburg’s Theorem says that every endomorphism f of a finitely generated free Heyting algebra is ultimately periodic if f fixes all the generators but one. More precisely, there is N ≥ 0 such that fN+2 = fN, thus the period equals 2. We give a semantic proof of this theorem, using duality techniques and bounded bisimulation ranks. By the same techniques, we tackle investigation of arbitrary endomorphisms of free algebras. We show that they are not, in general, ultimately periodic. Yet, when they are (e.g. in the case of locally finite subvarieties), the period can be explicitly bounded as function of the cardinality of the set of generators.

Keywords

Heyting algebraRuitenburg’s Theoremsheaf dualitybounded bisimulationsfree algebra endomorphisms
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Special Issue 6: Special Issue: Unification , June 2020 , pp. 572 - 596
Copyright
© Cambridge University Press 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Afshari, B. and Leigh, G. E. (2013). On closure ordinals for the modal μ-calculus. In: Computer Science Logic 2013, LIPIcs. Leibniz Int. Proc. Inform., vol. 23, Wadern, Schloss Dagstuhl. Leibniz-Zent. Inform., 30–44.Google Scholar
Alberucci, L. and Facchini, A. (2009). The modal μ-calculus hierarchy over restricted classes of transition systems. The Journal of Symbolic Logic 74 (4) 1367–1400.CrossRefGoogle Scholar
Bellissima, F. (1986). Finitely generated free Heyting algebras. The Journal of Symbolic Logic 51 (1) 152–165.CrossRefGoogle Scholar
Birkhoff, G. (1937). Rings of sets. Duke Mathematical Journal 3 (3) 443–454.CrossRefGoogle Scholar
Chagrov, A. and Zakharyaschev, M. (1997). Modal Logic, Oxford Logic Guides, vol. 35, New York, The Clarendon Press, Oxford University Press, Oxford Science Publications.Google Scholar
Czarnecki, M. (2010). How fast can the fixpoints in modal μ-calculus be reached? In: Santocanale, L. (ed.) 7th Workshop on Fixed Points in Computer Science, FICS 2010, Brno, Czech Republic, 89. Retrieved from Hal: https://hal.archives-ouvertes.fr/hal-00512377.Google Scholar
Davey, B. A. and Priestley, H. A. (2002). Introduction to Lattices and Order, 2nd edn., Cambridge University Press, New York.10.1017/CBO9780511809088CrossRefGoogle Scholar
Esakia, L. (1974). Topological Kripke models. Soviet Mathematics – Doklady 15 147–151.Google Scholar
Farhi, B. (2009). An identity involving the least common multiple of binomial coefficients and its application. American Mathematical Monthly 116 (9) 836–839.CrossRefGoogle Scholar
Fine, K. (1985). Logics containing K4. II. The Journal of Symbolic Logic 50 (3) 619–651.CrossRefGoogle Scholar
Frittella, S. and Santocanale, L. (2014). Fixed-point theory in the varieties $\mathcal{D}_{n}$ . In: Höfner, P., Jipsen, P., Kahl, W. and Müller, M. E. (eds.) RAMICS, Lecture Notes in Computer Science, vol. 8428, Springer, 446–462.Google Scholar
Ghilardi, S. (1997). Unification through projectivity. Journal of Logic and Computation 7 (6) 733–752.CrossRefGoogle Scholar
Ghilardi, S. (1999). Unification in intuitionistic logic. The Journal of Symbolic Logic 64 (2) 859–880.CrossRefGoogle Scholar
Ghilardi, S. (2000). Best solving modal equations. Annals of Pure and Applied Logic 102 (3) 183–198.CrossRefGoogle Scholar
Ghilardi, S. (2004). Unification, finite duality and projectivity in varieties of Heyting algebras. Annals of Pure and Applied Logic 127 (1–3) 99–115. Provinces of logic determined.CrossRefGoogle Scholar
Ghilardi, S., Gouveia, M. J. and Santocanale, L. (2016). Fixed-point elimination in the intuitionistic propositional calculus. In: Foundations of Software Science and Computation Structures, FOSSACS 2016, Proceedings, 126–141.CrossRefGoogle Scholar
Ghilardi, S., Gouveia, M. J. and Santocanale, L. (2019). Fixed-point elimination in the Intuitionistic Propositional Calculus. ACM Transactions on Computational Logic 21 (1) 1–37.CrossRefGoogle Scholar
Ghilardi, S. and Santocanale, L. (2018). Ruitenburg’s theorem via duality and bounded bisimulations. In: Advances in Modal Logic, AiML 2018, Proceedings, 277–290.Google Scholar
Ghilardi, S. and Zawadowski, M. (2002). Sheaves, Games, and Model Completions: A Categorical Approach to Nonclassical Propositional Logics, 1st edn., Springer Publishing Company, Incorporated.CrossRefGoogle Scholar
Ghilardi, S. and Zawadowski, M. W. (1997). Model completions, r-Heyting categories. Annals of Pure and Applied Logic 88 (1) 27–46.CrossRefGoogle Scholar
Goguen, J. A. (1989). What is unification? A categorical view of substitution, equation and solution. In: Resolution of Equations in Algebraic Structures, vol. 1, Boston, MA, Academic Press, 217–261.Google Scholar
Gouveia, M. J. and Santocanale, L. (2019). $\aleph_1$ and the modal μ-calculus. Logical Methods in Computer Science 15 (4) 1:1–1:34.Google Scholar
Mardaev, S. (2007). Definable fixed points in modal and temporal logics: a survey. Journal of Applied Non-Classical Logics 17 (3) 317–346.CrossRefGoogle Scholar
Mardaev, S. I. (1993). Least fixed points in and in the intuitionistic propositional logic. Algebra and Logic 32 (5) 279–288.CrossRefGoogle Scholar
Milanese, G. C. and Venema, Y. (2019). Closure ordinals of the two-way modal μ-calculus. In: Logic, Language, Information, and Computation, Lecture Notes in Comput. Sci., vol. 11541, Berlin, Springer, 498–515.CrossRefGoogle Scholar
Ruitenburg, W. (1984). On the period of sequences (a n (p)) in intuitionistic propositional calculus. The Journal of Symbolic Logic 49 (3) 892–899.CrossRefGoogle Scholar
Sambin, G. (1976). An effective fixed-point theorem in intuitionistic diagonalizable algebras. Studia Logica 35 (4) 345–361. The algebraization of the theories which express Theor, IX.CrossRefGoogle Scholar
Shavrukov, V. Y. (1993). Subalgebras of diagonalizable algebras of theories containing arithmetic. Dissertationes Mathematicae (Rozprawy Matematyczne), 323 82.Google Scholar
Visser, A. (1996). Uniform interpolation and layered bisimulation. In: Gödel ’96, Brno, 1996, Lecture Notes Logic, vol. 6, Berlin, Springer, 139–164.Google Scholar