Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question
1  
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
add comment

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
show 4 more comments

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|}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.