21
$\begingroup$

(This is a re-post of my old unanswered question from Math.SE)

For purposes of this question, let's concern ourselves only with linear (but not necessarily well-founded) order types.

Recall that:

  • $0, 1, 2, \dots$ — unique linear order types for each finite cardinality, that can be identified with natural numbers.
  • $\omega$ — the order type of $\mathbb{N}$ ordered by magnitude, the smallest infinite ordinal.
  • $\eta$ — the dense countable order type of rational numbers $\mathbb{Q}$ ordered my their magnitude, which is also an order type of any dense denumerable linear order without first and last elements (e.g. the set of positive algebraic numbers).

The sum and product of order types are natural generalizations of (and are consistent with) the sum and product of ordinals, which we consider well-known. Let's agree that a positive integer power of an order type is just a syntactic shortcut for repeated multiplication.

There are some order types satisfying $\tau^2=\tau$, for example: $0,\,1,\,\eta,\,\omega\,\eta$ and $\omega^2\eta$.

Question: Is there a linear order type $\tau$ such that $\tau^2\ne\tau$, but $\tau^n=\tau$ for some integer $n>2$?

$\endgroup$
14
$\begingroup$

Update 10/4/16: There is no such order type.

Theorem. Let $X$ be a linear order. If $X^n \cong X$ for some $n>1$, then $X^2 \cong X$.

My previous answer, which dealt with the countable case, can be found in the edit history.

For the proof, see my paper. There's an overview of the first part of the proof in these slides. In both the paper and the slides, I use the lexicographical ordering on the product of two orders.

Very roughly, the argument goes by showing that if $X^n \cong X$ for some $n>2$, then it is possible to construct an isomorphism between $X^2$ and $X$ by stitching together certain Schroeder-Bernstein style maps. It's also shown in the paper that for every $n > 1$ and cardinal $\kappa$, there exists a linear order $X$ of size $\kappa$ such that $X^n \cong X$. There are actually many such orders, with diverse structural properties.

The result surprised me. In the majority of cases when one is able to find an infinite structure $X$ (e.g. group, topological space, graph, Boolean algebra) that is isomorphic to its cube, it is possible to find such a structure such that $X \not\cong X^2$. In the rare cases when it is possible to prove $X^3 \cong X \implies X^2 \cong X$ it is usually possible to prove the significantly stronger implication $A\times B\times X \cong X \implies B \times X \cong X$, which is false for linear orders. In fact it is even possible to construct orders $A, X$ such that $A^2 \times X \cong X$ but $A \times X \not \cong X$. (The corresponding right-sided implication $X \times B \times A \cong X \implies X \times B \cong X$ is also false.)

--

Let me say what I know about the history and status of Sierpinski's other questions that bof quoted in their answer.

"We do not know so far any example of two types $\varphi$ and $\psi$, such that $\varphi^2 = \psi^2$ but $\varphi^3 \neq \psi^3$, or types $\gamma$ and $\delta$ such that $\gamma^2 \neq \delta^2$ but $\gamma^3 = \delta^3$."

Sierpinski knew of examples of non-isomorphic orders $X, Y$ whose squares are isomorphic. These examples are due to A.C. Morel and were generalized by Sierpinski. They have the property that not only is $X^2 \cong Y^2$ but in fact $X^n \cong Y^n$ for all $n>1$. Sierpinski's first question is whether the former condition actually implies the latter, or if there exist two orders whose squares are isomorphic but cubes are not.

Morel's examples show that linear orders need not have unique $n$th roots, that is, that $X^n \cong Y^n \implies X \cong Y$ is false over the class of linear orders for any fixed $n > 1$. However, the examples do not prove the falsity of the implication $X^n \cong Y^n \implies X^k \cong Y^k$ for $1 < k < n$. Sierpinski's second question is whether there is a counterexample when $n = 3$ and $k = 2$. Both of these questions remain open, to my knowledge.

"We do not know whether there exist two different denumerable order types which are left-hand divisors of each other."

Sierpinski was aware of distinct uncountable orders that are left-hand divisors of each other. It turns out the uncountability is necessary. This falls out of some of the work in the paper. A proof is given in the final section. (Sierpinski used the traditional anti-lexicographical ordering on products, so left-handed divisor for him is right-handed divisor in the convention of the paper.)

"Neither do we know whether there exist two different order types which are both left-hand and right-hand divisors of each other."

As already mentioned, Sierpinski was aware of distinct orders $X_0, Y_0$ that are left-hand divisors of one another. He also knew of distinct orders $X_1, Y_1$ that are right-hand divisors of one another. It is natural to ask if there are distinct orders $X, Y$ that divide each other on both the left and right.

As bof points out in their answer, if there were an order $X$ isomorphic to $X^3$ but not $X^2$, then the pair $X, X^2$ would give a positive answer. There is no such $X$, however, the answer to Sierpinski's question is still positive. The construction requires some work, and I do not yet have a writeup ready. The fact that such orders exist in some sense says that the implication $X^3 \cong X \implies X^2 \cong X$, while true for linear orders, is close to being false.

$\endgroup$
  • $\begingroup$ Garrett, I think I've lost confidence in the comments I had made at math.SE, since I no longer see why the forcing to make $\tau$ countable should not also create an isomorphism from $\tau$ to $\tau^2$. So I'm no longer certain whether the question is equivalent in the countable case or not. $\endgroup$ – Joel David Hamkins Nov 23 '13 at 14:12
  • $\begingroup$ I'm reading your answer, but I am a bit confused in some places. Have you reversed the usual meaning of $\times$ on linear orders? That is, usually $\alpha\times\beta$ means $\beta$ copies of $\alpha$, but in your remarks on $\eta_i\times L_i$, it seems that you intend the other order. $\endgroup$ – Joel David Hamkins Nov 23 '13 at 14:36
  • $\begingroup$ Joel, you're quite right. I was thinking of $\times$ as being lexicographic from the left while writing my answer. Hopefully now it reads correctly $\endgroup$ – Garrett Ervin Nov 23 '13 at 19:57
  • $\begingroup$ One thing I'm confused about -- why does the $\overline{s_i}$ all having order type $\eta$ imply that their union does? It doesn't seem that in general a countable union of things of order type $\eta$ again does; for instance, suppose you had $S=A+B+C+D$, where $A\cong D\cong \eta$, $B\cong \eta+1$, and $C\cong 1+\eta$. Then $A+C\cong B+D\cong \eta$, but $S$ itself fails to be dense. (Also, a nitpick: I don't see why $\overline{s}$ will be countable -- unless you meant to restrict to when $I_s\ne\emptyset$. But adding that restriction fixes that, I think.) $\endgroup$ – Harry Altman Nov 24 '13 at 0:28
  • 2
    $\begingroup$ Harry: every $\bar{s}$ is countable: for $s \in \beta^{\omega}$, $\bar{s}$ is the set of sequences of the form $r^{\frown}s'$, where $r \in \beta^{<\omega}$ and $s'$ is some tail sequence of $s$. There are only countably many $r$ (since $\beta$ is countable), and countably many $s'$. On your first comment: you're right, that sentence is unclear. The point is that each $\bar{s}$ is dense in $\beta^{\omega}$. In particular, if $a, b \in S = \cup_i \overline{s_i}$ and $a < b$ then there are $c, d, e \in S$ (we may even take $c, d, e$ all from $\bar{s_0}$) s.t. $c<a<d<b<e$. So $S \cong \eta$. $\endgroup$ – Garrett Ervin Nov 24 '13 at 1:42
6
$\begingroup$

[This partial answer was posted Nov. 19 to Math Stack Exchange but seems to have been ignored there. It seems to be a more concise version of the easy case (no endpoints) of Garrett Ervin's answer.]

Such questions have been considered in the past. From W. Sierpiński's Cardinal and Ordinal Numbers, second edition revised, Warszawa 1965, p. 235: "We do not know so far any example of two types $\varphi$ and $\psi$, such that $\varphi^2=\psi^2$ but $\varphi^3\ne\psi^3$, or types $\gamma$ and $\delta$ such that $\gamma^2\ne\delta^2$ but $\gamma^3=\delta^3$. Neither do we know any type $\alpha$ such that $\alpha^2\ne\alpha^3=\alpha$." Also, from p. 254: "We do not know whether there exist two different denumerable order types which are left-hand divisors of each other. Neither do we know whether there exist two different order types which are both left-hand and right-hand divisors of each other." Of course, if $\tau^n=\tau$ for some integer $n\gt2$, then $\tau^2$ and $\tau=\tau^2\tau^{n-2}=\tau^{n-2}\tau^2$ are both left-hand and right-hand divisors of each other.

For what it's worth, here is a partial answer to your question, for a very special class of order types. By "order type" I mean linear order type. An order type $\xi$ is said to have a "first element" if it's the type of an ordered set with a first element, i.e., if $\xi=1+\psi$ for some $\psi$; the same goes for "last element".

Proposition. If $\alpha$ is a countable order type, and if $\alpha\xi=\alpha$ for some order type $\xi$ with no first or last element, then $\alpha\beta=\alpha$ for every countable order type $\beta\ne0$.

Corollary. If $\tau$ is a countable order type with no first or last element, and if $\tau^n=\tau$ for some integer $n\gt1$, then $\tau^2=\tau$.

The corollary is obtained by setting $\alpha=\beta=\tau$ and $\xi=\tau^{n-1}$ in the proposition.

The proposition is proved by a modified form of Cantor's back-and-forth argument. Namely, let $A$ be an ordered set of type $\alpha=\alpha\xi$, and let $B$ be an ordered set of type $\alpha\beta=\alpha\xi\beta$. Since $A$ and $B$ are countable sets, let's fix an enumeration of each set.

An isomorphism between $A$ and $B$ will be constructed as the union of a chain of partial isomorphisms $f_k$ of the following form. The domain of $f_k$ is $I_1\cup I_2\cup\dots\cup I_k$, where $I_1,\dots,I_k$ are intervals in $A$ of order type $\alpha$; $I_1\lt\dots\lt I_k$; the interval in $A$ between $I_j$ and $I_{j+1}$ ($1\le j\lt k$), as well as the interval to the left of $I_1$ and the interval to the right of $I_k$, have order types which are nonzero right multiples of $\alpha$. The range of $f_k$ is $J_1\cup\dots\cup J_k$ where $J_1,\dots,J_k$ are intervals in $B$ of type $\alpha$, etc. etc. etc., and $f(I_1)=J_1,\dots,f(I_k)=J_k$.

Here is an informal description of the induction step. Suppose we have defined $f_k$ etc. as described above. Let $x$ be the first point in the enumeration of $A$ which is not in the domain of $f_k$, say $I_1\lt x\lt I_2$. The gap between $I_1$ and $I_2$ is of order type $\alpha\gamma$ for some order type $\gamma\gt0$. Since $\alpha\xi=\alpha$, we have $\alpha\gamma=\alpha\xi\gamma=\alpha\theta$ where $\theta=\xi\gamma$ is a nonzero order type with no first or last element. That is, the gap between $I_1$ and $I_2$ is the linear sum of a $\theta$-type set of intervals of type $\alpha$, and $x$ is in one of those intervals, let's call it $I$. Note that the gap between $I_1$ and $I$, as well as the gap between $I$ and $I_2$, has an order type which is a nonzero right multiple of $\alpha$. Choose an interval $J$ between $J_1$ and $J_2$ in the same way, except that there is no particular point to be covered. Extend $f_k$ to $f_{k+1}$ so that $I$ is mapped isomorphically onto $J$.

$\endgroup$
  • $\begingroup$ bof, I may misunderstand your argument, but why for example can you guarantee that the interval between $I_j$ and $I_{j+1}$ will always contain a copy of $\alpha$? If, say, $\xi = \mathbb{Z}$, then in your proof we would be constructing an isomorphism between $\alpha = \alpha \times \mathbb{Z}$ and $\alpha \times \beta$. Might we have chosen our intervals so that for some $n \in \mathbb{Z}$ we have $I_1 =$ the $n$th copy of $\alpha$ in $\alpha \times \mathbb{Z}$, and $I_2 =$ the $(n+1)$st copy of $\alpha$ in $\alpha \times \mathbb{Z}$? Then interval between $I_1$ and $I_2$ would be empty. $\endgroup$ – Garrett Ervin Nov 25 '13 at 23:40
  • $\begingroup$ @GarrettErvin My argument was terse, perhaps to the point of being cryptic. The intervals are defined inductively, and at each step we make sure that the newly chosen interval has room on both sides, the o.t. of the gap being a "nonzero right multiple of $\alpha$". Note that any nonzero right multiple of $\alpha$ can be expressed in the form $\alpha\theta$ where $\theta$ has no first or last element; this is because $\alpha\theta=\alpha\xi\theta$ and $\xi\theta$ has no first or last element. This is why the new interval can be chosen without crowding the old intervals. $\endgroup$ – bof Nov 26 '13 at 0:20
  • $\begingroup$ bof, I'm still a bit confused. In the usual back-and-forth argument one fixes an enumeration of the intended domain and range beforehand, to ensure that the $f$ you construct ends up being total. I agree that if you enumerate the $I_j$ inductively as you suggest, by splitting up multiples of $\alpha$ into multiples of $\alpha \xi$ when necessary, you can ensure at every finite stage there will be space between consecutive intervals. But how then do you guarantee that the intervals $\{I_j\}_{j \in \omega}$ you end up with cover $\alpha$ (or, equivalently, that the $f$ you construct is total)? $\endgroup$ – Garrett Ervin Nov 26 '13 at 22:30
  • $\begingroup$ @GarrettErvin Yes, we start by choosing enumerations of $A$ and $B$. I didn't think to mention then, I was only trying to describe how I modified the usual back-and-forth, namely, that the domain and range at each stage is a finite union of intervals instead of a finite set of points. Is your question about how to extend the partial isomorphism $f_k$ so as to cover a given point of $A$ or $B$? $\endgroup$ – bof Nov 27 '13 at 2:33
  • $\begingroup$ Ah, I see. I understood you to be enumerating only intervals, without any reference to the underlying points. That's a nice argument. It seems to go through similarly for any order $\alpha$ without endpoints of size $\kappa$, where $\kappa$ is regular, assuming that $\alpha$ has no cofinal sequences in either direction of length less than $\kappa$. $\endgroup$ – Garrett Ervin Nov 27 '13 at 10:35

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.