Ruitenburg’s Theorem says that every endomorphism f of a finitely generated free Heyting algebra is ulti- mately periodic if f fixes all the generators but one. More precisely, there is N ≥ 0 such that f^N+2 = f^N , 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.

Free Heyting algebra endomorphisms: Ruitenburg’s Theorem and beyond / S. Ghilardi, L. Santocanale. - In: MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE. - ISSN 0960-1295. - (2020). [Epub ahead of print] [10.1017/S0960129519000203]

Free Heyting algebra endomorphisms: Ruitenburg’s Theorem and beyond

S. Ghilardi;
2020

Abstract

Ruitenburg’s Theorem says that every endomorphism f of a finitely generated free Heyting algebra is ulti- mately periodic if f fixes all the generators but one. More precisely, there is N ≥ 0 such that f^N+2 = f^N , 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.
Heyting algebra; Ruitenburg’s Theorem; Sheaf Duality; Bounded Bisimulations; Free algebra endomorphisms
Settore MAT/01 - Logica Matematica
2020
21-gen-2020
Article (author)
File in questo prodotto:
File Dimensione Formato  
1901.01252.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 314.51 kB
Formato Adobe PDF
314.51 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/706157
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact