Free Heyting Algebra Endomorphisms: Ruitenburg's Theorem and Beyond

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 f N +2 = f N , thus the period equals 2. We give a semantic proof of this theorem, using dualit...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical structures in computer science 2019
Main Authors: Ghilardi, Silvio Silvio.Ghilardi@unimi.It, Santocanale, Luigi
Format: Article
Language:English
Subjects:
Computer Science
Logic
Logic in Computer Science
Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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 between 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.
ISSN:0960-1295
1469-8072