Search

A result obtained in Ref. 2 for least prefixed points in order enriched cartesian closed categories is generalized to initiality in cartesian closed 2-categories. In brief, the result is that if a fixed point operation on a cartesian closed 2-category is defined by initiality, then under a mild condition, the operation satisfies the cartesian Conway identities and the abstraction identity. In addition, we show that the operation satisfies the power identities, and hence, except for the law a**=a*, the analogues of Conway’s classical identities for the regular sets.

We assume the reader has some familiarity with theories and iteration theories. The main topic of the paper is properties of varieties of iteration algebras. After a preliminary section which contains all of the necessary definitions, we spend some time on a coproduct construction which is needed to prove a fundamental lemma: for each iteration theory T, any T-algebra is a retract of a T-iteration algebra. The proof of the lemma shows that only one property of iteration theories is used: the parameter identity. Hence, the lemma applies to any preiteration theory in which this identity is valid. It follows from this fact that the variety of all T-iteration algebras has “nice” properties only when every T-algebra is an iteration algebra. Some of the possible pathology in varieties of iteration algebras is demonstrated. It is shown that for each set Z of non-negative integers there is a variety of iteration algebras having an n-generated free algebra iff n∈Z. Also given is a theorem characterizing certain functors between varieties of iteration theories which are induced by iteration theory morphisms. We find an explicit description of all of the theory congruences on theories of partial functions. The last section is connected with the strong iteration algebras introduced in a paper by Ésik (1983).