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

  • 1
    S_m is isomorphic to the set of 1-1 mappings from T to itself. Does that help?2011-01-22
  • 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
    Yes, yes! Restricting the function! That's very insightful. Thank you!2011-01-23
  • 0
    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.2011-01-23
  • 0
    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?2011-01-25
  • 0
    @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*.2011-01-25
  • 0
    @Matt: That should be "...a bijection $g$ between $T$ and $\{1,\ldots,m\}$..."2011-01-25
  • 0
    @Arturo: When you say: 'A one-to-one mapping doesn't really "care" *where* you write the elements, it only cares what the elements *are*.', do you picture the one-to-one mapping as a set of ordered pairs, so you're saying it only "cares" about what pairs are in the set? It dawned on me that a function is a set of ordered pairs, so I can use this idea to describe a "permutation". It's been very confusing to me trying to picture what a permutation actually is and how I can represent it in my head because to me a permutation is the way some objects are arranged in a row.2011-02-01
  • 0
    @Matt: There are two standard ways of denoting a permutation of a finite set. What you seem to be thinking of is the "two line notation": say, the permutation of $\{a,b,c,d,e\}$ that sends $a$ to $c$, $c$ to $a$, $b$ to $d$, $d$ to $b$, and $e$ to $e$ could be written $$\left(\begin{array}{ccccc}a&b&c&d&e\\ c&d&a&b&e\end{array}\right)$$You think of each column as one of the "ordered pairs". But this is the same as$$\left(\begin{array}{ccccc}b&e&c&a&d\\d&e&a&c&b\end{array}\right)$$or any other "shuffling" of the columns. The second standard way is in "cycle notation"(cont...)2011-02-01
  • 0
    @Matt: (cont...) The cycle $(i_1,i_2,i_3,\ldots,i_k)$ means that $i_1$ maps to $i_2$; $i_2$ maps to $i_3,\ldots,$ $i_{k-1}$ maps to $i_k$, and $i_k$ maps to $i_1$. So the same permutation I described above would be written $(a,c)(b,d)(e)$ (or just $(a,c)(b,d)$), since $a\mapsto c$, $c\mapsto a$, $b\mapsto d$, and $d\mapsto b$. My point about the permutation not "caring" where the elements are is that in the first notation, you can write the columns in any order, it's still the same function; in the second, you can write the cycles in any order, and the elements inside the cycles (cont...)2011-02-01
  • 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|}$.