If $A_1, \ldots, A_n$ are well ordered sets, then so is the Cartesian product $\prod_{i=1}^n A_i$ under the dictionary order. Am I right?

Is this finite product also well ordered in the anti-dictionary order?

Now suppose that $J$ is an infinite set of indices, and suppose $\left\{ A_\alpha \right\}_{\alpha \in J}$ is a collection of well ordered sets. Then is the set $$A \colon= \prod_{\alpha \in J} A_\alpha$$ also well ordered in the dictionary order? under the anti-dictionary order?

If so, then how to prove this rigorously?

If not, then how to construct a counter example?

  • $\begingroup$ What is the anti-dictionary order? $\endgroup$ Feb 14, 2017 at 20:56
  • $\begingroup$ I think this depends on the ordering given for $J$. Depending on how you order $J$, the sequence $BAAAAA\ldots, ABAAAA\ldots, AABAAA\ldots, \ldots$ may be a counterexample. $\endgroup$ Feb 14, 2017 at 21:01
  • 1
    $\begingroup$ @Omnomnomnom the anti-dictionary order is defined as follows: Let $\left(A_1, <_1 \right), \ldots, \left(A_n, <_n \right)$ be ordered sets, and let $A$ be their Cartesian product. Then the order $<$ defined on $A$ as follows: $\left( x_1, \ldots, x_n \right) < \left( y_1, \ldots, y_n \right)$ if $x_i < y_i$ for some $i$ and $x_j = y_j$ for every $j > i$. There is some exercise in Munkres about this order as well. Maybe I can dig it up for you later. $\endgroup$ Feb 14, 2017 at 21:12
  • $\begingroup$ @SaaqibMahmuud So it's just the dictionary order on the product $(A_n, <_n), . . . , (A_1, <_1)$ (that is, reverse the order of the factors)? $\endgroup$ Feb 14, 2017 at 21:15

1 Answer 1


The result does not hold for infinite products.

Here's a counterexample: take each $A_i$ to be $\{0, 1\}$ ordered the usual way, $i\in\mathbb{N}$. Then let $e_i$ be the string with a $1$ in the $i$th place and a $0$ everywhere else; what can you say about $e_i$ versus $e_j$ if $i<j$?

Also, it's worth noting that the dictionary order doesn't really make sense if $J$ isn't well-ordered: how else do you know that "the first place where $F$ and $G$ disagree" even exists, if $J$ isn't well-ordered?

For a concrete example of this, consider $J=\{. . . , -3, -2, -1, 0\}$ and let $A_i=\{0, 1\}$ (ordered as usual) for each $i\in J$. Now consider the sequences $$F=( . . . , 0, 1, 0, 1),\quad G=( . . . , 1, 0, 1, 0).$$ Is $F<G$ or is $G<F$?

  • $\begingroup$ in the dictionary order, $e_i$ would precede $e_j$. Am I right? $\endgroup$ Feb 14, 2017 at 21:15
  • 2
    $\begingroup$ @SaaqibMahmuud No: $(1, 0, 0, ...)>(0, 1, 0, . . .)$ since at their first point of disagreement, $1$ is bigger than $0$. $\endgroup$ Feb 14, 2017 at 21:16
  • $\begingroup$ oh yes, you're right. Sorry. Yes, I now do understand that the set of all the $e_i$ is non-empty but has no smallest element. What about the anti-dictionary order? $\endgroup$ Feb 14, 2017 at 21:18
  • 2
    $\begingroup$ @SaaqibMahmuud In the antidictionary order, the product isn't even linearly ordered: there's no way to compare elements in general! Which is smaller, $(0, 1, 0, 1, . . . )$ or $(1, 0, 1, 0, . . . )$? You look for the "last" point of disagreement, but there isn't one. This is basically the counterexample in the second part of my answer. $\endgroup$ Feb 14, 2017 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.