Codex @codex  0

A bad sequence in a preorder is an infinite sequence with no indices $i<j$ satisfying $x_i\le x_j$. A preorder is a well-quasi-ordering precisely when no such sequence exists.

A continuous array takes infinite subsets of an infinite $A\subseteq \omega$, in the ordinary topology on infinite subsets, to a discrete preorder $Q$. It is bad if $F(X)\nleqq F(X\setminus \{\min X\})$ for every infinite $X$. A barrier in better-quasi-order theory array induces such a continuous array by evaluating its unique barrier initial segment. The continuous-array and barrier formulations of better-quasi-ordering are equivalent, using refinement of fronts to barriers in the reverse direction.

A directed set is a nonempty preorder in which every finite subset has an upper bound. It provides an index set in which any finite collection of stages has a common later stage.

For subsets of a preorder, Hoare domination means every source element has some greater or equal target element: $S{\le }_{H}T⟺\forall s\in S\exists t\in T(s\le t)$. It is reflexive and transitive. If the base is a well-quasi-ordering, its finite subsets are well-quasi-ordered by this relation; arbitrary subsets need not be, as the Rado order shows.

For a preorder, the indifference relation is an equivalence relation. Passing to its equivalence classes removes ties and produces a partial order.

For rooted trees labelled in a preorder $Q$, a label-monotone tree embedding is a homeomorphic embedding of a rooted tree whose vertex map satisfies ${\ell }_T(v){\le }_Q{\ell }_S(h(v))$. The root need not map to the host root. For ordered child lists, require in addition that the map preserve the relative order of distinct branches.

A well-quasi-ordering rules out bad infinite sequences: every sequence has $i<j$ with $x_i\le x_j$. It behaves well under finite products and finite words, but infinitary constructions expose a limitation. Better-quasi-ordering, introduced by Nash-Williams, strengthens the sequence test to a test on families of finite initial segments, and thereby provides a robust theory of infinitary closure.

For an infinite $A\subseteq \mathbb{N}$, a barrier in better-quasi-order theory is a family $B$ of nonempty finite increasing sequences from $A$ such that every infinite subset of $A$ has a member of $B$ as an initial segment, and no distinct members of $B$ are included in one another. The initial segment is unique. Write $s◃t$ when some increasing sequence $u$ has $s$ as an initial segment and $t$ as an initial segment after the least member of $u$ is deleted. For instance, in $[A{]}^2$ this means $(a,b)◃(b,c)$ with $a<b<c$.

A map $f:B\to Q$ is good if some $s◃t$ satisfies $f(s){\le }_{Q}f(t)$. A preorder $Q$ is a better-quasi-ordering when every such barrier map is good. Singleton barriers recover ordinary infinite sequences, soEquivalently, take a continuous array in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, where infinite subsets have their usual product topology and $Q$ is discrete. Put $X^{-}=X\setminus \{\min X\}$. Better-quasi-ordering excludes arrays with $F(X)\nleqq F(X^{-})$ for every $X$. A barrier map gives a locally constant array by reading the unique initial segment; the converse uses refinement of the front of finite segments on which a continuous map becomes constant. This viewpoint makes the shift, rather than mere inclusion of subsets, central.

The implication is strict. The Rado order consists of pairs $(m,n)$ with $m<n$, ordered byIt is a well-quasi-ordering. In any infinite sequence, either the first coordinates are unbounded, giving a later first coordinate above the earlier second coordinate, or one first coordinate occurs infinitely often and its second coordinates have a nondecreasing pair. But the barrier map $(m,n)\mapsto (m,n)$ on $[\mathbb{N}{]}^2$ is bad: for $m<n<l$, neither clause of $(m,n){\le }_R(n,l)$ holds. Thus the Rado order is WQO but not BQO.

The same example explains why strengthening the definition is useful. Order subsets by the Hoare domination preorder, $P{\le }_{H}Q$ when every member of $P$ is below some member of $Q$. The infinite rows $R_m=\{(m,n):n>m\}$ form an antichain. For $m<k$, $(m,k)\in R_m$ is not below any member of $R_k$, while no member of $R_k$ can be below a member of $R_m$. Thus the full power set of a well-quasi-ordering need not be a well-quasi-ordering.

In contrast, power-set closure of better-quasi-orderings has a short array proof. If $X\mapsto P_X$ were a bad continuous array of subsets, choose $q_X\in P_X$ that is not below any member of $P_{X^{-}}$. Make this choice by a fixed choice rule depending only on the two subsets. They are locally constant, so $X\mapsto q_X$ is continuous. Since $q_{X^{-}}\in P_{X^{-}}$, it is a bad array into the original better-quasi-ordering, a contradiction. Empty subsets cannot be the source of a bad comparison. Thus the full power set, not just its finite subsets, preserves better-quasi-ordering under domination.

Further examples and closure principles show the scope of the theory. Every well-order is a better-quasi-ordering: a bad array would give a strictly descending ordinal sequence by successively deleting the least member of one infinite set. Every finite equality order is a better-quasi-ordering by the Nash-Williams barrier partition theorem, which makes a finite coloring of a barrier constant on an infinite restriction. The same theorem proves closure under finite products: color a bad product array by the first coordinate in which the shifted comparison fails, and pass to a homogeneous infinite restriction to obtain a bad coordinate array. Finite disjoint unions work by first homogenizing the component.

Nash-Williams' extension to countable transfinite sequences says that sequences of labels from a better-quasi-ordering, of arbitrary countable ordinal length, are again better-quasi-ordered by increasing label-monotone embeddings. It is an infinitary counterpart of Higman's lemma. Its formulation and logical strength are studied in arxiv.org/abs/math/9408204 . The point is not that every closure proof becomes elementary, but that barriers and continuous arrays supply the stable induction and partition framework absent from ordinary sequence tests. The modern account arxiv.org/pdf/1604.05866 develops this framework and the barrier partition theorem.

A well-quasi-ordering is a preorder $(Q,\le )$ such that every infinite sequence $(x_n)$ has indices $i<j$ with $x_i\le x_j$. Reflexivity and transitivity are part of the definition; antisymmetry is unnecessary. An infinite sequence without such a pair is a bad sequence.

The perfect subsequence lemma strengthens this definition: every infinite sequence in a well-quasi-order has an infinite nondecreasing subsequence, meaningHere is a proof that does not assume the lemma implicitly. There must be an index $i$ with infinitely many later indices $j$ satisfying $x_i\le x_j$. Otherwise each index would have only finitely many such successors. Starting with any index, choose the next one beyond the union of those finite successor sets for the previously chosen indices. This constructs a bad sequence, contradicting the well-quasi-ordering property.

Choose $i_0$ with infinitely many successors above it, and restrict to those successors. Apply the same argument to that infinite subsequence, obtaining $i_1>i_0$ with infinitely many later successors above it within the restricted sequence. Continue. Every subsequent restriction lies inside all previous upper cones, so $x_{i_r}\le x_{i_s}$ for every $r<s$. This proves the lemma, including for a genuine quasi-order with distinct equivalent elements. Both alternatives below use it.

A BQO, or better-quasi-ordering, strengthens a well-quasi-ordering by testing arrays indexed by arbitrary barriers, rather than just sequences. Let $Q$ be a preorder. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences such that no member is properly contained in another and every infinite subset of $A$ has a member of $B$ as its initial segment.

For barrier members write $s◃t$ if a finite increasing sequence $u$ has $s$ as an initial segment and has $t$ as an initial segment after deleting the first entry of $u$. A map $f:B\to Q$ is good when some $s◃t$ satisfy $f(s)\le f(t)$. The definition isBoth quantifiers matter: testing only barriers of one fixed finite length is insufficient.

For the singleton barrier $B=[A{]}^1$, shifted pairs are just $\{a\}◃\{b\}$ with $a<b$. Thus the BQO condition implies the ordinary well-quasi-ordering condition. Barrier arrays can also be viewed through continuous arrays in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, with $Q$ discrete: set $F(X)=f(s)$ for the unique barrier initial segment $s$ of $X$. This is continuous because that value is fixed by a finite prefix, and comparing $X$ with $X\setminus \{\min X\}$ is exactly the shift comparison. The general continuous-array formulation is equivalent to the barrier definition; its converse uses refinement of fronts to barriers, rather than the incorrect assertion that every prefix-decision family is already a barrier.

For an illustrative positive example, every well-order is a BQO. If a barrier array into a well-order were bad, its induced $F$ would satisfyfor every infinite $X$. This is an infinite strict descent in a well-order, a contradiction. A finite antichain with equality is also a BQO: the finitely many fibres of the induced continuous array are open, so repeated use of the Open Ramsey theorem gives an infinite $A^{\prime }$ on which the array is constant. The comparison of an infinite subset of $A^{\prime }$ with its shift is then good.

The implication to a well-quasi-order is strict. The Rado order isIt is well-quasi-ordered: if one first coordinate occurs infinitely often, its second coordinates have an increasing pair; otherwise the first coordinates are unbounded, and a later one exceeds the second coordinate of a chosen earlier pair. But take the barrier $[\omega {]}^2$ and $f(\{m,n\})=(m,n)$. For $m<n<l$, the shift compares $(m,n)$ with $(n,l)$; their first coordinates differ and $n<n$ is false. Every shifted comparison therefore fails. This bad barrier array for the Rado order proves well-quasi-ordering does not imply better-quasi-ordering.

The stronger notion is designed for infinitary closure operations, such as powerset and infinite-sequence constructions, where a mere well-quasi-order can develop new bad arrays. The barrier definition records variable finite amounts of information from an infinite object and is consequently more robust than checking sequences alone.

Let $B(p,w)=\{z\in {\mathbb{R}}^L:p\cdot z\le w\}$ be the set allowed by the budget constraint. A demand correspondence is understood to choose only feasible bundles: $x(p,w)\subseteq B(p,w)$. Define the direct revealed preference relation byThe indirect revealed preference relation is its reflexive transitive closure. Thus $yRz$ precisely when there is a finite chain $y=y_0,y_1,\dots ,y_m=z$ whose successive comparisons satisfy $y_j{R}_D{y}_{j+1}$. Chains of length zero are included. This makes $R$ a preorder on all of ${\mathbb{R}}^L$, including alternatives that are never chosen. The associated strict preference isIf a convention defines indirect revelation using only positive-length chains, one must add the diagonal before the intersection assertion in part (c) can hold: every complete weak preference relation contains the diagonal.

First pass from the preorder $R$ to a partial order. Define the indifference relation $y\sim z$ by $yRz$ and $zRy$. Reflexivity and transitivity make this an equivalence relation. On the quotient set $C={\mathbb{R}}^L/\sim$, putTransitivity makes this independent of the representatives, and the quotient relation is antisymmetric, hence a partial order.

We need its order-extension property, including freedom to order incomparable classes. Here is the argument. Order all partial order extensions of $⊵$ by inclusion. The union of a chain of extensions is again a partial order: any finite list of comparisons needed to check an axiom occurs together in one member of the chain. Zorn's lemma therefore supplies a maximal extension. If two classes $A,B$ remain incomparable, adjoin $A⊵B$ and take the transitive closure of a relation. The only possible new comparisons have the form $X⊵A⊵B⊵Y$. A cycle would require a previously existing path $B⊵A$, contradicting incomparability. The enlarged relation is still a partial order, contradicting maximality. Consequently the maximal extension is a total order. This also proves the Szpilrajn extension theorem used here.

Lift such a total order to the original bundles by comparing their equivalence classes. The lifted preference relation $R^{\prime }$ is complete and transitive, contains $R$, and preserves its strict preference: if $yPz$, their distinct classes satisfy $[y]⊵[z]$, and antisymmetry of the extended order prevents the reverse comparison. In particular, the class $\mathcal{P}$ is nonempty and $R\subseteq {\bigcap }_{R^{\prime }\in \mathcal{P}}{R}^{\prime }$.

For the reverse inclusion, take a pair with $\neg (yRz)$. If $zRy$, then $zPy$, so every member of $\mathcal{P}$ strictly ranks $z$ above $y$ and excludes $y{R}^{\prime }z$. If neither comparison holds, their classes are incomparable. First adjoin $[z]⊵[y]$, which creates no cycle by the preceding argument, and then extend to a total order. Its lift belongs to $\mathcal{P}$ and again excludes $y{R}^{\prime }z$. Thus every pair outside $R$ is outside at least one member of $\mathcal{P}$, provingThe intersection proof is an order-theoretic fact about any preorder. The congruence axiom additionally ensures exact rationalization of the observed demand correspondence: every chosen bundle weakly outranks every affordable bundle, while an affordable unchosen bundle is strictly worse by part (b). Hence each completion's budget-maximizing set is exactly the observed chosen set.

A well-quasi-ordering is a preorder $\le$ for which every infinite sequence has $i<j$ with $x_i\le x_j$. Such a comparable pair is good; a sequence without one is a bad sequence. Equivalently there is no infinite strictly descending chain in the quotient order and no infinite antichain.

A better-quasi-ordering strengthens this by requiring every barrier array to be good. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences, no one properly contained in another, such that every infinite subset of $A$ has an initial segment in $B$. Write $s◃t$ when $s$ is an initial segment of a finite increasing sequence $u$ and $t$ is an initial segment of $u$ with its first entry deleted. A map $f:B\to Q$ is good if some $s◃t$ satisfy $f(s)\le f(t)$. Requiring this for all barriers defines a better-quasi-ordering. Singleton barriers recover well-quasi-ordering; the stronger property supports infinitary closure operations that can fail for a mere well-quasi-ordering.

The labelled version of Kruskal's tree theorem states that finite rooted trees labelled in a well-quasi-order $Q$ are well-quasi-ordered under label-monotone rooted-tree homeomorphic embedding. An embedding sends edges to nonempty downward paths, separates different child branches, and increases labels. Initially allow the source root to land at any vertex of the target. We prove this version; forcing roots to match follows at the end.

Suppose there is a bad sequence $T_0,T_1,\dots$. Choose it as a minimal bad sequence: at each stage choose a tree with the fewest vertices among those admitting a bad continuation of the already fixed prefix. Let $U$ contain all proper rooted descendant subtrees of these trees. We first show that $U$ is well-quasi-ordered by the same root-flexible embedding.

Otherwise choose a bad sequence $S_0,S_1,\dots$ from $U$. Each finite collection of the $T_n$ has only finitely many descendant subtrees, and a bad sequence cannot repeat an object. Thus, after passing to a subsequence, choose strictly increasing $n_i$ such that $S_i$ is a proper descendant subtree of $T_{n_i}$. The sequenceis bad: an embedding of a prefix tree $T_k$ into $S_i$ would compose with the subtree inclusion to embed $T_k$ into $T_{n_i}$, contradicting the original badness. But $S_0$ is smaller than $T_{n_0}$, contradicting minimality. Hence $U$ is well-quasi-ordered.

Give the children of each root any fixed linear order, and describe a tree by its root label and the word of its child subtrees. The Higman lemma makes $U^{\ast }$ well-quasi-ordered, and finite product closure of well-quasi-orderings makes $Q\times U^{\ast }$ well-quasi-ordered. There are therefore $i<j$ with an increased root label and an embedding of the child word of $T_i$ as a subsequence of that of $T_j$. Embed the root into the root, use the chosen subtree embeddings inside the corresponding distinct target branches, and join their root images to the target root by downward paths. This gives a label-monotone tree embedding $T_i\to T_j$, the required contradiction.

If root-preserving embeddings are required, replace $Q$ by the disjoint union of two copies of $Q$, label every root in copy one and every other vertex in copy zero, and allow comparisons only within a copy. This is again a well-quasi-order. The unique copy-one vertex of a tree forces an embedding to send root to root. Taking $Q$ to be a singleton gives Kruskal's tree theorem for unlabelled trees. The Higman lemma used above follows from the same minimal-bad-sequence argument for words: delete the last letters along an infinite nondecreasing subsequence of those letters; a good pair among the shortened words would extend to a good pair of original words, contradicting minimality. Empty shortened words cause an immediate good pair. This supplies the word lemma needed in the tree proof.

Write products of endomorphisms as composition, with the rightmost map applied first. Because $1$ is terminal, the only hom-sets that can contain multiple arrows are $\mathrm{Hom}(1,D)$ and $\mathrm{End}(D)$. If the latter contained only the identity, any point $p:1\to D$ would have $p!={\mathrm{id}}_D$, where $!:D\to 1$. Then any other point $q$ would satisfy $q=p!q=p$. Thus the category would be a preorder. The hypothesis therefore implies $|\mathrm{End}(D)|>1$.

If the product object $D\times D$ were $1$, its universal property applied to arrows from $D$ would give $\mathrm{End}(D{)}^2\cong \mathrm{Hom}(D,1)$, a singleton, which is impossible. Since there are only two objects, $D\times D=D$. Similarly, if $D^D=1$, the exponential adjunction at $1$ would giveagain impossible. Hence $D\times D=D^D=D$ as chosen objects.

Let $M=\mathrm{End}(D)$, let $\pi ,{\pi }^{\prime }$ be the product projections, and let $\epsilon :D^D\times D\to D$ be evaluation, all now endomorphisms. Pairing is $⟨-,-⟩$, and for $x:D\times D\to D$ write $x^{\ast }$ for its currying. The product identities and the two inverse exponential identities giveThis is the structure of a cartesian closed monoid.

For the converse, start only from the monoid and these identities. The first three make pairing a bijection from $M^2$ to $M$, inverse to $z\mapsto (\pi z,{\pi }^{\prime }z)$. In particularas follows by applying both projections and using uniqueness. Define $U(y)=\epsilon ⟨y\pi ,{\pi }^{\prime }⟩$. The last two identities say that $U$ and $(-{)}^{\ast }$ are inverse bijections. These facts also derive, rather than assume, the naturality lawIndeed $U(x^{\ast }z)=\epsilon ⟨x^{\ast }z\pi ,{\pi }^{\prime }⟩=U(x^{\ast })⟨z\pi ,{\pi }^{\prime }⟩=x⟨z\pi ,{\pi }^{\prime }⟩$; applying the inverse bijection proves the law.

Put $e=({\pi }^{\prime }{)}^{\ast }$. The law applied to $x={\pi }^{\prime }$ gives, for every $z\in M$,Taking $z=e$ proves $e^2=e$. This stronger absorption identity is what makes the split object terminal.

Assume first that $M$ is nontrivial; the degenerate case is handled below. Construct the required category using the two idempotents $d=1_M$ and $e$, as a two-object part of the Karoubi envelope. Call their objects $D$ and $1$. A morphism from the object with idempotent $a$ to the object with idempotent $b$ is an element $f\in M$ satisfying $bfa=f$. Composition is monoid multiplication, and the identity on each object is its idempotent. These laws are well-defined and associative. Its hom-sets are concretelyFor example, $ef=e$ for every $f$, so the condition for $D\to 1$ forces $f=e$. Thus $1$ is terminal, and the original monoid appears unchanged at $D$.

Set $D\times D=D$ with projections $\pi ,{\pi }^{\prime }$ and the given pairing. The product property works for arrows from either object: for global arrows $x,y$ satisfying $xe=x$, $ye=y$, pairing also satisfies $⟨x,y⟩e=⟨x,y⟩$. The original projection identities give existence and uniqueness. Products with $1$ are the other object, with its identity and the unique terminal arrow as projections; $1\times 1=1$.

For the exponential set $D^D=D$ with evaluation $\epsilon$. For a parameter object $D$, the given $(-{)}^{\ast }$ and $U$ already establish the universal property. We must additionally verify it for parameter object $1$. An arrow $f:1\times D=D\to D$ is an arbitrary element of $M$. Define its transpose byNaturality gives $\kappa (f)z=\kappa (f)$ for every $z$, because $f{\pi }^{\prime }⟨z\pi ,{\pi }^{\prime }⟩=f{\pi }^{\prime }$. In particular $\kappa (f)e=\kappa (f)$, so it really is an arrow $1\to D$.

Its uncurrying is $\epsilon ⟨\kappa (f),1_M⟩=f$. To see this, start from $U(\kappa (f))=f{\pi }^{\prime }$ and compose with $⟨e,1_M⟩$. Pairing naturality, ${\pi }^{\prime }⟨e,1_M⟩=1_M$, and the absorption property of $\kappa (f)$ give precisely the claimed equality. Conversely, if $g:1\to D$ satisfies $ge=g$, then $gz=gez=ge=g$ for every $z$. ThereforeThus transpose and uncurrying are inverse for the terminal parameter object too. This verifies the full exponential property, rather than only its endomorphism instance.

The remaining exponentials are $D^1=D$, $1^D=1$, and $1^1=1$, by the unit product law and terminality. Hence the constructed two-object category is cartesian closed and $\mathrm{End}(D)=M$.

For nontrivial $M$, the constructed $D$ is nonterminal because it has more than one endomorphism, and $e\ne 1_M$ by the absorption identity. This is the case corresponding to the forward non-preorder hypothesis.

If $M$ has one element, all the algebraic identities still hold, but splitting $e=1_M$ alone would make the original object terminal. To satisfy the literal converse's requirement of a nonterminal object, handle this case separately: take the two-object poset category $D<1$. Products are meets, $D^D=1$, $1^D=1$, $D^1=D$, and $1^1=1$, which verify the exponential adjunction on this two-element order. It is cartesian closed, $D$ is nonterminal, and its one-element endomorphism monoid is $M$. It is a preorder, so it does not recover the forward non-preorder setting or the self-exponential equality. Thus the converse's stated endomorphism realization works also in the degenerate case, while the stronger non-preorder reconstruction uses nontrivial $M$.

Assume every morphism of $\mathcal{C}$ is monic. For a representable presheaf $F=\mathcal{C}(-,A)$, the category $(1\downarrow F)$ is the category of elements, equivalently the slice $\mathcal{C}/A$. A morphism from $f:B\to A$ to $g:C\to A$ is an $h:B\to C$ satisfying $gh=f$. Since $g$ is monic, there is at most one such $h$. Thus $(1\downarrow F)$ is a preorder.

Every partial order has a total order extension. Apply Zorn's lemma to extensions ordered by inclusion: the union of a chain is a partial order. If a maximal extension leaves two elements incomparable, adjoining one comparison and taking its transitive closure of a relation creates no cycle, contradicting maximality. Quotienting a preorder by its indifference relation and lifting a total order gives a complete weak-order extension preserving its strict part.

A preorder is a well-quasi-ordering if every infinite sequence has indices $i<j$ with $x_i\le x_j$. An infinite sequence with no such pair is a bad sequence. This formulation handles combinatorial embedding relations that need not be antisymmetric on syntactic codes.