{"id":176,"date":"2013-06-13T11:19:38","date_gmt":"2013-06-13T09:19:38","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=176"},"modified":"2022-05-16T15:31:47","modified_gmt":"2022-05-16T13:31:47","slug":"bourbaki-witt-and-dito-pataraia","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=176","title":{"rendered":"Bourbaki, Witt, and Dito Pataraia"},"content":{"rendered":"

The Bourbaki-Witt theorem (Theorem 2.3.1) is a very natural result: take a chain-complete poset X<\/em>, an inflationary map f<\/em> (namely, f<\/em>(x<\/em>) is always above x<\/em>), and a point x<\/em>0<\/sub> in X<\/em>, then f<\/em> has a fixed point above x<\/em>0<\/sub>. \u00a0This is obtained by the following process: start from\u00a0x=<\/span><\/span><\/em>x<\/em>0<\/sub><\/em>,\u00a0and repetitively replace the current value of x<\/em> by f<\/em>(x<\/em>). \u00a0If you ever build infinitely many values of x without reaching a fixed point, then take the supremum of all values obtained so far. \u00a0Repeat these two operations (replacing f<\/em>(x<\/em>) by x<\/em>, taking sups) for as long as needed.<\/p>\n

This is the intuitive idea, but making it a formal proof is more challenging. \u00a0Notably, the proof I’m giving of Theorem 2.3.1 seems to progress rather laboriously, going through a series of auxiliary results that should be mostly obvious, but nonetheless require some ingenuity.<\/p>\n

Another proof would go through so-called ordinal iteration. \u00a0In set theory, one can show that there are objects called ordinals<\/em>, which\u00a0generalize the natural numbers by including infinite ordinals. \u00a0The sleight-of-hand definition is: the class of ordinals is the smallest class containing 0, such that a<\/em>+1 is an ordinal for every ordinal a<\/em>, and the sup of every chain of ordinals is an ordinal. \u00a0Actually defining it, which means in particular defining the ordering between ordinals, requires some set-theoretic cunning. \u00a0(See the wikipedia page on ordinals<\/a>.) \u00a0One can then obtain the fixed point that the Bourbaki-Witt theorem claims exists by ordinal induction. \u00a0That is, we define a collection xa<\/sub><\/em>\u00a0of points of X<\/em> by: x0\u00a0<\/sub><\/em>is already defined, xa+1<\/sub><\/em>=f(xa<\/sub><\/em>), and if a<\/em> is the sup of a chain of ordinals b<\/em>, then xa<\/sub><\/em>\u00a0is the sup in X of the chain of elements f(xb<\/sub><\/em>). \u00a0The class of all ordinals is not a set, i.e., it is not small. \u00a0But X<\/em> is small, so the elements xa\u00a0<\/sub><\/em>cannot be all distinct. \u00a0One then shows that if xa<\/sub><\/em>\u00a0is equal to xb<\/sub><\/em>, then it is a fixed point of f<\/em>. \u00a0If you include all the needed set theory, this is far from elementary.<\/p>\n

Dito Pataraia once found an elegant, and rather elementary of something very close to the Bourbaki-Witt theorem [1]. \u00a0Apparently, he would only very rarely publish his results, so his proof first appeared in a paper by Mart\u00edn\u00a0Escard\u00f3 [2]. \u00a0My attention was drawn to this result by an anonymous referee, whom I am thanking here.<\/p>\n

What Dito Pataraia proved was a version of the Bourbaki-Witt theorem that requires a bit more assumptions, and produces a vastly stronger result.<\/p>\n

The main change in assumptions is that we now require our inflationary maps to be\u00a0monotonic<\/em> as well. \u00a0This is the case in many applications. \u00a0One exception is the Caristi-Waszkiewicz theorem (Exercise 7.4.42). \u00a0The other change is that he requires X<\/em> not to be an inductive poset, rather to be a dcpo<\/em>; that does not make much of a change, since Markowsky’s Theorem (p.61) tells us that inductive posets and dcpos are one and the same thing, but Markowsky’s Theorem is itself non-trivial.<\/p>\n

The big change is in the result: we can find a fixed point x<\/em> above x<\/em>0<\/sub>, not of\u00a0one inflationary map, but of an arbitrary family (fi<\/sub><\/em>)i<\/sub><\/em> in <\/sub>I<\/sub><\/em> of inflationary (monotonic) maps simultaneously<\/em>: we shall have fi<\/sub><\/em>(x)=x with the same<\/em> x for every i<\/em> in I<\/em>.<\/p>\n

Here is how Pataraia does it. \u00a0In a bold move, he goes to a higher-order concept right away. \u00a0Given a dcpo X<\/em>, he considers the set Infl(X<\/em>) of all inflationary monotonic maps from X<\/em> to X<\/em>. \u00a0With the pointwise ordering, Infl(X<\/em>) is a dcpo, and sups are computed pointwise, as usual. \u00a0More: Infl(X<\/em>) is itself directed. \u00a0The key is that for any two inflationary monotonic maps f<\/em>, g<\/em>, their composition f<\/em> o g<\/em> is inflationary, monotonic, and above both f<\/em> (since g<\/em> is inflationary and f<\/em> monotonic) and g<\/em> (since f<\/em> is inflationary). \u00a0It follows that\u00a0Infl(X<\/em>) has a supremum \u22a4. \u00a0This is an inflationary, monotonic map. \u00a0For every f<\/em> in\u00a0Infl(X<\/em>), f<\/em> o \u22a4\u00a0is below\u00a0\u22a4 because\u00a0\u22a4 is the top element, and\u00a0f<\/em>\u00a0o\u00a0\u22a4\u00a0is above \u22a4 because f<\/em> is inflationary: so\u00a0f<\/em>\u00a0o\u00a0\u22a4 = \u22a4. \u00a0It follows that, for every x<\/em> in X<\/em>, f<\/em>(\u22a4(x<\/em>)) =\u00a0\u22a4(x<\/em>). \u00a0In other words,\u00a0\u22a4(x<\/em>) is a fixed point of f<\/em>, and one that is above x<\/em> as well since\u00a0\u22a4 is inflationary. \u00a0Hence:<\/p>\n

Theorem<\/strong> ([2], improving on [1]): On a dcpo X<\/em>, every family\u00a0(fi<\/sub><\/em>)i<\/sub><\/em>\u00a0in\u00a0<\/sub>I<\/sub><\/em>\u00a0of inflationary (monotonic) maps has a common fixed point x<\/em> above any given point x0<\/sub><\/em>. \u00a0We can take x=\u22a4(x0<\/sub><\/em>), where\u00a0\u22a4 is an inflationary monotonic map that is independent of x0\u00a0<\/sub><\/em>and of the family (fi<\/sub><\/em>)i<\/sub><\/em>\u00a0in\u00a0<\/sub>I<\/sub><\/em>.<\/p>\n

We can also require the common fixed point x<\/em> to be least. \u00a0In this case, we must accept that x<\/em> will depend on\u00a0the family (fi<\/sub><\/em>)i<\/sub><\/em>\u00a0in\u00a0<\/sub>I<\/sub><\/em>.<\/p>\n

Theorem<\/strong>\u00a0([2]): On a dcpo\u00a0X<\/em>, every family\u00a0(fi<\/sub><\/em>)i<\/sub><\/em>\u00a0in\u00a0<\/sub>I<\/sub><\/em>\u00a0of inflationary (monotonic) maps has a least common fixed point\u00a0x<\/em>\u00a0above any given point\u00a0x0<\/sub><\/em>.<\/p>\n

The proof goes as follows. \u00a0Let\u00a0F<\/em>\u00a0be smallest subset of X<\/em> that contains\u00a0x0<\/sub><\/em>, is closed under applications of every\u00a0fi<\/sub><\/em>, and is closed under taking sups of directed families. \u00a0This is a dcpo, and the restrictions\u00a0f’i<\/sub><\/em>\u00a0of\u00a0fi\u00a0<\/sub><\/em>to\u00a0F<\/em>\u00a0define inflationary maps from\u00a0F<\/em>\u00a0to\u00a0F<\/em>\u00a0again, which therefore have a common fixed point x<\/em>=\u22a4'(x0<\/sub><\/em>) in\u00a0F<\/em>, as we have just seen.<\/div>\n
To show that it is least, let y<\/em> be another common fixed point of the maps fi<\/sub><\/em>\u00a0above x0.<\/sub><\/em>\u00a0 The downward closure Y<\/em> of y contains x0<\/sub><\/em>, is closed under directed sups, and we claim that Y<\/em> is closed under applications of every fi<\/sub><\/em>: for every z<\/em> in Y<\/em>, fi<\/sub><\/em>(z<\/em>) is below fi<\/sub><\/em>(y<\/em>)=y<\/em> since fi\u00a0<\/sub><\/em>is monotonic and y is a fixed point of fi<\/sub><\/em>. \u00a0It follows that Y<\/em> contains F<\/em>, which is the smallest subset with these properties. \u00a0Therefore\u00a0x<\/em>=\u22a4'(x0<\/sub><\/em>) is also in Y<\/em>, which means that x<\/em> is below y<\/em>, hence y<\/em> is smallest.<\/div>\n
<\/div>\n

We then obtain the following fixed point induction principle, akin to Fact 2.3.3:<\/p>\n

Trick:<\/strong>\u00a0To show that a property P<\/em> holds of the least common fixed point x<\/em>, it is enough to show that P<\/em>(x0<\/sub><\/em>) holds, that P<\/em>(y<\/em>) implies P<\/em>(fi<\/sub><\/em>(y<\/em>)) for every y<\/em> in X<\/em> and every i<\/em> in I<\/em>, and that for every directed family D<\/em> of elements y<\/em> of X<\/em> such that P<\/em>(y<\/em>) holds, P<\/em>(sup D<\/em>) holds.<\/p>\n

Indeed, the set of points that satisfy P<\/em> is one that \u00a0contains\u00a0x0<\/sub><\/em>, is closed under applications of every\u00a0fi<\/sub><\/em>, and is closed under taking sups of directed families, hence contains the set F<\/em> mentioned in the proof of the previous theorem.<\/p>\n

\u2014 Jean Goubault-Larrecq<\/a>(June 13th, 2013)\"jgl-2011\"<\/p>\n

    \n
  1. Dito Pataraia. A constructive proof of Tarski\u2019s fixed-point theorem for dcpo\u2019s. Presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997.<\/li>\n
  2. Mart\u00edn H. Escard\u00f3<\/a>. Joins in the frame of nuclei. \u00a0Applied Categorical Structures<\/a>,\u00a0April 2003,\u00a0Volume 11,\u00a0Issue 2<\/a>,\u00a0pp 117-124.
    \n

    <\/h1>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    The Bourbaki-Witt theorem (Theorem 2.3.1) is a very natural result: take a chain-complete poset X, an inflationary map f (namely, f(x) is always above x), and a point x0 in X, then f has a fixed point above x0. \u00a0This … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-176","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/176","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=176"}],"version-history":[{"count":18,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/176\/revisions"}],"predecessor-version":[{"id":5319,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/176\/revisions\/5319"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}