nLab iteration theory

Iteration theory

Iteration theory

Idea

An iteration theory is an algebraic theory that supports iteration on its operators.

In particular, in an iteration theory, any equation

x=t x = t

has a well behaved solution, t t^\dagger, such that t[t /x]=t t[t^\dagger/x]=t^\dagger. More generally, any finite sequence of equations has a solution,

x 1=t 1,x 2=t 2,x n=t n x_1 = t_1, x_2 = t_2, \dots x_n = t_n

In general, t it_i‘s may have other free variables too.

Keeping it simple for a moment, suppose for a second that n=1n=1 and tt has just one free variable, xx. For any algebra AA, the term is interpreted as a function t:AA\llbracket t\rrbracket:A\to A, and the solution t t^\dagger is interpreted as a constant in t A\llbracket t^\dagger\rrbracket\in A, which is a fixed point for the function t\llbracket t\rrbracket. Thus an iteration theory provides canonical fixed points for equations, in every algebra.

Definition

Let TT be an abstract clone. It is a Conway theory when it is equipped with a family of operations

m,n:T(m+n) mT(n) m \dagger_{m,n} : T(m+n)^m \to T(n)^m

such that, for fT(m+n) mf\in T(m+n)^m, (omitting subscripts):

f (i)=f(i)j.{f (j) jm η(j) jn f^\dagger(i) \quad = \quad f(i) \rhd j. \begin{cases} f^\dagger(j) & j\in m \\ \eta(j) & j\in n\end{cases}

and satisfying axioms:

  • parameter identity: ((1 ng)f) =gf ((1_n \oplus g) \circ f)^\dagger = g \circ f ^\dagger where f:nn+p,g:pqf:n \to n+p, \ g:p \to q

  • composition identity: (f,0 m1 pg) ,1 pf=(g,0 n1 pf) \langle (\langle f , \ 0_m \oplus 1_p \rangle \circ g)^\dagger , 1_p \rangle \circ f = (\langle g , \ 0_n \oplus 1_p \rangle \circ f)^\dagger where f:nm+p,g:mn+pf:n \to m+p, \ g:m \to n+p

  • double dagger identity: (1 n,1 n1 p)f) =(f ) (\langle 1_n , \ 1_n \rangle \oplus 1_p) \circ f)^\dagger = (f^\dagger)^\dagger where f:nn+n+pf: n \to n+n+p

in the corresponding Lawvere theory.

It is an iteration theory if the operations also satisfy:

  • commutative identity: (ρ 11 p)(fρ) 1,...,(ρ m1 p)(fρ) m) =((ρ1 p)f) ρ\langle (\rho_1 \oplus 1_p) \circ (f \circ \rho)_1 , \ ... \ , \ (\rho_m \oplus 1_p) \circ (f \circ \rho)_m) \rangle ^\dagger = ((\rho \oplus 1_p) \circ f)^\dagger \circ \rho

where f:nm+p,ρ:mnf: n \to m+p, \ \rho: m \to n is a surjective base morphism and ρ i:mm\rho_i: m \to m are base with ρρ i=ρ\rho \circ \rho_i = \rho for every i.

This connects with the basic idea, because fT(m+n) mf\in T(m+n)^m can be thought of as a sequence of mm terms with m+nm+n variables, and the solution f f^\dagger comprises mm terms just having the nn free variables.

Properties

To equip an abstract clone TT with the structure of a Conway theory is to equip the corresponding Lawvere theory with the structure of a traced monoidal category for the categorical product structure.

Continuous theories

An abstract clone TT is continuous if each set T(n)T(n) is equipped with the structure of a cpo, and the clone operations are continuous.

If TT is also pointed, i.e. each T(n)T(n) has a least element \bot, then TT has a canonical structure of a Conway theory.

For any fT(m+n) mf\in T(m+n)^m, we define an endofunction F f:T(n) mT(n) mF_f : T(n)^m \to T(n)^m by

F f(g)=f(i)j.{g(j) jm η(j) jn F_f (g) \quad = \quad f(i) \rhd j. \begin{cases} g(j) & j\in m \\ \eta(j) & j\in n\end{cases}

and then use Tarski‘s fixed point theorem to define

f = i=1 (F f) n(). f^\dagger \quad = \quad \bigvee_{i=1}^\infty (F_f)^n(\bot) .

References

The ideas originated in the work by Calvin C. Elgot in the 1970s. A textbook reference is:

  • Stephen L. Bloom & Zoltán Ésik , Iteration theories, Springer 1993. (citeseer)

The connection with traced monoidal categories is due to Masahito Hasegawa and Martin Hyland, see Theorem 3.1 of:

  • Masahito Hasegawa, Recursion from Cyclic Sharing: Traced Monoidal Categories and Models of Cyclic Lambda Calculi, Proc. 3rd International Conference on Typed Lambda Calculi and Applications (TLCA 1997). Springer LNCS1210, 1997 (citeseer)

This setting is further studied by Alex Simpson and Gordon Plotkin in

Last revised on August 2, 2022 at 01:29:50. See the history of this page for a list of all contributions to it.