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

  • $\begingroup$ 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$ $\endgroup$
    – omar
    Apr 12 '14 at 2:07
  • $\begingroup$ @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)$ $\endgroup$ Apr 12 '14 at 2:20
  • $\begingroup$ I do not see why this is tagged as "abstract algebra"??? More wonder is "group theory" tag... $\endgroup$
    – user87543
    Apr 12 '14 at 4:58
  • $\begingroup$ If the cardinality of $S_1$ is m and the card $S_2$ is n then one has to assume that $ m \leq n $. $\endgroup$ Apr 18 '14 at 7:26
  • $\begingroup$ 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? $\endgroup$ 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.

  • $\begingroup$ why do we need an inverse?? $\endgroup$ Apr 12 '14 at 2:44
  • $\begingroup$ 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. $\endgroup$ Apr 12 '14 at 3:32
  • $\begingroup$ 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...). $\endgroup$ 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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.