4
$\begingroup$

Can some finite groups be well ordered in a "meaningful" way? I mean, it is clear that we can trivially find a bijection between $\{1,...,n\}$ and a finite group $G$ with $n$ elements, but I am interested in well ordering that are based on some scheme or pattern with respect to some group property (for example, it is immediate to well-order a cyclic group).

  • 5
    How is it immediate to well-order a cyclic group? If you mean the ordering "identity, generator, square of generator, ...", then which of the many generators will you choose?2012-06-07
  • 0
    You can obtain $n-1$ different wos, isn't it?2012-06-07
  • 3
    Other than the trivial group, there is no well-ordering on any finite group in a way that makes the group operation order-preserving. (Obvious.)2012-06-07

5 Answers 5

6

A finite group has a finite number of generators, which you can name $a,b,c,\dots$ (or $a_1,a_2,\dots,a_r$ for some $r$). Then you can write every group element as a word in the generators; among the many expressions for any given group element, consider only those of minimal length, and among those, pick the one that's lexicographically first. Then order the $n$ resulting expressions lexicographically.

A lot of choices to make along the way, so there's nothing canonical here, but that didn't seem to bother you for cyclic groups, so perhaps you'll accept it here, too.

  • 0
    This is crazy!! Well, +1 for the moment, waiting for further contributions...2012-06-07
  • 2
    This is a lot less crazy than you think - this is one of the key ideas behind algorithms for (infinite) _automatic_ groups, where there's a fast (linear in the size of the words) algorithm for computing the lexicographically first representation of the product of two words of the group. This can be useful, for instance, in doing calculations in some symmetry groups.2012-06-07
5

I'm not sure what you want but you cannot have an order that respects the group operation in the sense that $a

Indeed, suppose $1a$.

  • 0
    I am interested in more exotic ways to yield an order.2012-06-07
3

If you are prepared to represent the group as a permutation group on $\{1,...,n\}$, then the stabilizer chain produced by the Schreier-Sims algorithm leads to a fairly natural order (though of course the permutation representation itself is not canonical).

That is, given $\Delta\subseteq \{1,...,n\}$, let $G_{\Delta}$ be the pointwise stabilizer of $\Delta$ in $G$. Then there is a stabilizer chain:

$G = G_{\{\}} \supseteq G_{\{1\}} \supseteq G_{\{1,2\}} \supseteq ... \supseteq G_{\{1,...,n-1\}} \supseteq G_{\{1,...,n\}} = 1$.

Given some link $G_{\{1,...,i\}} \supseteq G_{\{1,...,i+1\}}$ in the chain, the cosets of $G_{\{1,...,i+1\}}$ in $G_{\{1,...,i\}}$ can be ordered by their action on i. This extends to an order on the whole group.

For example, $S_{3}$ would be ordered as: 1, (23), (12), (123), (13), (132).

First, the elements that send 1 to 1, then the elements that send 1 to 2, finally the elements that send 1 to 3. So these are the three cosets of $G_{\{1\}}$. Then, within the coset $(13)G_{\{1\}}$ (for example), we order recursively using the same order relation.

  • 0
    What do you mean exactly when you say: "if you are prepared to represent the group as permutation group on $\{1, \dots ,n\}$?2012-06-07
  • 0
    @Oo3 Well, many finite groups arise as permutation groups on {1,...,n} (eg the symmetric, alternating, and dihedral groups). Still others have natural permutation actions on small sets (eg PGL(n,Fq)), so we just have to decide on a way to number the small set. Every finite group can be represented as a permutation group - it acts on itself by multiplication on the right. However, in this case, we would already need to have decided on a numbering of the group elements, which defeats the point.2012-06-07
  • 0
    One nice thing about this answer (other than it is actually used by gap) is that it replaces a large enumeration problem (the whole group) to a series of smaller ones (cosets of k+1 point stabilizer inside a k point stabilizer). In other words, you are just labeling the cosets with {1...n} instead of the group elements. There are many problems that become simpler when considered over a chain of subgroups than when just looking at the entire group.2012-06-08
2

The most meaningful way to well-order a finite group would be in such way that the addition coheres with the order. However no finite group can be ordered, since $$1


The above shows that you cannot take an order which respects the group operation on a finite group. To the question "more exotic" one has to think about, and note that every finite set can be given several (possibly interesting) different group structures. In fact, if I have a set $\{a,b,c\}$ then there are several ways in which it can be made into $\mathbb Z/3\mathbb Z$.

We do not have a canonical way of choosing a group structure on a set. Once there are very arbitrary choices there is no real way to generate interesting well orders. If you agree that a canonical way would be to take a group of a finite cyclic group then you still have to ask yourself which element of your set is $1$.

Once you agreed which element is $1$ then there is one reasonable way of choosing an enumeration of the group, namely $n\cdot 1$. However this is still very arbitrary.

  • 0
    I beat you to it... :-)2012-06-07
  • 0
    Yes, and I have to go teach now... so you have time to beat me again!2012-06-07
  • 0
    Who's counting?2012-06-07
  • 0
    Well, combinatorialists count. In particular [Cameron counts](http://cameroncounts.wordpress.com/) :-)2012-06-07
  • 0
    I believe that if you just take into account addition and order that go together, then my question would have had not make any sense.2012-06-07
  • 0
    @Oo3: This is not 'just those two' this means that if you take *at least* an order and operation you get a contradiction. So there is no point in taking *more* constraints.2012-06-07
  • 0
    @AsafKaragila: Thanks for the profound answer. Well, I see what you say. But in finiteness, I see no real arbitrariness than choosing several elements and see what they produce.2012-06-07
  • 0
    @Oo3: Please give me a *good* reason why $a$ is the neutral element of a group structure on $\{a,b,c\}$... :-)2012-06-07
  • 0
    I was not talking about this point. But... if you just want to know it... then say why not? :D2012-06-07
  • 0
    @Oo3: Then why not $b$ or $c$? This is an arbitrary choice. You cannot avoid it, even for finite things. From this follows that even a well-order of a finite set requires arbitrary choices. This is also why without the axiom of choice there can be a sequence of disjoint *pairs* without a choice function. Finite choice is still arbitrary, it's just definable and therefore it exists.2012-06-07
  • 0
    @AsafKaragila: Semantically, I see no choice in what you say. If you say that one has to be 1, then it is immaterial what name you choose for it. I believe that choice has nothing to do with it, imho.2012-06-07
  • 0
    @Oo3: Take three people you find from the street, and without talking to them assign one to supervise the others. Did you make *any* choice, or was this choice immaterial? Of course this analogy does not go very far, since different people come with different skills. However the point I am trying to make is the same, this is not just about the name. This is about the fact that given three completely arbitrary objects in the mathematical universe you have no uniform way to assign them a group structure without making a very arbitrary choice which of them is going to be $0$, and so on.2012-06-07
1

The comment was too short, so I'm posting this as an answer.

Well order implies some linear structure so I don't see any meaningful orderings for groups other than cyclic (see Cayley graphs). For example you could take a group in which there are two (or even more) different elements that behave in the same way, e.g. $(0,1)$ and $(1,0)$ in $\mathbb{Z}_2\times\mathbb{Z}_2$, or generators of non-cyclic free group.

Note, that this is also the case also for cyclic groups, e.g. if $a$ is the generator, then is $a^{-1}$ too. In a way, they are symmetric, and any well order would destroy that.

On the other hand, I think that there are many well-founded partial orders that could apply here, and if you wish, you could make them total (by something like topological sorting). Moreover, this would actually correspond to the fact that you choose one element over the other (and thus destroy the symmetry).

Hope that helps ;-)