# Symmetric groups on sets with the same number of elements are isomorphic

Continuing my work through Abstract Algebra by Dummit and Foote, I'm stuck on what is probably a very easy proposition:

Let $\Delta$ and $\Omega$ be nonempty sets. The symmetric groups $S_\Delta$ and $S_\Omega$ are isomorphic if $|\Delta| = |\Omega|$

The proof is outlined in the text, then exercise 1.6.10 asks the reader to "fill in the details" by:
Let $\theta : \Delta \rightarrow \Omega$ be a bijection.
Define $\varphi : S_\Delta \rightarrow S_\Omega$ by $\varphi(\sigma) = \theta \circ \sigma \circ \theta ^{-1}$ for all $\sigma \in S_\Delta$

(a) $\varphi$ is well-defined, that is, if $\sigma$ is a permutation of $\Delta$ then $\theta \circ \sigma \circ \theta ^{-1}$ is a permutation of $\Omega$.

I thought I knew what "well-defined" meant ($x = y \rightarrow f(x) = f(y)$ ), but this doesn't seem anything like that. My best guess at how to prove this is: $\theta ^{-1}$ is a bijection from $\Omega$ to $\Delta$, then $\sigma$ is a bijection from $\Delta$ to itself, then $\theta$ is a bijection from $\Delta$ to $\Omega$. Is that correct?

Thanks. I think I can get the rest*, but I'll add to this question if need be.

* (b) $\varphi$ is a bijection from $S_\Delta$ onto $S_\Omega$. [Find a two-sided inverse for $\varphi$], and
(c) $\varphi$ is a homomorphism, that is $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \varphi(\tau)$

Added for (b), I used $\varphi ^{-1}(y) = \theta ^{-1} \circ y \circ \theta$ for $y \in S_\Omega$.
I showed that this is indeed an inverse since:
$\varphi^{-1}(\varphi(\sigma)) = \theta^{-1} \circ (\theta \circ \sigma \circ \theta^{-1}) \circ \theta = \sigma$, and likewise for the reverse composition.

And (c) was simply a matter of writing an equality using the definitions of the expressions on each side.

-

"Well-defined" is a notion that is, ahem, not very well defined. Generally, it just means that the function makes sense and is actually a function between the two sets that you claim it's a function from and to.

When we define functions whose domain are equivalence classes and the definition is in terms of "representatives" of those equivalence classes, the issue of "well-definedness" usually has to do with whether the value of the function changes if we use a different representative. For example, if you wanted to define a function from the set of human beings, and defined it in terms of the name of the person, then you would need to make sure that even if the person has more than one "name", the value of the function is always the same. This is what you talk about when you talk about "$x=y\rightarrow f(x)=f(y)$"; you want to make sure that your function always takes the same value, no matter what the "name" you give to the input.

On the other hand, when you define a function as going from a set $A$ to a set $B$, the notion of "well-definedness" may also refer to whether your definition actually gives you something that maps elements of $A$ to elements of $B$. If I wanted to define a function from the reals to the natural numbers, and I said $f(x) = \lfloor x\rfloor$, then this is "well-defined" in the first sense discussed above (if $x=y$ then $f(x)=f(y)$), but it's not well-defined in the second sense: the values of the function are not always in the desired set (the natural numbers). Or if I defined it "the last digit in the decimal expansion of $x$", then again it would not be "well-defined" in this second sense, because not every element of the domain would have an image. Thus, sometimes, when we talk about a function being "well-defined", we mean that the function is defined at all elements of the domain, and that the values are actually elements of the codomain.

So here, your definition of $\varphi$ requires you to make sure that if you plug in a bijection $\sigma\colon\Delta\to\Delta$, then $\varphi(\sigma)$ is actually a bijection $\Omega\to\Omega$, and not merely some function $\Omega\to\Omega$; i.e., that you are really "landing" in the set you are supposed to be landing on.

Your explanation is more or less correct: $\theta$ is a function from $\Delta$ to $\Omega$, $\theta^{-1}$ (which makes sense because $\theta$ is a bijection) is a function from $\Omega$ to $\Delta$, and $\sigma$ is a function from $\Delta$ to $\Delta$; so the composition $\theta\circ\sigma\circ\theta^{-1}$ is a function from $\Omega$ to $\Omega$. Since the three functions are bijections, the composition is a bijection, so $\theta\circ\sigma\circ\theta^{-1}$ is a bijection from $\Omega$ to $\Omega$, hence a permutation.

-
Arturo, thanks for verifying/fortifying my result, and for the explanation of the uses of "well-defined". –  Altar Ego Aug 30 '11 at 19:36
As a supplement to Arturo M's answer, at some point one may benefit from the idea that the issue of "well-definedness" arises when we try to define a map/function on a quotient Q of an object X by defining the map on X, and saying/showing it "descends to" or "factors through" the quotient, in the following sense. With $q:X\rightarrow Q$ the quotient map, a map $f:X\rightarrow Y$ factors_through $q$ if there is $g:Q\rightarrow Y$ such that $f=g\circ q$. If so, then (through some historical/semantic tradition) say $f$ is "well-defined on $Q$". (This understanding was a relief to me...) –  paul garrett Aug 30 '11 at 22:04
@paul: Well, that is a special case of a function being defined on a set of equivalence classes in terms of their representatives, is it not? That is, $f$ "factors through $q$" precisely when defining $f$ on the class of $[a]$ as $f(a)$ is "well-defined" in that first sense I mentioned: if $[a]=[b]$, then the definition in terms of $a$ agrees with the definition in terms of $b$. –  Arturo Magidin Aug 31 '11 at 0:14
To Arturo M's response: yes, indeed, ("my") "factoring through" is that "f([a]) depends only on [a], not necessarily on a". Nevertheless, and perhaps it is my own obtuseness, but, while (years ago) the issue of well-definedness was sufficiently clear to me to be able to cope with it, I had insufficient vocabulary to say what I was doing ... in terms that allowed reference to other stories. ... Beginners surely would not profit from any "factoring through quotients" story, but others might find some appeal in that particular turn-of-phrase. Others not, I suppose... My own weaknesses.. –  paul garrett Aug 31 '11 at 0:38
@Altar Ego: Yes, that looks right. –  Arturo Magidin Aug 31 '11 at 15:58

Here ‘well-defined’ means that for each $\sigma \in S_\Delta$, $\varphi(\sigma)$ really is a permutation of $\Omega$, so your best guess is essentially right: $\theta\circ\sigma\circ\theta^{-1}$ is certainly a well-defined function from $\Omega$ to $\Omega$, and you need only verify that it’s a bijection.

-
Thanks, Brian.  –  Altar Ego Aug 31 '11 at 4:37