4 votes 4 votes 1. If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e $f:S \rightarrow S$ is a surjective function), then $f$ is one-to-one. Set Theory & Algebra discrete-mathematics set-theory&algebra functions + – Soumya29 asked May 14, 2018 Soumya29 670 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Kushagra Chatterjee commented May 14, 2018 reply Follow Share No, f need not to be one-one. Right now I am in a little rush I will give the counter-example later on. I read your comment in gate 1988 there you wrote that S is equipotent to itself and it is given that S is surjective so, it has to be injective. Look A and B are said to be equipotent sets if there exists a bijective mapping from A to B rt. Yes,you are right that S is equipotent to itself because there exists a bijective mapping from S to S but that does not mean all mappings that can be defined from S to S has to be bijective. There may exist some mapping between S to S which is not bijective. I hope you are getting my point. 3 votes 3 votes Soumya29 commented May 14, 2018 i edited by Soumya29 Jul 3, 2018 reply Follow Share Yes, please give me some counter-example. You are correct that it does not mean all mappings that can be defined from S to S has to be bijective. But if it's given that mapping is surjective which means |A| $\geq$ |B|. Here mapping is between the same set. So |A| = |B|. Under this condition, all the mappings should be one to one as well. I am not getting how a function on the same countable set is onto but not one to one. :( 0 votes 0 votes srestha commented May 15, 2018 reply Follow Share some discussion https://gateoverflow.in/216802/set-theory 0 votes 0 votes Ayush Upadhyaya commented Jul 3, 2018 reply Follow Share @Saumya29-You cannot have a surjective function $f: A \rightarrow B$ such that $|A| \leq |B|$ it is possible only when $|B| \leq |A|$ 0 votes 0 votes Soumya29 commented Jul 3, 2018 reply Follow Share Ohh Yeah. It was a typo. Thanks, Ayush. 1 votes 1 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes this statement always doesn't hold.It depends on what the function f is. Suppose the mapping is from N(natural number set,countably infinite) -> N.And f(i)= $\left \lceil \frac{i}{2} \right \rceil$.it is onto function but not one-one. Sambit Kumar answered May 14, 2018 • selected May 14, 2018 by Soumya29 Sambit Kumar comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Soumya29 commented May 14, 2018 i edited by Soumya29 May 14, 2018 reply Follow Share @ankit @kushagra.. Above example looks perfectly fine. What i did in my comment on that que is , I wrote function f as a composition of 2 functions g:S→N and h:N→S. This is fine..g and h are just counting functions so that are bijective. But if f is onto but not one to one then one of these functions g and h must not be one to one.. So we can't write every f as composition of these 2 functions..Only those f that are bijections can be written like this. 0 votes 0 votes ankitgupta.1729 commented May 15, 2018 reply Follow Share could u please prove that all the elements of co-domain will be covered according to function f(i)= ⌈i/2⌉..since , 1 and 2 will be mapped to 1..3 and 4 will be mapped to 2...5 and 6 will be mapped to 3....similarly, n-1,n will be mapped to n/2...so in codomain , some elements will be existed for which there will be no pre-image...please correct me if I m wrong.. 1 votes 1 votes Kushagra Chatterjee commented May 15, 2018 reply Follow Share Take any element x in codomain the respective preimage will be 2x in the domain. 2 votes 2 votes Please log in or register to add a comment.