# One to one mapping from $A(S_1)$ into $A(S_2)$

Let $S_1$ and $S_2$ be two sets. Suppose there exists a one to one mapping $\phi$ of $S_1$ into $S_2$. Show that there exists an one to one mapping from $A(S_1)$ into $A(S_2)$, where $A(S)$ means the set of all one to one mappings of $S$ onto itself.

Suppose $\{\phi_1,\phi_2,....\}$ are the elements of $A(S_1)$ and $\{\phi'_1,\phi'_2,....\}$ are the elements of $A(S_2)$. I thought the way to connect them lies through $'\phi'$.

Let $F: A(S_1) \to A(S_2)$ defined by $F(\phi_i)=\phi\circ \phi_i$.

Not sure whether $\phi\circ \phi_i=\phi'_i$??

• Elements of $f\in A(S^1)$ are 1-1 functions from $f:S^1\to S^1$ and $\phi:S^1\to S^2$ is 1-1, what can you say about their composition $\phi\circ f$
– omar
Apr 12 '14 at 2:07
• @omar Dude if you could see that's what I have done exactly. I am not sure if these are exactly the isomorphisms of $A(S_2)$ Apr 12 '14 at 2:20
• I do not see why this is tagged as "abstract algebra"??? More wonder is "group theory" tag...
– user87543
Apr 12 '14 at 4:58
• If the cardinality of $S_1$ is m and the card $S_2$ is n then one has to assume that $m \leq n$. Apr 18 '14 at 7:26
• Think about the cardinality of $A(S_1)$ and $A(S_2)$. If you do not go by the way you have defined but just map an element(map) to some element(map) will that solve your purpose? Apr 18 '14 at 10:22

You want to induce the mapping some how. Define $\phi^* : A(S_1) \to A(S_2)$ as $g \mapsto$ something related to $\phi$. Well we know that $\phi \circ g$ is one-to-one and maps $S_1 \to S_2$. What we need is a map from $S_2$ to itself though. The only apparent option seems to be $\phi^{\leftarrow}$, which is a well-defined map since if $\phi^{\leftarrow}(a) = \{b,c\} \cup \dots$, then since $\phi\circ \phi^{\leftarrow} (a) = a$, we have $b = c$, by 1-1ness of $\phi$. Iow, use the fact that $\phi$ is 1-1 to produce the fact that its reverse map is a function (not multi-valued, aka $\phi^{-1}$ returns singletons when provided with a singleton, etc). You could use the notation $\phi^{-1} \equiv \phi^{\leftarrow}$ if you want, just know that there is a unique, well-defined map for $\phi$ also known as a right inverse. Then we're almost done. Now we've connected $\phi$ to the problem by defining $\phi^{-1}$ and showing that it's unique and well-defined. Now

# define $\phi^* : A(S_1) \to A(S_2)$ as $\phi^*(f) = \phi f\phi^{-1}$.

Now show that $\phi^{-1}$ additionally is 1-1 and you have a composition of 1-1 maps which is 1-1. $\phi^{-1}(a) = \phi^{-1}(b) \implies \phi\phi^{-1}a = \phi\phi^{-1}b = a = b$. So now we're done.

• why do we need an inverse?? Apr 12 '14 at 2:44
• You don't need one, but one exists and it is unique and it answers the question. Maybe there's a way to do it without an inverse, but that's another question. Prove this first: for an arbitrary map between any sets $f : X \to Y$, if $f$ is surjective a unique left inverse exists and if $f$ is injective then a unique right inverse exists. Not $100\%$ sure about uniqueness but that's for you to prove. Also prove that the converse of each of the two statements above is also true, iow, $f$ is injective $\iff$ a right inverse exists. These two statements are used ALOT. Apr 12 '14 at 3:32
• Crap, I got those two statements reversed: $f$ is injective iff a left inverse exists Before using the material above, make sure you undo that mistake. So $\phi^*$ may end up now as $\phi^{-1} f \phi$ (or something...). Apr 12 '14 at 3:51

Given $\phi:S_1\rightarrow S_2$ and $\psi:S_1\rightarrow S_1$ you are looking for a function a function $\eta :S_2\rightarrow S_2$.

For sure, your $F(\psi)=\phi\circ g$ does not make sense..

You need $F(\psi)$ to be a function from $S_2$ to $S_2$

i.e., given $s\in S_2$ you want to see what $F(\psi)(s)$ would be?

as you defined, $F(\psi)(s)=(\phi\circ \psi)(s)=\phi(\psi(s))$ does not make sense because $\psi(s)$ is not defined for $s\in S_2$ as $\psi\in A(S_1)$.

At present you only have :

a function whose image is in $S_2$ namely $\phi$ but not a function whose domain is $S_2$

So, only possible option is to consider inverse (I strongly feel there is no other way)

so, $\phi^{-1}:S_2\rightarrow S_1$

So, you took an element in $S_2$ and landed in $S_1$ but you want an element in $S_2$

So, only option is to search for a function which takes elements in $S_1$ and gives elements in $S_2$.

You do have $\phi:S_1\rightarrow S_2$ which takes elements in $S_1$ and produce an element in $S_2$ but that would not help you because you would then only get an identity function $\phi\circ \phi^{-1}$.

Another possible option is to consider $\phi\circ \psi$.. This takes elements in $S_1$ and gives elements in $S_2$

This should work I believe...

i.e., $F(\psi)=\phi\circ \psi\circ \phi^{-1}$

Rest is your part to check if it is one one...