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$ – Ben Grossmann Feb 14 '17 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$ – Tanner Swett Feb 14 '17 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$ – Saaqib Mahmood Feb 14 '17 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$ – Noah Schweber Feb 14 '17 at 21:15

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$?

| cite | improve this answer | |
  • $\begingroup$ in the dictionary order, $e_i$ would precede $e_j$. Am I right? $\endgroup$ – Saaqib Mahmood Feb 14 '17 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$ – Noah Schweber Feb 14 '17 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$ – Saaqib Mahmood Feb 14 '17 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$ – Noah Schweber Feb 14 '17 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.