Let $A : |A| = k$, and let elements of the power set $P(A)$ be (partially) ordered according to inclusion (that is, $\forall X, Y \in P(A) : X \leq Y \iff X \subseteq Y $). The question is then how many automorphisms exist on $P(A)$.

I think the answer is $k!$, and the sketch of my reasoning is roughly as follows:

  1. Any automorphism on $P(A)$ must map a set of size $l$ to a set of size $l$.
  2. For any automorphism $f$, its part restricted to sets of size $k-1$ defines the rest of the mapping: indeed, let $Z : Z \in P(A), |Z| = k - 2$. Then it's easy to see that there exist just two sets $X_1, X_2$ of size $k-1$ such that $Z \leq X_1, Z \leq X_2$. Since $f$ is an automorphism, $f(Z) \leq f(X_1), f(Z) \leq f(X_2)$, and it's easy to see that the set included in both $f(X_1)$ and $f(X_2)$ is unique, so $f(Z)$ is defined merely by $f(X_1)$ and $f(X_2)$. Applying this recursively proves the claim.
  3. Any permutation of subsets of size $k-1$ is a proper automorphism, once the rest of it is defined in accordance with the previous point.
  4. There are $k$ subsets of size $k-1$.
  5. The $k!$ answer immediately follows.

I have two questions:

  1. Is this reasoning correct?
  2. The factorial suggests there might be a beautiful recursive proof. Is there one?
  • 1
    $\begingroup$ I think it's even easier than this. Every permutation of $A$ gives you a permutation of $P(A)$ that preserves all the boolean set operations. You know there are $k!$ permutations of $A$ - perhaps you proved that by recursion. $\endgroup$ – Ethan Bolker Feb 25 '18 at 0:12
  • 1
    $\begingroup$ It might be clearer to do this by proving an automorphism is determined by its action on the subsets of cardinality 1. $\endgroup$ – saulspatz Feb 25 '18 at 0:15

What seems simpler to me is to use that any automorphism on $P(A)$ must map a set of size 1 to a set of size 1, so it permutes the size 1 subsets. This induces a permutation on the elements of $A$ itself. Conversely, any permutation of the elements of $A$ induces an automorphism. We are therefore getting a bijection between permutations of $A$ (of which there are $n!$) and automorphisms of $P(A)$.

  • $\begingroup$ Right, that (along with the answers given in comments) is definitely more straightforward! Thanks! $\endgroup$ – 0xd34df00d Feb 25 '18 at 0:18

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.