# Abstract Algebra: Bijection, Isomorphism, Symmetric Sets

1. Mar 13, 2016

### RJLiberator

1. The problem statement, all variables and given/known data

Suppose X is a set with n elements. Prove that Bij(X) ≅ S_n.

2. Relevant equations
S_n = Symmetric set
≅ = isomorphism

Definition: Let G and G2 be groups. G and G2 are called Isomorphic if there exists a bijection ϑ:G->G2 such that for all x,y∈G, ϑ(xy) = ϑ(x)ϑ(y) where the LHS is operation in G and the RHS is operation in G2.

3. The attempt at a solution

So if we have a set X with n elements.
A Bijection simply sends one element to some other unique element.
The symmetric operation just sends one element to a unique other element as well.

So clearly both sides have unique elements.

IF we take ϑ(xy) in the Bij(x) that sends them to ϑ(x)ϑ(y) in the symmetric group

I dont know enough about bijections to prove this tho.

2. Mar 13, 2016

### andrewkirk

Let $Z(n)\equiv \{1,...,n\}$. Then $S_n$ is the set of all bijective maps from $Z(n)$ to itself.

$Bij(X)$ is the set of all bijective maps from $X$ to itself.

When we say $X$ has $n$ elements, we mean precisely that there exists a bijection $\psi: X\to Z(n)$.

Given all that, for any bijection $\pi:X\to X$, we can construct a bijection $F(\pi):Z(n)\to Z(n)$ - by composing the maps $\psi$ and $\pi$ and/or their inverses in a suitable fashion. So construct that. If you're not sure, draw a four-cornered map diagram, with two adjacent corners being $Z(n)$ and two being $X$.

If there is an isomorphism of the sort you want, the map $F:Bij(X)\to S_n$ will be it.

Then all you need to prove is that $F$ is one-to-one and onto, that is, that:

1. $F(\pi)=F(\pi')\Rightarrow \pi=\pi'$
2. $\forall \sigma\in S_n$ there exists $\pi:X\to X$ such that $F(\pi)=\sigma$

Edit: I just realised you used the isomorphism symbol. So we not only need to prove that $F$ is a bijection. We also need to prove it's a homomorphism, that is, that

3. $F(\pi)\circ F(\pi')=F(\pi\circ\pi')$ where $\circ$ denotes function composition.

These three things, plus the initial construction of $F$, are fairly straightforward. No tricks are needed.

3. Mar 13, 2016

### RJLiberator

Thank you for the help. You are making this problem already much more clear to me.

So, what I need to do is show that the composition of the two maps (aka F) are one to one and onto.

I'm not quite sure what you mean by four-cornered map diagram. But I think you simply mean a square with the 4 corners being the points as you described.

I can try to prove one-to-one and onto tomorrow with this understanding.