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 660 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments 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 Soumya29 commented May 14, 2018 reply Follow Share @Sambit .. Got it. Thanks for the counter-example. :) Can you please give me counter-example for this too. If the set S is countably infinite, if f:S→S is an injective function, then f is onto. 1 votes 1 votes Kushagra Chatterjee commented May 14, 2018 reply Follow Share @Soumya f:N to N f(x) = x+1 The function above will be one-one but not onto. Note that 1 will not be in the range of f. 5 votes 5 votes Soumya29 commented May 14, 2018 reply Follow Share @kushagra.. Thanks :) 0 votes 0 votes Kushagra Chatterjee commented May 14, 2018 reply Follow Share @Ankit Definition of Countably infinite sets. A set is called countably infinite (or denumerable) if it can be put in bijective correspondence with the set of natural numbers. The above statement is the definition of countably infinite sets. So,ofcourse the converse of the statement is true. 0 votes 0 votes Kushagra Chatterjee commented May 14, 2018 reply Follow Share Ankit you are right that gof(x) is bijective. But I am not getting how does it prove that f is injective. And in the above comment you have written that "So, set S will definitely be one- one" Note that the adjective "one-one "does not go with sets. It goes with functions or mappings. A function or a mapping can be one-one a set can't be one-one. 0 votes 0 votes 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.