Abstract of Paper

Iteration Theories of Boolean Functions
by Z. Esik

Abstract:

An iteration theory is an algebraic theory equipped with a dagger operation
satisfying all equations that hold for the least (or greatest) fixed point
operation on monotonic functions on complete lattices. We prove that all
iteration theories of boolean functions equipped with a pointwise dagger
operation consist of monotonic functions, and that the dagger operation is
either the least, or the greatest fixed point operation. Thus, the iteration
theory identities provide a characterization of the extremal fixed point
operations on monotonic boolean functions. Our argument also proves that any
Conway theory of boolean functions with a pointwise dagger is an iteration
theory. Along the way of obtaining these results, we relate the parameter
identity, an equation that holds in all Conway and iteration theories, to
the pointwise property of the dagger operation, and to the extension of the
dagger operation to the theory obtained by adjoining all constants. We also
study conditions ensuring that the extension be conservative. It follows
form the general result proved in the paper that if a Conway theory is
equipped with a pointwise dagger, then the theory obtained by adjoining all
constants is a Conway theory in a unique way, and that the same fact holds
for iteration theories. We also exhibit an iteration theory of boolean
functions with a non-pointwise dagger, an iteration theory of monotonic
functions on the three-element lattice which has a pointwise dagger but such
that the dagger operation is not one of the extremal fixed point operations,
and a pointwise iteration theory on the three-element set such that there is
no cpo structure which would make all functions of the theory monotonic.