A syntactic approach to the MacNeille completion of \(\Lambda^\ast\), the free monoid over an ordered alphabet \(\Lambda\) (Q2314419)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A syntactic approach to the MacNeille completion of \(\Lambda^\ast\), the free monoid over an ordered alphabet \(\Lambda\) |
scientific article |
Statements
A syntactic approach to the MacNeille completion of \(\Lambda^\ast\), the free monoid over an ordered alphabet \(\Lambda\) (English)
0 references
22 July 2019
0 references
Let \(\Lambda^*\) be a free monoid of finite words over a not necessarily finite alphabet \(\Lambda\) which is equipped with some order. This order lifts to \(\Lambda^*\) , where it extends the divisibility ordering of words. The MacNeille completion of \(\Lambda^*\) constitutes a complete lattice ordered monoid and is realized by the system of closed lower sets in \(\Lambda^*\) (ordered by inclusion). Under some additional hypothesis on \(\Lambda\), one can esily identify the closed lower sets as the finitely generated ones, whereas it is more complicated to determine the closed upper sets. The following result was proved in 1952 by \textit{G. Higman} [Proc. Lond. Math. Soc. (3) 2, 326--336 (1952; Zbl 0047.03402)]: if \(\Lambda\) is well-quasi-orderd then \(\Lambda^*\) is well-quasi-orderd too, whence the complete lattice of all lower sets of \(\Lambda^*\) is well-founded, i.e. every upper set in \(\Lambda^*\) is finitely generated. The authors prove the following crucial result: Theorem 4.4. Let \(\Lambda\) be an ordered set in which any two elements bounded below have a meet and an upper bound. Then for every finite nonempty subset \(Y\) of \(\Lambda^*\) the smallest closed upper set and the smallest stable upper set containing \(Y\) coincide. If, in addition, \(\Lambda\) is well-founded, then the closed upper sets of \(\Lambda^*\) are exactly the stable upper sets.
0 references
free monoid
0 references
MacNeille completion
0 references
well-quasiorder
0 references