A set $A$ is a cylinder if there is a set $B$ such that A $\equiv_1$ B x N.
Show that if S is a cylinder, then for any set C: C $\le_m$ S => C $\le_1$ S
My Approach :
Since S is a cylinder therefore there exists a set S2 such that S $\equiv_1$ S2 x N.
What I understand by m reducibility is that the function will be many to one. Whereas in
1 reducibility the function will be one-to-one. I am not sure if I am interpreting the definition
correctly. To produce a one-to-one function seems difficult with this definition.
Let $f1$ be function for S $\le_1$ S2 x N and $f2$ for S2 x N $\le_m$ S
consider the function $f2(f1(x))$ this is a one-one mapping from S to S
I am wondering if it could somehow be converted to a mapping from C to S
I have a feeling this question is not difficult but I am missing something
Any hints or pointers to this ?