MHB Show that G is a subset of the symmetric group

[mathmari]

Hey!

Let $n\in \mathbb{N}$ and $M=\{1, 2, \ldots , n\}\subset \mathbb{N}$. Let $d:M\times M\rightarrow \mathbb{R}$ a map with the property $$\forall x, y\in M : d(x,y)=0\iff x=y$$
Let \begin{equation*}G=\{f: M\rightarrow M \mid \forall x,y\in M : d(x,y)=d\left (f(x), f(y)\right )\}\end{equation*} and $S_n$ the symmetric group, i.e. the set of all bijective maps of $M$ to itself with the composition.

Each $f\in G$ ist injective.

I want to show that $G\subseteq S_n$. We have to show that $f\in S_n$, i.e. that $f$ is surjective, or not? Could you give me a hint how we could show that? (Wondering)

 

[GJA]

Hi mathmari,

You're correct, we need to show that $f$ is both surjective and injective. Since you've only asked about surjectivity, I will assume you've handled the injectivity part already.

By way of contradiction, suppose $f$ is not surjective and that there are $k$ elements of $M$ that $f$ doesn't map onto. Can you construct an argument from here? Hints: Use the Pigeonhole Principle (https://en.wikipedia.org/wiki/Pigeonhole_principle) and the defining property of the set $G$. Feel free to let me know if anything is unclear.

 

[I like Serena]

Hey!

Let $n\in \mathbb{N}$ and $M=\{1, 2, \ldots , n\}\subset \mathbb{N}$. Let $d:M\times M\rightarrow \mathbb{R}$ a map with the property $$\forall x, y\in M : d(x,y)=0\iff x=y$$
Let \begin{equation*}G=\{f: M\rightarrow M \mid \forall x,y\in M : d(x,y)=d\left (f(x), f(y)\right )\}\end{equation*} and $S_n$ the symmetric group, i.e. the set of all bijective maps of $M$ to itself with the composition.

Each $f\in G$ ist injective.

I want to show that $G\subseteq S_n$. We have to show that $f\in S_n$, i.e. that $f$ is surjective, or not? Could you give me a hint how we could show that? (Wondering)

Hey mathmari!

From the property we have that if $x\ne y$ that $d(x,y)\ne 0$ don't we?

Now suppose that we have an $f\in G$ that is not surjective...
$M$ has exactly $n$ elements. If one element is not reached, then there must be 2 elements that have the same image, mustn't it?
After all, the pigeonhole principle says: if there are more items than slots, there must be a slot with 2 items. (Thinking)

EDIT: Aww, beaten to it by GJA.

 

[GJA]

Didn't mean to swoop in, I like Serena. I will gladly defer this post to your expertise!

 

[mathmari]

So, we have the following:

We assume that $f\in G$ is not surjective.

$M$ has exactly $n$ elements. If one element is not reached, then there must be $2$ elements that have the same image.

According to the pigeonhole principle we get that $x\neq y$ with $f(x)=f(y)$, or not?

From $x\neq y$ we get that $d(x,y)\neq 0$. From $f(x)=f(y)$ we have that $d(f(x), f(y))=0$. But since it holds that $d(x,y)=d(f(x), f(y))$, we get a contradiction.

Therefore, $f$ is a surjective map. Is everything correct? (Wondering)

 

[I like Serena]

Yep. All correct. (Nod)

 

[mathmari]

Yep. All correct. (Nod)

Great! Thanks a lot! (Smile)

 

[Olinguito]

In general, for any finite set $X$, a mapping $f:X\to X$ is injective if and only if it is surjective.