The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 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.
asked in Set Theory & Algebra by Boss (15.5k points) | 179 views
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.
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. :(
@Saumya29-You cannot have a surjective function $f: A \rightarrow B$ such that $|A| \leq |B|$

it is possible only when $|B| \leq |A|$
Ohh Yeah. It was a typo. Thanks, Ayush.

1 Answer

+2 votes
Best answer

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.

answered by Active (4.1k points)
selected by

@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.


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.
@kushagra.. Thanks :)

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.
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.
@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.

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/ in codomain , some elements will be existed for which there will be no pre-image...please correct me if I m wrong..

Take any element x in codomain the respective preimage will be 2x in the domain.
Thank you! @Kushagra ,@Soumya

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,481 answers
74,525 users