# Thread: Bijection and identity mappings

1. ## Bijection and identity mappings

Let D be a set and suppose that $\displaystyle \gamma : D \rightarrow D$ is a bijection which has the property that whenever $\displaystyle \delta : D \rightarrow D$ is a bijection, then $\displaystyle \gamma \circ \delta = \delta \circ \gamma$. If $\displaystyle \gamma \neq Id_D$, what can be said about $\displaystyle |D|$?

I can't even think about where to start with this apart from that I think that $\displaystyle |D|\ge 2$?
Help would be much appreciated.

2. Originally Posted by worc3247
Let D be a set and suppose that $\displaystyle \gamma : D \rightarrow D$ is a bijection which has the property that whenever $\displaystyle \delta : D \rightarrow D$ is a bijection, then $\displaystyle \gamma \circ \delta = \delta \circ \gamma$. If $\displaystyle \gamma \neq Id_D$, what can be said about $\displaystyle |D|$?

I can't even think about where to start with this apart from that I think that $\displaystyle |D|\ge 2$?
Help would be much appreciated.

If you know something about group theory and in particular about permutation groups, the above is equivalent to ask what

permutation commutes with any other permutation, i.e. what is the center of the group $\displaystyle S_X$, where $\displaystyle X$ can be any

set. It is known, and fairly easy to show, that the center is always trivial if $\displaystyle |D|>2$ , so in your case we get that it

must be $\displaystyle |D| = 2$ .

Tonio

3. Originally Posted by worc3247
Let D be a set and suppose that $\displaystyle \gamma : D \rightarrow D$ is a bijection which has the property that whenever $\displaystyle \delta : D \rightarrow D$ is a bijection, then $\displaystyle \gamma \circ \delta = \delta \circ \gamma$. If $\displaystyle \gamma \neq Id_D$, what can be said about $\displaystyle |D|$?

I can't even think about where to start with this apart from that I think that $\displaystyle |D|\ge 2$?
Help would be much appreciated.
To expand upon tonio's comment let $\displaystyle #(D)\geqslant 3$ and let $\displaystyle \pi\in S_D=\left\{\pi\in D^D:\pi\text{ is a bijection}\right\}$ and

$\displaystyle \pi\ne\text{id}_D$. We 'know' that $\displaystyle \pi$ may be written as the product of disjoint cycles $\displaystyle \pi=C_1C_2\cdots$ and by

assumption that $\displaystyle \pi\ne\text{id}_D$ we know that there exists some cycle $\displaystyle C_k$ with $\displaystyle \left|C_k\right|\geqslant 2$. If $\displaystyle \pi$ contains some

$\displaystyle C_k=(x,y)$ for some $\displaystyle x,y\in D$ then it's easy to construct a non-commuting permutation, so assume that

$\displaystyle \pi$ does not contain a transposition (in its cycle decomposition). Then, by prior assumption we know that

there exists some $\displaystyle C_k$ with $\displaystyle C_k=x\overset{\pi}{\mapsto}y\overset{\pi}{\mapsto} z\overset{\pi}{\mapsto}\cdots$ with $\displaystyle x,y,z$ distinct. Consider then the

transposition $\displaystyle \tau=(x,y)$. Note then that $\displaystyle \pi(\tau(x))=\pi(y)=z$ but $\displaystyle \tau(\pi(x))=\tau(y)=x$ from where

it follows that $\displaystyle \tau\pi\ne\pi\tau$.

4. Originally Posted by tonio
If you know something about group theory and in particular about permutation groups, the above is equivalent to ask what

permutation commutes with any other permutation, i.e. what is the center of the group $\displaystyle S_X$, where $\displaystyle X$ can be any

set. It is known, and fairly easy to show, that the center is always trivial if $\displaystyle |D|>2$ , so in your case we get that it

must be $\displaystyle |D| = 2$ .

Tonio
Does this still hold if X is infinite (countable or uncountable)?

5. Originally Posted by Swlabr
Does this still hold if X is infinite (countable or uncountable)?

Good question: I think it does, but a combinatorial proof isn't available unless we limit ourselves to permutations

moving a finite number of objects (because in that case we can work within $\displaystyle S_n$ , for some natural n).

So assume $\displaystyle \pi\in S_X\,,\,\,|X|\geq \aleph_0\,,\,\,\pi(x)\neq x\,\,\forall x\in S$ , for at least an infinite countable set of elements $\displaystyle S\subset X$.

But then we can find say $\displaystyle x_1,x_2,x_3\in S$ s.t. $\displaystyle \pi(x_i)\neq x_i\Longrightarrow \exists \sigma\in S_{X'_3}\,,\,\,X'_3:=\{x_i\,,\,\pi(x_i)\;;\;i=1,2, 3\}\,,\,s.t\,\,\sigma\overline{\pi}\neq \overline{\pi}\sigma$ , with $\displaystyle \overline{\pi}:=\pi\mid_{S_{X'_3}}$.

As we can take $\displaystyle \sigma$ as element of $\displaystyle S_x$ we're then done.

Tonio

6. Originally Posted by tonio
Good question: I think it does, but a combinatorial proof isn't available unless we limit ourselves to permutations

moving a finite number of objects (because in that case we can work within $\displaystyle S_n$ , for some natural n).

So assume $\displaystyle \pi\in S_X\,,\,\,|X|\geq \aleph_0\,,\,\,\pi(x)\neq x\,\,\forall x\in S$ , for at least an infinite countable set of elements $\displaystyle S\subset X$.

But then we can find say $\displaystyle x_1,x_2,x_3\in S$ s.t. $\displaystyle \pi(x_i)\neq x_i\Longrightarrow \exists \sigma\in S_{X'_3}\,,\,\,X'_3:=\{x_i\,,\,\pi(x_i)\;;\;i=1,2, 3\}\,,\,s.t\,\,\sigma\overline{\pi}\neq \overline{\pi}\sigma$ , with $\displaystyle \overline{\pi}:=\pi\mid_{S_{X'_3}}$.

As we can take $\displaystyle \sigma$ as element of $\displaystyle S_x$ we're then done.

Tonio
Why can't we just use the proof I used above? The only important part was that $\displaystyle \#(D)\geqslant 3$.

7. Originally Posted by Drexel28
Why can't we just use the proof I used above? The only important part was that $\displaystyle \#(D)\geqslant 3$.

You used that the given permutation is a product of disjoing cycles. I can't see how can this be extended to, say and infinite

number of cycles.

Tonio

8. Originally Posted by tonio
You used that the given permutation is a product of disjoing cycles. I can't see how can this be extended to, say and infinite

number of cycles.

Tonio
I agree that it's hard to make sense of disjoint if the set is infinite, but I still think the concept of partitioning up the set into orbits is still valid.

9. Originally Posted by Drexel28
I agree that it's hard to make sense of disjoint if the set is infinite, but I still think the concept of partitioning up the set into orbits is still valid.

And I agree with that, yet I still can't see how your proof can be extended, with or without this, to the infinite case.

Tonio