×

Well-quasiordering depends on the labels. (English) Zbl 0736.06007

For well-quasiordered \((WQO)\) categories \(Q\) of finite sets and injective mappings, for any \(WQO\) set \(A\), let \(Q(A)\) be the category of \(A\)- labeled objects of \(Q\): objects \(X\) of \(Q\) with a function \(\lambda: UX\to A\) (\(UX\) the underlying set), with those morphisms \(f: X\to Y\) which decrease no label \(\lambda(x)\) \((x\in UX)\). There are some known results to the effect that for interesting \(Q\)’s, all \(Q(A)\) are \(WQO\), and one theorem scheme “Certain \(Q(A)\) are \(WQO\Rightarrow \text{ all } Q(A)\) are \(WQO\)” [the first author and R. Thomas, Graphs Comb. 6, 41-44 (1990; Zbl 0699.06003)]. It has been unknown whether when \(Q(2)\) is \(WQO\), all \(Q(A)\) are \(WQO\). Now the authors provide \(\aleph_ 1\) ordinals \(\alpha\) such that “for all \(\beta < \alpha\), \(Q(\beta)\) is \(WQO\)” does not imply “\(Q(\alpha) \text{ is } WQO\)”. 3 is included.

MSC:

06A07 Combinatorics of partially ordered sets
18B35 Preorders, orders, domains and lattices (viewed as categories)

Citations:

Zbl 0699.06003
PDFBibTeX XMLCite