MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Suppose a group $G$ acts faithfully on a set $X$, or equivalently, $G$ is a subgroup of ${\rm Sym}(X)$.

By functoriality, $G$ acts on $P(X), P(P(X)), P(P(P(X))),$ etc. ($P(\cdot)$ means powerset.) Henceforth, I'll omit parentheses.

One can recover $G$ from ${\rm Fix}_G(PPPX)$ because, for example, one can encode a well-ordering of $X$ as an element of $PPX$.

Generally, one cannot recover $G$ from ${\rm Fix}_G(PPX)$. For example, the alternating group and symmetric groups on a finite set will give the same set of fixed elements.

Write $G\sim H$ if both groups act on $X$ and ${\rm Fix}_G(PPX) = {\rm Fix}_H(PPX)$. Equivalently, $$\forall u,v \subset X (\exists g\in G, gu=v \leftrightarrow \exists h\in H, hu=v) \ .$$


When does $G\sim H$ imply $G=H$?

Are there nontrivial examples of $G\sim H$ for infinite $X$? for $X$ of any infinite cardinality?

Is there a classification of such pairs for finite $X$?

Does this phenomenon have a name?

Can one always recover $G$ from ${\rm Fix}_G(PPPX)$ in ZF?

share|cite|improve this question
You assume that $H$ acts on the same set $X$ (it's clear after reading but you might say it). – YCor Oct 25 '12 at 23:23
For instance $G\sim Sym(X)$ iff $G$ is transitive on subsets of the same cardinal with complements of the same cardinal. For $X$ finite but large this implies a kind of multitransitivity I'd guess should imply that $G$ is the symmetric or alternating group. I'm curious whether for $X$ infinite it implies $G=Sym(X)$. On the the other hand the finitary symmetric group on $X$ infinite has the same orbits on the power set as the alternating group, so this it at least one example for your second question (assuming you call this nontrivial). – YCor Oct 25 '12 at 23:32
Thanks Yves, yes, I should have pointed that out. – David Feldman Oct 26 '12 at 0:01
>I'm curious whether for $X$ infinite it implies $G={\rm Sym}(X)$. I wonder what happens if you fix a transposition $t$, then zornify to get a subgroup of ${\rm Sym}(X)$ maximal with respect to omitting $t$. – David Feldman Oct 26 '12 at 0:19
@Will What do you mean? $Fix_G(Y)$ is by definition the set of points in $Y$ fixed by all $g\in G$. So $Fix_G(PY)$ is the set of $G$-invariant subsets of $Y$. Thus $Fix_G(PY)=Fix_H(PY)$ iff $G$ and $H$ have the same orbits on $Y$. Applying this to $X=PY$, you get that $Fix_G(PPX)=Fix_H(PPX)$ iff $G$ and $H$ have the same orbits on $PX$. – YCor Oct 27 '12 at 19:13

In the case of a finite group $G$, a lot can be said by looking at $Fix_G(PPX)$, as it includes information on primitivity of the action on $X$, etc. E.g. if $G$ is doubly transitive on $X$, one can list all the possible examples of $H$ equivalent to $G$ using the classification of finite simple groups.

More generally, for primitive groups, one can use O'Nan-Scott theorem to partition such groups into few relatively well-understood classes, and, hopefully, derive the list you are looking for. As a toy example, consider $G\cong S_5$ acting on the set $X$ of pairs of {1,...,5}. There are just two nontrivial invariant graphs on $X$, the Petersen graph, and its complement. $G$ is the automorphism group of the Petersen graph, thus $H$ must be a subgroup of $G$. It follows by inspection that the only $H\neq G$, $G$~$H$ is (EDIT: actually, it could be that this $H$ is distinguished from $G$ by other orbits on sets, this still needs to be checked!) the index 2 subgroup in $G$, isomorphic to $A_5$.

For imprimitive groups, probably there is a reduction to the primitive case. (And needless to say, intranisitive case reduces to the transitive.)

share|cite|improve this answer

The group of pwop (piecewise order-preserving) permutations of $\mathbf{N}$ is equivalent to the full symmetric group (i.e., has the same orbits on the power set $2^\mathbf{N}$. These are permutations for which there's a finite partition such that on every component, the permutation is order-preserving. It is transitive on moieties (infinite subsets with infinite complement) and obviously is also transitive on finite subsets of given cardinality. You can google "transitive on moieties" to find more.

share|cite|improve this answer
So on ${\Bbb Z}$ piecewise betweenness-preserving permutations give another example, right? – David Feldman Oct 27 '12 at 16:23
Yes, it seems so (betweenness-preserving, as I can guess, means piecewise (order-preserving or order-reversing)). It also seems that one more example is $H_1\simeq H_2$, where $H_1$ is the group of pwop permutations of $\mathbf{Z}$, and $H_2$ is the group of permutations $g$ of $\mathbf{Z}$ commensurating the subset $\mathbf{N}$, i.e. such that $g\mathbf{N}\Delta\mathbf{N}$ is finite. (Note that $H_1\subset H_2$.) – YCor Oct 27 '12 at 17:33

Since posting my question, I've thought of a general way to get examples, which I'll merely illustrate. Take $X={\Bbb N}\times {\Bbb N}$, say. Consider for the moment the group of permutations, a wreath product, each having the form $$p((x,y))=(f(x),g(x,y))\ .$$ For $G$ further restrict allowing any permutation $f$ but making $y\mapsto g(x,y)$ always finitary alternating; for $H$ merely insist on having $y\mapsto g(x,y)$ finitary.

Then $G\subset H$ properly, but they fix the same elements of $PPX$. $|G|=|H|=c$ and neither group is transitive on sets of a given cardinality and cocardinality.

One could enlarge $G$ and $H$ by including permutations that agree with these up to finitely many elements or up to finitely many rows (first coordinate determines the row). Thus we get examples where the action doesn't preserve an equivalence relation.

For a different example, we could make $f$ finitary alternating (for $G$) or merely finitary (for $H$) but put no restrictions on $g$.

share|cite|improve this answer

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.