Let $X$ be an infinite set, and $k \ge 1$ be a natural number. We work without the axiom of choice.

Let $G_0$ be the full symmetric group on $X$, and let $G_1$ be the full symmetric group on ${\cal P}(X)$, the power set of $X$. Both these groups act on ${\cal P}^k(X)$ (the $k$-fold power set $\mathcal{P}(\mathcal{P}(\cdots(X)\cdots)$ of $X$) in a natural way, with $G_0$ a subgroup of $G_1$. So in ${\cal P}^k(X)$ the orbits of $G_1$ split into orbits of $G_0$.

Is the following true in ZF: for all $k\ge 1$, for all distinct elements $a\neq b$ of ${\cal P}^k(X)$ that belong to the same $G_1$-orbit, there exists $\sigma \in G_1$ such that $\sigma(a)$ and $\sigma(b)$ belong to distinct $G_0$-orbits?

A positive result would have nice consequences for the model theory of Russell-Ramsey typed set theory, but I'll say nothing about that for the moment!

  • $\begingroup$ What does $k >> 1$ stand for? $\endgroup$ Nov 17, 2018 at 15:34
  • $\begingroup$ Also, if you could make the part about "fissioning" a bit more explicit, that would be quite helpful. $\endgroup$ Nov 17, 2018 at 15:36
  • $\begingroup$ Means $k$ much bigger than 1. I actually want it to hold for arbitrarily large $k$. fissioning' is a synonym of splits'. Sorry. Thank you for your attention to this question! tf $\endgroup$ Nov 17, 2018 at 15:38
  • 6
    $\begingroup$ By the way, your post would benefit of some streamline: remove the 1st paragraph, remove the confusing sentence "Clearly, we cannot expect them to...". Ask more concisely and then add comments if they can help understanding the question, put some context, or point out some difficulty/trap, etc. $\endgroup$
    – YCor
    Nov 17, 2018 at 16:45
  • 2
    $\begingroup$ One more instance of missing context is "put all thought of axiom of choice out of your mind". In standard language this translates as "We work without the axiom of choice." And this raises the question what occurs assuming AC. If it's obviously yes, you should have written it. Otherwise, the question should certainly first be solved assuming AC, to set up ideas. $\endgroup$
    – YCor
    Nov 18, 2018 at 10:59

1 Answer 1


Here's a comment (no longer an answer) about the case $k=2$, assuming the axiom of choice, and in particular assuming that $X$ is presented in one-on-one correspondence with some cardinal. Perhaps this can be generalized substantially.

Now $a,b\in{\cal P}^2(X)$ are in the same $G_1$ orbit iff they have the same cardinality. [Update: their complements should also have the same cardinality, and the construction below assumes infinite complements.] So for this case, we want to know: Given $a,b\subset {\cal P}(X)$ of the same infinite cardinality, are there sets $c,d\subset {\cal P}(X)$ of that same cardinality but in different $G_0$ orbits?

The answer to that question is yes. For $S\in{\cal P}(X)$, let \begin{align} f(S)&=\{s+4:s\in S\}\cup\{1,2,3\}\\ c&=\{f(S):S\in a\}\cup \{\{1,2\},\{2,3\},\{3,1\}\}\\ d&=\{f(S):S\in b\}\cup \{\{1\},\{2\},\{3\}\} \end{align} Clearly $a,b,c,d$ are all of the same cardinality, and:

  • i) $\exists x\in X$ which appears in all but one element of $c$.
  • ii) $\nexists x\in X$ which appears in all but one element of $d$.

These properties are invariant under $G_0$ actions, so $c$ and $d$ are in different $G_0$ orbits.

  • $\begingroup$ The same should work for all $k$ too, no? I mean, take two copies of the same leveled forest of height $k-1$ and let them grow differently to the $k$th level (differently means having, say, all cardinalities of all new branches just pairwise different) $\endgroup$ Nov 18, 2018 at 3:41
  • $\begingroup$ I assume so, but I don't trust my ability to visualize or reason informally about $\cal{P(P(P(X)))}$. $\endgroup$
    – user44143
    Nov 18, 2018 at 3:53
  • $\begingroup$ Mmm actually I oversimplified - in general one has leveled graphs that are not necessarily forests. But still I believe such a graph faithfully represents an element of $\mathcal P^k(X)$. Given one such, say $\mathfrak S$, place its elements on the bottom level, elements of $\bigcup\mathfrak S$ above them, elements of $\bigcup\bigcup\mathfrak S$ above those, etc. The relation is just $\ni$. Any embedding of the top level of every such height $k$ leveled graph into $X$ then determines an element of $\mathcal P^k(X)$ provided any two nodes at any level have distinct successor sets above them. $\endgroup$ Nov 18, 2018 at 4:41
  • $\begingroup$ Yes, k=2 is easy because, as you say, two things belong to the same $G_1$-orbit iff they [and their complements, actually] are equinumerous. However, for the purposes for which i need this result, it is quite important to have a proof that doesn't use AC. And i need it for arbitrarily large $k$. Thank you all for your interest! $\endgroup$ Nov 18, 2018 at 6:46
  • 1
    $\begingroup$ @ThomasForster, the phrase "put all thought of the axiom of choice out of your mind" was not helpful -- it was ambiguous between "avoid" and "don't worry about". I will edit the question. $\endgroup$
    – user44143
    Nov 18, 2018 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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