View source for Fixed-point property

''for (partially) ordered sets''

A (partially) ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101001.png" /> (cf. [[Partially ordered set|Partially ordered set]]; [[Ordered set|Ordered set]]) is said to have the fixed-point property if and only if each order-preserving mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101002.png" /> (order-preserving means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101003.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101004.png" />) has a [[Fixed point|fixed point]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101005.png" />. The fixed-point property is a comparability invariant for finite ordered sets [[#References|[a4]]]. The most famous results regarding this property likely are the Knaster–Tarski–Davis theorem that a [[Lattice|lattice]] has the fixed-point property if and only if it is complete (cf. [[Complete lattice|Complete lattice]]; [[#References|[a3]]], [[#References|[a14]]]), and the Abian–Brown–Pelczar theorem that in a chain-complete ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101006.png" /> the existence of a point comparable to its image is equivalent to the existence of a fixed point [[#References|[a1]]], [[#References|[a10]]]. In both these results, existence of a fixed point is proved by successive approximation: One starts with a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101007.png" /> such that (without loss of generality) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101008.png" />, and sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f1101009.png" />, taking suprema when reaching limit ordinals. This process eventually will find a fixed point. Applications of this process to analysis can be found in, e.g., [[#References|[a7]]]. The problem to characterize all (finite) ordered sets with the fixed-point property has drawn attention in many ways. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010010.png" />-version of the characterization problem is:

Instance) A finite ordered set.

Question) Is there an order-preserving self-mapping without a fixed point?

It is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010011.png" />-complete when considered in the class of ordered sets of height <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010012.png" /> [[#References|[a5]]]. The most efficient algorithm for this problem to date (1996) is given in [[#References|[a15]]].

One of the standard tools used in the investigation of the fixed-point property are retractions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010013.png" /> (idempotent order-preserving mappings). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010014.png" /> has the fixed-point property and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010015.png" /> is a retraction, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010016.png" /> also has the fixed-point property. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010017.png" /> is chain complete and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010018.png" /> is a comparative retraction (i.e., each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010019.png" /> is comparable to its image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010020.png" />), then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010021.png" /> has the fixed-point property if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010022.png" /> has the fixed-point property. This leads to the notion of dismantlability ([[#References|[a2]]], [[#References|[a11]]]): A chain-complete ordered set is dismantlable if and only if there is a finite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010023.png" /> of sets such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010024.png" /> is a singleton and there are comparative retractions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010025.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010026.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010027.png" />). Every dismantlable ordered set has the fixed-point property. Since a finite ordered set has a comparative retraction if and only if it has an irreducible point (a point with a unique upper or lower cover), dismantlability for finite ordered sets can be checked in polynomial time. For finite ordered sets of height <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010028.png" /> or width <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010029.png" /> the fixed-point property is equivalent to dismantlability and thus can be verified in polynomial time [[#References|[a6]]], [[#References|[a11]]].

An infinitary generalization of the dismantling approach has led to the following structure theorem [[#References|[a9]]]: A chain-complete ordered set with no infinite anti-chain can be dismantled to a finite set in finitely many steps (i.e., the  "core"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010030.png" /> is finite but not necessarily a singleton). This finite core is unique up to isomorphism. Another consequence is the following cancellation result, related to the Birkhoff cancellation problem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010033.png" /> are finite ordered sets, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010035.png" /> have no irreducible points and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010036.png" /> is dismantlable, then isomorphism of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010038.png" /> implies isomorphism of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010040.png" /> (since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010041.png" /> is the core of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010043.png" /> is the core of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010044.png" />).

Satisfying characterizations (many of them derived via retraction results) of the fixed-point property exist for the following classes of ordered sets (infinite sets included unless otherwise stated): height <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010045.png" />; chain-complete width <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010046.png" />; ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010047.png" /> that have a retraction onto a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010048.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010049.png" />; chain-complete lexicographic sums; and finite ordered sets of (interval) dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010050.png" />.

[[Algebraic topology|Algebraic topology]] can be invoked to investigate the fixed-point property via the chain [[Complex|complex]] of a finite ordered set (every chain is considered a [[Simplex|simplex]], cf. [[#References|[a2]]]). If this [[Simplicial complex|simplicial complex]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010051.png" /> is acyclic, or if its topological realization has the topological fixed-point property, then every simplicial mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010052.png" /> fixes a simplex. This, in turn, implies that every [[Graph|graph]] endomorphism of the comparability graph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010053.png" /> fixes a clique, which implies that every order-preserving self-mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010054.png" /> has a fixed point. These methods produced the surprising fact that every finite truncated non-complemented lattice has the fixed-point property. A simple combinatorial proof for this fact is still not available.

Clique graphs provide another criterion for the fixed-point property: If the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010055.png" />th iterated clique graph of the comparability graph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010056.png" /> is a one-point graph, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010057.png" /> has the fixed-point property.

The fixed-point property is productive in the finite setting, i.e., if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010058.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010059.png" /> are finite ordered sets with the fixed-point property, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010060.png" /> also has the fixed-point property [[#References|[a12]]].

Future investigations will address the fixed-point property for sets of height <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010061.png" /> or width <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110100/f11010062.png" />, truncated complemented lattices, products of infinite sets, infinite powers of finite sets, and the number of order-preserving mappings of an ordered set that is guaranteed to have a fixed point.

A survey with a fairly complete list of references is [[#References|[a13]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Abian,   A.B. Brown,   "A theorem on partially ordered sets with applications to fixed point theorems"  ''Canadian J. Math.'' , '''13'''  (1961)  pp. 78–82</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  K. Baclawski,   A. Björner,   "Fixed points in partially ordered sets"  ''Adv. Math.'' , '''31'''  (1979)  pp. 263–287</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.C. Davis,   "A characterization of complete lattices"  ''Pacific J. Math.'' , '''5'''  (1955)  pp. 311–319</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  B. Dreesen,   W. Poguntke,   P. Winkler,   "Comparability invariance of the fixed point property"  ''Order'' , '''2'''  (1985)  pp. 269–274</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D. Duffus,   T. Goddard,   "The complexity of the fixed point property"  ''Order'' , '''13'''  (1996)  pp. 209–218</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  T. Fofanova,   A. Rutkowski,   "The fixed point property in ordered sets of width two"  ''Order'' , '''4'''  (1987)  pp. 101–106</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  S. Heikkilä,   V. Lakhshmikantham,   "Monotone iterative techniques for discontinuous nonlinear differential equations" , M. Dekker  (1994)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  H. Höft,   M. Höft,   "Fixed point free components in lexicographic sums with the fixed point property"  ''Demonstratio Math.'' , '''XXIV'''  (1991)  pp. 294–304</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  B. Li,   E.C. Milner,   "From finite posets to chain complete posets having no infinite antichain"  ''Order'' , '''12'''  (1995)  pp. 159–171</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A. Pelczar,   "On the invariant points of a transformation"  ''Ann. Polonici Math.'' , '''XI'''  (1961)  pp. 199–202</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  I. Rival,   "A fixed point theorem for finite partially ordered sets"  ''J. Combin. Th. A'' , '''21'''  (1976)  pp. 309–318</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  M. Roddy,   "Fixed points and products"  ''Order'' , '''11'''  (1994)  pp. 11–14</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  B. Schröder,   "Algorithms vs. the fixed point property"  I. Rival (ed.) , ''Proc. 1996 ORDAL conference''  (1996)  (To appear in: Theor. Comput. Sci.)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  A. Tarski,   "A lattice-theoretical fixpoint theorem and its applications"  ''Pacific J. Math.'' , '''5'''  (1955)  pp. 285–309</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  W. Xia,   "Fixed point property and formal concept analysis"  ''Order'' , '''9'''  (1992)  pp. 255–264</TD></TR></table>