Still I'm reading Gowers's weblog about orbit-stabilizer theorem, I must admit that my understanding of this materiel improved, but still I have some question.
Let $G$ be a finite group, and $X$ be a finite $G$-set. We define the following sets:
$$S_x = \left\{ g\in G: gx=x\right\};$$
$$S_{xy} = \left\{g\in G:gx=y \right\}.$$
In second proof that Gowers presents, he explains that picking $h$ from $S_{xy}$ isn't so simple, since there is no canonical choice. Then he states the following statement:
If you can’t make a canonical choice, then make all choices at once.
And defines the next map:
$$\phi: S_{xy}\times S_x \to S_{xy},$$ $$(h,g)\mapsto hg .$$
My first question is:
Why is $\phi$ well defined?
My second question:
- Why is $\phi$ clearly not bijective?
His, and our purpose is to prove that $|S_{xy}|=|S_{x}|$. To do that, we wish to show that every element of $S_{xy}$ has exactly $|S_{xy}|$ preimages under $\phi$. That is, for every $u\in S_{xy}$:
$$|\phi^{-1}(u)|=|\{(h,g):hg=u\}|=|S_{xy}|$$
My third question:
How does one deduce from this that $|S_{xy}||S_x|=|S_{xy}|^2$ ?
Thank you.
I have answered your first and second questions in the comments. Let me answer the third question:
We have
$S_{xy}\times S_{x}=\bigcup_{u\in S_{xy}}\phi^{-1}\left( u\right) $,
and the union is a disjoint union (i.e., the sets $\phi^{-1}\left( u\right) $ for $u\in S_{xy}$ are pairwise disjoint). Thus,
(1) $\left\vert S_{xy}\times S_{x}\right\vert =\sum_{u\in S_{xy} }\left\vert \phi^{-1}\left( u\right) \right\vert $.
We shall now show that
(2) $\left\vert \phi^{-1}\left( u\right) \right\vert =\left\vert S_{xy}\right\vert $ for every $u\in S_{xy}$.
Proof of (2). Fix $u\in S_{xy}$. Then,
$\phi^{-1}\left( u\right) =\left\{ \left( h,g\right) \in S_{xy}\times S_{x}\ :\ \underbrace{\phi\left( \left( h,g\right) \right) } _{=hg}=u\right\} $
$=\left\{ \left( h,g\right) \in S_{xy}\times S_{x}\ :\ hg=u\right\} $.
Hence,
$\left\vert \phi^{-1}\left( u\right) \right\vert =\left\vert \left\{ \left( h,g\right) \in S_{xy}\times S_{x}\ :\ hg=u\right\} \right\vert $.
Now, how many elements $\left( h,g\right) \in S_{xy}\times S_{x}$ satisfy $hg=u$ ? It is easy to see that, for every $h\in S_{xy}$, there exists exactly one $g\in S_{x}$ satisfying $hg=u$ (namely, $g=h^{-1}u$; of course, you need to check that $h^{-1}u$ is actually a element of $S_{x}$). Therefore, for every $h\in S_{xy}$, we have $\left\vert \left\{ g\in S_{x}\ :\ hg=u\right\} \right\vert =1$. Now,
$\left\vert \phi^{-1}\left( u\right) \right\vert =\left\vert \left\{ \left( h,g\right) \in S_{xy}\times S_{x}\ :\ hg=u\right\} \right\vert $
$=\sum_{h\in S_{xy}}\underbrace{\left\vert \left\{ g\in S_{x} \ :\ hg=u\right\} \right\vert }_{=1}=\sum_{h\in S_{xy}}1=\left\vert S_{xy}\right\vert $.
This proves (2).
Now,
$\left\vert S_{xy}\right\vert \cdot\left\vert S_{x}\right\vert =\left\vert S_{xy}\times S_{x}\right\vert =\sum_{u\in S_{xy}}\left\vert \phi^{-1}\left( u\right) \right\vert $ (by (1))
$=\sum_{u\in S_{xy}}\left\vert S_{xy}\right\vert $ (by (2))
$=\left\vert S_{xy}\right\vert \cdot\left\vert S_{xy}\right\vert $.
Since $\left\vert S_{xy}\right\vert $ is nonzero, we can cancel $\left\vert S_{xy}\right\vert $ out of this equation and obtain $\left\vert S_{x} \right\vert =\left\vert S_{xy}\right\vert $.