Proving an equivalence about permutations

39 Views Asked by At

Let $S$ be a set. Let $\pi$ be a permutation on S. Extend $\pi$ to subsets $X$ of S in the natural way, viz

$\pi(X)=\{\pi(x): x\in S\}$

Further, let $f$ be the function such that for each $x$ in $S$

$f(x)=\{X\in\mathscr{P}(S): \pi(X)=X\textrm{ whenever }\pi(x)=x\}$

So $f(x)$ is the set of subsets of $S$ which are mapped to themselves by any permutation which is fixed on $x$.

Now it seems to me that the following must be true:

$X\in f(x)\Leftrightarrow\pi(X)\in f(\pi(x))$, for any permutation $\pi$

But I've been having trouble finding a proof and I think I may be missing something obvious. Any help would be much appreciated. Thanks!

1

There are 1 best solutions below

2
On

I claim that

$$f(x)=\big\{\varnothing,S,\{x\},S\setminus\{x\}\big\}\;.\tag{1}$$

To see this, suppose first that $\{x\}\subsetneqq A\subsetneqq X$. Then we can find $a\in A\setminus\{x\}$ and $y\in X\setminus A$, and if $\pi$ is the permutation of $S$ that swaps $a$ and $y$, then $\pi(x)=x$, but $\pi[A]\ne A$, so $A\notin f(x)$.

Now suppose that $\varnothing\ne A\subsetneqq X\setminus\{x\}$; then we can find $a\in A$ and $y\in X\setminus(A\cup\{x\})$, and again if $\pi$ is the permutation of $S$ that swaps $a$ and $y$, then $\pi(x)=x$, but $\pi[A]\ne A$, and $A\notin f(x)$.

The only subsets of $S$ not eliminated at this point are the four listed in $(1)$, and it’s easy to see that they are all in $f(x)$.

Now suppose that $X\in f(x)$, and let $\pi$ be any permutation of $S$. If $X=\varnothing$ or $X=S$, then $\pi[X]=X\in f\big(\pi(x)\big)$. If $X=\{x\}$, then $\pi[X]=\{\pi(x)\}\in f\big(\pi(x)\big)$. And if $X=S\setminus\{x\}$, then $\pi[X]=S\setminus\{\pi(x)\}\in f\big(\pi(x)\big)$. This shows that if $X\in f(x)$, and $\pi$ is a permutation of $S$, then $\pi[X]\in f\big(\pi(x)\big)$. Replacing $\pi$ by $\pi^{-1}$ yields the opposite implication and establishes the desired result.