8
$\begingroup$

Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint for a monotone operator on a complete lattice.

The fixpoints can be unique but in general can be many.

My question would be, under which conditions can a monotone function have a unique fixpoint on a complete lattice? Is there some practical sufficient conditions to guarantee a unique fixpoint? It would useful to know this, because sometimes you have a monotone operator that specifies a property. It can be non-trivial to spell out whether it is the greatest fix point or the least fix point you really want to specify. In some cases, the two coincide, and you know to iterate from top or from bottom yields the same result and you would be happy to pick up the one that is more simple or more efficient.

$\endgroup$
6
$\begingroup$

Constant functions have unique fixed points. Another criterion that may be applicable is to compare approximations, $\mu_i = \bigcup_{k<i}f^k(\bot)$ and $\nu_i = \bigcap_{k<i}f^k(\top)$, of the least and the greatest fixed points. Trivially, as soon as $\mu_i = \nu_i$ for some $i$, it has been settled that $f$ has a unique fixed point. The problem with this characterization is that, depending on the lattice and $f$, it is incomplete unless you are prepared to explore transfinite approximations.

$\endgroup$
4
$\begingroup$

Banach's fixed point theorem in constructive metric spaces is one source of unique fixed points. See this cstheory question for both the statement of the theorem and a constructive proof (so you essentially get a simple algorithm). This reference may also interest you.

Existence and Uniqueness of Fixed Point in Partially Ordered Sets and Applications to Ordinary Differential Equations. Juan J. Nieto and Rosana Rodriguez-Lopez. 2007

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.