# A subset of permutations on the set S such that the elements that are within T, a subset of S, are not exchanged with elements outside of T

Sorry about the title, I have no idea how to describe these types of problems.

Problem statement:

$A(S)$ is the set of 1-1 mappings of $S$ onto itself. Let $S \supset T$ and consider the subset $U(T) =$ { $f \in A(S)$ | $f(t) \in T$ for every $t \in T$ }. $S$ has $n$ elements and $T$ has $m$ elements. Show that there is a mapping $F:U(T) \rightarrow S_m$ such that $F(fg) = F(f)F(g)$ for $f, g \in U(T)$ and $F$ is onto $S_m$.

How do I write up this reasoning: When I look at the sets $S$ = { 1, 2, ..., $n$} and $T$ = { 1, 2, ..., $m$}, I can see that there are a bunch of permutations of the elements of $T$ within $S$. I can see there are $(n - m)!$ members of $S$ for each permutation of $T$'s elements. But there needs to be some way to get a handle on the positions of the elements in $S$ and $T$ in order to compare them to each other. But $S$ isn't any particular set, like a set of integers, so how can I relate the positions of the elements to one another? Or, is this the wrong way to go about it?

Example:

$U(T_3 \subset S_6) = \left( \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 6 & 5 \\ 1 & 2 & 3 & 5 & 4 & 6 \\ 1 & 2 & 3 & 5 & 6 & 4 \\ 1 & 2 & 3 & 6 & 4 & 5 \\ 1 & 2 & 3 & 6 & 5 & 4 \\ 1 & 3 & 2 & 4 & 5 & 6 \\ 1 & 3 & 2 & 4 & 6 & 5 \\ 1 & 3 & 2 & 5 & 4 & 6 \\ 1 & 3 & 2 & 5 & 6 & 4 \\ 1 & 3 & 2 & 6 & 4 & 5 \\ 1 & 3 & 2 & 6 & 5 & 4 \\ 2 & 1 & 3 & 4 & 5 & 6 \\ 2 & 1 & 3 & 4 & 6 & 5 \\ 2 & 1 & 3 & 5 & 4 & 6 \\ 2 & 1 & 3 & 5 & 6 & 4 \\ 2 & 1 & 3 & 6 & 4 & 5 \\ 2 & 1 & 3 & 6 & 5 & 4 \\ 2 & 3 & 1 & 4 & 5 & 6 \\ 2 & 3 & 1 & 4 & 6 & 5 \\ 2 & 3 & 1 & 5 & 4 & 6 \\ 2 & 3 & 1 & 5 & 6 & 4 \\ 2 & 3 & 1 & 6 & 4 & 5 \\ 2 & 3 & 1 & 6 & 5 & 4 \\ 3 & 1 & 2 & 4 & 5 & 6 \\ 3 & 1 & 2 & 4 & 6 & 5 \\ 3 & 1 & 2 & 5 & 4 & 6 \\ 3 & 1 & 2 & 5 & 6 & 4 \\ 3 & 1 & 2 & 6 & 4 & 5 \\ 3 & 1 & 2 & 6 & 5 & 4 \\ 3 & 2 & 1 & 4 & 5 & 6 \\ 3 & 2 & 1 & 4 & 6 & 5 \\ 3 & 2 & 1 & 5 & 4 & 6 \\ 3 & 2 & 1 & 5 & 6 & 4 \\ 3 & 2 & 1 & 6 & 4 & 5 \\ 3 & 2 & 1 & 6 & 5 & 4 \end{array} \right),A(T_3) = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \\ 2 & 1 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ 3 & 2 & 1 \end{array} \right)$

-
S_m is isomorphic to the set of 1-1 mappings from T to itself. Does that help? –  Qiaochu Yuan Jan 22 '11 at 17:28
Hmmm, yes, let me think about that for a bit... –  Matt Gregory Jan 22 '11 at 17:36

I honestly don't understand what you mean by "the positions of the elements of $S$ and of $T$". A one-to-one mapping doesn't really "care" where you write the elements, it only cares what the elements are.

Instead, think about this: if all you care about is what is happening to the elements of $T$, what happens if you just ignore all the elements of $S-T$?

To give you a different example so you can see what I'm talking about: suppose you are very interested in squaring positive real numbers, but you don't really care about numbers other than those numbers $x$ which satisfy $0\lt x\lt 1$. Although you have a perfectlty good function $f\colon\mathbb{R}\to[0,\infty)$ that maps $x$ to $x^2$, you don't really care what $f$ is doing on $[1,\infty)$, or on $(-\infty,0]$. You only care about what is happening on $(0,1)$. So, for instance, you might want to consider an inverse for the function; the function $f$ does not have an inverse, so instead, since we are only interested in what is going on inside $(0,1)$, we consider the restriction $g = f\bigm|_{(0,1)}$ of $f$ to $(0,1)$.

We can think of the idea of "restrict the function to $(0,1)$" as a way of taking any function defined on the whole real numbers, and getting a function that is defined on only $(0,1)$.

And here,, you have maps defined on all of $S$, but you are only interested in (i) those that map $T$ to itself; and (ii) only what they do to $T$. So...

And, once you have that, prove the following:

Theorem. Let $X$ and $Y$ be sets, and let $g\colon X\to Y$ be a bijection between $X$ and $Y$. Then $A(X)$ is isomorphic to $A(Y)$, via the map that sends $\sigma\colon X\to X$ to $g\circ\sigma\circ g^{-1}\colon Y\to Y$.

-
Yes, yes! Restricting the function! That's very insightful. Thank you! –  Matt Gregory Jan 23 '11 at 2:33
Oh, sorry, I'm not familiar with this site and I was trying to put a linefeed in the post. But, nevermind, I know what you're saying now. –  Matt Gregory Jan 23 '11 at 2:34
I'm supposed to "show that there is a mapping $F:U(T) \rightarrow S_m$ such that $F(fg) = F(f)F(g)$ for $f,g \in U(T)$ and $F$ is onto $S_m$." But when I start to define $F$, and I take the parameter $f$, which itself is a function, and I go to restrict it, then are multiple functions that it could resolve to. This is why I was talking about the $(n-m)!$ functions that this function could possibly resolve to. There is no way to get a handle on a specific one, so I don't know how to create a specific definition for this function. Am I being clear/sane? –  Matt Gregory Jan 25 '11 at 3:15
@Matt: Look at the last part of my answer: first map from $U(T)$ to $A(T)$ (via restriction); then fix a bijection $g$ between $T$ and $\{1,\ldots,n\}$, then use that bijection to define a function $A(T)\to S_m$. Then one possible $F$ will be the composition of these two maps. There are lots of functions from $U(T)$ to $S_m$ with the desired property (just compose any one function you find with any nontrivial automorphism of $S_m$ to get a new one), but you are just required to find one. –  Arturo Magidin Jan 25 '11 at 3:22
@Matt: That should be "...a bijection $g$ between $T$ and $\{1,\ldots,m\}$..." –  Arturo Magidin Jan 25 '11 at 3:30

You have noticed something that turns out to be quite interesting in a more general context: for each $f \in U(T)$, there are $(n-m)!$ elements $g \in U(T)$ that satisfy for all $t \in T, f(t) = g(t)$. This is because the kernel of the homomorphism $F$ we are looking have has order $(n-m)!$; but that doesn't actually get you any closer to the answer of the question that is being asked!i

First, let me suggest that instead of $A(X)$, we use the notation $Sym(X)$ as being the group of all bijections $X \to X$ with the group operation being composition. The important things to notice (and prove!) are that:

Theorem: $U(T)$ is a group (and thus a subgroup of $Sym(S)$; it is usually called the stabilizer of $T$ in $Sym(S)$).

Theorem: For each $f \in U(T)$, there exists a unique $g \in Sym(T)$ such that for all $t \in T$, $f(t) = g(t)$.

This lets us define $F$ to be the function that maps any $f \in U(T)$ to that unique element $g \in Sym(T)$.

Theorem: For each $g \in Sym(T)$, there exists at least one $f \in U(T)$ such that for all $t \in T, f(t) = g(t)$.

It follows that $F$ must therefore be onto $Sym(T)$.

Next prove that $F$ satisfies: $F(gh) = F(g)F(h)$; i.e. that $F$ is a homomorphism $U(T) \to Sym(T)$ which is onto.

Finally as Qiaochu hinted and Arturo more explicitly noted, given two sets $X, Y$ and a bijection $T : X \to Y$, we can prove that $Sym(X)$ is isomorphic to $Sym(Y)$. The set $[m] = \{1, 2, ..., m\}$ is in bijection with $T$; and $Sym([m])$ is what is usually meant by $S_m$. The conclusion follows.

To put the original problem in more common group theoretical language: Given $T \subset S$, let $G$ be the stabilizer of $T$ in $Sym(S)$. Show that there is a homomorphism from $G$ onto $S_{|T|}$.

-