Bourbaki–Witt theorem

Bourbaki–Witt theorem In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if X is a non-empty chain complete poset, and {displaystyle f:Xto X} such that {displaystyle f(x)geq x} for all {displaystyle x,} then f has a fixed point. Such a function f is called inflationary or progressive.

Contents 1 Special case of a finite poset 2 Proof of the theorem 3 Applications 4 References Special case of a finite poset If the poset X is finite then the statement of the theorem has a clear interpretation that leads to the proof. The sequence of successive iterates, {displaystyle x_{n+1}=f(x_{n}),n=0,1,2,ldots ,} where x0 is any element of X, is monotone increasing. By the finiteness of X, it stabilizes: {displaystyle x_{n}=x_{infty },} for n sufficiently large.

It follows that x∞ is a fixed point of f.

Proof of the theorem Pick some {displaystyle yin X} . Define a function K recursively on the ordinals as follows: {displaystyle ,K(0)=y} {displaystyle ,K(alpha +1)=f(K(alpha )).} If {displaystyle beta } is a limit ordinal, then by construction {displaystyle {K(alpha ) : alpha x}).} This is allowed as, by assumption, the set is non-empty. Then f(x) > x, so f is an inflationary function with no fixed point, contradicting the theorem.

This special case of Zorn's lemma is then used to prove the Hausdorff maximality principle, that every poset has a maximal chain, which is easily seen to be equivalent to Zorn's Lemma.

Bourbaki–Witt has other applications. In particular in computer science, it is used in the theory of computable functions. It is also used to define recursive data types, e.g. linked lists, in domain theory.

References Nicolas Bourbaki (1949). "Sur le théorème de Zorn". Archiv der Mathematik. 2 (6): 434–437. doi:10.1007/bf02036949. S2CID 117826806. Ernst Witt (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten. 4: 434–438. doi:10.1002/mana.3210040138. Categories: Order theoryFixed-point theoremsTheorems in the foundations of mathematics