Editing Complete partial order (section)

== Continuous functions and fixed-points ==

A [[function (mathematics)|function]] ''f'' between two dcpos ''P'' and ''Q'' is called '''[[Scott continuity|(Scott) continuous]]''' if it maps directed sets to directed sets while preserving their suprema:
* <math>f(D) \subseteq Q</math> is directed for every directed <math>D \subseteq P</math>.
* <math>f(\sup D) = \sup f(D)</math> for every directed <math>D \subseteq P</math>.
Note that every continuous function between dcpos is a [[Monotone function#Monotonicity in order theory|monotone function]]. 
This notion of continuity is equivalent to the [[topological continuity]] induced by the [[Scott topology]].

The set of all continuous functions between two dcpos ''P'' and ''Q'' is denoted <nowiki>[</nowiki>''P''&nbsp;→&nbsp;''Q''<nowiki>]</nowiki>. Equipped with the [[Pointwise#Pointwise relations|pointwise order]], this is again a dcpo, and pointed whenever ''Q'' is pointed.
Thus the complete partial orders with Scott-continuous maps form a [[cartesian closed category|cartesian closed]] [[category (mathematics)|category]].<ref name="barendregt1984">[[Henk Barendregt|Barendregt, Henk]], [http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description#description ''The lambda calculus, its syntax and semantics''] {{Webarchive|url=https://web.archive.org/web/20040823174002/http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description#description |date=2004-08-23 }}, [[North-Holland Publishing Company|North-Holland]] (1984)</ref>

Every order-preserving self-map ''f'' of a pointed dcpo (''P'', ⊥) has a least fixed-point.<ref>This is a strengthening of the [[Knaster–Tarski theorem]] sometimes referred to as "Pataraia’s theorem". For example, see Section 4.1 of [https://doi.org/10.4230/LIPIcs.TYPES.2016.6 "Realizability at Work: Separating Two Constructive Notions of Finiteness"] (2016) by Bezem et al.  See also Chapter 4 of ''The foundations of program verification'' (1987), 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, {{ISBN|0-471-91282-4}}, where the Knaster–Tarski theorem, formulated over pointed dcpo's, is given to prove as exercise 4.3-5 on page 90.</ref> If ''f'' is continuous then this fixed-point is equal to the supremum of the [[Iterated function|iterates]] (⊥, ''f''{{hairsp}}(⊥), ''f''{{hairsp}}(''f''{{hairsp}}(⊥)), … ''f''<sup>&thinsp;''n''</sup>(⊥), …) of ⊥ (see also the [[Kleene fixed-point theorem]]).

Another fixed point theorem is the [[Bourbaki–Witt theorem]], stating that if <math>f</math> is a function from a dcpo to itself with the property that <math>f(x) \geq x</math> for all <math>x</math>, then <math>f</math> has a fixed point. This theorem, in turn, can be used to prove that [[Zorn's lemma]] is a consequence of the axiom of choice.<ref>{{citation
 | last = Bourbaki | first = Nicolas | authorlink = Nicolas Bourbaki
 | journal = [[Archiv der Mathematik]]
 | mr = 0047739
 | pages = 434–437 (1951)
 | title = Sur le théorème de Zorn
 | volume = 2
 | year = 1949
 | issue = 6 | doi=10.1007/bf02036949| s2cid = 117826806 }}.</ref><ref>{{citation
 | last = Witt | first = Ernst | authorlink = Ernst Witt
 | journal = [[Mathematische Nachrichten]]
 | mr = 0039776
 | pages = 434–438
 | title = Beweisstudien zum Satz von M. Zorn
 | volume = 4
 | year = 1951
 | doi=10.1002/mana.3210040138}}.</ref>