{"id":2735,"date":"2020-09-20T19:48:02","date_gmt":"2020-09-20T17:48:02","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2735"},"modified":"2022-11-19T15:01:40","modified_gmt":"2022-11-19T14:01:40","slug":"on-the-word-topology-and-beyond","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2735","title":{"rendered":"On the word topology, and beyond"},"content":{"rendered":"\n

Given a quasi-ordered set (X<\/em>,\u2006\u2264), the set of finite words over X<\/em> is built as X<\/em>*<\/sup>\u2004\u225c\u2004\u22c30\u2004\u2264\u2004k<\/em>\u2004<\u2004\u221e<\/sub> X<\/em>k<\/em><\/sup>. (We will use \u225c for equality by definition.)<\/p>\n\n\n\n

This set can be equipped with many different quasi-orders, but it appears that often the right notion is the one relying on subwords<\/em>, that is, a word w<\/em> is smaller than a word w<\/em>\u2032 if there exists a map h<\/em>:\u2006|w<\/em>|\u2192|w<\/em>\u2032| such that \u22001\u2004\u2264\u2004k<\/em>\u2004\u2264\u2004|w<\/em>|,w<\/em>k<\/em><\/sub>\u2004\u2264\u2004w<\/em>h<\/em>(k<\/em>)<\/sub>\u2032. This order is called the subword ordering<\/em>.<\/p>\n\n\n\n

Allow us to recall that in a quasi-ordered set (X<\/em>,\u2006\u2264) an infinite sequence (x<\/em>i<\/em><\/sub>)i<\/em>\u2004\u2208\u2004I<\/em><\/sub> is good<\/em>, whenever there exists i<\/em>\u2004<\u2004j<\/em> such that x<\/em>i<\/em><\/sub>\u2004\u2264\u2004x<\/em>j<\/em><\/sub>. A set (X<\/em>,\u2006\u2264) is a well quasi-order<\/em> whenever every infinite sequence is good. Instances of well quasi-orders occur naturally in computer science and mathematics [6] as a natural generalization of well-founded orderings.<\/p>\n\n\n\n

The first lemma we are interested in this post is due to Higman [5] and states that if (X<\/em>,\u2006\u2264) is a well quasi-order, then (X<\/em>*<\/sup>,\u2006\u2264*<\/sup>) is, too.<\/p>\n\n\n\n

Now, if you have been reading this blog long enough, or if you have just read the title, you might wonder where topology is going to strike in. A good first guess would be to notice that a quasi-ordered space (X<\/em>,\u2006\u2264) always provides us with many topologies, among them we can find the upper topology<\/a>, the Alexandroff topology<\/a> or even the Scott topology<\/a>. The specialization preordering<\/em> of a topology \u03c4<\/em>, written \u2264\u03c4<\/em><\/sub>, is obtained as x<\/em>\u2264\u03c4<\/em><\/sub>y<\/em>\u2004\u21d4\u2004\u2200U<\/em>\u2004\u2208\u2004\u03c4<\/em>,\u2006x<\/em>\u2004\u2208\u2004U<\/em>\u2004\u27f9\u2004y<\/em>\u2004\u2208\u2004U<\/em>. The one thing that we expect when going from a preorder \u2264 to a topology \u03c4<\/em> in order to be called a ‘generalization’, is that \u2264\u03c4<\/em><\/sub>\u2004=\u2004\u2264.<\/p>\n\n\n\n

One can generalize many results from the theory of well quasi-orderings to the topological setting, see [1,2]. And the topological notion that corresponds to well quasi-orders is that of a Noetherian<\/em> space, that is a space in which all subsets are compact.<\/p>\n\n\n\n

We now have enough background to ask the real question: How can we generalize Higman’s Lemma? That is, how can we build a Noetherian space (X<\/em>*<\/sup>,\u2006\u03c4<\/em>*<\/sup>) from a Noetherian space (X<\/em>,\u2006\u03c4<\/em>)?<\/p>\n\n\n\n

This intriguing question has already been answered in [1]… and, as a consequence, we lied when we told you that this would be our goal this month.<\/p>\n\n\n\n

The real objective of this post is to explain why<\/em> there might be very different answers, and why the other constructions are wrong<\/em>. We will first study the relatively simple case of finite words<\/em>, then we will move on to infinite words<\/em>. This will lead us to a conjecture, and to a very brief comment on transfinite words.<\/p>\n\n\n\n

The word topology<\/h2>\n\n\n\n

Let us see what the current proposition for a topology over\u00a0X<\/em>*<\/sup> is, which would allow us to generalize Higman’s Lemma. We will observe a few key properties and reconstruct this topology using a perhaps more natural inductive construction. From this point on, every definition is going to be taken from the book<\/a><\/a>\u00a0[3].<\/p>\n\n\n\n

Definition<\/strong> [3, def 9.7.26<\/em>]. For every topological space X<\/em>, the word topology<\/em> on X<\/em>*<\/sup> is the coarsest one containing the subsets X<\/em>*<\/sup>U<\/em>1<\/sub>X<\/em>*<\/sup>U<\/em>2<\/sub>X<\/em>*<\/sup>\u2026X<\/em>*<\/sup>U<\/em>n<\/em><\/sub>X<\/em>*<\/sup> as open subsets, where n<\/em>\u2004\u2208\u2004\u2115, and U<\/em>1<\/sub>,\u2006U<\/em>2<\/sub>,\u2006\u2026,\u2006U<\/em>n<\/em><\/sub> are open subsets of X<\/em>. We write X<\/em>*<\/sup> for the space of all finite words over X<\/em> with this topology.<\/p>\n\n\n\n

Now, the adaptation of Higman’s Lemma works as you expect: when X<\/em> is a Noetherian space, X<\/em>*<\/sup> is Noetherian as well [3, thm 9.7.33].<\/p>\n\n\n\n

In order to better understand this topology, we will introduce a notation for the basic sets<\/em> that generate the word topology. We write [U<\/em>1<\/sub>,\u2026,U<\/em>n<\/em><\/sub>] for the set X<\/em>*<\/sup>U<\/em>1<\/sub>X<\/em>*<\/sup>\u2026X<\/em>*<\/sup>U<\/em>n<\/em><\/sub>X<\/em>*<\/sup>, and therefore the word topology<\/em> on X<\/em>*<\/sup> is generated by the set {[U<\/em><\/strong>]\u2005\u2223\u2005U<\/em><\/strong>\u2004\u2208\u2004(\u03c4<\/em>)*<\/sup>}. Notice that we write (\u03c4<\/em>)*<\/sup> to denote sequences of elements of \u03c4<\/em>, and not open subsets of X<\/em>*<\/sup>.<\/p>\n\n\n\n

Using this notation, the resemblance between the construction on the points and the construction on the topology is uncanny: we are basically doing the same thing except<\/em> that we have to intersperse X<\/em>*<\/sup> between the letters in the case of the topology. However, let us now instill doubt in your mind that this may be a completely arbitrary choice and others could work.<\/p>\n\n\n\n

    \n
  1. If we only want an equivalent of Higman’s Lemma, we could choose that \u03c4<\/em>*<\/sup> is always defined as the indiscrete topology, which is Noetherian.<\/li>\n\n\n\n
  2. If we also want that the specialisation preorder \u2264\u03c4<\/em>*<\/sup><\/sub> of \u03c4<\/em>*<\/sup> to coincide with (\u2264\u03c4<\/em><\/sub>)*<\/sup>, we also have a lot of choices. For instance, we can consider the Alexandroff topology over (\u2264\u03c4<\/em><\/sub>)*<\/sup>, although this one may fail to be Noetherian (it will be if and only if \u2264\u03c4<\/em><\/sub> is a well quasi-ordering).<\/li>\n<\/ol>\n\n\n\n

    One might argue that given two topologies that are Noetherian and have the same specialization preordering, their join is also Noetherian (oh yes! see the Appendix), and possesses the same specialization preordering (this you can certainly prove for yourselves, right?). Therefore the family of topologies of interest to us is directed. However, there might not be a single finest topology that is both Noetherian and possesses the right specialization preordering, leaving us with no canonical<\/em> choice of topology.<\/p>\n\n\n\n

    Constructors will not do<\/h2>\n\n\n\n

    A good way of finding a canonical<\/em> topology on a set is to insist that it is the coarsest (or the finest) one that satisfies a few properties.<\/p>\n\n\n\n

    Now finite words over X<\/em> are simply finite lists of letters in X<\/em>, and lists over X<\/em> are a data type (in computer science parlance), with two constructors<\/em>:<\/p>\n\n\n\n