3
$\begingroup$

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

  • 0
    Hmmm, yes, let me think about that for a bit...2011-01-22

2 Answers 2

2

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

  • 0
    @Matt: (cont...) in any order, still the same permutation. And if you write the permutation as$a$set of ordered pairs, $\{(a,c), (c,a), (b,d), (d,b), (e,e)\}$, then again it doesn't matter if you put $(a,c)$ first or last, if you think of $a$ as the "first" element of the set $\{a,b,c,d,e\}$ or you think of it as the fourth, or third, or last, the only relevant thing as far as the definition of the permutation is that $a$ maps to $c$.2011-02-01
2

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