Let $(A, \leq)$ and $(B, \leq)$ two better-quasi-orderings and let $(A \times B, \leq)$ an ordering such that $(a, b) \leq (a', b')$ iff $a \leq a'$ and $b \leq b'$.
Is $(A \times B, \leq)$ a better-quasi-ordering?
Background:
Better-quasi-orderings are often used in place of well-quasi-orderings because they are more "robust" in the sense that when we combine bqos, the resulting qo is often again a bqo. For example, (Marcone, 2001) has shown that if $(A, <)$ is a bqo, then $(2^A, <)$ is a bqo (this is not true for wqos).
Some other known properties (shown by Abdulla, 2010):
- Each bqo is a wqo.
- If $A$ is finite , then $(A, =)$ is a bqo.
- If $(A, \leq)$ is a bqo, then $(A^*,\leq^*)$ is a bqo (where $A^*$ is the set of finite words over $A$ and $\leq^*$ is the monotone domination order)
- If $(A, \leq)$ is a bqo, then $(A^\circ, \leq^\circ)$ is a bqo (where $A^\circ$ are the multisets over $A$).
On the other hand, (Higman, 1952) and (Kruskal, 1960) have shown that the Cartesian product of a finite number of wqos is a wqo.
However, I have not found anything regarding the Cartesian product of bqos, leading to the question at the top.
Motivation
I have a transition system with infinite paths and I want to show that it is decidable whether a certain state can be reached. The standard approach is based on well-structured transition systems (Finkel & Schnoebelen, 2001): If we can define a wqo on the states of the transition system, then (with some additional constraints) it is decidable whether some subset of states is reachable in the system. In my case, the states consist of the powerset of the cartesian product of possibly infinite sets, each of them having a bqo. If I know that the cartesian product is also a BQO, then using (Marcone, 2001), I can show that the ordering of the states is also bqo and hence wqo, which allows me to apply the theorem.
References
- Marcone, A. (2001). Fine Analysis of the Quasi-Orderings on the Power Set. Order, 18(4), 339–347. https://doi.org/10.1023/A:1013952225669
- Abdulla, P. A. (2010). Well (and Better) Quasi-Ordered Transition Systems. Bulletin of Symbolic Logic, 16(4), 457–515. https://doi.org/10.2178/bsl/1294171129
- Higman, G. (1952). Ordering by Divisibility in Abstract Algebras. Proceedings of the London Mathematical Society, s3-2(1), 326–336. https://doi.org/10.1112/plms/s3-2.1.326
- Kruskal, J. B. (1960). Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi’s Conjecture. Transactions of the American Mathematical Society, 95(2), 210–225. https://doi.org/10.2307/1993287
- Finkel, A., & Schnoebelen, Ph. (2001). Well-structured transition systems everywhere! Theoretical Computer Science, 256(1), 63–92. https://doi.org/10.1016/S0304-3975(00)00102-X