MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is well known that if $(P, \leq)$ is a partial order then $\leq$ can always be extended to a linear order. This is sometimes called Szpilrajn´s theorem although it had been previously proved by Banach, Kuratowski and Tarski.

Now suppose that $f$ is an automorphism of $(P, \leq)$ and we want to extend $\leq$ to a linear order in such a way that $f$ remains an automorphism. Of course, this is not always possible since $f$ could have a finite orbit and automorphisms of linear orders can´t have finite orbits; but I wonder if this is the only obstruction. So let $A$ be the collection of all those $f$´s for which it is possible (for instance $Id_P \in A$); here are my questions:

1) Is it true that If $f$ has no finite orbits then $f \in A$?

2) Is $A$ a subgroup of $Aut(P, \leq)$?

and the vaguer

3) If the answer to 1 is negative. Can we somehow characterize the elements of $A$?

Perhaps this is all well known and studied but I couldn´t find anything at all in the literature, so references are also appreciated.

share|cite|improve this question
up vote 4 down vote accepted

I couldn't find anything in the literature either, but the answer to the first question is positive. Let $G$ be a group acting on a space $X$. Say that $G$'s action on $X$ has the invariant order-extension property provided that every $G$-invariant partial order on $X$ (i.e., partial order $\le$ such that $x\le y$ iff $gx\le gy$, for each $g\in G$) extends to a $G$-invariant linear order on $X$.

I managed to show:

Theorem. The following are equivalent for an abelian group $G$:

  1. $G$'s action on $X$ has the invariant order extension property.
  2. $X$ has a linear $G$-invariant order.
  3. No element of $G$ has an orbit of finite size greater than one.

Here's the proof.

The answer to Question 1 follows by letting $G$ be the subgroup of permutations generated by $f$.

(By the way, I assume that your no-finite-orbits condition really means: no finite orbits of size greater than one. Fixed points aren't a problem.)

share|cite|improve this answer
Thank you Alexander. The MO question that you mention should be easy to answer now by taking first an appropiate quotient. – Ramiro de la Vega Sep 14 '13 at 20:45
That's the plan. I'm working on it now. – Alexander Pruss Sep 14 '13 at 20:58

The answer to question $2$ is negative. Let $P$ be any infinite set and let $\leq$ be the trivial partial order on $P$. In other words, $x\leq y\Rightarrow x=y$. Then $A$ is the set of all bijections from $P$ to $P$ with no finite cycles. If $f:P\rightarrow P$ has no finite cycles, then let $C$ be the partition of $P$ into its cycles. Give $C$ a total order $\preceq$. Finally, linearly order $P$ by letting $x\preceq y$ if i$x\in R\in C,y\in S\in C$ and $R\preceq S$ or where $f^{n}(x)=y$ for some $n>0$. Then $f$ is an automorphism of $(P,\preceq)$.

On the other hand, $A$ is generally not a subgroup of $Aut(P,\leq)=Sym(A)$. If $P=\mathbb{Z}$ and $f,g:\mathbb{Z}\rightarrow\mathbb{Z}$ are the maps where $f(x)=x+2$ for all $x$ and $g(x)=x+1$ whenever $x$ is even and $g(x)=x-1$ whenever $x$ is odd, then $f^{-1}g,f\in A$, but $ff^{-1}g=g\not\in A$.

share|cite|improve this answer
Thanks Joseph for a nice example. – Ramiro de la Vega Sep 12 '13 at 17:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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