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:
- Any automorphism on $P(A)$ must map a set of size $l$ to a set of size $l$.
- 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.
- 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.
- There are $k$ subsets of size $k-1$.
- The $k!$ answer immediately follows.
I have two questions:
- Is this reasoning correct?
- The factorial suggests there might be a beautiful recursive proof. Is there one?
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)$.