MHB Subsets of permutation group: Properties

[mathmari]

Hey!

Let $G$ be a permutation group of a set $X\neq \emptyset$ and let $x,y\in X$. We define:
\begin{align*}&G_x:=\{g\in G\mid g(x)=x\} \\ &G_{x\rightarrow y}:=\{g\in G\mid g(x)=y\} \\ &B:=\{y\in X\mid \exists g\in G: g(x)=y\}\end{align*}

Show the following:

1. $G_x$ is a subgroup of $G$.
2. The set $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$.
3. Let $g\in G_{x\rightarrow y}$ and let $u\in G_x$ and $v\in G_{x\rightarrow y}$. Then it holds that $g\circ u\in G_{x\rightarrow y}$ and $g^{-1}\circ v\in G_x$.
4. The maps \begin{align*}\alpha:G_x\rightarrow G_{x\rightarrow y}, \ u\mapsto g\circ u \\ \beta: G_{x\rightarrow y}\rightarrow G_x, \ v\mapsto g^{-1}\circ v\end{align*} are to each other inverse bijections.
5. Let $G$ be finite. Then it holds that $|G|=|B|\cdot |G_x|$.

I have done the following:

For 1:
We have to show the properties of a subgroup. :unsure:For 2:
We have to show that every element of $G$ is in exactly one of these subsets, right? How can we do that? :unsure:For 3:
Since $g\in G_{x\rightarrow y}$ we have that $g\in G\mid g(x)=y$.
Since $u\in G_x$ we have that $u\in G\mid u(x)=x$.
Since $v\in G_{x\rightarrow y}$ we have that $v\in G\mid v(x)=y$.

Isn't obvious that $g\circ u\in G_{x\rightarrow y}$ and $g^{-1}\circ v\in G_x$, since we look always at the outer left function? :unsure:For 5:
The is a hint given that the proof is similar to the idea to show that theere are $48$ symmetries of a cube.
How exactly can we use this? :unsure:

 

[I like Serena]

For 1:
We have to show the properties of a subgroup.

Hey mathmari!

So we have to show that it is not empty, closed for composition, and closed for inverses, don't we?

For 2:
We have to show that every element of G is in exactly one of these subsets, right? How can we do that?

A usual way is with a proof by contradiction.
Suppose it is not. Then there must be...

 

[mathmari]

For 1:

$G$ is the permutation group. The identity permutation is contained in $G$. We have that $\text{id}(x)=x$. So $\text{id}\in G_x$. Therefore, $G_x$ is not empty.
Let $g,h\in G_x$. Then $g(x)=x$ and $h(x)=x$ for $x\in X$. We have that $(g\circ h)(x)=g(h(x))=g(x)=x$. So $g\circ h\in G_x$ and this means that $G_x$ is closed for composition.
Let $g\in G_x$. Then $g(x)=x$. How do we show that $G_x$ is closed for inverses? :unsure: For 2:

We suppose that the set is not a partition of $G$. Then there must be anelement of $G$ that is contained it two different subsets or in no subset? :unsure:

 

[I like Serena]

For 1:
$G$ is the permutation group. The identity permutation is contained in $G$. We have that $\text{id}(x)=x$. So $\text{id}\in G_x$. Therefore, $G_x$ is not empty.
Let $g,h\in G_x$. Then $g(x)=x$ and $h(x)=x$ for $x\in X$. We have that $(g\circ h)(x)=g(h(x))=g(x)=x$. So $g\circ h\in G_x$ and this means that $G_x$ is closed for composition.
Let $g\in G_x$. Then $g(x)=x$. How do we show that $G_x$ is closed for inverses?

Since $g$ is an element of the group $G$, it must have an inverse $g^{-1}$ that is also in $G$, yes?
So we already have that $g^{-1}$ exists.
The only remaining question is whether it is in $G_x$.
Do we have that $g^{-1}(x)=x$? :unsure:

For 2:
We suppose that the set is not a partition of $G$. Then there must be an element of $G$ that is contained it two different subsets or in no subset?

Indeed.
So for the first case, let's suppose that there is a $g$ is in 2 different subsets.
Then there must be a $G^1_{x\to y}\ne G^2_{x\to y}$ such that $g$ is in both yes?
What does that mean?

 

[mathmari]

Since $g$ is an element of the group $G$, it must have an inverse $g^{-1}$ that is also in $G$, yes?
So we already have that $g^{-1}$ exists.
The only remaining question is whether it is in $G_x$.
Do we have that $g^{-1}(x)=x$? :unsure:

Ah yes! So since $g(x)=x\Rightarrow g^{-1}(g(x))=g^{-1}(x) \Rightarrow x=g^{-1}(x)$ and so $g^{-1}\in G_x$, right? :unsure:

Indeed.
So for the first case, let's suppose that there is a $g$ is in 2 different subsets.
Then there must be a $G^1_{x\to y}\ne G^2_{x\to y}$ such that $g$ is in both yes?
What does that mean?

Then the sets $G^1_{x\to y}$ and $ G^2_{x\to y}$ have a non-empty intersection. Or do you mean something else? :unsure:

 

[I like Serena]

Ah yes! So since $g(x)=x\Rightarrow g^{-1}(g(x))=g^{-1}(x) \Rightarrow x=g^{-1}(x)$ and so $g^{-1}\in G_x$, right?

Yep.

Then the sets $G^1_{x\to y}$ and $ G^2_{x\to y}$ have a non-empty intersection. Or do you mean something else?

Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it?

 

[mathmari]

Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it?

Ok!

So it remains to show that there is an element of $G$ that is in none of the susbsets, or not? :unsure:

 

[I like Serena]

So it remains to show that there is an element of $G$ that is in none of the susbsets, or not?

Yep. :)

 

[mathmari]

This cannot hold, can it? Because every element of $G$ send an element of $X$ to an an element of $X$ so it must be contained in one of the subsets. Is this correct? :unsure:

 

[I like Serena]

This cannot hold, can it? Because every element of $G$ send an element of $X$ to an an element of $X$ so it must be contained in one of the subsets. Is this correct?

Close, but it's not complete.

Let's take this one step at a time.
Suppose there is a $g\in G$ such that it is in none of the sets in $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$.
Let $x$ be an element in $X$.
Then $g(x)$ must indeed also be an element in $X$.
But that is not sufficient is it? There is more...

 

[I like Serena]

Wait!
I think I made a mistake.
I wrote:

Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it?

However, suppose $g\in G$ and there are two different sets in $\{G_{x\rightarrow y}\mid y\in B\}$ that contain $g$.
Then there must be $x_1,x_2,y_1,y_2\in X$ such that $g\in G_{x_1\to y_1}$, $g\in G_{x_2\to y_2}$, and $G_{x_1\to y_1}\ne G_{x_2\to y_2}$, yes?

Let's take a look at an example.
Suppose $X=\{a,b,c\}$, and let $f\in G$ with $f:a\mapsto a, b\mapsto c, c\mapsto b$.
Then $\operatorname{id}, f\in G_{a\to a}$.
And $\operatorname{id}\not\in G_{b\to c}$, but $f \in G_{b\to c}$.
So $f$ is contained in two distinct sets that are both in $\{G_{x\rightarrow y}\mid y\in B\}$, isn't it? :unsure:

I am stuck now because this would proof by counterexample that statement 2 is false.
Do you see in mistake in my reasoning?

 

[mathmari]

Since the definition of the set is $\{G_{x\rightarrow y}\mid y\in B\}$ do we maybe have to take only different $y$'s but same $x$'s ?
I mean one subset is $G_{x\rightarrow y_1}$ and an other one is $G_{x\rightarrow y_2}$ with $y_1\neq y_2$ and both are in $B$ ?
Or is there no logic at this? :unsure:

 

[I like Serena]

Since the definition of the set is $\{G_{x\rightarrow y}\mid y\in B\}$ do we maybe have to take only different $y$'s but same $x$'s ?
I mean one subset is $G_{x\rightarrow y_1}$ and an other one is $G_{x\rightarrow y_2}$ with $y_1\neq y_2$ and both are in $B$ ?
Or is there no logic at this?

Yes. That makes sense and would explain it.

 

[mathmari]

We consider a $x\in X$.

We suppose that $g\in G_{x\rightarrow y_1}$ and $g\in G_{x\rightarrow y_2}$ with $y_1\neq y_2$ for $y_1, y_2\in B$.
Then we have that $g(x)=y_1$ and $g(x)=y_2$. Then $g$ is not injective and this is not true since $g$ is a permutation.
So we get a contradiction and so $g$ must be in at most one subset.
Is this correct?

Then we suppose that $g$ is not contained in one subset. That means that there is a $y$ such that $g\notin G_{x\rightarrow y}$ and so $g(x)\neq y$ and since $y$ is any element in $X$ then we get a contradiction since $g$ has to map $x$ to some $y$.
Therefore $g$ must be in exactly one subset.
Is this correct?

:unsure:

 

[I like Serena]

Yep. All correct. :)

 

[mathmari]

Great! ☺

So let's consider question 3. Is it correct what I had done in my initial post? :unsure:

Could you give me a hint for the question 4 ? :unsure:

At 5:
We have that $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$. Does this mean that $|G|=|\{G_{x\rightarrow y}\mid y\in B\}|$ ?
If it is like that, then we have to show that $|\{G_{x\rightarrow y}\mid y\in B\}|=|B|\cdot |G_x|$, right? :unsure:

 

[I like Serena]

So let's consider question 3. Is it correct what I had done in my initial post?

Yes.
Still, I would state explicitly that the conditions are met.
For instance $(g\circ u)(x)=g(u(x))=g(x)=y\implies g\circ u\in G_{x\to y}$. :geek:

Could you give me a hint for the question 4 ?

Let $f$ be an element of $G$.
What is $\alpha(\beta(f))$ and what does it mean?

At 5:
We have that $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$. Does this mean that $|G|=|\{G_{x\rightarrow y}\mid y\in B\}|$ ?
If it is like that, then we have to show that $|\{G_{x\rightarrow y}\mid y\in B\}|=|B|\cdot |G_x|$, right?

What does the Orbit-stabilizer theorem say?

 

[mathmari]

Yes.
Still, I would state explicitly that the conditions are met.
For instance $(g\circ u)(x)=g(u(x))=g(x)=y\implies g\circ u\in G_{x\to y}$. :geek:

Ah ok! And respectively: $(g^{-1}\circ v)(x)=g^{-1}(v(x))=g^{-1}( y )$. This the last one equal to $x$ because $g\in G_{x\rightarrow y}$ and so $g(x)=y$ and so $x=g^{-1}( y )$ ? :unsure:

Let $f$ be an element of $G$.
What is $\alpha(\beta(f))$ and what does it mean?

We have that $$\alpha(\beta(f))=\alpha (g^{-1}\circ f)=g\circ g^{-1}\circ f=f$$ This means that $\alpha$ is the left inverse of $\beta$.
We have that $$\beta(\alpha(f))=\beta (g\circ f)=g^{-1}\circ g\circ f=f$$ This means that $\beta$ is the right inverse of $\alpha$.
So $\alpha=\beta^{-1}$ and $\beta=\alpha^{-1}$ and since these maps are invertible it follows that they are bijections.

Does this mean that these two are to each other inverse bijections? :unsure:

 

[I like Serena]

Ah ok! And respectively: $(g^{-1}\circ v)(x)=g^{-1}(v(x))=g^{-1}( y )$. This the last one equal to $x$ because $g\in G_{x\rightarrow y}$ and so $g(x)=y$ and so $x=g^{-1}( y )$ ?

Yep.
So $(g^{-1}\circ v)(x)=x \implies (g^{-1}\circ v)\in G_x$. :geek:

Does this mean that these two are to each other inverse bijections?

Yep.