Bekić's theorem

Template:Short description In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Austrian Hans Bekić (1936-1982) in 1969, and published posthumously in a book by Cliff Jones in 1984.

The theorem is set up as follows. Consider two operators $f:P\times Q\to P$ and $g:P\times Q\to Q$ on pointed directed-complete partial orders $P$ and $Q$, continuous in each component. Then define the operator $(f,g)(x,y)=(f(x,y),g(x,y))$. This is monotone with respect to the product order (componentwise order). By the Kleene fixed-point theorem, it has a least fixed point $\mu (x,y).(f,g)(x,y)$, a pair $(x_0,y_0)$ in $P\times Q$ such that $f(x_0,y_0)=x_0$ and $g(x_0,y_0)=y_0$.

Bekić's theorem (called the "bisection lemma" in his notes) is that the simultaneous least fixed point $\mu (x,y).(f,g)(x,y)=(x_0,y_0)$ can be separated into a series of least fixed points on $P$ and $Q$, in particular:

$$\begin{array}{cc}{x}_0& =\mu x.f(x,\mu y.g(x,y))\\ y_0& =\mu y.g(x_0,y)\end{array}$$

In this presentation $y_0$ is defined in terms of $x_0$. It can instead be defined in a symmetric presentation:

$$\begin{array}{cc}{x}_0& =\mu x.f(x,\mu y.g(x,y))\\ y_0& =\mu y.g(\mu x.f(x,y),y)\end{array}$$

Proof (Bekić):

$y_0=g(x_0,y_0)$ since it is the fixed point. Similarly $x_0=f(x_0,\mu y.g(x_0,y))=f(x_0,y_0)$. Hence $(x_0,y_0)$ is a fixed point of $(f,g)$. Conversely, if there is a pre-fixed point $(x_1,y_1)$ with $(x_1,y_1)\ge (f(x_1,y_1),g(x_1,y_1))$, then $x_1\ge f(x_1,\mu y.g(x_1,y))\ge x_0$ and $y_1\ge \mu y.g(x_1,y)\ge \mu y.g(x_0,y)=y_0$; hence $(x_1,y_1)\ge (x_0,y_0)$ and $(x_0,y_0)$ is the minimal fixed point.

Variants

In a complete lattice

A variant of the theorem strengthens the conditions on $P$ and $Q$ to be that they are complete lattices, and finds the least fixed point using the Knaster–Tarski theorem. The requirement for continuity of $f$ and $g$ can then be weakened to only requiring them to be monotonic functions.

Categorical formulation

Bekić's lemma has been generalized to fix-points of endofunctors of categories (initial $F$-algebras).

Given two functors $F:𝐂\times 𝐃\to 𝐂$ and $G:𝐂\times 𝐃\to 𝐃$ such that all $\mu X.F(X,Y)$ and $\mu Y.G(X,Y)$ exist, the fix-point $\mu ⟨X,Y⟩.⟨F(X,Y),G(X,Y)⟩$ is carried by the pair:

$$\begin{array}{cc}{X}_0& =\mu X.F(X,\mu Y.G(X,Y))\\ Y_0& =\mu Y.G(X_0,Y)\end{array}$$

Usage

Bekić's theorem can be applied repeatedly to find the least fixed point of a tuple in terms of least fixed points of single variables. Although the resulting expression might become rather complex, it can be easier to reason about fixed points of single variables when designing an automated theorem prover.